Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11848)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11849)
@@ -17,4 +17,8 @@
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.GeneticProgramming", "HeuristicLab.Algorithms.GeneticProgramming\HeuristicLab.Algorithms.GeneticProgramming.csproj", "{14BEC23F-63FD-4954-B8AE-E2F4962E9B57}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Distributions", "HeuristicLab.Distributions\HeuristicLab.Distributions.csproj", "{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Bandits", "HeuristicLab.Problems.Bandits\HeuristicLab.Problems.Bandits.csproj", "{E8138227-0C64-4E85-B676-21D3B97F254F}"
 EndProject
 Global
@@ -56,4 +60,12 @@
 		{14BEC23F-63FD-4954-B8AE-E2F4962E9B57}.Release|Any CPU.ActiveCfg = Release|Any CPU
 		{14BEC23F-63FD-4954-B8AE-E2F4962E9B57}.Release|Any CPU.Build.0 = Release|Any CPU
+		{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}.Release|Any CPU.Build.0 = Release|Any CPU
+		{E8138227-0C64-4E85-B676-21D3B97F254F}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{E8138227-0C64-4E85-B676-21D3B97F254F}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{E8138227-0C64-4E85-B676-21D3B97F254F}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{E8138227-0C64-4E85-B676-21D3B97F254F}.Release|Any CPU.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/BernoulliPolicyActionInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/BernoulliPolicyActionInfo.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/BernoulliPolicyActionInfo.cs	(revision 11849)
@@ -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.BanditPolicies {
+  public class BernoulliPolicyActionInfo : IBanditPolicyActionInfo {
+    public int NumSuccess { get; private set; }
+    public int NumFailure { get; private set; }
+    public int Tries { get { return NumSuccess + NumFailure; } }
+    public double Value {
+      get {
+        return NumSuccess / (double)(Tries);
+      }
+    }
+    public void UpdateReward(double reward) {
+      //Debug.Assert(reward.IsAlmost(0.0) || reward.IsAlmost(1.0));
+
+      //if (reward.IsAlmost(1.0)) NumSuccess++;
+      if (reward > 0) NumSuccess++;
+      else NumFailure++;
+    }
+    public void Reset() {
+      NumSuccess = 0;
+      NumFailure = 0;
+    }
+    public void PrintStats() {
+      Console.WriteLine("expected value {0,5:F2}", Value);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs	(revision 11849)
@@ -0,0 +1,48 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // stores information that is relevant for most of the policies
+  public class DefaultPolicyActionInfo : IBanditPolicyActionInfo {
+    public double SumReward { get; private set; }
+    public int Tries { get; private set; }
+    public double MaxReward { get; private set; }
+    public double Value {
+      get {
+        return Tries > 0 ? SumReward / Tries : 0.0;
+      }
+    }
+    public DefaultPolicyActionInfo() {
+      MaxReward = 0.0;
+    }
+
+    public void UpdateReward(double reward) {
+      Tries++;
+      SumReward += reward;
+      MaxReward = Math.Max(MaxReward, reward);
+    }
+
+    public void Reset() {
+      SumReward = 0.0;
+      Tries = 0;
+      MaxReward = 0.0;
+    }
+
+    public override string ToString() {
+      return string.Format("{0:F3} {1:F3} {2}", Value, MaxReward, Tries);
+    }
+
+    public static Func<DefaultPolicyActionInfo, double> AverageReward {
+      get {
+        return (aInfo) =>
+          aInfo.Tries == 0 ?
+          double.PositiveInfinity :
+          aInfo.SumReward / (double)aInfo.Tries;
+      }
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/MeanAndVariancePolicyActionInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/MeanAndVariancePolicyActionInfo.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/MeanAndVariancePolicyActionInfo.cs	(revision 11849)
@@ -0,0 +1,29 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class MeanAndVariancePolicyActionInfo : IBanditPolicyActionInfo {
+    private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
+    public int Tries { get { return estimator.N; } }
+    public double SumReward { get { return estimator.Sum; } }
+    public double AvgReward { get { return estimator.Avg; } }
+    public double RewardVariance { get { return estimator.Variance; } }
+    public double Value {
+      get {
+        return AvgReward;
+      }
+    }
+
+    public void UpdateReward(double reward) {
+      estimator.UpdateReward(reward);
+    }
+
+    public void Reset() {
+      estimator.Reset();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/ModelPolicyActionInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/ModelPolicyActionInfo.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/ActionInfos/ModelPolicyActionInfo.cs	(revision 11849)
@@ -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.BanditPolicies {
+  // uses a statistical model to sample and update posterior distribution p(Reward | Data)
+  public class ModelPolicyActionInfo : IBanditPolicyActionInfo {
+    private readonly IModel model;
+    public double Value {
+      get {
+        return model.SampleExpectedReward(new Random());
+      }
+    }
+
+    public int Tries { get; private set; }
+    public ModelPolicyActionInfo(IModel model) {
+      this.model = model;
+    }
+
+    public void UpdateReward(double reward) {
+      Tries++;
+      model.Update(reward);
+    }
+
+    public double SampleExpectedReward(Random random) {
+      return model.SampleExpectedReward(random);
+    }
+
+    public void Reset() {
+      Tries = 0;
+      model.Reset();
+    }
+
+    public override string ToString() {
+      return string.Format("model {1}", model);
+    }
+  }
+}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditHelper.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditHelper.cs	(revision 11848)
+++ 	(revision )
@@ -1,37 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.Bandits {
-  class BanditHelper {
-    public static void SampleArms(Random random, IBandit bandit, int nSamples, out double expRewardEst, out int bestArmForExpReward, out int bestArmForMaxReward) {
-      bestArmForExpReward = 0;
-      bestArmForMaxReward = 0;
-      expRewardEst = 0.0;
-      var bestSumReward = 0.0;
-      var bestUpperPercCount = 0;
-      for (int a = 0; a < bandit.NumArms; a++) {
-        var sumReward = 0.0;
-        var upperPercCount = 0;
-
-        for (int i = 0; i < nSamples; i++) {
-          var reward = bandit.Pull(a);
-          sumReward += reward;
-          if (reward >= 0.95) upperPercCount++;
-        }
-
-        if (sumReward > bestSumReward) {
-          bestSumReward = sumReward;
-          bestArmForExpReward = a;
-          expRewardEst = bestSumReward / nSamples;
-        }
-        if (upperPercCount > bestUpperPercCount) {
-          bestUpperPercCount = upperPercCount;
-          bestArmForMaxReward = a;
-        }
-      }
-    }
-  }
-}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11848)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11849)
@@ -38,28 +38,8 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="BanditHelper.cs" />
-    <Compile Include="BanditPolicies\BernoulliPolicyActionInfo.cs" />
-    <Compile Include="BanditPolicies\BernoulliThompsonSamplingPolicy.cs" />
-    <Compile Include="BanditPolicies\BoltzmannExplorationPolicy.cs" />
-    <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
-    <Compile Include="BanditPolicies\ActiveLearningPolicy.cs" />
-    <Compile Include="BanditPolicies\ModifiedUCTPolicy.cs" />
-    <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
-    <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />
-    <Compile Include="BanditPolicies\GaussianThompsonSamplingPolicy.cs" />
-    <Compile Include="BanditPolicies\GenericThompsonSamplingPolicy.cs" />
-    <Compile Include="BanditPolicies\MeanAndVariancePolicyActionInfo.cs" />
-    <Compile Include="BanditPolicies\ModelPolicyActionInfo.cs" />
-    <Compile Include="BanditPolicies\RandomPolicy.cs" />
-    <Compile Include="BanditPolicies\ThresholdAscentPolicy.cs" />
-    <Compile Include="BanditPolicies\UCB1Policy.cs" />
-    <Compile Include="BanditPolicies\UCB1TunedPolicy.cs" />
-    <Compile Include="BanditPolicies\UCBNormalPolicy.cs" />
-    <Compile Include="BanditPolicies\UCTPolicy.cs" />
-    <Compile Include="Bandits\BernoulliBandit.cs" />
-    <Compile Include="Bandits\GaussianBandit.cs" />
-    <Compile Include="Bandits\GaussianMixtureBandit.cs" />
-    <Compile Include="Bandits\IBandit.cs" />
-    <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="ActionInfos\BernoulliPolicyActionInfo.cs" />
+    <Compile Include="ActionInfos\DefaultPolicyActionInfo.cs" />
+    <Compile Include="ActionInfos\MeanAndVariancePolicyActionInfo.cs" />
+    <Compile Include="ActionInfos\ModelPolicyActionInfo.cs" />
     <Compile Include="GrammarPolicies\GenericFunctionApproximationGrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericContextualGrammarPolicy.cs" />
@@ -76,10 +56,18 @@
     <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" />
-    <Compile Include="Models\GaussianModel.cs" />
-    <Compile Include="Models\IModel.cs" />
+    <Compile Include="Policies\ActiveLearningPolicy.cs" />
+    <Compile Include="Policies\BernoulliThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\BoltzmannExplorationPolicy.cs" />
+    <Compile Include="Policies\ChernoffIntervalEstimationPolicy.cs" />
+    <Compile Include="Policies\EpsGreedyPolicy.cs" />
+    <Compile Include="Policies\GaussianThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\GenericThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\ModifiedUCTPolicy.cs" />
+    <Compile Include="Policies\RandomPolicy.cs" />
+    <Compile Include="Policies\ThresholdAscentPolicy.cs" />
+    <Compile Include="Policies\UCB1Policy.cs" />
+    <Compile Include="Policies\UCB1TunedPolicy.cs" />
+    <Compile Include="Policies\UCBNormalPolicy.cs" />
+    <Compile Include="Policies\UCTPolicy.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
@@ -88,4 +76,8 @@
       <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
       <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Distributions\HeuristicLab.Distributions.csproj">
+      <Project>{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}</Project>
+      <Name>HeuristicLab.Distributions</Name>
     </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/OnlineMeanAndVarianceEstimator.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/OnlineMeanAndVarianceEstimator.cs	(revision 11848)
+++ 	(revision )
@@ -1,32 +1,0 @@
-﻿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/ActiveLearningPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs	(revision 11849)
@@ -0,0 +1,54 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class ActiveLearningPolicy : IBanditPolicy {
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+      const double delta = 0.1;
+      int k = myActionInfos.Count();
+      var bestActions = new List<int>();
+      var us = new List<double>();
+      var ls = new List<double>();
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        double u;
+        double l;
+        if (aInfo.Tries == 0) {
+          u = double.PositiveInfinity;
+          l = double.NegativeInfinity;
+        } else {
+          q = aInfo.SumReward / aInfo.Tries;
+          var b = Math.Sqrt(Math.Log(2.0 * k * totalTries / delta) / (2.0 * aInfo.Tries));
+          u = q + 0.5 * b;
+          l = q - 0.5 * b;
+        }
+        bestActions.Add(aIdx);
+        us.Add(u);
+        ls.Add(l);
+      }
+      var active = new List<int>();
+      var maxL = ls.Max();
+      for (int i = 0; i < us.Count; i++) {
+        if (us[i] >= maxL) active.Add(bestActions[i]);
+      }
+      Debug.Assert(active.Any());
+      return active.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+    public override string ToString() {
+      return "ActiveLearningPolicy";
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11849)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class BernoulliThompsonSamplingPolicy : IBanditPolicy {
+    // parameters of beta prior distribution
+    private readonly double alpha = 1.0;
+    private readonly double beta = 1.0;
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<BernoulliPolicyActionInfo>();
+      int bestAction = -1;
+      double maxTheta = double.NegativeInfinity;
+      var aIdx = -1;
+
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        var theta = Rand.BetaRand(random, aInfo.NumSuccess + alpha, aInfo.NumFailure + beta);
+        if (theta > maxTheta) {
+          maxTheta = theta;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new BernoulliPolicyActionInfo();
+    }
+
+
+    public override string ToString() {
+      return "BernoulliThompsonSamplingPolicy";
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BoltzmannExplorationPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BoltzmannExplorationPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BoltzmannExplorationPolicy.cs	(revision 11849)
@@ -0,0 +1,54 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // also called softmax policy
+  public class BoltzmannExplorationPolicy : IBanditPolicy {
+    private readonly double beta;
+    private readonly Func<DefaultPolicyActionInfo, double> valueFunction;
+
+    public BoltzmannExplorationPolicy(double beta) : this(beta, DefaultPolicyActionInfo.AverageReward) { }
+
+    public BoltzmannExplorationPolicy(double beta, Func<DefaultPolicyActionInfo, double> valueFunction) {
+      if (beta < 0) throw new ArgumentException();
+      this.beta = beta;
+      this.valueFunction = valueFunction;
+    }
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+
+      // select best
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+
+      // try any of the untries actions randomly
+      // for RoyalSequence it is much better to select the actions in the order of occurrence (all terminal alternatives first)
+      //if (myActionInfos.Any(aInfo => !aInfo.Disabled && aInfo.Tries == 0)) {
+      //  return myActionInfos
+      //  .Select((aInfo, idx) => new { aInfo, idx })
+      //  .Where(p => !p.aInfo.Disabled)
+      //  .Where(p => p.aInfo.Tries == 0)
+      //  .SelectRandom(random).idx;
+      //}
+
+      var w = from aInfo in myActionInfos
+              select Math.Exp(beta * valueFunction(aInfo));
+
+      var bestAction = Enumerable.Range(0, myActionInfos.Count()).SampleProportional(random, w);
+      Debug.Assert(bestAction >= 0);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("BoltzmannExplorationPolicy({0:F2})", beta);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs	(revision 11849)
@@ -0,0 +1,63 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* see: Streeter and Smith: A simple distribution-free approach to the max k-armed bandit problem, Proceedings  of the 12th
+International Conference, CP 2006, Nantes, France, September 25-29, 2006. pp 560-574 */
+
+  public class ChernoffIntervalEstimationPolicy : IBanditPolicy {
+    private readonly double delta;
+
+    public ChernoffIntervalEstimationPolicy(double delta = 0.01) {
+      this.delta = delta;
+    }
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      // select best
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      int k = myActionInfos.Count();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+      double bestQ = double.NegativeInfinity;
+      var bestActions = new List<int>();
+      var aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+
+          var avgReward = aInfo.SumReward / aInfo.Tries;
+
+          // page 5 of "A simple distribution-free appraoch to the max k-armed bandit problem"
+          // var alpha = Math.Log(2 * totalTries * k / delta);
+          double alpha = Math.Log(2.0) + Math.Log(totalTries) + Math.Log(k) - Math.Log(delta);
+          // total tries is max tries in the original paper
+          q = avgReward + (alpha + Math.Sqrt(2 * aInfo.Tries * avgReward * alpha + alpha * alpha)) / aInfo.Tries;
+        }
+        if (q > bestQ) {
+          bestQ = q;
+          bestActions.Clear();
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ChernoffIntervalEstimationPolicy({0:F2})", delta);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11849)
@@ -0,0 +1,65 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class EpsGreedyPolicy : IBanditPolicy {
+    private readonly double eps;
+    private readonly RandomPolicy randomPolicy;
+    private readonly Func<DefaultPolicyActionInfo, double> valueFunction;
+    private readonly string desc;
+
+
+    public EpsGreedyPolicy(double eps) : this(eps, DefaultPolicyActionInfo.AverageReward, string.Empty) { }
+
+    public EpsGreedyPolicy(double eps, Func<DefaultPolicyActionInfo, double> valueFunction, string desc) {
+      this.eps = eps;
+      this.randomPolicy = new RandomPolicy();
+      this.valueFunction = valueFunction;
+      this.desc = desc;
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      if (random.NextDouble() >= eps) { // eps == 0 should be equivalent to pure exploitation, eps == 1 is pure exploration
+        // select best
+        var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+        var bestActions = new List<int>();
+        double bestQ = double.NegativeInfinity;
+
+        int aIdx = -1;
+        foreach (var aInfo in myActionInfos) {
+          aIdx++;
+
+          var q = valueFunction(aInfo);
+
+          if (q > bestQ) {
+            bestActions.Clear();
+            bestActions.Add(aIdx);
+            bestQ = q;
+          } else if (q.IsAlmost(bestQ)) {
+            bestActions.Add(aIdx);
+          }
+        }
+        Debug.Assert(bestActions.Any());
+        return bestActions.SelectRandom(random);
+      } else {
+        // select random
+        return randomPolicy.SelectAction(random, actionInfos);
+      }
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+
+    public override string ToString() {
+      return string.Format("EpsGreedyPolicy({0:F2},{1})", eps, desc);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11849)
@@ -0,0 +1,85 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+
+  [Obsolete("Replaced by GenericThompsonSamplingPolicy(GaussianModel(0.5, 1.0, 0.1))")]
+  public class GaussianThompsonSamplingPolicy : IBanditPolicy {
+    private bool compatibility;
+
+    // assumes a Gaussian reward distribution with different means but the same variances for each action
+    // the prior for the mean is also Gaussian with the following parameters
+    private readonly double rewardVariance = 0.1; // we assume a known variance 
+
+    private readonly double priorMean = 0.5;
+    private readonly double priorVariance = 1;
+
+
+    public GaussianThompsonSamplingPolicy(bool compatibility = false) {
+      this.compatibility = compatibility;
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+
+        var tries = aInfo.Tries;
+        var sampleMean = aInfo.AvgReward;
+        var sampleVariance = aInfo.RewardVariance;
+
+        double theta;
+        if (compatibility) {
+          // old code used for old experiments (preserved because it performed very well)
+          if (tries < 2) return aIdx;
+          var mu = sampleMean;
+          var variance = sampleVariance;
+          var stdDev = Math.Sqrt(variance);
+          theta = Rand.RandNormal(random) * stdDev + mu;
+        } else {
+          // calculate posterior mean and variance (for mean reward)
+
+          // see Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution (http://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf)
+          var posteriorVariance = 1.0 / (tries / rewardVariance + 1.0 / priorVariance);
+          var posteriorMean = posteriorVariance * (priorMean / priorVariance + tries * sampleMean / rewardVariance);
+
+          // sample a mean from the posterior 
+          theta = Rand.RandNormal(random) * Math.Sqrt(posteriorVariance) + posteriorMean;
+
+          // theta already represents the expected reward value => nothing else to do
+        }
+
+        if (theta > bestQ) {
+          bestQ = theta;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
+    }
+
+
+    //public override void UpdateReward(int action, double reward) {
+    //  Debug.Assert(Actions.Contains(action));
+    //  tries[action]++;
+    //  var delta = reward - sampleMean[action];
+    //  sampleMean[action] += delta / tries[action];
+    //  sampleM2[action] += sampleM2[action] + delta * (reward - sampleMean[action]);
+    //}
+
+    public override string ToString() {
+      return "GaussianThompsonSamplingPolicy";
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GenericThompsonSamplingPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GenericThompsonSamplingPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GenericThompsonSamplingPolicy.cs	(revision 11849)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class GenericThompsonSamplingPolicy : IBanditPolicy {
+    private readonly IModel model;
+
+    public GenericThompsonSamplingPolicy(IModel model) {
+      this.model = model;
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<ModelPolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      var aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        var q = aInfo.SampleExpectedReward(random);
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = aIdx;
+        }
+      }
+      Debug.Assert(bestAction > -1);
+      return bestAction;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new ModelPolicyActionInfo((IModel)model.Clone());
+    }
+
+    public override string ToString() {
+      return string.Format("GenericThompsonSamplingPolicy({0})", model);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ModifiedUCTPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ModifiedUCTPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ModifiedUCTPolicy.cs	(revision 11849)
@@ -0,0 +1,55 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* modified UCT: see Coquelin & Munos, Bandit Algorithms for Tree Search, UAI 2007 */
+  public class ModifiedUCTPolicy : IBanditPolicy {
+    private readonly double c;
+
+    public ModifiedUCTPolicy(double c = 1.0) {
+      this.c = c;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+
+      int aIdx = -1;
+      var bestActions = new List<int>();
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          q = aInfo.SumReward / aInfo.Tries + c * Math.Sqrt(Math.Sqrt(totalTries) / aInfo.Tries); // modification in comparison to original UCT
+        }
+        if (q > bestQ) {
+          bestActions.Clear();
+          bestQ = q;
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ModifiedUCTPolicy({0:F2})", c);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11849)
@@ -0,0 +1,26 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class RandomPolicy : IBanditPolicy {
+
+    public override string ToString() {
+      return "RandomPolicy";
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      return actionInfos
+        .Select((aInfo, idx) => Tuple.Create(aInfo, idx))
+        .SelectRandom(random).Item2;
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ThresholdAscentPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ThresholdAscentPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ThresholdAscentPolicy.cs	(revision 11849)
@@ -0,0 +1,131 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* see: Streeter and Smith: A simple distribution-free approach to the max k-armed bandit problem, Proceedings  of the 12th
+ International Conference, CP 2006, Nantes, France, September 25-29, 2006. pp 560-574 */
+
+  public class ThresholdAscentPolicy : IBanditPolicy {
+    public const int numBins = 101;
+    public const double binSize = 1.0 / (numBins - 1);
+
+    private class ThresholdAscentActionInfo : IBanditPolicyActionInfo {
+
+      // for each arm store the number of observed rewards for each bin of size delta
+      // for delta = 0.01 we have 101 bins
+      // the first bin is freq of rewards  >= 0 // all
+      // the second bin is freq of rewards > 0
+      // the third bin is freq of rewards > 0.01
+      // the last bin is for rewards > 0.99
+      // 
+      // (also see RewardBin function)
+      public int[] rewardHistogram = new int[numBins];    // for performance reasons we store cumulative counts (freq of rewards > lower threshold)
+      public int Tries { get; private set; }
+      public int thresholdBin = 1;
+
+      public double Value {
+        get {
+          if (Tries == 0.0) return 0.0;
+          return rewardHistogram[thresholdBin] / (double)Tries;
+        }
+      }
+
+      public void UpdateReward(double reward) {
+        Tries++;
+        for (var idx = thresholdBin; idx <= RewardBin(reward); idx++)
+          rewardHistogram[idx]++;
+      }
+
+      public void Reset() {
+        Tries = 0;
+        thresholdBin = 1;
+        Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
+      }
+
+      // maps a reward value to it's bin
+      private static int RewardBin(double reward) {
+        Debug.Assert(reward >= 0 && reward <= 1.0);
+        // reward = 0 => 0
+        // ]0.00 .. 0.01] => 1
+        // ]0.01 .. 0.02] => 2
+        // ...
+        // ]0.99 .. 1.00] => 100
+        if (reward <= 0) return 0;
+        return (int)Math.Ceiling((reward / binSize));
+      }
+    }
+
+    private readonly int s;
+    private readonly double delta;
+
+    public ThresholdAscentPolicy(int s = 100, double delta = 0.05) {
+      this.s = s;
+      this.delta = delta;
+    }
+
+    private double U(double mu, 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);
+      return mu + (alpha + Math.Sqrt(2 * n * mu * alpha + alpha * alpha)) / n;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      Debug.Assert(actionInfos.Any());
+      var myActionInfos = actionInfos.OfType<ThresholdAscentActionInfo>();
+      UpdateThreshold(myActionInfos);
+
+      var bestActions = new List<int>();
+      double bestQ = double.NegativeInfinity;
+      int k = myActionInfos.Count();
+      var totalTries = myActionInfos.Sum(a => a.Tries);
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          double mu = aInfo.Value; // probability of rewards > T 
+          q = U(mu, totalTries, aInfo.Tries, k); // totalTries is max iterations in original paper
+        }
+        if (q > bestQ) {
+          bestQ = q;
+          bestActions.Clear();
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+
+    private void UpdateThreshold(IEnumerable<ThresholdAscentActionInfo> actionInfos) {
+      var thresholdBin = 1; // first bin to check is bin idx 1 == freq of rewards > 0
+      while (thresholdBin < (numBins - 1) && actionInfos.Sum(a => a.rewardHistogram[thresholdBin]) >= s) {
+        thresholdBin++;
+        // Console.WriteLine("New threshold {0:F2}", T);
+      }
+      foreach (var aInfo in actionInfos) {
+        aInfo.thresholdBin = thresholdBin;
+      }
+    }
+
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new ThresholdAscentActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ThresholdAscentPolicy({0},{1:F2})", s, delta);
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11849)
@@ -0,0 +1,47 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // policy for k-armed bandit (see Auer et al. 2002)
+  public class UCB1Policy : IBanditPolicy {
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+
+      var bestActions = new List<int>();
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+
+          q = aInfo.SumReward / aInfo.Tries + 0.5 * Math.Sqrt((2 * Math.Log(totalTries)) / aInfo.Tries);
+        }
+        if (q > bestQ) {
+          bestQ = q;
+          bestActions.Clear();
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+    public override string ToString() {
+      return "UCB1Policy";
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11849)
@@ -0,0 +1,60 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  // policy for k-armed bandit (see Auer et al. 2002)
+  public class UCB1TunedPolicy : IBanditPolicy {
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+
+      int aIdx = -1;
+      double bestQ = double.NegativeInfinity;
+      var bestActions = new List<int>();
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          var sumReward = aInfo.SumReward;
+          var tries = aInfo.Tries;
+
+          var avgReward = sumReward / tries;
+          q = avgReward + Math.Sqrt((Math.Log(totalTries) / tries) * Math.Min(1.0 / 4, V(aInfo, totalTries)));
+          // 1/4 is upper bound of bernoulli distributed variable
+        }
+        if (q > bestQ) {
+          bestQ = q;
+          bestActions.Clear();
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+      }
+      Debug.Assert(bestActions.Any());
+
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
+    }
+
+    private double V(MeanAndVariancePolicyActionInfo actionInfo, int totalTries) {
+      var s = actionInfo.Tries;
+      return actionInfo.RewardVariance + Math.Sqrt(2 * Math.Log(totalTries) / s);
+    }
+
+    public override string ToString() {
+      return "UCB1TunedPolicy";
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11849)
@@ -0,0 +1,50 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  public class UCBNormalPolicy : IBanditPolicy {
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+      double bestQ = double.NegativeInfinity;
+      int aIdx = -1;
+      var bestActions = new List<int>();
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (totalTries <= 1 || aInfo.Tries <= 1 || aInfo.Tries <= Math.Ceiling(8 * Math.Log(totalTries))) {
+          q = double.PositiveInfinity;
+        } else {
+          var tries = aInfo.Tries;
+          var avgReward = aInfo.AvgReward;
+          var rewardVariance = aInfo.RewardVariance;
+          var estVariance = 16.0 * rewardVariance * (Math.Log(totalTries - 1) / tries);
+          q = avgReward + Math.Sqrt(estVariance);
+        }
+        if (q > bestQ) {
+          bestQ = q;
+          bestActions.Clear();
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new MeanAndVariancePolicyActionInfo();
+    }
+
+    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 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCTPolicy.cs	(revision 11849)
@@ -0,0 +1,56 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* Kocsis et al. Bandit based Monte-Carlo Planning */
+  public class UCTPolicy : IBanditPolicy {
+    private readonly double c;
+
+    public UCTPolicy(double c = 1.0) {
+      this.c = c;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+
+      int aIdx = -1;
+      var bestActions = new List<int>();
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          q = aInfo.SumReward / aInfo.Tries + 2.0 * c * Math.Sqrt(Math.Log(totalTries) / aInfo.Tries);
+        }
+        if (q > bestQ) {
+          bestActions.Clear();
+          bestQ = q;
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("UCTPolicy({0:F2})", c);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 11848)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 11849)
@@ -38,4 +38,5 @@
     <Compile Include="Extensions.cs" />
     <Compile Include="MostRecentlyUsedCache.cs" />
+    <Compile Include="OnlineMeanAndVarianceEstimator.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="Rand.cs" />
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/OnlineMeanAndVarianceEstimator.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/OnlineMeanAndVarianceEstimator.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/OnlineMeanAndVarianceEstimator.cs	(revision 11849)
@@ -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 {
+  public 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.Distributions/BernoulliModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/BernoulliModel.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/BernoulliModel.cs	(revision 11849)
@@ -0,0 +1,55 @@
+﻿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 {
+  public class BernoulliModel : IModel {
+
+    private int success;
+    private int failure;
+
+    // parameters of beta prior distribution
+    private readonly double alpha;
+    private readonly double beta;
+
+    public BernoulliModel(double alpha = 1.0, double beta = 1.0) {
+      this.alpha = alpha;
+      this.beta = beta;
+    }
+
+    public double SampleExpectedReward(Random random) {
+      // sample bernoulli mean from beta prior
+      return Rand.BetaRand(random, success + alpha, failure + beta);
+    }
+
+    public void Update(double reward) {
+      // Debug.Assert(reward.IsAlmost(1.0) || reward.IsAlmost(0.0));
+      if (reward > 0) {
+        success++;
+      } else {
+        failure++;
+      }
+    }
+
+    public void Reset() {
+      success = 0;
+      failure = 0;
+    }
+
+    public void PrintStats() {
+      Console.Write("{0:F2} ", success / (double)failure);
+    }
+
+    public object Clone() {
+      return new BernoulliModel() { failure = this.failure, success = this.success };
+    }
+
+    public override string ToString() {
+      return string.Format("Bernoulli with Beta prior: mu={0:F2}", (success + alpha) / (success + alpha + failure + beta));
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/GaussianMixtureModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/GaussianMixtureModel.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/GaussianMixtureModel.cs	(revision 11849)
@@ -0,0 +1,103 @@
+﻿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 {
+  public class GaussianMixtureModel : IModel {
+    private double[] componentMeans;
+    private double[] componentVars;
+    private double[] componentProbs;
+    private readonly List<double> allRewards = new List<double>();
+
+    private int numComponents;
+
+    public GaussianMixtureModel(int nComponents = 5) {
+      this.numComponents = nComponents;
+
+      Reset();
+    }
+
+
+    public double SampleExpectedReward(Random random) {
+      var k = Enumerable.Range(0, numComponents).SampleProportional(random, componentProbs);
+      return alglib.invnormaldistribution(random.NextDouble()) * Math.Sqrt(componentVars[k]) + componentMeans[k];
+    }
+
+    public void Update(double reward) {
+      allRewards.Add(reward);
+      throw new NotSupportedException("this does not yet work");
+      if (allRewards.Count < 1000 && allRewards.Count % 10 == 0) {
+        // see http://www.cs.toronto.edu/~mackay/itprnn/ps/302.320.pdf Algorithm 22.2 soft k-means
+        Reset();
+        for (int i = 0; i < 20; i++) {
+          var responsibilities = allRewards.Select(r => CalcResponsibility(r)).ToArray();
+
+
+          var sumWeightedRewards = new double[numComponents];
+          var sumResponsibilities = new double[numComponents];
+          foreach (var p in allRewards.Zip(responsibilities, Tuple.Create)) {
+            for (int k = 0; k < numComponents; k++) {
+              sumWeightedRewards[k] += p.Item2[k] * p.Item1;
+              sumResponsibilities[k] += p.Item2[k];
+            }
+          }
+          for (int k = 0; k < numComponents; k++) {
+            componentMeans[k] = sumWeightedRewards[k] / sumResponsibilities[k];
+          }
+
+          sumWeightedRewards = new double[numComponents];
+          foreach (var p in allRewards.Zip(responsibilities, Tuple.Create)) {
+            for (int k = 0; k < numComponents; k++) {
+              sumWeightedRewards[k] += p.Item2[k] * Math.Pow(p.Item1 - componentMeans[k], 2);
+            }
+          }
+          for (int k = 0; k < numComponents; k++) {
+            componentVars[k] = sumWeightedRewards[k] / sumResponsibilities[k];
+            componentProbs[k] = sumResponsibilities[k] / sumResponsibilities.Sum();
+          }
+        }
+      }
+    }
+
+    private double[] CalcResponsibility(double r) {
+      var res = new double[numComponents];
+      for (int k = 0; k < numComponents; k++) {
+        componentVars[k] = Math.Max(componentVars[k], 0.001);
+        res[k] = componentProbs[k] * alglib.normaldistribution((r - componentMeans[k]) / Math.Sqrt(componentVars[k]));
+        res[k] = Math.Max(res[k], 0.0001);
+      }
+      var sum = res.Sum();
+      for (int k = 0; k < numComponents; k++) {
+        res[k] /= sum;
+      }
+      return res;
+    }
+
+    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() {
+      var rand = new Random();
+      this.componentProbs = Enumerable.Range(0, numComponents).Select((_) => rand.NextDouble()).ToArray();
+      var sum = componentProbs.Sum();
+      for (int i = 0; i < componentProbs.Length; i++) componentProbs[i] /= sum;
+      this.componentMeans = Enumerable.Range(0, numComponents).Select((_) => Rand.RandNormal(rand)).ToArray();
+      this.componentVars = Enumerable.Range(0, numComponents).Select((_) => 0.01).ToArray();
+    }
+
+    public void PrintStats() {
+      throw new NotImplementedException();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/GaussianModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/GaussianModel.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/GaussianModel.cs	(revision 11849)
@@ -0,0 +1,149 @@
+﻿using System;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.Models {
+  // bayesian estimation of a Gaussian with 
+  // 1) unknown mean and known variance
+  // 2) unknown mean and unknown variance
+  public class GaussianModel : IModel {
+
+    private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
+
+    // parameters of Gaussian prior for mean
+    private readonly double meanPriorMu;
+    private readonly double meanPriorVariance;
+
+    private readonly bool knownVariance;
+    private readonly double rewardVariance = 0.1; // assumed know reward variance
+
+    // 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 SampleExpectedReward(Random random) {
+      if (knownVariance) {
+        return SampleExpectedRewardKnownVariance(random);
+      } else {
+        return SampleExpectedRewardUnknownVariance(random);
+      }
+    }
+
+    private double SampleExpectedRewardKnownVariance(Random random) {
+      // expected values for reward
+      // 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);
+
+      // 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;
+
+      // 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)) 
+
+      var t2alpha = alglib.invstudenttdistribution((int)(2 * posteriorAlpha), random.NextDouble());
+
+      var theta = t2alpha * posteriorBeta / (posteriorAlpha * posteriorK) + posteriorMean;
+      return theta;
+
+
+      /*
+       * value function : 0.99-quantile
+      // sample posterior mean and posterior variance independently
+      var sampledPrec = Rand.GammaRand(random, posteriorAlpha) * posteriorBeta;
+      var t2alpha = alglib.invstudenttdistribution((int)(2 * posteriorAlpha), random.NextDouble());
+      var sampledMean = t2alpha * posteriorBeta / (posteriorAlpha * posteriorK) + posteriorMean;
+
+      return alglib.invnormaldistribution(0.99) / Math.Sqrt(sampledPrec) + sampledMean;
+       */
+    }
+
+
+    public void Update(double reward) {
+      estimator.UpdateReward(reward);
+    }
+
+    public void Reset() {
+      estimator.Reset();
+    }
+
+    public void PrintStats() {
+      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);
+    }
+
+    public override string ToString() {
+      if (knownVariance) {
+        var posteriorMeanVariance = 1.0 / (estimator.N / rewardVariance + 1.0 / meanPriorVariance);
+        var posteriorMeanMean = posteriorMeanVariance * (meanPriorMu / meanPriorVariance + estimator.Sum / rewardVariance);
+        return string.Format("Gaussian(mu, var=0.1), mu ~ Gaussian(mu'={0:F3}, var'={1:F3})", posteriorMeanMean, posteriorMeanVariance);
+      } else {
+        var posteriorMean = (priorK * meanPriorMu + estimator.Sum) / (priorK + estimator.N);
+        var posteriorK = priorK + estimator.N;
+        var posteriorAlpha = precisionPriorAlpha + estimator.N / 2.0;
+        double posteriorBeta;
+        if (estimator.N > 0) {
+          posteriorBeta = precisionPriorBeta + 0.5 * estimator.N * estimator.Variance + priorK * estimator.N * Math.Pow(estimator.Avg - meanPriorMu, 2) / (2.0 * (priorK + estimator.N));
+        } else {
+          posteriorBeta = precisionPriorBeta;
+        }
+        var nu = (int)(2 * posteriorAlpha);
+        var meanVariance = posteriorBeta / (posteriorAlpha * posteriorK) * (nu / (double)(nu - 2));
+        return string.Format("Gaussian(mu, var), mu ~ T{0}(mu'={1:F3}, var'={2:F3}), 1.0/var ~ Gamma(mu={3:F3}, var={4:F3})",
+          nu, posteriorMean, meanVariance,
+          posteriorAlpha / posteriorBeta, posteriorAlpha / (posteriorBeta * posteriorBeta));
+      }
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/HeuristicLab.Distributions.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/HeuristicLab.Distributions.csproj	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/HeuristicLab.Distributions.csproj	(revision 11849)
@@ -0,0 +1,66 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Distributions</RootNamespace>
+    <AssemblyName>HeuristicLab.Distributions</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </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" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="BernoulliModel.cs" />
+    <Compile Include="GaussianMixtureModel.cs" />
+    <Compile Include="GaussianModel.cs" />
+    <Compile Include="IModel.cs" />
+    <Compile Include="LogitNormalModel.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+  </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. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/IModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/IModel.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/IModel.cs	(revision 11849)
@@ -0,0 +1,15 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // 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.Distributions/LogitNormalModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/LogitNormalModel.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/LogitNormalModel.cs	(revision 11849)
@@ -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.Distributions/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/Properties/AssemblyInfo.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Distributions/Properties/AssemblyInfo.cs	(revision 11849)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Distributions")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("FH-Hagenberg")]
+[assembly: AssemblyProduct("HeuristicLab.Distributions")]
+[assembly: AssemblyCopyright("Copyright © FH-Hagenberg 2015")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("d23ca007-4842-4ccd-89b3-21b6e9df0273")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/BanditHelper.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/BanditHelper.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/BanditHelper.cs	(revision 11849)
@@ -0,0 +1,37 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  class BanditHelper {
+    public static void SampleArms(Random random, IBandit bandit, int nSamples, out double expRewardEst, out int bestArmForExpReward, out int bestArmForMaxReward) {
+      bestArmForExpReward = 0;
+      bestArmForMaxReward = 0;
+      expRewardEst = 0.0;
+      var bestSumReward = 0.0;
+      var bestUpperPercCount = 0;
+      for (int a = 0; a < bandit.NumArms; a++) {
+        var sumReward = 0.0;
+        var upperPercCount = 0;
+
+        for (int i = 0; i < nSamples; i++) {
+          var reward = bandit.Pull(a);
+          sumReward += reward;
+          if (reward >= 0.95) upperPercCount++;
+        }
+
+        if (sumReward > bestSumReward) {
+          bestSumReward = sumReward;
+          bestArmForExpReward = a;
+          expRewardEst = bestSumReward / nSamples;
+        }
+        if (upperPercCount > bestUpperPercCount) {
+          bestUpperPercCount = upperPercCount;
+          bestArmForMaxReward = a;
+        }
+      }
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/BernoulliBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/BernoulliBandit.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/BernoulliBandit.cs	(revision 11849)
@@ -0,0 +1,38 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class BernoulliBandit : 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; }
+    // the arm with highest expected reward also has the highest probability of return a reward of 1.0
+    public int OptimalMaximalRewardArm { get { return OptimalExpectedRewardArm; } }
+
+    private readonly Random random;
+    private readonly double[] expReward;
+    public BernoulliBandit(Random random, int nArms) {
+      this.random = random;
+      this.NumArms = nArms;
+      // expected reward of arms is iid and uniformly distributed 
+      expReward = new double[nArms];
+      OptimalExpectedReward = double.NegativeInfinity;
+      for (int i = 0; i < nArms; i++) {
+        expReward[i] = random.NextDouble();
+        if (expReward[i] > OptimalExpectedReward) {
+          OptimalExpectedReward = expReward[i];
+          OptimalExpectedRewardArm = i;
+        }
+      }
+    }
+
+    // pulling an arm results in a bernoulli distributed reward 
+    // with mean expReward[i]
+    public double Pull(int arm) {
+      return random.NextDouble() <= expReward[arm] ? 1 : 0;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/GaussianBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/GaussianBandit.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/GaussianBandit.cs	(revision 11849)
@@ -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.Problems.Bandits/GaussianMixtureBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/GaussianMixtureBandit.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/GaussianMixtureBandit.cs	(revision 11849)
@@ -0,0 +1,55 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // uses a gaussian mixture reward distribution for each arm
+  public class GaussianMixtureBandit : 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[] expReward; // for each component components
+    private readonly double[][] componentProb; // arms x components
+    public GaussianMixtureBandit(Random random, int nArms) {
+      this.random = random;
+      this.NumArms = nArms;
+      var numComponents = 0;
+      expReward = new double[] { 0.1, 0.3, 0.5, 0.7, 0.9 };
+      componentProb = new double[nArms][];
+      OptimalExpectedReward = double.NegativeInfinity;
+      // decide on optimal arm
+      OptimalMaximalRewardArm = random.Next(NumArms);
+      OptimalExpectedRewardArm = OptimalMaximalRewardArm;
+      for (int i = 0; i < nArms; i++) {
+        componentProb[i] = new double[numComponents];
+        if (i == OptimalMaximalRewardArm) {
+          componentProb[i] = new double[] { 0.24, 0.24, 0.24, 0.24, 0.04 };
+        } else {
+          componentProb[i] = new double[] { 0.25, 0.25, 0.25, 0.25, 0 };
+        }
+      }
+
+      OptimalExpectedReward = Enumerable.Range(0, 100000).Select(_ => Pull(OptimalExpectedRewardArm)).Average();
+    }
+
+    // std.dev = 0.1 
+    // and truncation to the interval [0..1]
+    public double Pull(int arm) {
+      double x = 0;
+      do {
+        var k = Enumerable.Range(0, componentProb[arm].Length).SampleProportional(random, componentProb[arm]);
+
+        var z = Rand.RandNormal(random);
+        x = z * 0.1 + expReward[k];
+      }
+      while (x < 0 || x > 1);
+      return x;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj	(revision 11849)
@@ -0,0 +1,67 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{E8138227-0C64-4E85-B676-21D3B97F254F}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Problems.Bandits</RootNamespace>
+    <AssemblyName>HeuristicLab.Problems.Bandits</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </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" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="BanditHelper.cs" />
+    <Compile Include="BernoulliBandit.cs" />
+    <Compile Include="GaussianBandit.cs" />
+    <Compile Include="GaussianMixtureBandit.cs" />
+    <Compile Include="IBandit.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="TruncatedNormalBandit.cs" />
+  </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. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/IBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/IBandit.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/IBandit.cs	(revision 11849)
@@ -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 IBandit {
+    int NumArms { get; }
+    double OptimalExpectedReward { get; } // expected reward of the best arm, for calculating regret
+    int OptimalExpectedRewardArm { get; } // arm which is optimal for optimization of expected reward
+    int OptimalMaximalRewardArm { get; } // arm which is optimal for optimization of maximal reward
+
+    double Pull(int arm); // pulling an arm returns a regret
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/Properties/AssemblyInfo.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/Properties/AssemblyInfo.cs	(revision 11849)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Problems.Bandits")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("FH-Hagenberg")]
+[assembly: AssemblyProduct("HeuristicLab.Problems.Bandits")]
+[assembly: AssemblyCopyright("Copyright © FH-Hagenberg 2015")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("54229c20-7557-41e9-b81a-e1fde89f3ab0")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/TruncatedNormalBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/TruncatedNormalBandit.cs	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.Bandits/TruncatedNormalBandit.cs	(revision 11849)
@@ -0,0 +1,45 @@
+﻿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 TruncatedNormalBandit : 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; }
+    // the arm with highest expected reward also has the highest probability of return a reward of 1.0
+    public int OptimalMaximalRewardArm { get { return OptimalExpectedRewardArm; } }
+
+    private readonly Random random;
+    private readonly double[] expReward;
+    public TruncatedNormalBandit(Random random, int nArms) {
+      this.random = random;
+      this.NumArms = nArms;
+      // expected reward of arms is iid and uniformly distributed 
+      expReward = new double[nArms];
+      OptimalExpectedReward = double.NegativeInfinity;
+      for (int i = 0; i < nArms; i++) {
+        expReward[i] = random.NextDouble() * 0.7;
+        if (expReward[i] > OptimalExpectedReward) {
+          OptimalExpectedReward = expReward[i];
+          OptimalExpectedRewardArm = 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) {
+      double x = 0;
+      do {
+        var z = Rand.RandNormal(random);
+        x = z * 0.1 + expReward[arm];
+      }
+      while (x < 0 || x > 1);
+      return x;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj	(revision 11848)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj	(revision 11849)
@@ -91,4 +91,12 @@
       <Name>HeuristicLab.Algorithms.GrammaticalOptimization</Name>
     </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Distributions\HeuristicLab.Distributions.csproj">
+      <Project>{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}</Project>
+      <Name>HeuristicLab.Distributions</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.Bandits\HeuristicLab.Problems.Bandits.csproj">
+      <Project>{E8138227-0C64-4E85-B676-21D3B97F254F}</Project>
+      <Name>HeuristicLab.Problems.Bandits</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization.SymbReg\HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj">
       <Project>{17a7a380-86ce-482d-8d22-cbd70cc97f0d}</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj	(revision 11848)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj	(revision 11849)
@@ -56,4 +56,8 @@
       <Name>HeuristicLab.Algorithms.GrammaticalOptimization</Name>
     </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Distributions\HeuristicLab.Distributions.csproj">
+      <Project>{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}</Project>
+      <Name>HeuristicLab.Distributions</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization.SymbReg\HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj">
       <Project>{17A7A380-86CE-482D-8D22-CBD70CC97F0D}</Project>
