Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11744)
@@ -20,4 +20,5 @@
     public void UpdateReward(double reward) {
       Debug.Assert(!Disabled);
+      Tries++;
       model.Update(reward);
     }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11744)
@@ -77,5 +77,5 @@
     }
 
-    private double U(double mu, int totalTries, int n, int k) {
+    private double U(double mu, double 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);
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11744)
@@ -69,4 +69,6 @@
     <Compile Include="IBanditPolicy.cs" />
     <Compile Include="IBanditPolicyActionInfo.cs" />
+    <Compile Include="Models\GaussianMixtureModel.cs" />
+    <Compile Include="Models\LogitNormalModel.cs" />
     <Compile Include="OnlineMeanAndVarianceEstimator.cs" />
     <Compile Include="Models\BernoulliModel.cs" />
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11744)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11744)
@@ -0,0 +1,19 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // this interface represents a policy for reinforcement learning
+  public interface IPolicy<in TState, TAction> {
+    TAction SelectAction(Random random, TState state, IEnumerable<TAction> actions);
+    void UpdateReward(TState state, TAction action, double reward, TState newState); // reward received when after taking action in state and new state
+    bool Done(TState state); // for deterministic MDP with deterministic rewards and goal to find a state with max reward
+  }
+
+  public interface IGrammarPolicy : IPolicy<ReadonlySequence, ReadonlySequence> {
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianMixtureModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianMixtureModel.cs	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianMixtureModel.cs	(revision 11744)
@@ -9,58 +9,42 @@
 namespace HeuristicLab.Algorithms.Bandits.Models {
   public class GaussianMixtureModel : IModel {
-    private readonly int numActions;
-    private readonly double[][] meanMean; // mean of mean for each arm and component 
-    private readonly double[][] meanVariance; // variance of mean for each arm and component 
-    private readonly double[][] componentProb;
+    private readonly double[] componentMeans;
+    private readonly double[] componentVars;
+    private readonly double[] componentProbs;
 
-    // parameters of beta prior distribution
     private int numComponents;
-    private double priorMean;
 
-    public GaussianMixtureModel(int numActions, double priorMean = 0.5, int nComponents = 5) {
-      this.numActions = numActions;
+    public GaussianMixtureModel(int nComponents = 5) {
       this.numComponents = nComponents;
-      this.priorMean = priorMean;
-      this.meanMean = new double[numActions][];
-      this.meanVariance = new double[numActions][];
-      this.componentProb = new double[numActions][];
-      for (int a = 0; a < numActions; a++) {
-        // TODO: probably need to initizalize this randomly to allow learning
-        meanMean[a] = Enumerable.Repeat(priorMean, nComponents).ToArray();
-        meanVariance[a] = Enumerable.Repeat(1.0, nComponents).ToArray(); // prior variance of mean variance = 1
-        componentProb[a] = Enumerable.Repeat(1.0 / nComponents, nComponents).ToArray(); // uniform prior for component probabilities
-      }
+      this.componentProbs = new double[nComponents];
+      this.componentMeans = new double[nComponents];
+      this.componentVars = new double[nComponents];
     }
 
 
-    public double[] SampleExpectedRewards(Random random) {
-      // sample mean foreach action and component from the prior
-      var exp = new double[numActions];
-      for (int a = 0; a < numActions; a++) {
-        var sumReward = 0.0;
-        var numSamples = 10000;
-        var sampledComponents = Enumerable.Range(0, numComponents).SampleProportional(random, componentProb[a]).Take(numSamples);
-        foreach (var k in sampledComponents) {
-          sumReward += Rand.RandNormal(random) * Math.Sqrt(meanVariance[a][k]) + meanMean[a][k];
-        }
-        exp[a] = sumReward / (double)numSamples;
-      }
-
-      return exp;
+    public double SampleExpectedReward(Random random) {
+      var k = Enumerable.Range(0, numComponents).SampleProportional(random, componentProbs).First();
+      return alglib.invnormaldistribution(random.NextDouble()) * Math.Sqrt(componentVars[k]) + componentMeans[k];
     }
 
-    public void Update(int action, double reward) {
+    public void Update(double reward) {
       // see http://www.cs.toronto.edu/~mackay/itprnn/ps/302.320.pdf Algorithm 22.2 soft k-means
       throw new NotImplementedException();
     }
 
-    public void Disable(int action) {
-      Array.Clear(meanMean[action], 0, meanMean[action].Length);
-      Array.Clear(meanVariance[action], 0, meanVariance[action].Length);
+    public void Disable() {
+      Array.Clear(componentMeans, 0, numComponents);
+      for (int i = 0; i < numComponents; i++)
+        componentVars[i] = 0.0;
+    }
+
+    public object Clone() {
+      return new GaussianMixtureModel(numComponents);
     }
 
     public void Reset() {
-      Array.Clear(meanMean, 0, meanMean.Length);
-      Array.Clear(meanVariance, 0, meanVariance.Length);
+      Array.Clear(componentMeans, 0, numComponents);
+      Array.Clear(componentVars, 0, numComponents);
+      Array.Clear(componentProbs, 0, numComponents);
     }
 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/LogitNormalModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/LogitNormalModel.cs	(revision 11744)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/LogitNormalModel.cs	(revision 11744)
@@ -0,0 +1,38 @@
+﻿using System;
+using System.Runtime.InteropServices;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.Models {
+  public class LogitNormalModel : IModel {
+
+    private readonly GaussianModel gaussian;
+
+    // this constructor assumes the variance is known
+    public LogitNormalModel() { gaussian = new GaussianModel(0, 1000, 1, 1); }
+
+
+
+    public double SampleExpectedReward(Random random) {
+      return 1.0 / (1 + Math.Exp(-gaussian.SampleExpectedReward(random)));
+    }
+
+    public void Update(double reward) {
+      gaussian.Update(Math.Log(reward / (1 - reward)));
+    }
+
+    public void Reset() {
+      gaussian.Reset();
+    }
+
+    public void PrintStats() {
+    }
+
+    public object Clone() {
+      return new LogitNormalModel();
+    }
+
+    public override string ToString() {
+      return string.Empty;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11744)
@@ -45,4 +45,5 @@
     <Compile Include="AlternativesSampler.cs" />
     <Compile Include="AlternativesContextSampler.cs" />
+    <Compile Include="TemporalDifferenceTreeSearchSampler.cs" />
     <Compile Include="ExhaustiveRandomFirstSearch.cs" />
     <Compile Include="MctsContextualSampler.cs">
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11744)
@@ -40,4 +40,5 @@
     public int treeDepth;
     public int treeSize;
+    private double bestQuality;
 
     // public MctsSampler(IProblem problem, int maxLen, Random random) :
@@ -55,5 +56,5 @@
 
     public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
+      bestQuality = double.MinValue;
       InitPolicies(problem.Grammar);
       for (int i = 0; !rootNode.done && i < maxIterations; i++) {
@@ -77,5 +78,5 @@
     public void PrintStats() {
       var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, n.actionInfo.Tries);
+      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.actionInfo.Tries, n.actionInfo.Value, bestQuality);
       while (n.children != null) {
         Console.WriteLine();
@@ -86,5 +87,4 @@
         n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First();
       }
-      Console.ReadLine();
     }
 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/TemporalDifferenceTreeSearchSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/TemporalDifferenceTreeSearchSampler.cs	(revision 11744)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/TemporalDifferenceTreeSearchSampler.cs	(revision 11744)
@@ -0,0 +1,206 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  // SARSA (fig. 6.9 in Sutton & Barto)
+  public class TemporalDifferenceTreeSearchSampler {
+    private class TreeNode {
+      public string ident;
+      public int randomTries;
+      public double q;
+      public int tries;
+      public TreeNode[] children;
+      public bool done = false;
+
+      public TreeNode(string id) {
+        this.ident = id;
+      }
+
+      public override string ToString() {
+        return string.Format("Node({0} tries: {1}, done: {2})", ident, tries, done);
+      }
+    }
+
+
+    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 IBanditPolicy policy;
+
+    private List<TreeNode> updateChain;
+    private TreeNode rootNode;
+
+    public int treeDepth;
+    public int treeSize;
+    private double bestQuality;
+
+
+    public TemporalDifferenceTreeSearchSampler(IProblem problem, int maxLen, Random random, int randomTries, IBanditPolicy policy) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = random;
+      this.randomTries = randomTries;
+      this.policy = policy;
+    }
+
+    public void Run(int maxIterations) {
+      InitPolicies(problem.Grammar);
+      for (int i = 0; !rootNode.done && 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}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.tries, n.q, bestQuality);
+      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:F2}", ch.q * 10))));
+        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.done ? "X" : ch.tries.ToString()))));
+        //n.policy.PrintStats();
+        n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.q).First();
+      }
+      //Console.ReadLine();
+    }
+
+    private void InitPolicies(IGrammar grammar) {
+      this.updateChain = new List<TreeNode>();
+
+      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
+      treeDepth = 0;
+      treeSize = 0;
+    }
+
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      var startPhrase = new Sequence(grammar.SentenceSymbol);
+      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 n = rootNode;
+      var curDepth = 0;
+      while (!phrase.IsTerminal) {
+        updateChain.Add(n);
+
+        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 = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
+            treeSize += n.children.Length;
+          }
+          // => select using bandit policy
+          int selectedAltIdx = SelectAction(random, n.children);
+          Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
+
+          // replace nt with alt
+          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
+
+          curDepth++;
+
+          // prepare for next iteration
+          n = n.children[selectedAltIdx];
+        }
+      } // while
+
+      updateChain.Add(n);
+
+
+      // the last node is a leaf node (sentence is done), so we never need to visit this node again
+      n.done = true;
+
+      treeDepth = Math.Max(treeDepth, curDepth);
+      return phrase;
+    }
+
+
+    // eps-greedy
+    private int SelectAction(Random random, TreeNode[] children) {
+      if (random.NextDouble() < 0.1) {
+
+        return children.Select((ch, i) => Tuple.Create(ch, i)).Where(p => !p.Item1.done).SelectRandom(random).Item2;
+      } else {
+        var bestQ = double.NegativeInfinity;
+        var bestChildIdx = -1;
+        for (int i = 0; i < children.Length; i++) {
+          if (children[i].done) continue;
+          if (children[i].tries == 0) return i;
+          if (children[i].q > bestQ) {
+            bestQ = children[i].q;
+            bestChildIdx = i;
+          }
+        }
+        Debug.Assert(bestChildIdx > -1);
+        return bestChildIdx;
+      }
+    }
+
+    private void DistributeReward(double reward) {
+      const double alpha = 0.1;
+      const double gamma = 1;
+      // iterate in reverse order (bottom up)
+      updateChain.Reverse();
+      var nextQ = 0.0;
+      foreach (var e in updateChain) {
+        var node = e;
+        node.tries++;
+        if (node.children != null && node.children.All(c => c.done)) {
+          node.done = true;
+        }
+        // reward is recieved only for the last action
+        if (e == updateChain.First()) {
+          node.q = node.q + alpha * (reward + gamma * nextQ - node.q);
+          nextQ = node.q;
+        } else {
+          node.q = node.q + alpha * (0 + gamma * nextQ - node.q);
+          nextQ = node.q;
+        }
+      }
+    }
+
+    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/Main/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11743)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11744)
@@ -175,5 +175,6 @@
       //var problem = new RoyalPairProblem();
       //var problem = new EvenParityProblem();
-      var alg = new MctsSampler(problem, 25, random, 0, new GaussianThompsonSamplingPolicy(true));
+      var alg = new MctsSampler(problem, 25, random, 0, new GenericThompsonSamplingPolicy(new LogitNormalModel()));
+      //var alg = new TemporalDifferenceTreeSearchSampler(problem, 23, random, 0, new RandomPolicy());
       //var alg = new ExhaustiveBreadthFirstSearch(problem, 17);
       //var alg = new AlternativesContextSampler(problem, random, 17, 4, (rand, numActions) => new RandomPolicy(rand, numActions));
@@ -191,5 +192,6 @@
         iterations++;
         globalStatistics.AddSentence(sentence, quality);
-        if (iterations % 1000 == 0) {
+        if (iterations % 100 == 0) {
+          Console.Clear();
           alg.PrintStats();
         }
