Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11727)
@@ -43,4 +43,7 @@
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
     <Compile Include="Policies\BanditPolicy.cs" />
+    <Compile Include="Policies\BernoulliThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\GaussianThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\Exp3Policy.cs" />
     <Compile Include="Policies\EpsGreedyPolicy.cs" />
     <Compile Include="Policies\RandomPolicy.cs" />
@@ -51,5 +54,10 @@
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
-  <ItemGroup />
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Common\HeuristicLab.Common.csproj">
+      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
+  </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11727)
@@ -6,7 +6,17 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
+  // this interface represents a policy for reinforcement learning
   public interface IPolicy {
-    int SelectAction();
-    void UpdateReward(int action, double reward);
+    IEnumerable<int> Actions { get; }
+    int SelectAction(); // action selection ...
+    void UpdateReward(int action, double reward); // ... and reward update are defined as usual
+
+    // policies must also support disabling of potential actions
+    // for instance if we know that an action in a state has a deterministic 
+    // reward we need to sample it only once
+    // it is necessary to sample an action only once
+    void DisableAction(int action);
+
+    // reset causes the policy to be reinitialized to it's initial state (as after constructor-call)
     void Reset();
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -7,12 +8,24 @@
 namespace HeuristicLab.Algorithms.Bandits {
   public abstract class BanditPolicy : IPolicy {
-    public int NumActions { get; private set; }
-    public BanditPolicy(int numActions) {
-      this.NumActions = numActions;
+    public IEnumerable<int> Actions { get; private set; }
+    private readonly int numInitialActions;
+
+    protected BanditPolicy(int numActions) {
+      this.numInitialActions = numActions;
+      Actions = Enumerable.Range(0, numActions).ToArray();
     }
 
     public abstract int SelectAction();
     public abstract void UpdateReward(int action, double reward);
-    public abstract void Reset();
+
+    public virtual void DisableAction(int action) {
+      Debug.Assert(Actions.Contains(action));
+
+      Actions = Actions.Where(a => a != action).ToArray();
+    }
+
+    public virtual void Reset() {
+      Actions = Enumerable.Range(0, numInitialActions).ToArray();
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11727)
@@ -0,0 +1,58 @@
+﻿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 {
+  public class BernoulliThompsonSamplingPolicy : BanditPolicy {
+    private readonly Random random;
+    private readonly int[] success;
+    private readonly int[] failure;
+
+    // parameters of beta prior distribution
+    private readonly double alpha = 1.0;
+    private readonly double beta = 1.0;
+
+    public BernoulliThompsonSamplingPolicy(Random random, int numActions)
+      : base(numActions) {
+      this.random = random;
+      this.success = new int[numActions];
+      this.failure = new int[numActions];
+    }
+
+    public override int SelectAction() {
+      Debug.Assert(Actions.Any());
+      var maxTheta = double.NegativeInfinity;
+      int bestAction = -1;
+      foreach (var a in Actions) {
+        var theta = Rand.BetaRand(random, success[a] + alpha, failure[a] + beta);
+        if (theta > maxTheta) {
+          maxTheta = theta;
+          bestAction = a;
+        }
+      }
+      return bestAction;
+    }
+
+    public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+
+      if (reward > 0) success[action]++;
+      else failure[action]++;
+    }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      success[action] = -1;
+    }
+
+    public override void Reset() {
+      base.Reset();
+      Array.Clear(success, 0, success.Length);
+      Array.Clear(failure, 0, failure.Length);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -11,36 +12,54 @@
     private readonly int[] tries;
     private readonly double[] sumReward;
+    private readonly RandomPolicy randomPolicy;
+
     public EpsGreedyPolicy(Random random, int numActions, double eps)
       : base(numActions) {
       this.random = random;
       this.eps = eps;
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
+      this.randomPolicy = new RandomPolicy(random, numActions);
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
     }
 
     public override int SelectAction() {
+      Debug.Assert(Actions.Any());
       if (random.NextDouble() > eps) {
         // select best
         var maxReward = double.NegativeInfinity;
         int bestAction = -1;
-        for (int i = 0; i < NumActions; i++) {
-          if (tries[i] == 0) return i;
-          var avgReward = sumReward[i] / tries[i];
+        foreach (var a in Actions) {
+          if (tries[a] == 0) return a;
+          var avgReward = sumReward[a] / tries[a];
           if (maxReward < avgReward) {
             maxReward = avgReward;
-            bestAction = i;
+            bestAction = a;
           }
         }
+        Debug.Assert(bestAction >= 0);
         return bestAction;
       } else {
         // select random
-        return random.Next(NumActions);
+        return randomPolicy.SelectAction();
       }
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+
+      randomPolicy.UpdateReward(action, reward); // does nothing
       tries[action]++;
       sumReward[action] += reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      randomPolicy.DisableAction(action);
+      sumReward[action] = 0;
+      tries[action] = -1;
+    }
+
     public override void Reset() {
+      base.Reset();
+      randomPolicy.Reset();
       Array.Clear(tries, 0, tries.Length);
       Array.Clear(sumReward, 0, sumReward.Length);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs	(revision 11727)
@@ -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 {
+  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;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11727)
@@ -0,0 +1,60 @@
+﻿using System;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class GaussianThompsonSamplingPolicy : BanditPolicy {
+    private readonly Random random;
+    private readonly double[] sumRewards;
+    private readonly double[] sumSqrRewards;
+    private readonly int[] tries;
+    public GaussianThompsonSamplingPolicy(Random random, int numActions)
+      : base(numActions) {
+      this.random = random;
+      this.sumRewards = new double[numActions];
+      this.sumSqrRewards = new double[numActions];
+      this.tries = new int[numActions];
+    }
+
+
+    public override int SelectAction() {
+      Debug.Assert(Actions.Any());
+      var maxTheta = double.NegativeInfinity;
+      int bestAction = -1;
+      foreach (var a in Actions) {
+        if (tries[a] == 0) return a;
+        var mu = sumRewards[a] / tries[a];
+        var stdDev = Math.Sqrt(sumSqrRewards[a] / tries[a] - Math.Pow(mu, 2));
+        var theta = Rand.RandNormal(random) * stdDev + mu;
+        if (theta > maxTheta) {
+          maxTheta = theta;
+          bestAction = a;
+        }
+      }
+      return bestAction;
+    }
+
+    public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+
+      sumRewards[action] += reward;
+      sumSqrRewards[action] += reward * reward;
+      tries[action]++;
+    }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      sumRewards[action] = 0;
+      sumSqrRewards[action] = 0;
+      tries[action] = -1;
+    }
+
+    public override void Reset() {
+      base.Reset();
+      Array.Clear(sumRewards, 0, sumRewards.Length);
+      Array.Clear(sumSqrRewards, 0, sumSqrRewards.Length);
+      Array.Clear(tries, 0, tries.Length);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11727)
@@ -1,11 +1,14 @@
 ﻿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 {
   public class RandomPolicy : BanditPolicy {
     private readonly Random random;
+
     public RandomPolicy(Random random, int numActions)
       : base(numActions) {
@@ -14,12 +17,11 @@
 
     public override int SelectAction() {
-      return random.Next(NumActions);
+      Debug.Assert(Actions.Any());
+      return Actions.SelectRandom(random);
     }
     public override void UpdateReward(int action, double reward) {
       // do nothing
     }
-    public override void Reset() {
-      // do nothing
-    }
+
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -12,6 +13,6 @@
     public UCB1Policy(int numActions)
       : base(numActions) {
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
     }
 
@@ -19,10 +20,10 @@
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      for (int i = 0; i < NumActions; i++) {
-        if (tries[i] == 0) return i;
-        var q = sumReward[i] / tries[i] + Math.Sqrt((2 * Math.Log(totalTries)) / tries[i]);
+      foreach (var a in Actions) {
+        if (tries[a] == 0) return a;
+        var q = sumReward[a] / tries[a] + Math.Sqrt((2 * Math.Log(totalTries)) / tries[a]);
         if (q > bestQ) {
           bestQ = q;
-          bestAction = i;
+          bestAction = a;
         }
       }
@@ -30,9 +31,19 @@
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
       totalTries++;
       tries[action]++;
       sumReward[action] += reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      totalTries -= tries[action];
+      tries[action] = -1;
+      sumReward[action] = 0;
+    }
+
     public override void Reset() {
+      base.Reset();
       totalTries = 0;
       Array.Clear(tries, 0, tries.Length);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -13,7 +14,7 @@
     public UCB1TunedPolicy(int numActions)
       : base(numActions) {
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
-      this.sumSqrReward = new double[NumActions];
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
+      this.sumSqrReward = new double[numActions];
     }
 
@@ -25,12 +26,13 @@
 
     public override int SelectAction() {
+      Debug.Assert(Actions.Any());
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      for (int i = 0; i < NumActions; i++) {
-        if (tries[i] == 0) return i;
-        var q = sumReward[i] / tries[i] + Math.Sqrt((Math.Log(totalTries) / tries[i]) * Math.Min(1.0 / 4, V(i))); // 1/4 is upper bound of bernoulli distributed variable
+      foreach (var a in Actions) {
+        if (tries[a] == 0) return a;
+        var q = sumReward[a] / tries[a] + Math.Sqrt((Math.Log(totalTries) / tries[a]) * Math.Min(1.0 / 4, V(a))); // 1/4 is upper bound of bernoulli distributed variable
         if (q > bestQ) {
           bestQ = q;
-          bestAction = i;
+          bestAction = a;
         }
       }
@@ -38,4 +40,5 @@
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
       totalTries++;
       tries[action]++;
@@ -43,5 +46,15 @@
       sumSqrReward[action] += reward * reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      totalTries -= tries[action];
+      tries[action] = -1;
+      sumReward[action] = 0;
+      sumSqrReward[action] = 0;
+    }
+
     public override void Reset() {
+      base.Reset();
       totalTries = 0;
       Array.Clear(tries, 0, tries.Length);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11711)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -13,26 +14,21 @@
     public UCBNormalPolicy(int numActions)
       : base(numActions) {
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
-      this.sumSqrReward = new double[NumActions];
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
+      this.sumSqrReward = new double[numActions];
     }
 
-    private double V(int arm) {
-      var s = tries[arm];
-      return sumSqrReward[arm] / s - Math.Pow(sumReward[arm] / s, 2) + Math.Sqrt(2 * Math.Log(totalTries) / s);
-    }
-
-
     public override int SelectAction() {
+      Debug.Assert(Actions.Any());
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      for (int i = 0; i < NumActions; i++) {
-        if (totalTries == 0 || tries[i] == 0 || tries[i] < Math.Ceiling(8 * Math.Log(totalTries))) return i;
-        var avgReward = sumReward[i] / tries[i];
+      foreach (var a in Actions) {
+        if (totalTries == 0 || tries[a] == 0 || tries[a] < Math.Ceiling(8 * Math.Log(totalTries))) return a;
+        var avgReward = sumReward[a] / tries[a];
         var q = avgReward
-          + Math.Sqrt(16 * ((sumSqrReward[i] - tries[i] * Math.Pow(avgReward, 2)) / (tries[i] - 1)) * (Math.Log(totalTries - 1) / tries[i]));
+          + Math.Sqrt(16 * ((sumSqrReward[a] - tries[a] * Math.Pow(avgReward, 2)) / (tries[a] - 1)) * (Math.Log(totalTries - 1) / tries[a]));
         if (q > bestQ) {
           bestQ = q;
-          bestAction = i;
+          bestAction = a;
         }
       }
@@ -40,4 +36,5 @@
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
       totalTries++;
       tries[action]++;
@@ -45,5 +42,15 @@
       sumSqrReward[action] += reward * reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      totalTries -= tries[action];
+      tries[action] = -1;
+      sumReward[action] = 0;
+      sumSqrReward[action] = 0;
+    }
+
     public override void Reset() {
+      base.Reset();
       totalTries = 0;
       Array.Clear(tries, 0, tries.Length);
