Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EmptyPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EmptyPolicyActionInfo.cs	(revision 11792)
+++ 	(revision )
@@ -1,20 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
-  public class EmptyPolicyActionInfo : IBanditPolicyActionInfo {
-    public double Value { get { return 0.0; } }
-
-    public bool Disabled { get; private set; }
-    public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
-    }
-    public void Disable() { this.Disabled = true; }
-    public void Reset() { this.Disabled = false; }
-    public void PrintStats() { Console.WriteLine("disabled {0}", Disabled); }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11793)
@@ -26,5 +26,5 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       Debug.Assert(actionInfos.Any());
-      if (random.NextDouble() > eps) {
+      if (random.NextDouble() >= eps) { // eps == 0 should be equivalent to pure exploitation, eps == 1 is pure exploration
         // select best
         var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/BoltzmanExplorationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/BoltzmanExplorationPolicy.cs	(revision 11792)
+++ 	(revision )
@@ -1,57 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Configuration;
-using System.Linq;
-using System.Security.Policy;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class BoltzmannExplorationPolicy : GrammarPolicy {
-
-    private readonly HashSet<string> done;
-    private readonly double beta;
-
-    public BoltzmannExplorationPolicy(IProblem problem, bool useCanonicalRepresentation = false, int beta = 100)
-      : base(problem, useCanonicalRepresentation) {
-      this.beta = beta;
-      this.done = new HashSet<string>();
-    }
-
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
-      // only select states that are not yet done
-      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
-      if (!afterStates.Any()) {
-        // fail because all follow states have already been visited => also disable the current state
-        done.Add(CanonicalState(curState.ToString()));
-        selectedState = null;
-        return false;
-      }
-      // try each state at least once
-      if (afterStates.Any(s => GetTries(s) == 0)) {
-        selectedState = afterStates.First(s => GetTries(s) == 0);
-        return true;
-      }
-
-      var w = from state in afterStates
-              select Math.Exp(beta * AvgReward(state));
-
-      selectedState = afterStates.SampleProportional(random, w).First();
-      return true;
-    }
-
-    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
-      base.UpdateReward(stateTrajectory, reward);
-      // the last state could be terminal
-      var lastState = stateTrajectory.Last();
-      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
-    }
-
-    public void Reset() {
-      base.Reset();
-      done.Clear();
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/EpsGreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/EpsGreedyPolicy.cs	(revision 11792)
+++ 	(revision )
@@ -1,66 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Configuration;
-using System.Linq;
-using System.Security.Policy;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class EpsGreedyPolicy : GrammarPolicy {
-
-    private readonly HashSet<string> done;
-    private readonly double eps;
-    private readonly IGrammarPolicy greedyPolicy;
-    private readonly IGrammarPolicy randomPolicy;
-
-    public EpsGreedyPolicy(IProblem problem, bool useCanonicalRepresentation = false, double eps = 0.1)
-      : base(problem, useCanonicalRepresentation) {
-      this.eps = eps;
-      this.done = new HashSet<string>();
-      this.greedyPolicy = new GreedyPolicy(problem, useCanonicalRepresentation);
-      this.randomPolicy = new RandomPolicy(problem, useCanonicalRepresentation);
-    }
-
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
-      // only select states that are not yet done
-      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
-      if (!afterStates.Any()) {
-        // fail because all follow states have already been visited => also disable the current state
-        done.Add(CanonicalState(curState.ToString()));
-        selectedState = null;
-        return false;
-      }
-
-      if (random.NextDouble() > eps) {
-        return greedyPolicy.TrySelect(random, curState, afterStates, out selectedState);
-      } else {
-        return randomPolicy.TrySelect(random, curState, afterStates, out selectedState);
-      }
-    }
-
-    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
-      base.UpdateReward(stateTrajectory, reward);
-      // the last state could be terminal
-      var lastState = stateTrajectory.Last();
-      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
-
-      // forward
-      greedyPolicy.UpdateReward(stateTrajectory, reward);
-      randomPolicy.UpdateReward(stateTrajectory, reward); // is ignored but for completeness
-    }
-
-    public override void Reset() {
-      base.Reset();
-      done.Clear();
-      greedyPolicy.Reset();
-      randomPolicy.Reset();
-    }
-
-    public double GetValue(ReadonlySequence state) {
-      return greedyPolicy.GetValue(state);
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11793)
@@ -14,5 +14,5 @@
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
-    private readonly HashSet<string> done;
+    //private readonly HashSet<string> done;
 
     public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
@@ -21,26 +21,23 @@
       this.banditPolicy = banditPolicy;
       this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
-      this.done = new HashSet<string>();
+      //this.done = new HashSet<string>();
     }
 
-    public bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates,
-      out ReadonlySequence selectedState) {
-      // only select states that are not yet done
-      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a))).ToArray();
-      if (!afterStates.Any()) {
+    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      // fail if all states are done (corresponding state infos are disabled)
+      if (afterStates.All(s => GetStateInfo(s).Disabled)) {
         // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
 
-        done.Add(CanonicalState(curState));
-        selectedState = null;
+        GetStateInfo(curState).Disable(0.0); // should the value be max of afterstate values instead of 0.0?
+        selectedStateIdx = -1;
         return false;
       }
 
+      selectedStateIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
 
-      var selectedIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
-      selectedState = afterStates.ElementAt(selectedIdx);
       return true;
     }
 
-    private IBanditPolicyActionInfo GetStateInfo(ReadonlySequence state) {
+    private IBanditPolicyActionInfo GetStateInfo(string state) {
       var s = CanonicalState(state);
       IBanditPolicyActionInfo info;
@@ -52,10 +49,13 @@
     }
 
-    public virtual void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       // the last state could be terminal
       var lastState = stateTrajectory.Last();
-      if (lastState.IsTerminal) done.Add(CanonicalState(lastState));
+      if (problem.Grammar.IsTerminal(lastState)) {
+        GetStateInfo(lastState).Disable(reward);
+      }
 
-      foreach (var state in stateTrajectory) {
+      // update remaining states
+      foreach (var state in stateTrajectory.Reverse().Skip(1)) {
         GetStateInfo(state).UpdateReward(reward);
       }
@@ -64,8 +64,8 @@
     public virtual void Reset() {
       stateInfo.Clear();
-      done.Clear();
+      //done.Clear();
     }
 
-    public int GetTries(ReadonlySequence state) {
+    public int GetTries(string state) {
       var s = CanonicalState(state);
       if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
@@ -73,5 +73,5 @@
     }
 
-    public double GetValue(ReadonlySequence state) {
+    public double GetValue(string state) {
       var s = CanonicalState(state);
       if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
@@ -79,8 +79,8 @@
     }
 
-    protected string CanonicalState(ReadonlySequence state) {
+    protected string CanonicalState(string state) {
       if (useCanonicalState) {
-        if (state.IsTerminal)
-          return problem.CanonicalRepresentation(state.ToString());
+        if (problem.Grammar.IsTerminal(state))
+          return problem.CanonicalRepresentation(state);
         else {
           // for non-terminal phrases make sure we don't disable canonical states that have not yet been fully explored
@@ -88,8 +88,8 @@
           // then we are not allowed to disable rS (canonical of lllS) because rS might not have been fully explored
           // solution: we disable the state rS4 
-          return problem.CanonicalRepresentation(state.ToString()) + state.Length;
+          return problem.CanonicalRepresentation(state) + state.Length;
         }
       } else
-        return state.ToString();
+        return state;
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GrammarPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GrammarPolicy.cs	(revision 11793)
@@ -8,13 +8,13 @@
 
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  // stores: tries, avg reward and max reward for each state
+  // stores: tries, avg reward and max reward for each state (base class for RandomPolicy and TDPolicy
   public abstract class GrammarPolicy : IGrammarPolicy {
     protected Dictionary<string, double> avgReward;
     protected Dictionary<string, int> tries;
     protected Dictionary<string, double> maxReward;
-    private readonly bool useCanonicalState;
-    private readonly IProblem problem;
+    protected readonly bool useCanonicalState;
+    protected readonly IProblem problem;
 
-    public GrammarPolicy(IProblem problem, bool useCanonicalState = false) {
+    protected GrammarPolicy(IProblem problem, bool useCanonicalState = false) {
       this.useCanonicalState = useCanonicalState;
       this.problem = problem;
@@ -24,9 +24,9 @@
     }
 
-    public abstract bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState);
+    public abstract bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx);
 
-    public virtual void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       foreach (var state in stateTrajectory) {
-        var s = CanonicalState(state.ToString());
+        var s = CanonicalState(state);
 
         if (!tries.ContainsKey(s)) tries.Add(s, 0);
@@ -47,23 +47,23 @@
     }
 
-    public double AvgReward(ReadonlySequence state) {
-      var s = CanonicalState(state.ToString());
+    public double AvgReward(string state) {
+      var s = CanonicalState(state);
       if (avgReward.ContainsKey(s)) return avgReward[s];
       else return 0.0;
     }
 
-    public double MaxReward(ReadonlySequence state) {
-      var s = CanonicalState(state.ToString());
+    public double MaxReward(string state) {
+      var s = CanonicalState(state);
       if (maxReward.ContainsKey(s)) return maxReward[s];
       else return 0.0;
     }
 
-    public virtual int GetTries(ReadonlySequence state) {
-      var s = CanonicalState(state.ToString());
+    public virtual int GetTries(string state) {
+      var s = CanonicalState(state);
       if (tries.ContainsKey(s)) return tries[s];
       else return 0;
     }
 
-    public virtual double GetValue(ReadonlySequence state) {
+    public virtual double GetValue(string state) {
       return AvgReward(state);
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GreedyPolicy.cs	(revision 11792)
+++ 	(revision )
@@ -1,44 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics.Eventing.Reader;
-using System.Linq;
-using System.Runtime.InteropServices;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class GreedyPolicy : GrammarPolicy {
-    private readonly IProblem problem;
-
-    public GreedyPolicy(IProblem problem, bool useCanonicalRepresentation)
-      : base(problem, useCanonicalRepresentation) {
-    }
-
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
-      // always returns the afterstate with the highest value
-      double maxV = V(afterStates.First());
-      var bestStates = new List<ReadonlySequence>();
-      bestStates.Add(afterStates.First());
-      foreach (var state in afterStates.Skip(1)) {
-        if (maxV < V(state)) {
-          maxV = V(state);
-          bestStates.Clear();
-          bestStates.Add(state);
-        } else if (maxV == V(state)) {
-          bestStates.Add(state);
-        }
-      }
-      // break ties randomly
-      // selectedState = bestStates.SelectRandom(random);
-      // break ties using first
-      selectedState = bestStates.First();
-      return true;
-    }
-
-    private double V(ReadonlySequence state) {
-      return base.AvgReward(state);
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/IGrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/IGrammarPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/IGrammarPolicy.cs	(revision 11793)
@@ -8,5 +8,5 @@
 
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public interface IGrammarPolicy : IPolicy<ReadonlySequence> {
+  public interface IGrammarPolicy : IPolicy<string> {
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs	(revision 11792)
+++ 	(revision )
@@ -1,48 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Configuration;
-using System.Linq;
-using System.Security.Policy;
-using System.Text;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class RandomNoResamplingPolicy : GrammarPolicy {
-
-    private readonly HashSet<string> done;
-
-    public RandomNoResamplingPolicy(IProblem problem, bool useCanonicalRepresentation)
-      : base(problem, useCanonicalRepresentation) {
-      this.done = new HashSet<string>();
-    }
-
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
-      // only select states that are not yet done
-      afterStates = afterStates.Where(a => !done.Contains(a.ToString())).ToArray();
-      if (!afterStates.Any()) {
-        // fail because all follow states have already been visited => also disable the current state
-        done.Add(CanonicalState(curState.ToString()));
-        selectedState = null;
-        return false;
-      }
-
-      selectedState = afterStates.SelectRandom(random);
-      return true;
-    }
-
-    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
-      base.UpdateReward(stateTrajectory, reward);
-      // ignore rewards but update the set of visited terminal states
-
-      // the last state could be terminal
-      var lastState = stateTrajectory.Last();
-      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
-    }
-
-    public override void Reset() {
-      base.Reset();
-      done.Clear();
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs	(revision 11793)
@@ -13,7 +13,7 @@
     }
 
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+    public override bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
       // never fail => allows re-visits of terminal states
-      selectedState = afterStates.SelectRandom(random);
+      selectedStateIdx = random.Next(afterStates.Count());
       return true;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs	(revision 11793)
@@ -2,4 +2,5 @@
 using System.Collections.Generic;
 using System.Configuration;
+using System.Diagnostics;
 using System.Linq;
 using System.Security.Policy;
@@ -7,4 +8,5 @@
 using System.Threading;
 using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
 using HeuristicLab.Common;
 using HeuristicLab.Problems.GrammaticalOptimization;
@@ -15,5 +17,5 @@
     private readonly HashSet<string> done;
     private readonly Dictionary<string, double> v;
-    private EpsGreedyPolicy epsGreedy;
+    private IGrammarPolicy epsGreedy;
 
     public TDPolicy(IProblem problem, bool useCanonicalRepresentation = false)
@@ -21,25 +23,28 @@
       this.done = new HashSet<string>();
       this.v = new Dictionary<string, double>();
-      this.epsGreedy = new EpsGreedyPolicy(problem, useCanonicalRepresentation, 0.1);
+      this.epsGreedy = new GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.1), useCanonicalRepresentation);
     }
 
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+    public override bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
       // only select states that are not yet done
       afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
       if (!afterStates.Any()) {
         // fail because all follow states have already been visited => also disable the current state
-        done.Add(CanonicalState(curState.ToString()));
-        selectedState = null;
+        done.Add(CanonicalState(curState));
+        selectedStateIdx = -1;
         return false;
       }
+      throw new NotImplementedException(); // TODO: remap indices of reduced action enumerable to indices of original enumerable
 
       //return epsGreedy.TrySelect(random, curState, afterStates, out selectedState);
 
       var bestQ = double.NegativeInfinity;
-      selectedState = null;
+      int idx = -1;
+      selectedStateIdx = -1;
       foreach (var state in afterStates) {
+        idx++;
         // try each state at least once
         if (GetTries(state) == 0) {
-          selectedState = state;
+          selectedStateIdx = idx;
           return true;
         }
@@ -47,25 +52,26 @@
         if (q > bestQ) {
           bestQ = q;
-          selectedState = state;
+          selectedStateIdx = idx;
         }
       }
 
+      Debug.Assert(selectedStateIdx > -1);
       return true;
     }
 
-    private double V(ReadonlySequence state) {
-      var s = CanonicalState(state.ToString());
+    private double V(string state) {
+      var s = CanonicalState(state);
       if (v.ContainsKey(s)) return v[s];
       else return 0.0;
     }
 
-    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+    public override void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       base.UpdateReward(stateTrajectory, reward);
       epsGreedy.UpdateReward(stateTrajectory, reward);
       // the last state could be terminal
       var lastState = stateTrajectory.Last();
-      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
+      if (problem.Grammar.IsTerminal(lastState)) done.Add(CanonicalState(lastState));
 
-      v[CanonicalState(lastState.ToString())] = V(lastState) + 1.0 / GetTries(lastState) * (reward - V(lastState));
+      v[CanonicalState(lastState)] = V(lastState) + 1.0 / GetTries(lastState) * (reward - V(lastState));
 
       foreach (var p in stateTrajectory.Zip(stateTrajectory.Skip(1), Tuple.Create).Reverse()) {
@@ -73,5 +79,5 @@
         var next = p.Item2;
 
-        v[CanonicalState(cur.ToString())] = V(cur) + 1.0 / GetTries(cur) * (V(next) - V(cur));
+        v[CanonicalState(cur)] = V(cur) + 1.0 / GetTries(cur) * (V(next) - V(cur));
         //v[CanonicalState(cur.ToString())] = V(cur) + 0.1 * (V(next) - V(cur));
       }
@@ -79,9 +85,9 @@
     }
 
-    public override double GetValue(ReadonlySequence state) {
+    public override double GetValue(string state) {
       return V(state);
     }
 
-    public void Reset() {
+    public override void Reset() {
       base.Reset();
       epsGreedy.Reset();
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/UCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/UCTPolicy.cs	(revision 11792)
+++ 	(revision )
@@ -1,64 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Configuration;
-using System.Linq;
-using System.Security.Policy;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class UCTPolicy : GrammarPolicy {
-
-    private readonly HashSet<string> done;
-    private readonly double c;
-
-    public UCTPolicy(IProblem problem, bool useCanonicalRepresentation = false, double c = 1.0)
-      : base(problem, useCanonicalRepresentation) {
-      this.c = c;
-      this.done = new HashSet<string>();
-    }
-
-    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
-      // only select states that are not yet done
-      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
-      if (!afterStates.Any()) {
-        // fail because all follow states have already been visited => also disable the current state
-        done.Add(CanonicalState(curState.ToString()));
-        selectedState = null;
-        return false;
-      }
-
-      var totalTries = afterStates.Select(GetTries).Sum();
-      var bestQ = double.NegativeInfinity;
-      selectedState = null;
-      foreach (var state in afterStates) {
-        // try each state at least once
-        if (GetTries(state) == 0) {
-          selectedState = state;
-          return true;
-        }
-        var q = AvgReward(state) + 2.0 * c * Math.Sqrt(Math.Log(totalTries) / GetTries(state));
-        if (q > bestQ) {
-          bestQ = q;
-          selectedState = state;
-        }
-      }
-
-      return true;
-    }
-
-    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
-      base.UpdateReward(stateTrajectory, reward);
-      // the last state could be terminal
-      var lastState = stateTrajectory.Last();
-      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
-    }
-
-    public void Reset() {
-      base.Reset();
-      done.Clear();
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11793)
@@ -66,16 +66,13 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
-    <Compile Include="GrammarPolicies\BoltzmanExplorationPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
       <SubType>Code</SubType>
     </Compile>
+    <Compile Include="GrammarPolicies\RandomPolicy.cs">
+      <SubType>Code</SubType>
+    </Compile>
     <Compile Include="GrammarPolicies\TDPolicy.cs" />
-    <Compile Include="GrammarPolicies\UCTPolicy.cs" />
     <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
-    <Compile Include="GrammarPolicies\EpsGreedyPolicy.cs" />
-    <Compile Include="GrammarPolicies\GreedyPolicy.cs" />
     <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />
-    <Compile Include="GrammarPolicies\RandomNoResamplingPolicy.cs" />
-    <Compile Include="GrammarPolicies\RandomPolicy.cs" />
     <Compile Include="IPolicy.cs" />
     <Compile Include="IBanditPolicy.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11792)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11793)
@@ -11,6 +11,6 @@
   // here we assume that a reward is only recieved at the end of the episode and the update is done only after an episode is complete
   // we also assume that the policy can fail to select one of the followStates
-  public interface IPolicy<TState> {
-    bool TrySelect(Random random, TState curState, IEnumerable<TState> afterStates, out TState selectedState); // selectedState \in afterStates
+  public interface IPolicy<in TState> {
+    bool TrySelect(Random random, TState curState, IEnumerable<TState> afterStates, out int selectedStateIdx); // selectedState \in afterStates
 
     // state-trajectory are the states of the episode, at the end we recieved the reward (only for the terminal state)
