Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Bandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Bandit.cs	(revision 11709)
+++ 	(revision )
@@ -1,31 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.Bandits {
-  public class Bandit {
-    public int NumArms { get; private set; }
-    public double OptimalExpectedReward { get; private set; } // reward of the best arm, for calculating regret
-    private readonly Random random;
-    private readonly double[] expReward;
-    public Bandit(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];
-      }
-    }
-
-    // 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.Algorithms.Bandits/BernoulliBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BernoulliBandit.cs	(revision 11710)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BernoulliBandit.cs	(revision 11710)
@@ -0,0 +1,31 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class BernoulliBandit {
+    public int NumArms { get; private set; }
+    public double OptimalExpectedReward { get; private set; } // reward of the best arm, for calculating regret
+    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];
+      }
+    }
+
+    // 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.Algorithms.Bandits/EpsGreedyPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/EpsGreedyPolicy.cs	(revision 11709)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/EpsGreedyPolicy.cs	(revision 11710)
@@ -24,10 +24,10 @@
         var maxReward = double.NegativeInfinity;
         int bestAction = -1;
-        int curAction = -1;
-        foreach (var avgReward in sumReward.Zip(tries, (r, t) => r / (t + 1))) { // prevent division by zero
-          curAction++;
+        for (int i = 0; i < NumActions; i++) {
+          if (tries[i] == 0) return i;
+          var avgReward = sumReward[i] / tries[i];
           if (maxReward < avgReward) {
             maxReward = avgReward;
-            bestAction = curAction;
+            bestAction = i;
           }
         }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11709)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11710)
@@ -40,10 +40,18 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="Bandit.cs" />
+    <Compile Include="BernoulliBandit.cs" />
     <Compile Include="BanditPolicy.cs" />
+    <Compile Include="TruncatedNormalBandit.cs" />
+    <Compile Include="UCBNormalPolicy.cs" />
+    <Compile Include="UCB1TunedPolicy.cs" />
+    <Compile Include="UCB1Policy.cs" />
     <Compile Include="EpsGreedyPolicy.cs" />
     <Compile Include="IPolicy.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="RandomPolicy.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <Folder Include="Bandits\" />
+    <Folder Include="Policies\" />
   </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/TruncatedNormalBandit.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/TruncatedNormalBandit.cs	(revision 11710)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/TruncatedNormalBandit.cs	(revision 11710)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class TruncatedNormalBandit {
+    public int NumArms { get; private set; }
+    public double OptimalExpectedReward { get; private set; } // reward of the best arm, for calculating regret
+    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();
+        if (expReward[i] > OptimalExpectedReward) OptimalExpectedReward = expReward[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 = Transform(random.NextDouble(), random.NextDouble());
+        x = z * 0.1 + expReward[arm];
+      }
+      while (x < 0 || x > 1);
+      return x;
+    }
+
+    // box muller transform
+    private double Transform(double u1, double u2) {
+      return Math.Sqrt(-2 * Math.Log(u1)) * Math.Cos(2 * Math.PI * u2);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCB1Policy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCB1Policy.cs	(revision 11710)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCB1Policy.cs	(revision 11710)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+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() {
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      for (int i = 0; i < NumActions; i++) {
+        if (tries[i] == 0) return i;
+        var q = sumReward[i] / tries[i] + Math.Sqrt((2 * Math.Log(totalTries)) / tries[i]);
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = i;
+        }
+      }
+      return bestAction;
+    }
+    public override void UpdateReward(int action, double reward) {
+      totalTries++;
+      tries[action]++;
+      sumReward[action] += reward;
+    }
+    public override void Reset() {
+      totalTries = 0;
+      Array.Clear(tries, 0, tries.Length);
+      Array.Clear(sumReward, 0, sumReward.Length);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCB1TunedPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCB1TunedPolicy.cs	(revision 11710)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCB1TunedPolicy.cs	(revision 11710)
@@ -0,0 +1,52 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+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];
+    }
+
+    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() {
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      for (int i = 0; i < NumActions; i++) {
+        if (tries[i] == 0) return i;
+        var q = sumReward[i] / tries[i] + Math.Sqrt((Math.Log(totalTries) / tries[i]) * Math.Min(1.0 / 4, V(i))); // 1/4 is upper bound of bernoulli distributed variable
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = i;
+        }
+      }
+      return bestAction;
+    }
+    public override void UpdateReward(int action, double reward) {
+      totalTries++;
+      tries[action]++;
+      sumReward[action] += reward;
+      sumSqrReward[action] += reward * reward;
+    }
+    public override void Reset() {
+      totalTries = 0;
+      Array.Clear(tries, 0, tries.Length);
+      Array.Clear(sumReward, 0, sumReward.Length);
+      Array.Clear(sumSqrReward, 0, sumSqrReward.Length);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCBNormalPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCBNormalPolicy.cs	(revision 11710)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/UCBNormalPolicy.cs	(revision 11710)
@@ -0,0 +1,54 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+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];
+    }
+
+    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() {
+      int bestAction = -1;
+      double bestQ = double.NegativeInfinity;
+      for (int i = 0; i < NumActions; i++) {
+        if (totalTries == 0 || tries[i] == 0 || tries[i] < Math.Ceiling(8 * Math.Log(totalTries))) return i;
+        var avgReward = sumReward[i] / tries[i];
+        var q = avgReward
+          + Math.Sqrt(16 * ((sumSqrReward[i] - tries[i] * Math.Pow(avgReward, 2)) / (tries[i] - 1)) * (Math.Log(totalTries - 1) / tries[i]));
+        if (q > bestQ) {
+          bestQ = q;
+          bestAction = i;
+        }
+      }
+      return bestAction;
+    }
+    public override void UpdateReward(int action, double reward) {
+      totalTries++;
+      tries[action]++;
+      sumReward[action] += reward;
+      sumSqrReward[action] += reward * reward;
+    }
+    public override void Reset() {
+      totalTries = 0;
+      Array.Clear(tries, 0, tries.Length);
+      Array.Clear(sumReward, 0, sumReward.Length);
+      Array.Clear(sumSqrReward, 0, sumSqrReward.Length);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs	(revision 11709)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs	(revision 11710)
@@ -10,5 +10,5 @@
   public class TestBanditPolicies {
     [TestMethod]
-    public void ComparePolicies() {
+    public void ComparePoliciesForBernoulliBandit() {
       System.Threading.Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
       var globalRand = new Random(31415);
@@ -16,18 +16,49 @@
       var nArms = 10;
       Console.WriteLine("Random");
-      TestPolicy(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), 10));
+      TestPolicyBernoulli(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), 10));
+      Console.WriteLine("UCB1");
+      TestPolicyBernoulli(globalRand, nArms, new UCB1Policy(10));
+      Console.WriteLine("UCB1Tuned");
+      TestPolicyBernoulli(globalRand, nArms, new UCB1TunedPolicy(10));
+      Console.WriteLine("UCB1Normal");
+      TestPolicyBernoulli(globalRand, nArms, new UCBNormalPolicy(10));
       Console.WriteLine("Eps(0.01)");
-      TestPolicy(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.01));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.01));
       Console.WriteLine("Eps(0.05)");
-      TestPolicy(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.05));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.05));
       Console.WriteLine("Eps(0.1)");
-      TestPolicy(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.1));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.1));
       Console.WriteLine("Eps(0.2)");
-      TestPolicy(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.2));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.2));
       Console.WriteLine("Eps(0.5)");
-      TestPolicy(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.5));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.5));
+    }
+    [TestMethod]
+    public void ComparePoliciesForNormalBandit() {
+      System.Threading.Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
+      var globalRand = new Random(31415);
+      var seedForPolicy = globalRand.Next();
+      var nArms = 10;
+      Console.WriteLine("Random");
+      TestPolicyNormal(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), 10));
+      Console.WriteLine("UCB1");
+      TestPolicyNormal(globalRand, nArms, new UCB1Policy(10));
+      Console.WriteLine("UCB1Tuned");
+      TestPolicyNormal(globalRand, nArms, new UCB1TunedPolicy(10));
+      Console.WriteLine("UCB1Normal");
+      TestPolicyNormal(globalRand, nArms, new UCBNormalPolicy(10));
+      Console.WriteLine("Eps(0.01)");
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.01));
+      Console.WriteLine("Eps(0.05)");
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.05));
+      Console.WriteLine("Eps(0.1)");
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.1));
+      Console.WriteLine("Eps(0.2)");
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.2));
+      Console.WriteLine("Eps(0.5)");
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.5));
     }
 
-    private void TestPolicy(Random globalRand, int nArms, IPolicy policy) {
+    private void TestPolicyBernoulli(Random globalRand, int nArms, IPolicy policy) {
       var maxIt = 1E6;
       var reps = 10; // 10 independent runs
@@ -36,5 +67,5 @@
       for (int r = 0; r < reps; r++) {
         var nextLogStep = 1;
-        var b = new Bandit(new Random(globalRand.Next()), 10);
+        var b = new BernoulliBandit(new Random(globalRand.Next()), 10);
         policy.Reset();
         var totalRegret = 0.0;
@@ -59,4 +90,35 @@
       }
     }
+    private void TestPolicyNormal(Random globalRand, int nArms, IPolicy policy) {
+      var maxIt = 1E6;
+      var reps = 10; // 10 independent runs
+      var avgRegretForIteration = new Dictionary<int, double>();
+      // calculate statistics
+      for (int r = 0; r < reps; r++) {
+        var nextLogStep = 1;
+        var b = new TruncatedNormalBandit(new Random(globalRand.Next()), 10);
+        policy.Reset();
+        var totalRegret = 0.0;
+
+        for (int i = 0; i <= maxIt; i++) {
+          var selectedAction = policy.SelectAction();
+          var reward = b.Pull(selectedAction);
+          totalRegret += b.OptimalExpectedReward - reward;
+          policy.UpdateReward(selectedAction, reward);
+          if (i == nextLogStep) {
+            nextLogStep *= 10;
+            if (!avgRegretForIteration.ContainsKey(i)) {
+              avgRegretForIteration.Add(i, 0.0);
+            }
+            avgRegretForIteration[i] += totalRegret / i;
+          }
+        }
+      }
+      // print
+      foreach (var p in avgRegretForIteration.Keys.OrderBy(k => k)) {
+        Console.WriteLine("{0} {1}", p, avgRegretForIteration[p] / reps); // print avg. of avg. regret
+      }
+    }
+
   }
 }
