Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs	(revision 12291)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs	(revision 12291)
@@ -0,0 +1,114 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  // resampling is not prevented
+  public sealed class GenericPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state 
+    private readonly IProblem problem;
+    private readonly IBanditPolicy banditPolicy;
+    private readonly HashSet<string> done; // contains all visited chains
+
+    public GenericPolicy(IProblem problem, IBanditPolicy banditPolicy) {
+      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 => 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;
+      }
+
+      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) {
+      var s = CalcState(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.Reverse()) {
+        GetStateInfo(state).UpdateReward(reward);
+
+        // actually only the last state can be terminal
+        if (problem.Grammar.IsTerminal(state)) {
+          MarkAsDone(state);
+        }
+      }
+    }
+
+    public void Reset() {
+      stateInfo.Clear();
+      done.Clear();
+    }
+
+
+    private bool Done(string chain) {
+      return done.Contains(chain);
+    }
+
+    private void MarkAsDone(string chain) {
+      done.Add(chain);
+    }
+
+
+    public int GetTries(string state) {
+      var s = CalcState(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
+      else return 0;
+    }
+
+    public double GetValue(string state) {
+      var s = CalcState(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      else return 0.0; // TODO: check alternatives
+    }
+
+    private string CalcState(string chain) {
+      var f = problem.GetFeatures(chain);
+      // this policy only works for problems that return exactly one feature (the 'state')
+      if (f.Skip(1).Any()) throw new ArgumentException();
+      return f.First().Id;
+    }
+  }
+}
