Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs	(revision 11742)
@@ -0,0 +1,36 @@
+﻿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 {
+  public class BernoulliPolicyActionInfo : IBanditPolicyActionInfo {
+    public bool Disabled { get { return NumSuccess == -1; } }
+    public int NumSuccess { get; private set; }
+    public int NumFailure { get; private set; }
+    public int Tries { get { return NumSuccess + NumFailure; } }
+    public double Value { get { return NumSuccess / (double)(Tries); } }
+    public void UpdateReward(double reward) {
+      Debug.Assert(!Disabled);
+      //Debug.Assert(reward.IsAlmost(0.0) || reward.IsAlmost(1.0));
+
+      //if (reward.IsAlmost(1.0)) NumSuccess++;
+      if (reward > 0) NumSuccess++;
+      else NumFailure++;
+    }
+    public void Disable() {
+      this.NumSuccess = -1;
+      this.NumFailure = -1;
+    }
+    public void Reset() {
+      NumSuccess = 0;
+      NumFailure = 0;
+    }
+    public void PrintStats() {
+      Console.WriteLine("expected value {0,5:F2} disabled {1}", Value, Disabled);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs	(revision 11742)
@@ -0,0 +1,43 @@
+﻿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 {
+  public class BernoulliThompsonSamplingPolicy : IBanditPolicy {
+    // parameters of beta prior distribution
+    private readonly double alpha = 1.0;
+    private readonly double beta = 1.0;
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<BernoulliPolicyActionInfo>();
+      int bestAction = -1;
+      double maxTheta = double.NegativeInfinity;
+      var aIdx = -1;
+
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        var theta = Rand.BetaRand(random, aInfo.NumSuccess + alpha, aInfo.NumFailure + beta);
+        if (theta > maxTheta) {
+          maxTheta = theta;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new BernoulliPolicyActionInfo();
+    }
+
+
+    public override string ToString() {
+      return "BernoulliThompsonSamplingPolicy";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs	(revision 11742)
@@ -0,0 +1,51 @@
+﻿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 {
+  // also called softmax policy
+  public class BoltzmannExplorationPolicy : IBanditPolicy {
+    private readonly double beta;
+    private readonly Func<DefaultPolicyActionInfo, double> valueFunction;
+
+    public BoltzmannExplorationPolicy(double eps) : this(eps, DefaultPolicyActionInfo.AverageReward) { }
+
+    public BoltzmannExplorationPolicy(double beta, Func<DefaultPolicyActionInfo, double> valueFunction) {
+      if (beta < 0) throw new ArgumentException();
+      this.beta = beta;
+      this.valueFunction = valueFunction;
+    }
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+
+      // select best
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      Debug.Assert(myActionInfos.Any(a => !a.Disabled));
+
+      var w = from aInfo in myActionInfos
+              select aInfo.Disabled
+                ? 0.0
+                : Math.Exp(beta * valueFunction(aInfo));
+
+      var bestAction = myActionInfos
+        .Select((aInfo, idx) => new { aInfo, idx })
+        .SampleProportional(random, w)
+        .Select(p => p.idx)
+        .First();
+      Debug.Assert(bestAction >= 0);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("BoltzmannExplorationPolicy({0:F2})", beta);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs	(revision 11742)
@@ -0,0 +1,55 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* see: Streeter and Smith: A simple distribution-free approach to the max k-armed bandit problem, Proceedings  of the 12th
+International Conference, CP 2006, Nantes, France, September 25-29, 2006. pp 560-574 */
+
+  public class ChernoffIntervalEstimationPolicy : IBanditPolicy {
+    private readonly double delta;
+
+    public ChernoffIntervalEstimationPolicy(double delta = 0.01) {
+      this.delta = delta;
+    }
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      // 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 bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      var aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        if (aInfo.Tries == 0) return aIdx;
+
+        var avgReward = aInfo.SumReward / aInfo.Tries;
+
+        // page 5 of "A simple distribution-free appraoch to the max k-armed bandit problem"
+        // var alpha = Math.Log(2 * totalTries * k / delta);
+        double alpha = Math.Log(2.0) + Math.Log(totalTries) + Math.Log(k) - Math.Log(delta); // total tries is max tries in the original paper
+        var q = avgReward + (alpha + Math.Sqrt(2 * aInfo.Tries * avgReward * alpha + alpha * alpha)) / aInfo.Tries;
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction >= 0);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ChernoffIntervalEstimationPolicy({0:F2})", delta);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11742)
@@ -0,0 +1,49 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // stores information that is relevant for most of the policies
+  public class DefaultPolicyActionInfo : IBanditPolicyActionInfo {
+    public bool Disabled { get { return Tries == -1; } }
+    public double SumReward { get; private set; }
+    public int Tries { get; private set; }
+    public double MaxReward { get; private set; }
+    public double Value { get { return SumReward / Tries; } }
+    public DefaultPolicyActionInfo() {
+      MaxReward = double.MinValue;
+    }
+
+    public void UpdateReward(double reward) {
+      Debug.Assert(!Disabled);
+
+      Tries++;
+      SumReward += reward;
+      MaxReward = Math.Max(MaxReward, reward);
+    }
+    public void Disable() {
+      this.Tries = -1;
+      this.SumReward = 0.0;
+    }
+    public void Reset() {
+      SumReward = 0.0;
+      Tries = 0;
+      MaxReward = 0.0;
+    }
+    public void PrintStats() {
+      Console.WriteLine("avg reward {0,5:F2} disabled {1}", SumReward / Tries, Disabled);
+    }
+
+    public static Func<DefaultPolicyActionInfo, double> AverageReward {
+      get {
+        return (aInfo) =>
+          aInfo.Tries == 0 ?
+          double.PositiveInfinity :
+          aInfo.SumReward / (double)aInfo.Tries;
+      }
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EmptyPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EmptyPolicyActionInfo.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EmptyPolicyActionInfo.cs	(revision 11742)
@@ -0,0 +1,20 @@
+﻿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 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11742)
@@ -0,0 +1,66 @@
+﻿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 {
+  public class EpsGreedyPolicy : IBanditPolicy {
+    private readonly double eps;
+    private readonly RandomPolicy randomPolicy;
+    private readonly Func<DefaultPolicyActionInfo, double> valueFunction;
+    private readonly string desc;
+
+
+    public EpsGreedyPolicy(double eps) : this(eps, DefaultPolicyActionInfo.AverageReward, string.Empty) { }
+
+    public EpsGreedyPolicy(double eps, Func<DefaultPolicyActionInfo, double> valueFunction, string desc) {
+      this.eps = eps;
+      this.randomPolicy = new RandomPolicy();
+      this.valueFunction = valueFunction;
+      this.desc = desc;
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      if (random.NextDouble() > eps) {
+        // select best
+        var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+        var bestActions = new List<int>();
+        double bestQ = double.NegativeInfinity;
+
+        int aIdx = -1;
+        foreach (var aInfo in myActionInfos) {
+          aIdx++;
+          if (aInfo.Disabled) continue;
+
+          var q = valueFunction(aInfo);
+
+          if (q > bestQ) {
+            bestActions.Clear();
+            bestActions.Add(aIdx);
+            bestQ = q;
+          } else if (q.IsAlmost(bestQ)) {
+            bestActions.Add(aIdx);
+          }
+        }
+        Debug.Assert(bestActions.Any());
+        return bestActions.SelectRandom(random);
+      } else {
+        // select random
+        return randomPolicy.SelectAction(random, actionInfos);
+      }
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+
+    public override string ToString() {
+      return string.Format("EpsGreedyPolicy({0:F2},{1})", eps, desc);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/Exp3Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/Exp3Policy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/Exp3Policy.cs	(revision 11742)
@@ -0,0 +1,68 @@
+﻿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 Exp3Policy : BanditPolicy {
+    private readonly Random random;
+    private readonly double gamma;
+    private readonly double[] w;
+    // TODO: debug (very large weights over time)
+    public Exp3Policy(Random random, int numActions, double gamma)
+      : base(numActions) {
+      if (gamma < 0 || gamma > 1) throw new ArgumentException();
+      this.random = random;
+      this.gamma = gamma;
+      this.w = Enumerable.Repeat(1.0, numActions).ToArray();
+    }
+
+    public override int SelectAction() {
+      Debug.Assert(Actions.Any());
+      var numActions = Actions.Count();
+      var sumW = w.Sum();
+      var r = random.NextDouble();
+      var sumP = (1 - gamma) * w[0] / sumW + gamma / numActions;
+      int i = 0;
+      while (r > sumP) {
+        i++;
+        sumP += (1 - gamma) * w[i] / sumW + gamma / numActions;
+      }
+      Debug.Assert(i >= 0 && i < numActions);
+      return i;
+    }
+
+    public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+      var numActions = Actions.Count();
+      var p = (1 - gamma) * w[action] / w.Sum() + gamma / numActions;
+      var estReward = reward / p;
+      w[action] = w[action] * Math.Exp(gamma * estReward / numActions);
+    }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      w[action] = 0;
+    }
+
+    public override void Reset() {
+      base.Reset();
+      foreach (var a in Actions) w[a] = 1.0;
+    }
+    public override void PrintStats() {
+      for (int i = 0; i < w.Length; i++) {
+        if (w[i] > 0) {
+          Console.Write("{0,5:F2}", w[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return "Exp3Policy";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs	(revision 11742)
@@ -0,0 +1,86 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+
+  [Obsolete("Replaced by GenericThompsonSamplingPolicy(GaussianModel(0.5, 1.0, 0.1))")]
+  public class GaussianThompsonSamplingPolicy : IBanditPolicy {
+    private bool compatibility;
+
+    // assumes a Gaussian reward distribution with different means but the same variances for each action
+    // the prior for the mean is also Gaussian with the following parameters
+    private readonly double rewardVariance = 0.1; // we assume a known variance 
+
+    private readonly double priorMean = 0.5;
+    private readonly double priorVariance = 1;
+
+
+    public GaussianThompsonSamplingPolicy(bool compatibility = false) {
+      this.compatibility = compatibility;
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+
+        var tries = aInfo.Tries;
+        var sampleMean = aInfo.AvgReward;
+        var sampleVariance = aInfo.RewardVariance;
+
+        double theta;
+        if (compatibility) {
+          // old code used for old experiments (preserved because it performed very well)
+          if (tries < 2) return aIdx;
+          var mu = sampleMean;
+          var variance = sampleVariance;
+          var stdDev = Math.Sqrt(variance);
+          theta = Rand.RandNormal(random) * stdDev + mu;
+        } else {
+          // calculate posterior mean and variance (for mean reward)
+
+          // see Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution (http://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf)
+          var posteriorVariance = 1.0 / (tries / rewardVariance + 1.0 / priorVariance);
+          var posteriorMean = posteriorVariance * (priorMean / priorVariance + tries * sampleMean / rewardVariance);
+
+          // sample a mean from the posterior 
+          theta = Rand.RandNormal(random) * Math.Sqrt(posteriorVariance) + posteriorMean;
+
+          // theta already represents the expected reward value => nothing else to do
+        }
+
+        if (theta > bestQ) {
+          bestQ = theta;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
+    }
+
+
+    //public override void UpdateReward(int action, double reward) {
+    //  Debug.Assert(Actions.Contains(action));
+    //  tries[action]++;
+    //  var delta = reward - sampleMean[action];
+    //  sampleMean[action] += delta / tries[action];
+    //  sampleM2[action] += sampleM2[action] + delta * (reward - sampleMean[action]);
+    //}
+
+    public override string ToString() {
+      return "GaussianThompsonSamplingPolicy";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs	(revision 11742)
@@ -0,0 +1,44 @@
+﻿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 {
+  public class GenericThompsonSamplingPolicy : IBanditPolicy {
+    private readonly IModel model;
+
+    public GenericThompsonSamplingPolicy(IModel model) {
+      this.model = model;
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<ModelPolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      var aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        //if (aInfo.Tries == 0) return aIdx;
+        var q = aInfo.SampleExpectedReward(random);
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new ModelPolicyActionInfo((IModel)model.Clone());
+    }
+
+    public override string ToString() {
+      return string.Format("GenericThompsonSamplingPolicy(\"{0}\")", model);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11742)
@@ -0,0 +1,37 @@
+﻿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 MeanAndVariancePolicyActionInfo : IBanditPolicyActionInfo {
+    private bool disabled;
+    public bool Disabled { get { return disabled; } }
+    private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
+    public int Tries { get { return estimator.N; } }
+    public double SumReward { get { return estimator.Sum; } }
+    public double AvgReward { get { return estimator.Avg; } }
+    public double RewardVariance { get { return estimator.Variance; } }
+    public double Value { get { return AvgReward; } }
+
+    public void UpdateReward(double reward) {
+      Debug.Assert(!Disabled);
+      estimator.UpdateReward(reward);
+    }
+
+    public void Disable() {
+      disabled = true;
+    }
+
+    public void Reset() {
+      disabled = false;
+      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 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11742)
@@ -0,0 +1,46 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // uses a statistical model to sample and update posterior distribution p(Reward | Data)
+  public class ModelPolicyActionInfo : IBanditPolicyActionInfo {
+    private readonly IModel model;
+    public bool Disabled { get { return Tries == -1; } }
+    public double Value { get { return model.SampleExpectedReward(new Random()); } }
+
+    public int Tries { get; private set; }
+    public ModelPolicyActionInfo(IModel model) {
+      this.model = model;
+    }
+
+    public void UpdateReward(double reward) {
+      Debug.Assert(!Disabled);
+      model.Update(reward);
+    }
+
+    public double SampleExpectedReward(Random random) {
+      return model.SampleExpectedReward(random);
+    }
+
+    public void Disable() {
+      this.Tries = -1;
+    }
+
+    public void Reset() {
+      Tries = 0;
+      model.Reset();
+    }
+
+    public void PrintStats() {
+      model.PrintStats();
+    }
+
+    public override string ToString() {
+      return string.Format("disabled {0} model {1}", Disabled, model);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs	(revision 11742)
@@ -0,0 +1,27 @@
+﻿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 {
+  public class RandomPolicy : IBanditPolicy {
+
+    public override string ToString() {
+      return "RandomPolicy";
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      return actionInfos
+        .Select((aInfo, idx) => Tuple.Create(aInfo, idx))
+        .Where(p => !p.Item1.Disabled)
+        .SelectRandom(random).Item2;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11742)
@@ -0,0 +1,133 @@
+﻿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 {
+  /* see: Streeter and Smith: A simple distribution-free approach to the max k-armed bandit problem, Proceedings  of the 12th
+ International Conference, CP 2006, Nantes, France, September 25-29, 2006. pp 560-574 */
+
+  public class ThresholdAscentPolicy : IBanditPolicy {
+    public const int numBins = 101;
+    public const double binSize = 1.0 / (numBins - 1);
+
+    private class ThresholdAscentActionInfo : IBanditPolicyActionInfo {
+
+      // for each arm store the number of observed rewards for each bin of size delta
+      // for delta = 0.01 we have 101 bins
+      // the first bin is freq of rewards  >= 0 // all
+      // the second bin is freq of rewards > 0
+      // the third bin is freq of rewards > 0.01
+      // the last bin is for rewards > 0.99
+      // 
+      // (also see RewardBin function)
+      public int[] rewardHistogram = new int[numBins];    // for performance reasons we store cumulative counts (freq of rewards > lower threshold)
+      public int Tries { get; private set; }
+      public int thresholdBin = 1;
+      public double Value { get { return rewardHistogram[thresholdBin] / (double)Tries; } }
+
+      public bool Disabled { get { return Tries == -1; } }
+
+      public void UpdateReward(double reward) {
+        Tries++;
+        for (var idx = thresholdBin; idx <= RewardBin(reward); idx++)
+          rewardHistogram[idx]++;
+      }
+
+      public void Disable() {
+        Tries = -1;
+      }
+
+      public void Reset() {
+        Tries = 0;
+        thresholdBin = 1;
+        Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
+      }
+
+      public void PrintStats() {
+        if (Tries >= 0) {
+          Console.Write("{0,6}", Tries);
+        } else {
+          Console.Write("{0,6}", "");
+        }
+      }
+
+      // maps a reward value to it's bin
+      private static int RewardBin(double reward) {
+        Debug.Assert(reward >= 0 && reward <= 1.0);
+        // reward = 0 => 0
+        // ]0.00 .. 0.01] => 1
+        // ]0.01 .. 0.02] => 2
+        // ...
+        // ]0.99 .. 1.00] => 100
+        if (reward <= 0) return 0;
+        return (int)Math.Ceiling((reward / binSize));
+      }
+    }
+
+    private readonly int s;
+    private readonly double delta;
+
+    public ThresholdAscentPolicy(int s = 100, double delta = 0.05) {
+      this.s = s;
+      this.delta = delta;
+    }
+
+    private double U(double mu, int totalTries, int n, int k) {
+      //var alpha = Math.Log(2.0 * totalTries * k / delta);
+      double alpha = Math.Log(2) + Math.Log(totalTries) + Math.Log(k) - Math.Log(delta);
+      return mu + (alpha + Math.Sqrt(2 * n * mu * alpha + alpha * alpha)) / n;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      var myActionInfos = actionInfos.OfType<ThresholdAscentActionInfo>();
+      UpdateThreshold(myActionInfos);
+
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      int k = myActionInfos.Count(a => !a.Disabled);
+      var totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        if (aInfo.Tries == 0) return aIdx;
+        double mu = aInfo.Value; // probability of rewards > T 
+        double q = U(mu, totalTries, aInfo.Tries, k);          // totalTries is max iterations in original paper
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+
+    private void UpdateThreshold(IEnumerable<ThresholdAscentActionInfo> actionInfos) {
+      var thresholdBin = 1; // first bin to check is bin idx 1 == freq of rewards > 0
+      while (thresholdBin < (numBins - 1) && actionInfos.Sum(a => a.rewardHistogram[thresholdBin]) >= s) {
+        thresholdBin++;
+        // Console.WriteLine("New threshold {0:F2}", T);
+      }
+      foreach (var aInfo in actionInfos) {
+        aInfo.thresholdBin = thresholdBin;
+      }
+    }
+
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new ThresholdAscentActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ThresholdAscentPolicy({0},{1:F2})", s, delta);
+    }
+
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs	(revision 11742)
@@ -0,0 +1,37 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // policy for k-armed bandit (see Auer et al. 2002)
+  public class UCB1Policy : IBanditPolicy {
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>().ToArray(); // TODO: performance
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+
+      for (int a = 0; a < myActionInfos.Length; a++) {
+        if (myActionInfos[a].Disabled) continue;
+        if (myActionInfos[a].Tries == 0) return a;
+        var q = myActionInfos[a].SumReward / myActionInfos[a].Tries + Math.Sqrt((2 * Math.Log(totalTries)) / myActionInfos[a].Tries);
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = a;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+    public override string ToString() {
+      return "UCB1Policy";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11742)
@@ -0,0 +1,51 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // policy for k-armed bandit (see Auer et al. 2002)
+  public class UCB1TunedPolicy : IBanditPolicy {
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        if (aInfo.Tries == 0) return aIdx;
+
+        var sumReward = aInfo.SumReward;
+        var tries = aInfo.Tries;
+
+        var avgReward = sumReward / tries;
+        var q = avgReward + Math.Sqrt((Math.Log(totalTries) / tries) * Math.Min(1.0 / 4, V(aInfo, totalTries))); // 1/4 is upper bound of bernoulli distributed variable
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
+    }
+
+    private double V(MeanAndVariancePolicyActionInfo actionInfo, int totalTries) {
+      var s = actionInfo.Tries;
+      return actionInfo.RewardVariance + Math.Sqrt(2 * Math.Log(totalTries) / s);
+    }
+
+    public override string ToString() {
+      return "UCB1TunedPolicy";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11742)
@@ -0,0 +1,44 @@
+﻿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 UCBNormalPolicy : IBanditPolicy {
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        if (totalTries <= 1 || aInfo.Tries <= 1 || aInfo.Tries <= Math.Ceiling(8 * Math.Log(totalTries))) return aIdx;
+
+        var tries = aInfo.Tries;
+        var avgReward = aInfo.AvgReward;
+        var rewardVariance = aInfo.RewardVariance;
+        var estVariance = 16.0 * rewardVariance * (Math.Log(totalTries - 1) / tries);
+        var q = avgReward + Math.Sqrt(estVariance);
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return "UCBNormalPolicy";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs	(revision 11742)
@@ -0,0 +1,46 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* Kocsis et al. Bandit based Monte-Carlo Planning */
+  public class UCTPolicy : IBanditPolicy {
+    private readonly double c;
+
+    public UCTPolicy(double c = 1.0) {
+      this.c = c;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        if (aInfo.Disabled) continue;
+        if (aInfo.Tries == 0) return aIdx;
+        var q = aInfo.SumReward / aInfo.Tries + 2.0 * c * Math.Sqrt(Math.Log(totalTries) / aInfo.Tries);
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("UCTPolicy({0:F2})", c);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs	(revision 11742)
@@ -0,0 +1,44 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class RandomNoResamplingPolicy : IGrammarPolicy {
+
+    private readonly Dictionary<ReadonlySequence, bool> done;
+    private readonly Dictionary<Tuple<ReadonlySequence, ReadonlySequence>, ReadonlySequence> nextState;
+
+
+    public RandomNoResamplingPolicy() {
+      this.done = new Dictionary<ReadonlySequence, bool>();
+    }
+
+    public ReadonlySequence SelectAction(Random random, ReadonlySequence state, IEnumerable<ReadonlySequence> actions) {
+      var allDone = true;
+      foreach (var a in actions) {
+        var p = Tuple.Create(state, a);
+        allDone &= nextState.ContainsKey(p) && Done(nextState[p]);
+        if (!allDone) break;
+      }
+      if(allDone)
+      return actions
+        .Where(a => !nextState.ContainsKey(Tuple.Create(state, a)) || Done(nextState[Tuple.Create(state, a)]))
+        .SelectRandom(random);
+    }
+
+    public void UpdateReward(ReadonlySequence state, ReadonlySequence action, double reward, ReadonlySequence newState) {
+      var key = Tuple.Create(state, action);
+      nextState[key] = newState;
+      if (newState.IsTerminal) done[newState] = true;
+      if 
+    }
+
+    public bool Done(ReadonlySequence state) {
+      return done.ContainsKey(state);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs	(revision 11742)
@@ -0,0 +1,23 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class RandomPolicy : IGrammarPolicy {
+    public ReadonlySequence SelectAction(Random random, ReadonlySequence state, IEnumerable<ReadonlySequence> actions) {
+      return actions.SelectRandom(random);
+    }
+
+    public void UpdateReward(ReadonlySequence state, ReadonlySequence action, double reward, ReadonlySequence newState) {
+      // ignore
+    }
+
+    public bool Done(ReadonlySequence state) {
+      return false;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11742)
@@ -44,4 +44,20 @@
   <ItemGroup>
     <Compile Include="BanditHelper.cs" />
+    <Compile Include="BanditPolicies\BernoulliPolicyActionInfo.cs" />
+    <Compile Include="BanditPolicies\BernoulliThompsonSamplingPolicy.cs" />
+    <Compile Include="BanditPolicies\BoltzmannExplorationPolicy.cs" />
+    <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
+    <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
+    <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />
+    <Compile Include="BanditPolicies\GaussianThompsonSamplingPolicy.cs" />
+    <Compile Include="BanditPolicies\GenericThompsonSamplingPolicy.cs" />
+    <Compile Include="BanditPolicies\MeanAndVariancePolicyActionInfo.cs" />
+    <Compile Include="BanditPolicies\ModelPolicyActionInfo.cs" />
+    <Compile Include="BanditPolicies\RandomPolicy.cs" />
+    <Compile Include="BanditPolicies\ThresholdAscentPolicy.cs" />
+    <Compile Include="BanditPolicies\UCB1Policy.cs" />
+    <Compile Include="BanditPolicies\UCB1TunedPolicy.cs" />
+    <Compile Include="BanditPolicies\UCBNormalPolicy.cs" />
+    <Compile Include="BanditPolicies\UCTPolicy.cs" />
     <Compile Include="Bandits\BernoulliBandit.cs" />
     <Compile Include="Bandits\GaussianBandit.cs" />
@@ -49,44 +65,12 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\RandomPolicy.cs" />
+    <Compile Include="IPolicy.cs" />
+    <Compile Include="IBanditPolicy.cs" />
+    <Compile Include="IBanditPolicyActionInfo.cs" />
     <Compile Include="OnlineMeanAndVarianceEstimator.cs" />
-    <Compile Include="IPolicyActionInfo.cs" />
     <Compile Include="Models\BernoulliModel.cs" />
     <Compile Include="Models\GaussianModel.cs" />
     <Compile Include="Models\IModel.cs" />
-    <Compile Include="Policies\BernoulliThompsonSamplingPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\BoltzmannExplorationPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\ChernoffIntervalEstimationPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\BernoulliPolicyActionInfo.cs" />
-    <Compile Include="Policies\ModelPolicyActionInfo.cs" />
-    <Compile Include="Policies\EpsGreedyPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\GaussianThompsonSamplingPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\GenericThompsonSamplingPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\MeanAndVariancePolicyActionInfo.cs" />
-    <Compile Include="Policies\DefaultPolicyActionInfo.cs" />
-    <Compile Include="Policies\EmptyPolicyActionInfo.cs" />
-    <Compile Include="Policies\RandomPolicy.cs" />
-    <Compile Include="Policies\UCB1Policy.cs" />
-    <Compile Include="IPolicy.cs" />
-    <Compile Include="Policies\UCB1TunedPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\UCBNormalPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="Policies\UCTPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
@@ -95,4 +79,8 @@
       <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
       <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
+      <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization</Name>
     </ProjectReference>
   </ItemGroup>
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicy.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicy.cs	(revision 11742)
@@ -0,0 +1,13 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // this interface represents a policy for bandit problems
+  public interface IBanditPolicy {
+    int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actions);
+    IBanditPolicyActionInfo CreateActionInfo();
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11742)
@@ -0,0 +1,18 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public interface IBanditPolicyActionInfo {
+    bool Disabled { get; }
+    double Value { get; }
+    int Tries { get; }
+    void UpdateReward(double reward);
+    void Disable();
+    // reset causes the state of the action to be reinitialized (as after constructor-call)
+    void Reset();
+    void PrintStats();
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11741)
+++ 	(revision )
@@ -1,13 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.Bandits {
-  // this interface represents a policy for reinforcement learning
-  public interface IPolicy {
-    int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos);
-    IPolicyActionInfo CreateActionInfo();
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicyActionInfo.cs	(revision 11741)
+++ 	(revision )
@@ -1,16 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.Bandits {
-  public interface IPolicyActionInfo {
-    bool Disabled { get; }
-    void UpdateReward(double reward);
-    void Disable();
-    // reset causes the state of the action to be reinitialized (as after constructor-call)
-    void Reset();
-    void PrintStats();
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/BernoulliModel.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/BernoulliModel.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/BernoulliModel.cs	(revision 11742)
@@ -9,4 +9,5 @@
 namespace HeuristicLab.Algorithms.Bandits.Models {
   public class BernoulliModel : IModel {
+
     private int success;
     private int failure;
@@ -47,4 +48,8 @@
       return new BernoulliModel() { failure = this.failure, success = this.success };
     }
+
+    public override string ToString() {
+      return string.Format("Bernoulli with Beta prior: mu={0:F2}", (success + alpha) / (success + alpha + failure + beta));
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianModel.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianModel.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianModel.cs	(revision 11742)
@@ -7,4 +7,5 @@
   // 2) unknown mean and unknown variance
   public class GaussianModel : IModel {
+
     private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
 
@@ -82,8 +83,8 @@
       }
 
+
       // sample from the posterior marginal for mu (expected value) equ. 91
       // p(µ|D) = T2αn (µ| µn, βn/(αnκn)) 
 
-      // sample from Tk distribution : http://stats.stackexchange.com/a/70270
       var t2alpha = alglib.invstudenttdistribution((int)(2 * posteriorAlpha), random.NextDouble());
 
@@ -91,6 +92,14 @@
       return theta;
 
-      //return alglib.invnormaldistribution(random.NextDouble()) * + theta;
-      //return alglib.invstudenttdistribution((int)(2 * posteriorAlpha), 0.99) * (posteriorBeta*posteriorK + posteriorBeta) / (posteriorAlpha*posteriorK) + posteriorMean;
+
+      /*
+       * value function : 0.99-quantile
+      // sample posterior mean and posterior variance independently
+      var sampledPrec = Rand.GammaRand(random, posteriorAlpha) * posteriorBeta;
+      var t2alpha = alglib.invstudenttdistribution((int)(2 * posteriorAlpha), random.NextDouble());
+      var sampledMean = t2alpha * posteriorBeta / (posteriorAlpha * posteriorK) + posteriorMean;
+
+      return alglib.invnormaldistribution(0.99) / Math.Sqrt(sampledPrec) + sampledMean;
+       */
     }
 
@@ -114,4 +123,27 @@
         return new GaussianModel(meanPriorMu, meanPriorVariance, precisionPriorAlpha, precisionPriorBeta);
     }
+
+    public override string ToString() {
+      if (knownVariance) {
+        var posteriorMeanVariance = 1.0 / (estimator.N / rewardVariance + 1.0 / meanPriorVariance);
+        var posteriorMeanMean = posteriorMeanVariance * (meanPriorMu / meanPriorVariance + estimator.Sum / rewardVariance);
+        return string.Format("Gaussian(mu, var=0.1), mu ~ Gaussian(mu'={0:F3}, var'={1:F3})", posteriorMeanMean, posteriorMeanVariance);
+      } else {
+        var posteriorMean = (priorK * meanPriorMu + estimator.Sum) / (priorK + estimator.N);
+        var posteriorK = priorK + estimator.N;
+        var posteriorAlpha = precisionPriorAlpha + estimator.N / 2.0;
+        double posteriorBeta;
+        if (estimator.N > 0) {
+          posteriorBeta = precisionPriorBeta + 0.5 * estimator.N * estimator.Variance + priorK * estimator.N * Math.Pow(estimator.Avg - meanPriorMu, 2) / (2.0 * (priorK + estimator.N));
+        } else {
+          posteriorBeta = precisionPriorBeta;
+        }
+        var nu = (int)(2 * posteriorAlpha);
+        var meanVariance = posteriorBeta / (posteriorAlpha * posteriorK) * (nu / (double)(nu - 2));
+        return string.Format("Gaussian(mu, var), mu ~ T{0}(mu'={1:F3}, var'={2:F3}), 1.0/var ~ Gamma(mu={3:F3}, var={4:F3})",
+          nu, posteriorMean, meanVariance,
+          posteriorAlpha / posteriorBeta, posteriorAlpha / (posteriorBeta * posteriorBeta));
+      }
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11742)
@@ -17,7 +17,7 @@
     private readonly Random random;
     private readonly int contextLen;
-    private readonly IPolicy policy;
+    private readonly IBanditPolicy policy;
 
-    public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, IPolicy policy) {
+    public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, IBanditPolicy policy) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -45,9 +45,9 @@
 
 
-    private Dictionary<string, IPolicyActionInfo[]> contextActionInfos;
+    private Dictionary<string, IBanditPolicyActionInfo[]> contextActionInfos;
     private List<Tuple<string, int>> updateChain;
 
     private void InitPolicies(IGrammar grammar) {
-      this.contextActionInfos = new Dictionary<string, IPolicyActionInfo[]>();
+      this.contextActionInfos = new Dictionary<string, IBanditPolicyActionInfo[]>();
       this.updateChain = new List<Tuple<string, int>>();
     }
@@ -82,5 +82,5 @@
           var endIdx = Math.Min(startIdx + contextLen, ntIdx);
           var lft = phrase.Subsequence(startIdx, endIdx - startIdx + 1).ToString();
-          lft = problem.Hash(lft);
+          lft = problem.CanonicalRepresentation(lft);
           if (!contextActionInfos.ContainsKey(lft)) {
             contextActionInfos.Add(lft, g.GetAlternatives(nt).Select(_ => policy.CreateActionInfo()).ToArray());
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11742)
@@ -16,7 +16,7 @@
     private readonly Random random;
     private readonly IProblem problem;
-    private readonly IPolicy policy;
+    private readonly IBanditPolicy policy;
 
-    public AlternativesSampler(IProblem problem, IPolicy policy, int maxLen) {
+    public AlternativesSampler(IProblem problem, IBanditPolicy policy, int maxLen) {
       this.problem = problem;
       this.maxLen = maxLen;
@@ -43,9 +43,9 @@
 
 
-    private Dictionary<char, IPolicyActionInfo[]> ntActionInfos;
+    private Dictionary<char, IBanditPolicyActionInfo[]> ntActionInfos;
     private List<Tuple<char, int>> updateChain;
 
     private void InitPolicies(IGrammar grammar) {
-      this.ntActionInfos = new Dictionary<char, IPolicyActionInfo[]>();
+      this.ntActionInfos = new Dictionary<char, IBanditPolicyActionInfo[]>();
       this.updateChain = new List<Tuple<char, int>>();
       foreach (var nt in grammar.NonTerminalSymbols) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11742)
@@ -46,4 +46,7 @@
     <Compile Include="AlternativesContextSampler.cs" />
     <Compile Include="ExhaustiveRandomFirstSearch.cs" />
+    <Compile Include="MctsContextualSampler.cs">
+      <SubType>Code</SubType>
+    </Compile>
     <Compile Include="MctsSampler.cs" />
     <Compile Include="ExhaustiveDepthFirstSearch.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsContextualSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsContextualSampler.cs	(revision 11742)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsContextualSampler.cs	(revision 11742)
@@ -0,0 +1,187 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class MctsContextualSampler {
+    private class TreeNode {
+      public int randomTries;
+      public int policyTries;
+      public TreeNode[] children;
+      public readonly ReadonlySequence phrase;
+      public readonly ReadonlySequence alt;
+
+      // phrase represents the phrase of the state and alt represents how the phrase has been reached from the parent state
+      public TreeNode(ReadonlySequence phrase, ReadonlySequence alt) {
+        this.phrase = phrase;
+        this.alt = alt;
+      }
+
+      public override string ToString() {
+        return string.Format("Node({0} tries: {1})", phrase, randomTries + policyTries);
+      }
+    }
+
+
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly IProblem problem;
+    private readonly Random random;
+    private readonly int randomTries;
+    private readonly IGrammarPolicy policy;
+
+    private List<Tuple<ReadonlySequence, ReadonlySequence, ReadonlySequence>> updateChain;
+    private TreeNode rootNode;
+
+    public int treeDepth;
+    public int treeSize;
+
+    // public MctsSampler(IProblem problem, int maxLen, Random random) :
+    //   this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) {
+    // 
+    // }
+
+    public MctsContextualSampler(IProblem problem, int maxLen, Random random, int randomTries, IGrammarPolicy policy) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = random;
+      this.randomTries = randomTries;
+      this.policy = policy;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      InitPolicies(problem.Grammar);
+      for (int i = 0; !policy.Done(rootNode.phrase) && i < maxIterations; i++) {
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        Debug.Assert(quality >= 0 && quality <= 1.0);
+        DistributeReward(quality);
+
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+
+      // clean up
+      InitPolicies(problem.Grammar); GC.Collect();
+    }
+
+    public void PrintStats() {
+      var n = rootNode;
+      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries);
+      while (n.children != null) {
+        Console.WriteLine();
+        Console.WriteLine("{0,5}->{1,-50}", n.alt, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.alt))));
+        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.randomTries + ch.policyTries))));
+        //n.policy.PrintStats();
+        n = n.children.OrderByDescending(c => c.policyTries).First();
+      }
+      Console.ReadLine();
+    }
+
+    private void InitPolicies(IGrammar grammar) {
+      this.updateChain = new List<Tuple<ReadonlySequence, ReadonlySequence, ReadonlySequence>>();
+
+      rootNode = new TreeNode(new ReadonlySequence(grammar.SentenceSymbol), new ReadonlySequence("$"));
+      treeDepth = 0;
+      treeSize = 0;
+    }
+
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      var startPhrase = new Sequence(rootNode.phrase);
+      return CompleteSentence(grammar, startPhrase);
+    }
+
+    private Sequence CompleteSentence(IGrammar g, Sequence phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      TreeNode parent = null;
+      TreeNode n = rootNode;
+      bool done = false;
+      var curDepth = 0;
+      while (!done) {
+        if (parent != null)
+          updateChain.Add(Tuple.Create(parent.phrase, n.alt, n.phrase));
+
+        if (n.randomTries < randomTries) {
+          n.randomTries++;
+          treeDepth = Math.Max(treeDepth, curDepth);
+          return g.CompleteSentenceRandomly(random, phrase, maxLen);
+        } else {
+          char nt = phrase.FirstNonTerminal;
+
+          int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
+          Debug.Assert(maxLenOfReplacement > 0);
+
+          var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
+
+          if (n.randomTries == randomTries && n.children == null) {
+            n.children = new TreeNode[alts.Count()];
+            int cIdx = 0;
+            foreach (var alt in alts) {
+              var newPhrase = new Sequence(phrase);
+              newPhrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, alt);
+              n.children[cIdx++] = new TreeNode(new ReadonlySequence(newPhrase), new ReadonlySequence(alt));
+            }
+            treeSize += n.children.Length;
+          }
+
+          n.policyTries++;
+          // => select using bandit policy
+          ReadonlySequence selectedAlt = policy.SelectAction(random, n.phrase, n.children.Select(c => c.alt));
+
+          // replace nt with alt
+          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
+
+          curDepth++;
+
+          done = phrase.IsTerminal;
+
+          // prepare for next iteration
+          parent = n;
+          n = n.children.Single(ch => ch.alt == selectedAlt); // TODO: perf
+        }
+      } // while
+
+      n.policyTries++;
+      updateChain.Add(Tuple.Create(parent.phrase, n.alt, n.phrase));
+
+
+      treeDepth = Math.Max(treeDepth, curDepth);
+      return phrase;
+    }
+
+    private void DistributeReward(double reward) {
+      // iterate in reverse order (bottom up)
+      updateChain.Reverse();
+
+      foreach (var e in updateChain) {
+        var state = e.Item1;
+        var action = e.Item2;
+        var newState = e.Item3;
+        policy.UpdateReward(state, action, reward, newState);
+        //policy.UpdateReward(action, reward / updateChain.Count);
+      }
+    }
+
+    private void RaiseSolutionEvaluated(string sentence, double quality) {
+      var handler = SolutionEvaluated;
+      if (handler != null) handler(sentence, quality);
+    }
+    private void RaiseFoundNewBestSolution(string sentence, double quality) {
+      var handler = FoundNewBestSolution;
+      if (handler != null) handler(sentence, quality);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11742)
@@ -12,6 +12,5 @@
       public string ident;
       public int randomTries;
-      public int policyTries;
-      public IPolicyActionInfo actionInfo;
+      public IBanditPolicyActionInfo actionInfo;
       public TreeNode[] children;
       public bool done = false;
@@ -22,5 +21,5 @@
 
       public override string ToString() {
-        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, randomTries + policyTries, done, actionInfo);
+        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, actionInfo.Tries, done, actionInfo);
       }
     }
@@ -34,5 +33,5 @@
     private readonly Random random;
     private readonly int randomTries;
-    private readonly IPolicy policy;
+    private readonly IBanditPolicy policy;
 
     private List<TreeNode> updateChain;
@@ -47,5 +46,5 @@
     // }
 
-    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, IPolicy policy) {
+    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, IBanditPolicy policy) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -78,11 +77,12 @@
     public void PrintStats() {
       var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries);
+      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, n.actionInfo.Tries);
       while (n.children != null) {
         Console.WriteLine();
         Console.WriteLine("{0,5}->{1,-50}", n.ident, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.ident))));
-        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.randomTries + ch.policyTries))));
+        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4:F2}", ch.actionInfo.Value * 10))));
+        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.done ? "X" : ch.actionInfo.Tries.ToString()))));
         //n.policy.PrintStats();
-        n = n.children.OrderByDescending(c => c.policyTries).First();
+        n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First();
       }
       Console.ReadLine();
@@ -108,7 +108,6 @@
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
       TreeNode n = rootNode;
-      bool done = phrase.IsTerminal;
       var curDepth = 0;
-      while (!done) {
+      while (!phrase.IsTerminal) {
         updateChain.Add(n);
 
@@ -127,9 +126,7 @@
           if (n.randomTries == randomTries && n.children == null) {
             n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
-            //n.children = alts.Select(alt => new TreeNode(string.Empty)).ToArray(); // create a new node for each alternative
             foreach (var ch in n.children) ch.actionInfo = policy.CreateActionInfo();
             treeSize += n.children.Length;
           }
-          n.policyTries++;
           // => select using bandit policy
           int selectedAltIdx = policy.SelectAction(random, n.children.Select(c => c.actionInfo));
@@ -140,6 +137,4 @@
 
           curDepth++;
-
-          done = phrase.IsTerminal;
 
           // prepare for next iteration
@@ -153,5 +148,4 @@
       // the last node is a leaf node (sentence is done), so we never need to visit this node again
       n.done = true;
-      n.actionInfo.Disable();
 
       treeDepth = Math.Max(treeDepth, curDepth);
@@ -165,4 +159,5 @@
       foreach (var e in updateChain) {
         var node = e;
+        if (node.done) node.actionInfo.Disable();
         if (node.children != null && node.children.All(c => c.done)) {
           node.done = true;
@@ -171,5 +166,4 @@
         if (!node.done) {
           node.actionInfo.UpdateReward(reward);
-          //policy.UpdateReward(action, reward / updateChain.Count);
         }
       }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs	(revision 11742)
@@ -8,5 +8,5 @@
   public static class Extensions {
     public static bool IsAlmost(this double x, double y) {
-      return Math.Abs(x - y) < 1.0e-6;
+      return Math.Abs(x - y) < 1.0e-12;
     }
 
@@ -38,9 +38,14 @@
       var ssX = 0.0;
       var ssY = 0.0;
-      foreach (var p in xs.Zip(ys, (x, y) => new { x, y })) {
-        s += (p.x - meanX) * (p.y - meanY);
-        ssX += Math.Pow(p.x - meanX, 2);
-        ssY += Math.Pow(p.y - meanY, 2);
+      var xEnum = xs.GetEnumerator();
+      var yEnum = ys.GetEnumerator();
+      while (xEnum.MoveNext() & yEnum.MoveNext()) {
+        var x = xEnum.Current;
+        var y = yEnum.Current;
+        s += (x - meanX) * (y - meanY);
+        ssX += Math.Pow(x - meanX, 2);
+        ssY += Math.Pow(y - meanY, 2);
       }
+      if (xEnum.MoveNext() | yEnum.MoveNext()) throw new ArgumentException("lengths are not equal");
 
       if (s.IsAlmost(0)) return 0;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11742)
@@ -74,5 +74,5 @@
 
     // right now only + and * is supported
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
       //var terms = terminalPhrase.Split('+');
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs	(revision 11742)
@@ -4,4 +4,5 @@
 using System.Globalization;
 using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
 using HeuristicLab.Algorithms.Bandits.Models;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -16,10 +17,8 @@
       var nArms = 20;
 
-      // Console.WriteLine("Threshold Ascent (20)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new ThresholdAscent(20, 0.01));
-      // Console.WriteLine("Threshold Ascent (100)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new ThresholdAscent(100, 0.01));
-      // Console.WriteLine("Threshold Ascent (500)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new ThresholdAscent(500, 0.01));
-      // Console.WriteLine("Threshold Ascent (1000)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new ThresholdAscent(1000, 0.01));
-      Console.WriteLine("Thompson (Gaussian fixed variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 1)));
-      Console.WriteLine("Thompson (Gaussian est variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 1, 0.1)));
+      // ThresholdAscent only works for rewards in [0..1] so far
+
+      Console.WriteLine("Thompson (Gaussian est variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 1, 1)));
+      Console.WriteLine("Thompson (Gaussian fixed variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 0.1)));
       Console.WriteLine("GaussianThompson (compat)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
       Console.WriteLine("GaussianThompson"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GaussianThompsonSamplingPolicy());
@@ -91,7 +90,13 @@
       var randSeed = 31415;
       var nArms = 20;
+      Console.WriteLine("Threshold Ascent (20)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(20, 0.01));
+      Console.WriteLine("Threshold Ascent (100)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(100, 0.01));
+      Console.WriteLine("Threshold Ascent (500)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(500, 0.01));
+      Console.WriteLine("Threshold Ascent (1000)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(1000, 0.01));
+      Console.WriteLine("Generic Thompson (Gaussian fixed var)"); TestPolicyGaussian(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1)));
+      Console.WriteLine("Generic Thompson (Gaussian unknown var)"); TestPolicyGaussian(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1, 1, 1)));
       Console.WriteLine("Thompson (Gaussian orig)"); TestPolicyGaussian(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
       Console.WriteLine("Thompson (Gaussian new)"); TestPolicyGaussian(randSeed, nArms, new GaussianThompsonSamplingPolicy());
-      Console.WriteLine("Generic Thompson (Gaussian)"); TestPolicyGaussian(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1)));
+
       /*
       Console.WriteLine("Random"); TestPolicyNormal(randSeed, nArms, new RandomPolicy(new Random(seedForPolicy), nArms));
@@ -123,5 +128,5 @@
       Console.WriteLine("ChernoffIntervalEstimationPolicy(0.01)"); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.01));
       Console.WriteLine("ChernoffIntervalEstimationPolicy(0.05)"); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.05));
-      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.1) "); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.1));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.1) "); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.1));      
       Console.WriteLine("ThresholdAscent(10,0.01)  "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10, 0.01));
       Console.WriteLine("ThresholdAscent(10,0.05)  "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10, 0.05));
@@ -141,7 +146,12 @@
       var randSeed = 31415;
       var nArms = 20;
+      Console.WriteLine("Threshold Ascent (20)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(20, 0.01));
+      Console.WriteLine("Threshold Ascent (100)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(100, 0.01));
+      Console.WriteLine("Threshold Ascent (500)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(500, 0.01));
+      Console.WriteLine("Threshold Ascent (1000)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(1000, 0.01));
       Console.WriteLine("Thompson (Gaussian orig)"); TestPolicyGaussianMixture(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
       Console.WriteLine("Thompson (Gaussian new)"); TestPolicyGaussianMixture(randSeed, nArms, new GaussianThompsonSamplingPolicy());
-      Console.WriteLine("Generic Thompson (Gaussian)"); TestPolicyGaussianMixture(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1)));
+      Console.WriteLine("Generic Thompson (Gaussian fixed variance)"); TestPolicyGaussianMixture(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1, 0.1)));
+      Console.WriteLine("Generic Thompson (Gaussian unknown variance)"); TestPolicyGaussianMixture(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1, 1, 1)));
 
       /*
@@ -167,19 +177,19 @@
 
 
-    private void TestPolicyBernoulli(int randSeed, int nArms, IPolicy policy) {
+    private void TestPolicyBernoulli(int randSeed, int nArms, IBanditPolicy policy) {
       TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new BernoulliBandit(banditRandom, nActions));
     }
-    private void TestPolicyGaussian(int randSeed, int nArms, IPolicy policy) {
+    private void TestPolicyGaussian(int randSeed, int nArms, IBanditPolicy policy) {
       TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new TruncatedNormalBandit(banditRandom, nActions));
     }
-    private void TestPolicyGaussianMixture(int randSeed, int nArms, IPolicy policy) {
+    private void TestPolicyGaussianMixture(int randSeed, int nArms, IBanditPolicy policy) {
       TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianMixtureBandit(banditRandom, nActions));
     }
-    private void TestPolicyGaussianUnknownVariance(int randSeed, int nArms, IPolicy policy) {
+    private void TestPolicyGaussianUnknownVariance(int randSeed, int nArms, IBanditPolicy policy) {
       TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianBandit(banditRandom, nActions));
     }
 
 
-    private void TestPolicy(int randSeed, int nArms, IPolicy policy, Func<Random, int, IBandit> banditFactory) {
+    private void TestPolicy(int randSeed, int nArms, IBanditPolicy policy, Func<Random, int, IBandit> banditFactory) {
       var maxIt = 1E5;
       var reps = 10; // independent runs
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11742)
@@ -51,5 +51,5 @@
     }
 
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11742)
@@ -39,5 +39,5 @@
     }
 
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11742)
@@ -9,5 +9,5 @@
     IGrammar Grammar { get; }
     double Evaluate(string sentence);
-    string Hash(string terminalPhrase);
+    string CanonicalRepresentation(string terminalPhrase);
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11742)
@@ -80,5 +80,5 @@
     }
 
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ReadonlySequence.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ReadonlySequence.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ReadonlySequence.cs	(revision 11742)
@@ -4,13 +4,13 @@
   public class ReadonlySequence : Sequence {
     public ReadonlySequence(string s)
-      : base(s) {
+      : base(s, s.Length) {
     }
 
     public ReadonlySequence(char ch)
-      : base(ch) {
+      : base(ch, 1) {
     }
 
     public ReadonlySequence(Sequence s)
-      : base(s) {
+      : base(s, s.Length) {
     }
 
@@ -32,5 +32,7 @@
     public override int GetHashCode() {
       int h = 31 * Length;
-      foreach (var ch in this) { h += 31 * (byte)h; }
+      for (int i = 0; i < Length; i++) {
+        h += 31 * (byte)this[i];
+      }
       return h;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11742)
@@ -34,5 +34,5 @@
     }
 
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11742)
@@ -29,5 +29,5 @@
       throw new NotImplementedException();
     }
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11742)
@@ -33,5 +33,5 @@
       return regex.Matches(sentence).Count;
     }
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11742)
@@ -29,5 +29,5 @@
       throw new NotImplementedException();
     }
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11742)
@@ -98,5 +98,5 @@
     }
 
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       return terminalPhrase.Replace("rl", "").Replace("lr", "");
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Sequence.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Sequence.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Sequence.cs	(revision 11742)
@@ -46,11 +46,15 @@
     }
 
-    private Sequence() {
-      this.symbols = new char[maxIdx + 1];
+    private Sequence(int maxLength) {
+      this.symbols = new char[maxLength];
     }
 
     // create a sequence from a character
     public Sequence(char ch)
-      : this() {
+      : this(ch, maxIdx + 1) {
+    }
+
+    protected Sequence(char ch, int maxLength)
+      : this(maxLength) {
       this.len = 1;
       symbols[0] = ch;
@@ -61,6 +65,7 @@
 
     // create a sequence from a string
-    public Sequence(string s)
-      : this() {
+    public Sequence(string s) : this(s, maxIdx + 1) { }
+    protected Sequence(string s, int maxLength)
+      : this(maxLength) {
       if (string.IsNullOrEmpty(s)) throw new ArgumentException();
       if (s.Length > (maxIdx + 1)) throw new ArgumentException();
@@ -77,6 +82,7 @@
 
     // cloning ctor
-    public Sequence(Sequence original)
-      : this() {
+    public Sequence(Sequence original) : this(original, maxIdx + 1) { }
+    protected Sequence(Sequence original, int maxLength)
+      : this(maxLength) {
       this.len = original.len;
       Array.Copy(original.symbols, this.symbols, len);
@@ -128,5 +134,5 @@
       if (startIdx >= this.len) throw new ArgumentException();
       if (startIdx + len > this.len) throw new ArgumentException();
-      var subsequence = new Sequence { len = len };
+      var subsequence = new Sequence(maxIdx + 1) { len = len };
 
       Array.Copy(this.symbols, startIdx, subsequence.symbols, 0, len);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11742)
@@ -21,5 +21,4 @@
 
     private readonly IGrammar grammar;
-    private readonly ExpressionInterpreter interpreter;
 
     private readonly int N;
@@ -29,5 +28,4 @@
     public SymbolicRegressionPoly10Problem() {
       this.grammar = new Grammar(grammarString);
-      this.interpreter = new ExpressionInterpreter();
 
       this.N = 500;
@@ -67,4 +65,5 @@
 
     public double Evaluate(string sentence) {
+      var interpreter = new ExpressionInterpreter();
       return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
     }
@@ -73,5 +72,5 @@
 
     // right now only + and * is supported
-    public string Hash(string terminalPhrase) {
+    public string CanonicalRepresentation(string terminalPhrase) {
       var terms = terminalPhrase.Split('+');
       return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11741)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11742)
@@ -8,4 +8,5 @@
 using System.Threading.Tasks;
 using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
 using HeuristicLab.Algorithms.Bandits.Models;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
@@ -26,12 +27,17 @@
       //var globalRandom = new Random(31415);
       var localRandSeed = 31415;
-      var reps = 20;
-
-      var policies = new Func<IPolicy>[]
+      var reps = 8;
+
+      var policies = new Func<IBanditPolicy>[]
         {
-         () => new GaussianThompsonSamplingPolicy(), 
+         () => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"), 
+         //() => new GaussianThompsonSamplingPolicy(), 
          () => new GaussianThompsonSamplingPolicy(true), 
-         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1)), 
-         () => new BernoulliThompsonSamplingPolicy(),
+         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)), 
+         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), 
+         //() => new BernoulliThompsonSamplingPolicy(),
          () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)), 
          () => new RandomPolicy(), 
@@ -61,23 +67,23 @@
          () => new ChernoffIntervalEstimationPolicy( 0.1),
          () => new ChernoffIntervalEstimationPolicy( 0.2),
-         // (rand) => new ThresholdAscentPolicy(10, 0.01), 
-         // (rand) => new ThresholdAscentPolicy(10, 0.05),
-         // (rand) => new ThresholdAscentPolicy(10, 0.1),
-         // (rand) => new ThresholdAscentPolicy(10, 0.2),
-         // (rand) => new ThresholdAscentPolicy(100, 0.01), 
-         // (rand) => new ThresholdAscentPolicy(100, 0.05),
-         // (rand) => new ThresholdAscentPolicy(100, 0.1),
-         // (rand) => new ThresholdAscentPolicy(100, 0.2),
-         // (rand) => new ThresholdAscentPolicy(1000, 0.01), 
-         // (rand) => new ThresholdAscentPolicy(1000, 0.05),
-         // (rand) => new ThresholdAscentPolicy(1000, 0.1),
-         // (rand) => new ThresholdAscentPolicy(1000, 0.2),
-         // (rand) => new ThresholdAscentPolicy(5000, 0.01), 
-         // (rand) => new ThresholdAscentPolicy(10000, 0.01), 
+         () => new ThresholdAscentPolicy(10, 0.01), 
+         () => new ThresholdAscentPolicy(10, 0.05),
+         () => new ThresholdAscentPolicy(10, 0.1),
+         () => new ThresholdAscentPolicy(10, 0.2),
+         () => new ThresholdAscentPolicy(100, 0.01), 
+         () => new ThresholdAscentPolicy(100, 0.05),
+         () => new ThresholdAscentPolicy(100, 0.1),
+         () => new ThresholdAscentPolicy(100, 0.2),
+         () => new ThresholdAscentPolicy(1000, 0.01), 
+         () => new ThresholdAscentPolicy(1000, 0.05),
+         () => new ThresholdAscentPolicy(1000, 0.1),
+         () => new ThresholdAscentPolicy(1000, 0.2),
+         () => new ThresholdAscentPolicy(5000, 0.01), 
+         () => new ThresholdAscentPolicy(10000, 0.01), 
         };
 
       foreach (var problem in new Tuple<IProblem, int>[]
         {
-          Tuple.Create((IProblem)new SantaFeAntProblem(), 17), 
+          //Tuple.Create((IProblem)new SantaFeAntProblem(), 17), 
           Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23), 
         })
@@ -87,5 +93,5 @@
             var localRand = new Random(localRandSeed);
             var options = new ParallelOptions();
-            options.MaxDegreeOfParallelism = 1;
+            options.MaxDegreeOfParallelism = 4;
             Parallel.For(0, reps, options, (i) => {
               //var t = Task.Run(() => {
@@ -132,23 +138,17 @@
     private static void RunDemo() {
       // TODO: test with eps-greedy using max instead of average as value (seems to work well for symb-reg! explore further!)
-      // TODO: implement GaussianWithUnknownMeanAndVariance Model for Thompson Sampling (verify with unit test if correct mean and variance is identified)
       // TODO: separate value function from policy
-      // TODO: debug and verify implementation variants of Gaussian Thompson Sampling with unit test
-      // TODO: refactor Policies to use banditInfos (policies are factories for bandit infos and bandit info only has an update routine, each policy works only with it's type of banditinfo)
       // TODO: in contextual MCTS store a bandit info for each node in the _graph_ and also update all bandit infos of all parents
       // TODO: exhaustive search with priority list
-      // TODO: warum funktioniert die alte Implementierung von GaussianThompson besser für SantaFe als alte? Siehe Vergleich: alte vs. neue implementierung GaussianThompsonSampling
+      // TODO: warum funktioniert die alte Implementierung von GaussianThompson besser für SantaFe als neue? Siehe Vergleich: alte vs. neue implementierung GaussianThompsonSampling
       // TODO: why does GaussianThompsonSampling work so well with MCTS for the artificial ant problem?
       // TODO: wie kann ich sampler noch vergleichen bzw. was kann man messen um die qualität des samplers abzuschätzen (bis auf qualität und iterationen bis zur besten lösung) => ziel schnellere iterationen zu gutem ergebnis
-      // TODO: likelihood für R=1 bei Gaussian oder GaussianMixture einfach berechenbar?
       // TODO: research thompson sampling for max bandit?
       // TODO: ausführlicher test von strategien für k-armed max bandit
       // TODO: verify TA implementation using example from the original paper      
-      // TODO: compare results for different policies also for the symb-reg problem
       // TODO: separate policy from MCTS tree data structure to allow sharing of information over disconnected parts of the tree (semantic equivalence)
       // TODO: implement thompson sampling for gaussian mixture models
       // TODO: implement inspection for MCTS (eventuell interactive command line für statistiken aus dem baum anzeigen)
       // TODO: implement ACO-style bandit policy
-      // TODO: implement sequences that can be manipulated in-place (instead of strings), alternatives are also stored as sequences, for a sequence the index of the first NT-symb can be stored 
       // TODO: gleichzeitige modellierung von transformierter zielvariable (y, 1/y, log(y), exp(y), sqrt(y), ...)
       // TODO: vergleich bei complete-randomly möglichst kurze sätze generieren vs. einfach zufällig alternativen wählen
@@ -165,12 +165,15 @@
       var random = new Random();
 
-      var problem = new SymbolicRegressionPoly10Problem();
-      //var problem = new SantaFeAntProblem(); // good results e.g. with       var alg = new MctsSampler(problem, 17, random, 1, (rand, numActions) => new ThresholdAscentPolicy(numActions, 500, 0.01));
-      //var problem = new SymbolicRegressionProblem("Tower"); // very good results e.g. new EpsGreedyPolicy(0.2) using max reward as quality !!!
+      var problem = new SymbolicRegressionPoly10Problem();   // good results e.g. 10 randomtries and EpsGreedyPolicy(0.2, (aInfo)=>aInfo.MaxReward)
+      // Ant
+      // good results e.g. with       var alg = new MctsSampler(problem, 17, random, 1, (rand, numActions) => new ThresholdAscentPolicy(numActions, 500, 0.01));
+      // GaussianModelWithUnknownVariance (and Q= 0.99-quantil) also works well for Ant
+      //var problem = new SantaFeAntProblem(); 
+      //var problem = new SymbolicRegressionProblem("Tower"); 
       //var problem = new PalindromeProblem();
       //var problem = new HardPalindromeProblem();
       //var problem = new RoyalPairProblem();
       //var problem = new EvenParityProblem();
-      var alg = new MctsSampler(problem, 23, random, 10, new EpsGreedyPolicy(0.2)); // GaussianModelWithUnknownVariance (and Q= 0.99-quantil) works well for Ant
+      var alg = new MctsSampler(problem, 25, random, 0, new GaussianThompsonSamplingPolicy(true));
       //var alg = new ExhaustiveBreadthFirstSearch(problem, 17);
       //var alg = new AlternativesContextSampler(problem, random, 17, 4, (rand, numActions) => new RandomPolicy(rand, numActions));
