Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs	(revision 11806)
@@ -11,7 +11,7 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       const double delta = 0.1;
-      int k = myActionInfos.Where(a => !a.Disabled).Count();
+      int k = myActionInfos.Count();
       var bestActions = new List<int>();
       var us = new List<double>();
@@ -20,5 +20,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         double u;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs	(revision 11806)
@@ -37,7 +37,5 @@
 
       var w = from aInfo in myActionInfos
-              select aInfo.Disabled
-                ? 0.0
-                : Math.Exp(beta * valueFunction(aInfo));
+              select Math.Exp(beta * valueFunction(aInfo));
 
       var bestAction = Enumerable.Range(0, myActionInfos.Count()).SampleProportional(random, w);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs	(revision 11806)
@@ -21,6 +21,6 @@
       // select best
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int k = myActionInfos.Count(a => !a.Disabled);
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       double bestQ = double.NegativeInfinity;
       var bestActions = new List<int>();
@@ -28,5 +28,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -46,5 +45,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11806)
@@ -9,6 +9,4 @@
   // stores information that is relevant for most of the policies
   public class DefaultPolicyActionInfo : IBanditPolicyActionInfo {
-    private double knownValue;
-    public bool Disabled { get { return Tries == -1; } }
     public double SumReward { get; private set; }
     public int Tries { get; private set; }
@@ -16,6 +14,4 @@
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
           return Tries > 0 ? SumReward / Tries : 0.0;
       }
@@ -26,23 +22,13 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
-
       Tries++;
       SumReward += reward;
       MaxReward = Math.Max(MaxReward, reward);
     }
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.SumReward = 0.0;
-      this.knownValue = reward;
-    }
+
     public void Reset() {
       SumReward = 0.0;
       Tries = 0;
       MaxReward = 0.0;
-      knownValue = 0.0;
-    }
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", SumReward / Tries, Disabled);
     }
 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11806)
@@ -35,5 +35,4 @@
         foreach (var aInfo in myActionInfos) {
           aIdx++;
-          if (aInfo.Disabled) continue;
 
           var q = valueFunction(aInfo);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs	(revision 11806)
@@ -22,6 +22,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
-        //if (aInfo.Tries == 0) return aIdx;
         var q = aInfo.SampleExpectedReward(random);
         if (q > bestQ) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11806)
@@ -39,8 +39,4 @@
       estimator.Reset();
     }
-
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", AvgReward, Disabled);
-    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11806)
@@ -10,11 +10,7 @@
   public class ModelPolicyActionInfo : IBanditPolicyActionInfo {
     private readonly IModel model;
-    private double knownValue;
-    public bool Disabled { get { return Tries == -1; } }
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
-          return model.SampleExpectedReward(new Random());
+        return model.SampleExpectedReward(new Random());
       }
     }
@@ -26,5 +22,4 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       Tries++;
       model.Update(reward);
@@ -35,21 +30,11 @@
     }
 
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.knownValue = reward;
-    }
-
     public void Reset() {
       Tries = 0;
-      knownValue = 0.0;
       model.Reset();
     }
 
-    public void PrintStats() {
-      model.PrintStats();
-    }
-
     public override string ToString() {
-      return string.Format("disabled {0} model {1}", Disabled, model);
+      return string.Format("model {1}", model);
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs	(revision 11806)
@@ -0,0 +1,55 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* modified UCT: see Coquelin & Munos, Bandit Algorithms for Tree Search, UAI 2007 */
+  public class ModifiedUCTPolicy : IBanditPolicy {
+    private readonly double c;
+
+    public ModifiedUCTPolicy(double c = 1.0) {
+      this.c = c;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+
+      int aIdx = -1;
+      var bestActions = new List<int>();
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          q = aInfo.SumReward / aInfo.Tries + c * Math.Sqrt(Math.Sqrt(totalTries) / aInfo.Tries); // modification in comparison to original UCT
+        }
+        if (q > bestQ) {
+          bestActions.Clear();
+          bestQ = q;
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ModifiedUCTPolicy({0:F2})", c);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs	(revision 11806)
@@ -17,5 +17,4 @@
       return actionInfos
         .Select((aInfo, idx) => Tuple.Create(aInfo, idx))
-        .Where(p => !p.Item1.Disabled)
         .SelectRandom(random).Item2;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11806)
@@ -28,15 +28,11 @@
       public int Tries { get; private set; }
       public int thresholdBin = 1;
-      private double knownValue;
 
       public double Value {
         get {
-          if (Disabled) return knownValue;
           if (Tries == 0.0) return 0.0;
           return rewardHistogram[thresholdBin] / (double)Tries;
         }
       }
-
-      public bool Disabled { get { return Tries == -1; } }
 
       public void UpdateReward(double reward) {
@@ -46,22 +42,8 @@
       }
 
-      public void Disable(double reward) {
-        this.knownValue = reward;
-        Tries = -1;
-      }
-
       public void Reset() {
         Tries = 0;
         thresholdBin = 1;
-        this.knownValue = 0.0;
         Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
-      }
-
-      public void PrintStats() {
-        if (Tries >= 0) {
-          Console.Write("{0,6}", Tries);
-        } else {
-          Console.Write("{0,6}", "");
-        }
       }
 
@@ -101,10 +83,9 @@
       var bestActions = new List<int>();
       double bestQ = double.NegativeInfinity;
-      int k = myActionInfos.Count(a => !a.Disabled);
-      var totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      var totalTries = myActionInfos.Sum(a => a.Tries);
       int aIdx = -1;
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -118,5 +99,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs	(revision 11806)
@@ -13,5 +13,5 @@
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       var bestActions = new List<int>();
@@ -19,5 +19,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -31,5 +30,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11806)
@@ -37,5 +37,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11806)
@@ -33,5 +33,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs	(revision 11806)
@@ -21,5 +21,5 @@
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       int aIdx = -1;
@@ -27,5 +27,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -38,6 +37,5 @@
           bestQ = q;
           bestActions.Add(aIdx);
-        }
-        if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11806)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -9,31 +10,55 @@
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
   // this represents grammar policies that use one of the available bandit policies for state selection
-  public class GenericGrammarPolicy : IGrammarPolicy {
-    protected Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state 
-    private readonly bool useCanonicalState;
+  // any bandit policy can be used to select actions for states
+  // a separate datastructure is used to store visited states and to prevent revisiting of states
+  public sealed class GenericGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
 
-    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
-      this.useCanonicalState = useCanonicalState;
+    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
       this.problem = problem;
       this.banditPolicy = banditPolicy;
       this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
     }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
 
     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)) {
+      if (afterStates.All(s => Done(s))) {
         // 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)
+        MarkAsDone(curState);
 
-        GetStateInfo(curState).Disable(afterStates.Select(afterState => GetStateInfo(afterState).Value).Max());
         selectedStateIdx = -1;
         return false;
       }
 
-      selectedStateIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
 
       return true;
     }
+
+
 
     private IBanditPolicyActionInfo GetStateInfo(string state) {
@@ -47,5 +72,5 @@
     }
 
-    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       foreach (var state in stateTrajectory) {
         GetStateInfo(state).UpdateReward(reward);
@@ -53,11 +78,13 @@
         // only the last state can be terminal
         if (problem.Grammar.IsTerminal(state)) {
-          GetStateInfo(state).Disable(reward);
+          MarkAsDone(state);
         }
       }
     }
 
-    public virtual void Reset() {
+
+    public void Reset() {
       stateInfo.Clear();
+      done.Clear();
     }
 
@@ -74,6 +101,42 @@
     }
 
-    protected string CanonicalState(string state) {
-      if (useCanonicalState) {
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
         return problem.CanonicalRepresentation(state);
       } else
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs	(revision 11806)
@@ -0,0 +1,153 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public sealed class GenericTDPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
+    private readonly IProblem problem;
+    private readonly IBanditPolicy banditPolicy;
+
+    public GenericTDPolicy(IProblem problem, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
+      this.problem = problem;
+      this.banditPolicy = new EpsGreedyPolicy(0.1);
+      this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
+    }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
+
+    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 => Done(s))) {
+        // 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)
+        MarkAsDone(curState);
+
+        selectedStateIdx = -1;
+        return false;
+      }
+
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+      
+      
+      GetStateInfo(curState).UpdateReward(afterStates.Select(s=>GetStateInfo(s).Value).Max());
+
+      return true;
+    }
+
+
+
+    private IBanditPolicyActionInfo GetStateInfo(string state) {
+      var s = CanonicalState(state);
+      IBanditPolicyActionInfo info;
+      if (!stateInfo.TryGetValue(s, out info)) {
+        info = banditPolicy.CreateActionInfo();
+        stateInfo[s] = info;
+      }
+      return info;
+    }
+
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+
+      foreach (var state in stateTrajectory.Zip(stateTrajectory.Skip(1), Tuple.Create)) {
+        var parent = state.Item1;
+        var child = state.Item2;
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(child)) {
+          MarkAsDone(child);
+        }
+        // GetStateInfo(parent).UpdateReward(GetValue(child));
+
+      }
+
+      GetStateInfo(stateTrajectory.Last()).UpdateReward(reward);
+    }
+
+
+    public void Reset() {
+      stateInfo.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(string state) {
+      var s = CanonicalState(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
+      else return 0;
+    }
+
+    public double GetValue(string state) {
+      var s = CanonicalState(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      else return 0.0; // TODO: check alternatives
+    }
+
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
+        return problem.CanonicalRepresentation(state);
+      } else
+        return state;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11806)
@@ -49,4 +49,5 @@
     <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
     <Compile Include="BanditPolicies\ActiveLearningPolicy.cs" />
+    <Compile Include="BanditPolicies\ModifiedUCTPolicy.cs" />
     <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
     <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />
@@ -66,4 +67,5 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
       <SubType>Code</SubType>
@@ -72,5 +74,4 @@
       <SubType>Code</SubType>
     </Compile>
-    <Compile Include="GrammarPolicies\TDPolicy.cs" />
     <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11799)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11806)
@@ -1,12 +1,11 @@
 ﻿namespace HeuristicLab.Algorithms.Bandits {
   public interface IBanditPolicyActionInfo {
-    bool Disabled { get; }
+    //bool Disabled { get; }
     double Value { get; }
     int Tries { get; }
     void UpdateReward(double reward);
-    void Disable(double reward);
+    //void Disable(double reward);
     // reset causes the state of the action to be reinitialized (as after constructor-call)
     void Reset();
-    void PrintStats();
   }
 }
