Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Bandits/GaussianBandit.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Bandits/GaussianBandit.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Bandits/GaussianBandit.cs	(revision 11732)
@@ -0,0 +1,49 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class GaussianBandit : IBandit {
+    public int NumArms { get; private set; }
+    public double OptimalExpectedReward { get; private set; } // reward of the best arm, for calculating regret
+    public int OptimalExpectedRewardArm { get; private set; }
+    public int OptimalMaximalRewardArm { get; private set; }
+
+    private readonly Random random;
+    private readonly double[] exp;
+    private readonly double[] stdDev;
+    public GaussianBandit(Random random, int nArms) {
+      this.random = random;
+      this.NumArms = nArms;
+      // expected reward of arms is iid and uniformly distributed 
+      exp = new double[nArms];
+      stdDev = new double[nArms];
+      OptimalExpectedReward = double.NegativeInfinity;
+      var bestQ = double.NegativeInfinity;
+      for (int i = 0; i < nArms; i++) {
+        exp[i] = Rand.RandNormal(random);  // exp values for arms is N(0,1) distributed
+        stdDev[i] = 1.0 / Rand.GammaRand(random, 1); // variance is inv-gamma distributed 
+        if (exp[i] > OptimalExpectedReward) {
+          OptimalExpectedReward = exp[i];
+          OptimalExpectedRewardArm = i;
+        }
+        var q = alglib.invnormaldistribution(0.99) * stdDev[i] + exp[i];
+        if (q > bestQ) {
+          bestQ = q;
+          OptimalMaximalRewardArm = i;
+        }
+      }
+    }
+
+    // pulling an arm results in a truncated normally distributed reward 
+    // with mean expReward[i] and std.dev 0.1
+    public double Pull(int arm) {
+      var z = Rand.RandNormal(random);
+      var x = z * stdDev[arm] + exp[arm];
+      return x;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11732)
@@ -31,4 +31,7 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="ALGLIB-3.7.0">
+      <HintPath>..\..\..\trunk\sources\bin\ALGLIB-3.7.0.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -42,26 +45,48 @@
     <Compile Include="BanditHelper.cs" />
     <Compile Include="Bandits\BernoulliBandit.cs" />
+    <Compile Include="Bandits\GaussianBandit.cs" />
     <Compile Include="Bandits\GaussianMixtureBandit.cs" />
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="OnlineMeanAndVarianceEstimator.cs" />
+    <Compile Include="IPolicyActionInfo.cs" />
     <Compile Include="Models\BernoulliModel.cs" />
     <Compile Include="Models\GaussianModel.cs" />
-    <Compile Include="Models\GaussianMixtureModel.cs" />
     <Compile Include="Models\IModel.cs" />
-    <Compile Include="Policies\BanditPolicy.cs" />
-    <Compile Include="Policies\BernoulliThompsonSamplingPolicy.cs" />
-    <Compile Include="Policies\BoltzmannExplorationPolicy.cs" />
-    <Compile Include="Policies\ChernoffIntervalEstimationPolicy.cs" />
-    <Compile Include="Policies\GenericThompsonSamplingPolicy.cs" />
-    <Compile Include="Policies\ThresholdAscentPolicy.cs" />
-    <Compile Include="Policies\UCTPolicy.cs" />
-    <Compile Include="Policies\GaussianThompsonSamplingPolicy.cs" />
-    <Compile Include="Policies\Exp3Policy.cs" />
-    <Compile Include="Policies\EpsGreedyPolicy.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="Policies\UCB1TunedPolicy.cs" />
-    <Compile Include="Policies\UCBNormalPolicy.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>
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11732)
@@ -8,18 +8,6 @@
   // this interface represents a policy for reinforcement learning
   public interface IPolicy {
-    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();
-
-    void PrintStats();
+    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 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicyActionInfo.cs	(revision 11732)
@@ -0,0 +1,16 @@
+﻿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 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/BernoulliModel.cs	(revision 11732)
@@ -9,7 +9,6 @@
 namespace HeuristicLab.Algorithms.Bandits.Models {
   public class BernoulliModel : IModel {
-    private readonly int numActions;
-    private readonly int[] success;
-    private readonly int[] failure;
+    private int success;
+    private int failure;
 
     // parameters of beta prior distribution
@@ -17,52 +16,34 @@
     private readonly double beta;
 
-    public BernoulliModel(int numActions, double alpha = 1.0, double beta = 1.0) {
-      this.numActions = numActions;
-      this.success = new int[numActions];
-      this.failure = new int[numActions];
+    public BernoulliModel(double alpha = 1.0, double beta = 1.0) {
       this.alpha = alpha;
       this.beta = beta;
     }
 
-
-    public double[] SampleExpectedRewards(Random random) {
+    public double SampleExpectedReward(Random random) {
       // sample bernoulli mean from beta prior
-      var theta = new double[numActions];
-      for (int a = 0; a < numActions; a++) {
-        if (success[a] == -1)
-          theta[a] = 0.0;
-        else {
-          theta[a] = Rand.BetaRand(random, success[a] + alpha, failure[a] + beta);
-        }
-      }
-
-      // no need to sample we know the exact expected value
-      // the expected value of a bernoulli variable is just theta
-      return theta.Select(t => t).ToArray();
+      return Rand.BetaRand(random, success + alpha, failure + beta);
     }
 
-    public void Update(int action, double reward) {
-      const double EPSILON = 1E-6;
-      Debug.Assert(Math.Abs(reward - 0.0) < EPSILON || Math.Abs(reward - 1.0) < EPSILON);
-      if (Math.Abs(reward - 1.0) < EPSILON) {
-        success[action]++;
+    public void Update(double reward) {
+      Debug.Assert(reward.IsAlmost(1.0) || reward.IsAlmost(0.0));
+      if (reward.IsAlmost(1.0)) {
+        success++;
       } else {
-        failure[action]++;
+        failure++;
       }
     }
 
-    public void Disable(int action) {
-      success[action] = -1;
-    }
-
     public void Reset() {
-      Array.Clear(success, 0, numActions);
-      Array.Clear(failure, 0, numActions);
+      success = 0;
+      failure = 0;
     }
 
     public void PrintStats() {
-      for (int i = 0; i < numActions; i++) {
-        Console.Write("{0:F2} ", success[i] / (double)failure[i]);
-      }
+      Console.Write("{0:F2} ", success / (double)failure);
+    }
+
+    public object Clone() {
+      return new BernoulliModel() { failure = this.failure, success = this.success };
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianModel.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianModel.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianModel.cs	(revision 11732)
@@ -1,17 +1,11 @@
 ﻿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.Models {
-  // bayesian estimation of a Gaussian with unknown mean and known variance
+  // bayesian estimation of a Gaussian with 
+  // 1) unknown mean and known variance
+  // 2) unknown mean and unknown variance
   public class GaussianModel : IModel {
-    private readonly int numActions;
-    private readonly int[] tries;
-    private readonly double[] sumRewards;
-
+    private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
 
     // parameters of Gaussian prior for mean
@@ -19,57 +13,104 @@
     private readonly double meanPriorVariance;
 
+    private readonly bool knownVariance;
     private readonly double rewardVariance = 0.1; // assumed know reward variance
 
-    public GaussianModel(int numActions, double meanPriorMu, double meanPriorVariance) {
-      this.numActions = numActions;
-      this.tries = new int[numActions];
-      this.sumRewards = new double[numActions];
+    // parameters of Gamma prior for precision (= inverse variance)
+    private readonly int precisionPriorAlpha;
+    private readonly double precisionPriorBeta;
+
+    // non-informative prior
+    private const double priorK = 1.0;
+
+    // this constructor assumes the variance is known
+    public GaussianModel(double meanPriorMu, double meanPriorVariance, double rewardVariance = 0.1) {
       this.meanPriorMu = meanPriorMu;
       this.meanPriorVariance = meanPriorVariance;
+
+      this.knownVariance = true;
+      this.rewardVariance = rewardVariance;
+    }
+
+    // this constructor assumes the variance is also unknown 
+    // uses Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution equation 85 - 89
+    public GaussianModel(double meanPriorMu, double meanPriorVariance, int precisionPriorAlpha, double precisionPriorBeta) {
+      this.meanPriorMu = meanPriorMu;
+      this.meanPriorVariance = meanPriorVariance;
+
+      this.knownVariance = false;
+      this.precisionPriorAlpha = precisionPriorAlpha;
+      this.precisionPriorBeta = precisionPriorBeta;
     }
 
 
-    public double[] SampleExpectedRewards(Random random) {
+    public double SampleExpectedReward(Random random) {
+      if (knownVariance) {
+        return SampleExpectedRewardKnownVariance(random);
+      } else {
+        return SampleExpectedRewardUnknownVariance(random);
+      }
+    }
+
+    private double SampleExpectedRewardKnownVariance(Random random) {
       // expected values for reward
-      var theta = new double[numActions];
+      // calculate posterior mean and variance (for mean reward)
 
-      for (int a = 0; a < numActions; a++) {
-        if (tries[a] == -1) {
-          theta[a] = double.NegativeInfinity; // disabled action
-        } 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 posteriorMeanVariance = 1.0 / (estimator.N / rewardVariance + 1.0 / meanPriorVariance);
+      var posteriorMeanMean = posteriorMeanVariance * (meanPriorMu / meanPriorVariance + estimator.Sum / rewardVariance);
 
-          // see Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution (http://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf)
-          var posteriorVariance = 1.0 / (tries[a] / rewardVariance + 1.0 / meanPriorVariance);
-          var posteriorMean = posteriorVariance * (meanPriorMu / meanPriorVariance + sumRewards[a] / rewardVariance);
+      // sample a mean from the posterior 
+      var posteriorMeanSample = Rand.RandNormal(random) * Math.Sqrt(posteriorMeanVariance) + posteriorMeanMean;
+      // theta already represents the expected reward value => nothing else to do
+      return posteriorMeanSample;
 
-          // sample a mean from the posterior 
-          theta[a] = Rand.RandNormal(random) * Math.Sqrt(posteriorVariance) + posteriorMean;
-          // theta already represents the expected reward value => nothing else to do
-        }
+      // return 0.99-quantile value
+      //return alglib.invnormaldistribution(0.99) * Math.Sqrt(rewardVariance + posteriorMeanVariance) + posteriorMeanMean;
+    }
+
+    // see Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution page 6 onwards (http://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf)
+    private double SampleExpectedRewardUnknownVariance(Random random) {
+
+      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;
       }
 
+      // 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());
+
+      var theta = t2alpha * posteriorBeta / (posteriorAlpha * posteriorK) + posteriorMean;
       return theta;
+
+      //return alglib.invnormaldistribution(random.NextDouble()) * + theta;
+      //return alglib.invstudenttdistribution((int)(2 * posteriorAlpha), 0.99) * (posteriorBeta*posteriorK + posteriorBeta) / (posteriorAlpha*posteriorK) + posteriorMean;
     }
 
-    public void Update(int action, double reward) {
-      sumRewards[action] += reward;
-      tries[action]++;
-    }
 
-    public void Disable(int action) {
-      tries[action] = -1;
-      sumRewards[action] = 0.0;
+    public void Update(double reward) {
+      estimator.UpdateReward(reward);
     }
 
     public void Reset() {
-      Array.Clear(tries, 0, numActions);
-      Array.Clear(sumRewards, 0, numActions);
+      estimator.Reset();
     }
 
     public void PrintStats() {
-      for (int i = 0; i < numActions; i++) {
-        Console.Write("{0:F2} ", sumRewards[i] / (double)tries[i]);
-      }
+      Console.Write("{0:F2} ", estimator.Avg);
+    }
+
+    public object Clone() {
+      if (knownVariance)
+        return new GaussianModel(meanPriorMu, meanPriorVariance, rewardVariance);
+      else
+        return new GaussianModel(meanPriorMu, meanPriorVariance, precisionPriorAlpha, precisionPriorBeta);
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/IModel.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/IModel.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/IModel.cs	(revision 11732)
@@ -6,8 +6,8 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public interface IModel {
-    double[] SampleExpectedRewards(Random random);
-    void Update(int action, double reward);
-    void Disable(int action);
+  // represents a model for the reward distribution (of an action given a state)
+  public interface IModel : ICloneable {
+    double SampleExpectedReward(Random random);
+    void Update(double reward);
     void Reset();
     void PrintStats();
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/OnlineMeanAndVarianceEstimator.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/OnlineMeanAndVarianceEstimator.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/OnlineMeanAndVarianceEstimator.cs	(revision 11732)
@@ -0,0 +1,32 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  class OnlineMeanAndVarianceEstimator {
+    public int N { get; private set; }
+    public double Sum { get; private set; }
+    public double Avg { get; private set; }
+    public double Variance { get { return sampleM2 / N; } }
+    private double sampleM2;
+
+    public void UpdateReward(double reward) {
+      N++;
+      Sum += reward;
+
+      var delta = reward - Avg;
+      Avg += delta / N;
+      sampleM2 += delta * (reward - Avg);
+    }
+
+    public void Reset() {
+      Sum = 0.0;
+      Avg = 0.0;
+      N = 0;
+      sampleM2 = 0.0;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs	(revision 11732)
@@ -7,5 +7,5 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public abstract class BanditPolicy : IPolicy {
+  public abstract class BanditPolicy<TPolicyActionInfo> : IPolicy<TPolicyActionInfo> where TPolicyActionInfo : IPolicyActionInfo {
     public IEnumerable<int> Actions { get; private set; }
     private readonly int numInitialActions;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliPolicyActionInfo.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliPolicyActionInfo.cs	(revision 11732)
@@ -0,0 +1,34 @@
+﻿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 BernoulliPolicyActionInfo : IPolicyActionInfo {
+    public bool Disabled { get { return NumSuccess == -1; } }
+    public int NumSuccess { get; private set; }
+    public int NumFailure { get; private set; }
+    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}", NumSuccess / (double)NumFailure, Disabled);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11732)
@@ -8,62 +8,32 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class BernoulliThompsonSamplingPolicy : BanditPolicy {
-    private readonly Random random;
-    private readonly int[] success;
-    private readonly int[] failure;
-
+  public class BernoulliThompsonSamplingPolicy : IPolicy {
     // 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 int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<BernoulliPolicyActionInfo>(); // TODO: performance
+      int bestAction = -1;
+      double maxTheta = double.NegativeInfinity;
+      var aIdx = -1;
 
-    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);
+      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 = a;
+          bestAction = aIdx;
         }
       }
+      Debug.Assert(bestAction > -1);
       return bestAction;
     }
 
-    public override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-
-      if (reward > 0) success[action]++;
-      else failure[action]++;
+    public IPolicyActionInfo CreateActionInfo() {
+      return new BernoulliPolicyActionInfo();
     }
 
-    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);
-    }
-
-    public override void PrintStats() {
-      for (int i = 0; i < success.Length; i++) {
-        if (success[i] >= 0) {
-          Console.Write("{0,5:F2}", success[i] / failure[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
-    }
 
     public override string ToString() {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BoltzmannExplorationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BoltzmannExplorationPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BoltzmannExplorationPolicy.cs	(revision 11732)
@@ -5,69 +5,44 @@
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Algorithms.Bandits {
   // also called softmax policy
-  public class BoltzmannExplorationPolicy : BanditPolicy {
-    private readonly Random random;
-    private readonly double eps;
-    private readonly int[] tries;
-    private readonly double[] sumReward;
+  public class BoltzmannExplorationPolicy : IPolicy {
     private readonly double beta;
 
-    public BoltzmannExplorationPolicy(Random random, int numActions, double beta)
-      : base(numActions) {
+    public BoltzmannExplorationPolicy(double beta) {
       if (beta < 0) throw new ArgumentException();
-      this.random = random;
       this.beta = beta;
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
+    }
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+
+      // select best
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>().ToArray(); // TODO: performance
+      Debug.Assert(myActionInfos.Any(a => !a.Disabled));
+      double[] w = new double[myActionInfos.Length];
+
+      for (int a = 0; a < myActionInfos.Length; a++) {
+        if (myActionInfos[a].Disabled) {
+          w[a] = 0; continue;
+        }
+        if (myActionInfos[a].Tries == 0) return a;
+        var sumReward = myActionInfos[a].SumReward;
+        var tries = myActionInfos[a].Tries;
+        var avgReward = sumReward / tries;
+        w[a] = Math.Exp(beta * avgReward);
+      }
+
+
+      var bestAction = Enumerable.Range(0, w.Length).SampleProportional(random, w).First();
+      Debug.Assert(bestAction >= 0);
+      Debug.Assert(bestAction < w.Length);
+      Debug.Assert(!myActionInfos[bestAction].Disabled);
+      return bestAction;
     }
 
-    public override int SelectAction() {
-      Debug.Assert(Actions.Any());
-      // select best
-      var maxReward = double.NegativeInfinity;
-      int bestAction = -1;
-      if (Actions.Any(a => tries[a] == 0))
-        return Actions.First(a => tries[a] == 0);
-
-      var ts = Actions.Select(a => Math.Exp(beta * sumReward[a] / tries[a]));
-      var r = random.NextDouble() * ts.Sum();
-
-      var agg = 0.0;
-      foreach (var p in Actions.Zip(ts, Tuple.Create)) {
-        agg += p.Item2;
-        if (agg >= r) return p.Item1;
-      }
-      throw new InvalidProgramException();
-    }
-    public override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-
-      tries[action]++;
-      sumReward[action] += reward;
-    }
-
-    public override void DisableAction(int action) {
-      base.DisableAction(action);
-      sumReward[action] = 0;
-      tries[action] = -1;
-    }
-
-    public override void Reset() {
-      base.Reset();
-      Array.Clear(tries, 0, tries.Length);
-      Array.Clear(sumReward, 0, sumReward.Length);
-    }
-
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
+    public IPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
     }
 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs	(revision 11732)
@@ -10,29 +10,31 @@
 International Conference, CP 2006, Nantes, France, September 25-29, 2006. pp 560-574 */
 
-  public class ChernoffIntervalEstimationPolicy : BanditPolicy {
-    private readonly int[] tries;
-    private readonly double[] sumReward;
-    private int totalTries = 0;
+  public class ChernoffIntervalEstimationPolicy : IPolicy {
     private readonly double delta;
 
-    public ChernoffIntervalEstimationPolicy(int numActions, double delta = 0.01)
-      : base(numActions) {
+    public ChernoffIntervalEstimationPolicy(double delta = 0.01) {
       this.delta = delta;
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
     }
-
-    public override int SelectAction() {
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      // select best
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>().ToArray(); // TODO: performance
+      int k = myActionInfos.Length;
+      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      double k = Actions.Count();
-      Debug.Assert(k > 0);
-      foreach (var a in Actions) {
-        if (tries[a] == 0) return a;
+      for (int a = 0; a < myActionInfos.Length; a++) {
+        if (myActionInfos[a].Disabled) continue;
+        if (myActionInfos[a].Tries == 0) return a;
+
+        var sumReward = myActionInfos[a].SumReward;
+        var tries = myActionInfos[a].Tries;
+
+        var avgReward = sumReward / 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) + Math.Log(totalTries) + Math.Log(k) - Math.Log(delta); // total tries is max tries in the original paper
-        double mu = sumReward[a] / tries[a];
-        var q = mu + (alpha + Math.Sqrt(2 * tries[a] * mu * alpha + alpha * alpha)) / tries[a];
+        var q = avgReward + (alpha + Math.Sqrt(2 * tries * avgReward * alpha + alpha * alpha)) / tries;
         if (q > bestQ) {
           bestQ = q;
@@ -40,37 +42,12 @@
         }
       }
+      Debug.Assert(bestAction >= 0);
       return bestAction;
     }
-    public override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-      totalTries++;
-      tries[action]++;
-      sumReward[action] += reward;
+
+    public IPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
     }
 
-    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);
-      Array.Clear(sumReward, 0, sumReward.Length);
-    }
-
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
-    }
     public override string ToString() {
       return string.Format("ChernoffIntervalEstimationPolicy({0:F2})", delta);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/DefaultPolicyActionInfo.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/DefaultPolicyActionInfo.cs	(revision 11732)
@@ -0,0 +1,40 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // stores information that is relevant for most of the policies
+  public class DefaultPolicyActionInfo : IPolicyActionInfo {
+    public bool Disabled { get { return Tries == -1; } }
+    public double SumReward { get; private set; }
+    public double MaxReward { get; private set; }
+    public int Tries { get; private set; }
+
+    public DefaultPolicyActionInfo() {
+      MaxReward = double.NegativeInfinity;
+    }
+
+    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);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EmptyPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EmptyPolicyActionInfo.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EmptyPolicyActionInfo.cs	(revision 11732)
@@ -0,0 +1,18 @@
+﻿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 EmptyPolicyActionInfo : IPolicyActionInfo {
+    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/Policies/EpsGreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11732)
@@ -7,32 +7,33 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class EpsGreedyPolicy : BanditPolicy {
-    private readonly Random random;
+  public class EpsGreedyPolicy : IPolicy {
     private readonly double eps;
-    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;
+    public EpsGreedyPolicy(double eps) {
       this.eps = eps;
-      this.randomPolicy = new RandomPolicy(random, numActions);
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
+      this.randomPolicy = new RandomPolicy();
     }
-
-    public override int SelectAction() {
-      Debug.Assert(Actions.Any());
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
       if (random.NextDouble() > eps) {
         // select best
-        var bestQ = double.NegativeInfinity;
+        var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
         int bestAction = -1;
-        foreach (var a in Actions) {
-          if (tries[a] == 0) return a;
-          var q = sumReward[a] / tries[a];
-          if (bestQ < q) {
+        double bestQ = double.NegativeInfinity;
+        int aIdx = -1;
+        foreach (var aInfo in myActionInfos) {
+
+          aIdx++;
+          if (aInfo.Disabled) continue;
+          if (aInfo.Tries == 0) return aIdx;
+
+
+          var avgReward = aInfo.SumReward / aInfo.Tries;         
+          //var q = avgReward;
+          var q = aInfo.MaxReward;
+          if (q > bestQ) {
             bestQ = q;
-            bestAction = a;
+            bestAction = aIdx;
           }
         }
@@ -41,38 +42,13 @@
       } else {
         // select random
-        return randomPolicy.SelectAction();
+        return randomPolicy.SelectAction(random, actionInfos);
       }
     }
-    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 IPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
     }
 
-    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);
-    }
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write(" {0,5:F2} {1}", sumReward[i] / tries[i], tries[i]);
-        } else {
-          Console.Write("-", "");
-        }
-      }
-      Console.WriteLine();
-    }
     public override string ToString() {
       return string.Format("EpsGreedyPolicy({0:F2})", eps);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11732)
@@ -1,3 +1,4 @@
 ﻿using System;
+using System.Collections.Generic;
 using System.Diagnostics;
 using System.Linq;
@@ -5,10 +6,6 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  
-  public class GaussianThompsonSamplingPolicy : BanditPolicy {
-    private readonly Random random;
-    private readonly double[] sampleMean;
-    private readonly double[] sampleM2;
-    private readonly int[] tries;
+
+  public class GaussianThompsonSamplingPolicy : IPolicy {
     private bool compatibility;
 
@@ -21,25 +18,27 @@
 
 
-    public GaussianThompsonSamplingPolicy(Random random, int numActions, bool compatibility = false)
-      : base(numActions) {
-      this.random = random;
-      this.sampleMean = new double[numActions];
-      this.sampleM2 = new double[numActions];
-      this.tries = new int[numActions];
+    public GaussianThompsonSamplingPolicy(bool compatibility = false) {
       this.compatibility = compatibility;
     }
 
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
 
-    public override int SelectAction() {
-      Debug.Assert(Actions.Any());
-      var maxTheta = double.NegativeInfinity;
-      int bestAction = -1;
-      foreach (var a in Actions) {
-        if(tries[a] == -1) continue; // skip disabled actions
+      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) {
-          if (tries[a] < 2) return a;
-          var mu = sampleMean[a];
-          var variance = sampleM2[a] / tries[a];
+          if (tries < 2) return aIdx;
+          var mu = sampleMean;
+          var variance = sampleVariance;
           var stdDev = Math.Sqrt(variance);
           theta = Rand.RandNormal(random) * stdDev + mu;
@@ -48,6 +47,6 @@
 
           // see Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution (http://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf)
-          var posteriorVariance = 1.0 / (tries[a] / rewardVariance + 1.0 / priorVariance);
-          var posteriorMean = posteriorVariance * (priorMean / priorVariance + tries[a] * sampleMean[a] / rewardVariance);
+          var posteriorVariance = 1.0 / (tries / rewardVariance + 1.0 / priorVariance);
+          var posteriorMean = posteriorVariance * (priorMean / priorVariance + tries * sampleMean / rewardVariance);
 
           // sample a mean from the posterior 
@@ -56,45 +55,27 @@
           // theta already represents the expected reward value => nothing else to do
         }
-        if (theta > maxTheta) {
-          maxTheta = theta;
-          bestAction = a;
+
+        if (theta > bestQ) {
+          bestQ = theta;
+          bestAction = aIdx;
         }
       }
-      Debug.Assert(Actions.Contains(bestAction));
+      Debug.Assert(bestAction > -1);
       return bestAction;
     }
 
-    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 IPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
     }
 
-    public override void DisableAction(int action) {
-      base.DisableAction(action);
-      sampleMean[action] = 0;
-      sampleM2[action] = 0;
-      tries[action] = -1;
-    }
 
-    public override void Reset() {
-      base.Reset();
-      Array.Clear(sampleMean, 0, sampleMean.Length);
-      Array.Clear(sampleM2, 0, sampleM2.Length);
-      Array.Clear(tries, 0, tries.Length);
-    }
+    //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 void PrintStats() {
-      for (int i = 0; i < sampleMean.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write(" {0,5:F2} {1}", sampleMean[i] / tries[i], tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
-    }
     public override string ToString() {
       return "GaussianThompsonSamplingPolicy";
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GenericThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GenericThompsonSamplingPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GenericThompsonSamplingPolicy.cs	(revision 11732)
@@ -8,47 +8,32 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class GenericThompsonSamplingPolicy : BanditPolicy {
-    private readonly Random random;
+  public class GenericThompsonSamplingPolicy : IPolicy {
     private readonly IModel model;
 
-    public GenericThompsonSamplingPolicy(Random random, int numActions, IModel model)
-      : base(numActions) {
-      this.random = random;
+    public GenericThompsonSamplingPolicy(IModel model) {
       this.model = model;
     }
 
-    public override int SelectAction() {
-      Debug.Assert(Actions.Any());
-      var maxR = double.NegativeInfinity;
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<ModelPolicyActionInfo>();
       int bestAction = -1;
-      var expRewards = model.SampleExpectedRewards(random);
-      foreach (var a in Actions) {
-        var r = expRewards[a];
-        if (r > maxR) {
-          maxR = r;
-          bestAction = a;
+      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 override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-
-      model.Update(action, reward);
-    }
-
-    public override void DisableAction(int action) {
-      base.DisableAction(action);
-      model.Disable(action);
-    }
-
-    public override void Reset() {
-      base.Reset();
-      model.Reset();
-    }
-
-    public override void PrintStats() {
-      model.PrintStats();
+    public IPolicyActionInfo CreateActionInfo() {
+      return new ModelPolicyActionInfo((IModel)model.Clone());
     }
 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/MeanAndVariancePolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/MeanAndVariancePolicyActionInfo.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/MeanAndVariancePolicyActionInfo.cs	(revision 11732)
@@ -0,0 +1,36 @@
+﻿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 MeanAndVariancePolicyActionInfo : IPolicyActionInfo {
+    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 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/Policies/ModelPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ModelPolicyActionInfo.cs	(revision 11732)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ModelPolicyActionInfo.cs	(revision 11732)
@@ -0,0 +1,41 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // uses a statistical model to sample and update posterior distribution p(Reward | Data)
+  public class ModelPolicyActionInfo : IPolicyActionInfo {
+    private readonly IModel model;
+    public bool Disabled { get { return Tries == -1; } }
+
+    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();
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11732)
@@ -8,25 +8,20 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class RandomPolicy : BanditPolicy {
-    private readonly Random random;
+  public class RandomPolicy : IPolicy {
 
-    public RandomPolicy(Random random, int numActions)
-      : base(numActions) {
-      this.random = random;
-    }
-
-    public override int SelectAction() {
-      Debug.Assert(Actions.Any());
-      return Actions.SelectRandom(random);
-    }
-    public override void UpdateReward(int action, double reward) {
-      // do nothing
-    }
-    public override void PrintStats() {
-      Console.WriteLine("Random");
-    }
     public override string ToString() {
       return "RandomPolicy";
     }
+
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      return actionInfos
+        .Select((a, i) => Tuple.Create(a, i))
+        .Where(p => !p.Item1.Disabled)
+        .SelectRandom(random).Item2;
+    }
+
+    public IPolicyActionInfo CreateActionInfo() {
+      return new EmptyPolicyActionInfo();
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11732)
@@ -7,20 +7,15 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class UCB1Policy : BanditPolicy {
-    private readonly int[] tries;
-    private readonly double[] sumReward;
-    private int totalTries = 0;
-    public UCB1Policy(int numActions)
-      : base(numActions) {
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
-    }
-
-    public override int SelectAction() {
+  public class UCB1Policy : IPolicy {
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>().ToArray(); // TODO: performance
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      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]);
+      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;
@@ -28,35 +23,10 @@
         }
       }
+      Debug.Assert(bestAction > -1);
       return bestAction;
     }
-    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);
-      Array.Clear(sumReward, 0, sumReward.Length);
-    }
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
+    public IPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
     }
     public override string ToString() {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11732)
@@ -7,29 +7,21 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class UCB1TunedPolicy : BanditPolicy {
-    private readonly int[] tries;
-    private readonly double[] sumReward;
-    private readonly double[] sumSqrReward;
-    private int totalTries = 0;
-    public UCB1TunedPolicy(int numActions)
-      : base(numActions) {
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
-      this.sumSqrReward = new double[numActions];
-    }
+  public class UCB1TunedPolicy : IPolicy {
 
-    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());
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>().ToArray(); // TODO: performance
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      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
+      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 sumReward = myActionInfos[a].SumReward;
+        var tries = myActionInfos[a].Tries;
+
+        var avgReward = sumReward / tries;
+        var q = avgReward + Math.Sqrt((Math.Log(totalTries) / tries) * Math.Min(1.0 / 4, V(myActionInfos[a], totalTries))); // 1/4 is upper bound of bernoulli distributed variable
         if (q > bestQ) {
           bestQ = q;
@@ -37,39 +29,17 @@
         }
       }
+      Debug.Assert(bestAction > -1);
       return bestAction;
     }
-    public override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-      totalTries++;
-      tries[action]++;
-      sumReward[action] += reward;
-      sumSqrReward[action] += reward * reward;
+
+    public IPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
     }
 
-    public override void DisableAction(int action) {
-      base.DisableAction(action);
-      totalTries -= tries[action];
-      tries[action] = -1;
-      sumReward[action] = 0;
-      sumSqrReward[action] = 0;
+    private double V(MeanAndVariancePolicyActionInfo actionInfo, int totalTries) {
+      var s = actionInfo.Tries;
+      return actionInfo.RewardVariance + Math.Sqrt(2 * Math.Log(totalTries) / s);
     }
 
-    public override void Reset() {
-      base.Reset();
-      totalTries = 0;
-      Array.Clear(tries, 0, tries.Length);
-      Array.Clear(sumReward, 0, sumReward.Length);
-      Array.Clear(sumSqrReward, 0, sumSqrReward.Length);
-    }
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
-    }
     public override string ToString() {
       return "UCB1TunedPolicy";
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11732)
@@ -7,24 +7,20 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  public class UCBNormalPolicy : BanditPolicy {
-    private readonly int[] tries;
-    private readonly double[] sumReward;
-    private readonly double[] sumSqrReward;
-    private int totalTries = 0;
-    public UCBNormalPolicy(int numActions)
-      : base(numActions) {
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
-      this.sumSqrReward = new double[numActions];
-    }
+  public class UCBNormalPolicy : IPolicy {
 
-    public override int SelectAction() {
-      Debug.Assert(Actions.Any());
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>().ToArray(); // TODO: performance
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      foreach (var a in Actions) {
-        if (totalTries <= 1 || tries[a] <= 1 || tries[a] <= Math.Ceiling(8 * Math.Log(totalTries))) return a;
-        var avgReward = sumReward[a] / tries[a];
-        var estVariance = 16 * ((sumSqrReward[a] - tries[a] * Math.Pow(avgReward, 2)) / (tries[a] - 1)) * (Math.Log(totalTries - 1) / tries[a]);
+      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 (totalTries <= 1 || myActionInfos[a].Tries <= 1 || myActionInfos[a].Tries <= Math.Ceiling(8 * Math.Log(totalTries))) return a;
+
+        var tries = myActionInfos[a].Tries;
+        var avgReward = myActionInfos[a].AvgReward;
+        var rewardVariance = myActionInfos[a].RewardVariance;
+        var estVariance = 16 * rewardVariance * (Math.Log(totalTries - 1) / tries);
         if (estVariance < 0) estVariance = 0; // numerical problems
         var q = avgReward
@@ -35,40 +31,12 @@
         }
       }
-      Debug.Assert(Actions.Contains(bestAction));
+      Debug.Assert(bestAction > -1);
       return bestAction;
     }
-    public override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-      totalTries++;
-      tries[action]++;
-      sumReward[action] += reward;
-      sumSqrReward[action] += reward * reward;
+
+    public IPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
     }
 
-    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);
-      Array.Clear(sumReward, 0, sumReward.Length);
-      Array.Clear(sumSqrReward, 0, sumSqrReward.Length);
-    }
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
-    }
     public override string ToString() {
       return "UCBNormalPolicy";
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCTPolicy.cs	(revision 11731)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCTPolicy.cs	(revision 11732)
@@ -8,23 +8,22 @@
 namespace HeuristicLab.Algorithms.Bandits {
   /* Kocsis et al. Bandit based Monte-Carlo Planning */
-  public class UCTPolicy : BanditPolicy {
-    private readonly int[] tries;
-    private readonly double[] sumReward;
-    private int totalTries = 0;
+  public class UCTPolicy : IPolicy {
     private readonly double c;
 
-    public UCTPolicy(int numActions, double c = 1.0)
-      : base(numActions) {
-      this.tries = new int[numActions];
-      this.sumReward = new double[numActions];
+    public UCTPolicy(double c = 1.0) {
       this.c = c;
     }
 
-    public override int SelectAction() {
+
+    public int SelectAction(Random random, IEnumerable<IPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>().ToArray(); // TODO: performance
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      foreach (var a in Actions) {
-        if (tries[a] == 0) return a;
-        var q = sumReward[a] / tries[a] + 2 * c * Math.Sqrt(Math.Log(totalTries) / tries[a]);
+      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 + 2 * c * Math.Sqrt(Math.Log(totalTries) / myActionInfos[a].Tries);
         if (q > bestQ) {
           bestQ = q;
@@ -32,36 +31,12 @@
         }
       }
+      Debug.Assert(bestAction > -1);
       return bestAction;
     }
-    public override void UpdateReward(int action, double reward) {
-      Debug.Assert(Actions.Contains(action));
-      totalTries++;
-      tries[action]++;
-      sumReward[action] += reward;
+
+    public IPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
     }
 
-    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);
-      Array.Clear(sumReward, 0, sumReward.Length);
-    }
-    public override void PrintStats() {
-      for (int i = 0; i < sumReward.Length; i++) {
-        if (tries[i] >= 0) {
-          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
-        } else {
-          Console.Write("{0,5}", "");
-        }
-      }
-      Console.WriteLine();
-    }
     public override string ToString() {
       return string.Format("UCTPolicy({0:F2})", c);
