Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/GrammaticalOptimization.sln
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/GrammaticalOptimization.sln	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/GrammaticalOptimization.sln	(revision 12876)
@@ -1,7 +1,5 @@
 ﻿
 Microsoft Visual Studio Solution File, Format Version 12.00
-# Visual Studio 2013
-VisualStudioVersion = 12.0.31101.0
-MinimumVisualStudioVersion = 10.0.40219.1
+# Visual Studio 2012
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GrammaticalOptimization", "HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj", "{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}"
 EndProject
@@ -66,4 +64,5 @@
 	ProjectSection(SolutionItems) = preProject
 		local.testsettings = local.testsettings
+		Performance1.psess = Performance1.psess
 	EndProjectSection
 EndProject
@@ -122,3 +121,6 @@
 		HideSolutionNode = FALSE
 	EndGlobalSection
+	GlobalSection(Performance) = preSolution
+		HasPerformanceSessions = true
+	EndGlobalSection
 EndGlobal
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs	(revision 12876)
@@ -27,6 +27,5 @@
       MaxReward = Math.Max(MaxReward, reward);
       var delta = reward - avgValue;
-      //var alpha = 0.01;
-      var alpha = Math.Max(1.0/Tries, 0.01);
+      double alpha = 1.0 / Tries;
       avgValue = avgValue + alpha * delta;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/ExtremeHunterActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/ExtremeHunterActionInfo.cs	(revision 12876)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/ExtremeHunterActionInfo.cs	(revision 12876)
@@ -0,0 +1,93 @@
+﻿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 {
+  // stores information that is relevant for most of the policies
+  public class ExtremeHunterActionInfo : IBanditPolicyActionInfo {
+
+    // hills estimator using a fraction r of the largest sample values
+    private class OnlineHillEstimator {
+      private MinHeap<double> minHeap;
+      private MaxHeap<double> maxHeap;
+
+      public double R { get; set; }
+      private long n;
+      public double Alpha {
+        get {
+          if (minHeap.Count <= 1) return double.PositiveInfinity;
+          double xk = minHeap.GetMin();
+          if (xk.IsAlmost(0.0)) return double.NegativeInfinity;
+          var alpha = 1.0 / (minHeap.Count - 1) * minHeap.Skip(1).Sum(x => Math.Log(x) - Math.Log(xk));
+          Debug.Assert(alpha > 0);
+          return alpha;
+        }
+      }
+      public OnlineHillEstimator(double r = 0.1) {
+        this.R = r;
+        this.minHeap = new MinHeap<double>();
+        this.maxHeap = new MaxHeap<double>();
+        n = 0;
+      }
+
+      private double maxNotInHeap = double.NegativeInfinity;
+      public void Update(double reward) {
+        // if we found a new larger reward then the best n*r so far then insert and drop the smallest
+        if (minHeap.Count > 0 && reward > minHeap.GetMin()) {
+          maxHeap.Add(minHeap.ExtractDominating());
+          minHeap.Add(reward);
+        } else {
+          maxHeap.Add(reward);
+        }
+
+        // increase number of observed rewards
+        n++;
+
+        // now it could be possible that we need to increase the size of the heap by 1 
+        // => add the largest observed reward so far which is not in the heap
+        if (((int)Math.Floor(n * R)) > minHeap.Count) {
+          minHeap.Add(maxHeap.ExtractDominating());
+        }
+
+        Debug.Assert(minHeap.Count == ((int)Math.Floor(n * R)));
+        Debug.Assert(maxHeap.Count == 0 || minHeap.Count == 0 || maxHeap.GetMin() < minHeap.GetMin());
+      }
+    }
+
+
+    public int Tries { get; private set; }
+    public IEnumerable<double> Rewards { get { return rewards; } }
+    private OnlineHillEstimator hillEstimator;
+    private List<double> rewards;
+
+    public double Value {
+      get {
+        return hillEstimator.Alpha;
+      }
+    }
+    public ExtremeHunterActionInfo() {
+      Reset();
+    }
+
+    public void UpdateReward(double reward) {
+      if (reward < 0.0) throw new ArgumentException("reward");
+      Tries++;
+      rewards.Add(reward);
+      hillEstimator.Update(reward);
+    }
+
+    public void Reset() {
+      this.hillEstimator = new OnlineHillEstimator();
+      this.rewards = new List<double>();
+      this.Tries = 0;
+    }
+
+    public override string ToString() {
+      return string.Format("{0:F3} {1}", Value, Tries);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 12876)
@@ -31,4 +31,8 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="ALGLIB-3.7.0, Version=3.7.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\ALGLIB-3.7.0.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -36,4 +40,5 @@
   <ItemGroup>
     <Compile Include="ActionInfos\BernoulliPolicyActionInfo.cs" />
+    <Compile Include="ActionInfos\ExtremeHunterActionInfo.cs" />
     <Compile Include="ActionInfos\DefaultPolicyActionInfo.cs" />
     <Compile Include="ActionInfos\MeanAndVariancePolicyActionInfo.cs" />
@@ -45,4 +50,6 @@
     <Compile Include="Policies\BoltzmannExplorationPolicy.cs" />
     <Compile Include="Policies\ChernoffIntervalEstimationPolicy.cs" />
+    <Compile Include="Policies\IntervalEstimationPolicy.cs" />
+    <Compile Include="Policies\ExtremeHunterPolicy.cs" />
     <Compile Include="Policies\EpsGreedyPolicy.cs" />
     <Compile Include="Policies\GaussianThompsonSamplingPolicy.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs	(revision 12876)
@@ -9,4 +9,8 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   public class ActiveLearningPolicy : IBanditPolicy {
+    public double MaxReward { get; private set; }
+    public ActiveLearningPolicy(double maxReward = 1.0) {
+      this.MaxReward = maxReward;
+    }
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
@@ -29,6 +33,6 @@
           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;
+          u = q + MaxReward * b;
+          l = q - MaxReward * b;
         }
         bestActions.Add(aIdx);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs	(revision 12876)
@@ -35,5 +35,5 @@
           var avgReward = aInfo.SumReward / aInfo.Tries;
 
-          // page 5 of "A simple distribution-free appraoch to the max k-armed bandit problem"
+          // page 5 of "A simple distribution-free approach 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);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ExtremeHunterPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ExtremeHunterPolicy.cs	(revision 12876)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ExtremeHunterPolicy.cs	(revision 12876)
@@ -0,0 +1,89 @@
+﻿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 {
+  // Extreme Bandits, NIPS2014
+  public class ExtremeHunterPolicy : IBanditPolicy {
+
+
+    public double E { get; set; }
+    public double D { get; set; }
+    public double delta { get; set; }
+    public double b { get; set; }
+
+    public ExtremeHunterPolicy(double E = 1.0E-3, double D = 1.0E-2, double b = 1.0) {
+      this.E = E; // parameter TODO
+      this.D = D; // parameter TODO
+      this.b = b; // parameter TODO
+      // private communication with Alexandra Carpentier: 
+      // For instance, on our synthetic experiments, we calibrated the constants by 
+      // cross validation, using exact Pareto distributions and b=1, and we found 
+      // out that taking E =  1e-3 is acceptable. For all the datasets 
+      // (exact Pareto, approximate Pareto, and network data), we kept this same constant
+    }
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<ExtremeHunterActionInfo>();
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+      int K = myActionInfos.Count();
+      double n = 1.0E2; // total tries parameter
+      double minPulls = 100; // parameter: TODO (there are conditions for N given in the paper)
+
+      this.delta = Math.Exp(-Math.Log(Math.Log(n))) / (2.0 * n * K); // TODO 
+
+      var bestActions = new List<int>();
+      int aIdx = -1;
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries <= minPulls) {
+          q = double.PositiveInfinity;
+        } else {
+          double t = aInfo.Tries;
+          double h = aInfo.Value;
+          var thres = Math.Pow(t, h / (2 * b + 1));
+          double c = Math.Pow(t, 1.0 / (2 * b + 1)) * ((1.0 / t) * aInfo.Rewards.Count(r => r >= thres));
+          q = Math.Pow((c + B2(t)) * n, h + B1(t)) * Gamma(h, B1(t)); // eqn (5)
+          Debug.Assert(q > 0);
+        }
+        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 double Gamma(double x, double y) {
+      if (1.0 - x - y <= 0) return double.PositiveInfinity;
+      else return alglib.gammafunction(1.0 - x - y); // comment on eqn 5
+    }
+
+    // eqn 2
+    public double B1(double t) {
+      return D * Math.Sqrt(Math.Log(1.0 / delta)) * Math.Pow(t, -b / (2 * b + 1));
+    }
+
+    // eqn 4
+    public double B2(double t) {
+      return E * Math.Sqrt(Math.Log(t / delta)) * Math.Log(t) * Math.Pow(t, -b / (2 * b + 1));
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new ExtremeHunterActionInfo();
+    }
+    public override string ToString() {
+      return "ExtremeHunter";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/IntervalEstimationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/IntervalEstimationPolicy.cs	(revision 12876)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/IntervalEstimationPolicy.cs	(revision 12876)
@@ -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 {
+  // Powell, Approximate Dynamic Programming, section 12.3.5, page 466, 
+  public class IntervalEstimationPolicy : IBanditPolicy {
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
+      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 {
+          double sigmaSqr = aInfo.RewardVariance * 1.0 / aInfo.Tries;
+          q = aInfo.SumReward / aInfo.Tries + 3.0 * Math.Sqrt(sigmaSqr); // 3.0 for around 95th percentile
+        }
+        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 "IntervalEstimationPolicy(Powell)";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 12876)
@@ -10,4 +10,8 @@
   // policy for k-armed bandit (see Auer et al. 2002)
   public class UCB1Policy : IBanditPolicy {
+    public double MaxReward { get; private set; }
+    public UCB1Policy(double maxReward = 1.0) {
+      this.MaxReward = maxReward;
+    }
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
@@ -24,5 +28,5 @@
         } else {
 
-          q = aInfo.SumReward / aInfo.Tries + 0.5 * Math.Sqrt((2 * Math.Log(totalTries)) / aInfo.Tries);
+          q = aInfo.SumReward / aInfo.Tries + MaxReward * Math.Sqrt((2 * Math.Log(totalTries)) / aInfo.Tries);
         }
         if (q > bestQ) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 12876)
@@ -9,4 +9,5 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   // policy for k-armed bandit (see Auer et al. 2002)
+  // specific to Bernoulli distributed rewards
   public class UCB1TunedPolicy : IBanditPolicy {
 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCBPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCBPolicy.cs	(revision 12876)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCBPolicy.cs	(revision 12876)
@@ -0,0 +1,52 @@
+﻿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 {
+  // Powell, Approximate Dynamic Programming, section 12.3.6, page 467, 
+  public class UCBPolicy : IBanditPolicy {
+    private double maxReward;
+    public UCBPolicy(double maxReward = 1.0) {
+      this.maxReward = maxReward;
+    }
+
+    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 + maxReward * 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 "UCBPolicy(Powell)";
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs	(revision 12876)
@@ -201,12 +201,10 @@
         var children = n.children;
         if (children == null || !children.Any()) break;
-        var values = children.Select(ch => policy.GetValue(ch.phrase));
-        var maxValue = values.Max();
-        if (maxValue == 0) maxValue = 1.0;
-        if (double.IsPositiveInfinity(maxValue)) maxValue = double.MaxValue;
-
+        var triesEnumerable = children.Select(ch => policy.GetTries(ch.phrase));
+        double maxTries = triesEnumerable.Where(v => !double.IsInfinity(v)).DefaultIfEmpty(1).Max();
+        maxTries = Math.Max(maxTries, 1.0);
         // write phrases
         foreach (var ch in children) {
-          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
           Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
         }
@@ -215,6 +213,9 @@
         // write values
         foreach (var ch in children) {
-          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-          Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
+          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          if (!double.IsInfinity(policy.GetValue(ch.phrase)))
+            Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
+          else
+            Console.Write(" Inf ");
         }
         Console.WriteLine();
@@ -222,5 +223,5 @@
         // write tries
         foreach (var ch in children) {
-          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
           Console.Write(" {0,4}", policy.GetTries(ch.phrase));
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/Heap.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/Heap.cs	(revision 12876)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/Heap.cs	(revision 12876)
@@ -0,0 +1,192 @@
+﻿// http://stackoverflow.com/questions/102398/priority-queue-in-net/13776636#13776636
+
+
+using System.Collections;
+using System.Collections.Generic;
+using System.Linq;
+using System;
+
+public abstract class Heap<T> : IEnumerable<T> {
+  private const int InitialCapacity = 0;
+  private const int GrowFactor = 2;
+  private const int MinGrow = 1;
+
+  private int _capacity = InitialCapacity;
+  private T[] _heap = new T[InitialCapacity];
+  private int _tail = 0;
+
+  public int Count { get { return _tail; } }
+  public int Capacity { get { return _capacity; } }
+
+  protected Comparer<T> Comparer { get; private set; }
+  protected abstract bool Dominates(T x, T y);
+
+  protected Heap()
+    : this(Comparer<T>.Default) {
+  }
+
+  protected Heap(Comparer<T> comparer)
+    : this(Enumerable.Empty<T>(), comparer) {
+  }
+
+  protected Heap(IEnumerable<T> collection)
+    : this(collection, Comparer<T>.Default) {
+  }
+
+  protected Heap(IEnumerable<T> collection, Comparer<T> comparer) {
+    if (collection == null) throw new ArgumentNullException("collection");
+    if (comparer == null) throw new ArgumentNullException("comparer");
+
+    Comparer = comparer;
+
+    foreach (var item in collection) {
+      if (Count == Capacity)
+        Grow();
+
+      _heap[_tail++] = item;
+    }
+
+    for (int i = Parent(_tail - 1); i >= 0; i--)
+      BubbleDown(i);
+  }
+  protected Heap(Heap<T> original) {
+    // clone;
+    this._capacity = original._capacity;
+    this._tail = original._tail;
+    this._heap = new T[original._heap.Length];
+    Array.Copy(original._heap, this._heap, this._heap.Length);
+    this.Comparer = original.Comparer;
+  }
+
+  public void Add(T item) {
+    if (Count == Capacity)
+      Grow();
+
+    _heap[_tail++] = item;
+    BubbleUp(_tail - 1);
+  }
+
+  private void BubbleUp(int i) {
+    if (i == 0 || Dominates(_heap[Parent(i)], _heap[i]))
+      return; //correct domination (or root)
+
+    Swap(i, Parent(i));
+    BubbleUp(Parent(i));
+  }
+
+  public T GetMin() {
+    if (Count == 0) throw new InvalidOperationException("Heap is empty");
+    return _heap[0];
+  }
+
+  public T ExtractDominating() {
+    if (Count == 0) throw new InvalidOperationException("Heap is empty");
+    T ret = _heap[0];
+    _tail--;
+    Swap(_tail, 0);
+    BubbleDown(0);
+    return ret;
+  }
+
+  private void BubbleDown(int i) {
+    int dominatingNode = Dominating(i);
+    if (dominatingNode == i) return;
+    Swap(i, dominatingNode);
+    BubbleDown(dominatingNode);
+  }
+
+  private int Dominating(int i) {
+    int dominatingNode = i;
+    dominatingNode = GetDominating(YoungChild(i), dominatingNode);
+    dominatingNode = GetDominating(OldChild(i), dominatingNode);
+
+    return dominatingNode;
+  }
+
+  private int GetDominating(int newNode, int dominatingNode) {
+    if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
+      return newNode;
+    else
+      return dominatingNode;
+  }
+
+  private void Swap(int i, int j) {
+    T tmp = _heap[i];
+    _heap[i] = _heap[j];
+    _heap[j] = tmp;
+  }
+
+  private static int Parent(int i) {
+    return (i + 1) / 2 - 1;
+  }
+
+  private static int YoungChild(int i) {
+    return (i + 1) * 2 - 1;
+  }
+
+  private static int OldChild(int i) {
+    return YoungChild(i) + 1;
+  }
+
+  private void Grow() {
+    int newCapacity = _capacity * GrowFactor + MinGrow;
+    var newHeap = new T[newCapacity];
+    Array.Copy(_heap, newHeap, _capacity);
+    _heap = newHeap;
+    _capacity = newCapacity;
+  }
+
+  public IEnumerator<T> GetEnumerator() {
+    return _heap.Take(Count).GetEnumerator();
+  }
+
+  IEnumerator IEnumerable.GetEnumerator() {
+    return GetEnumerator();
+  }
+}
+
+public class MaxHeap<T> : Heap<T> {
+  public MaxHeap()
+    : this(Comparer<T>.Default) {
+  }
+
+  public MaxHeap(Comparer<T> comparer)
+    : base(comparer) {
+  }
+
+  public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)
+    : base(collection, comparer) {
+  }
+
+  public MaxHeap(IEnumerable<T> collection)
+    : base(collection) {
+  }
+  public MaxHeap(MaxHeap<T> original) : base(original) { }
+
+  protected override bool Dominates(T x, T y) {
+    return Comparer.Compare(x, y) >= 0;
+  }
+}
+
+public class MinHeap<T> : Heap<T> {
+  public MinHeap()
+    : this(Comparer<T>.Default) {
+  }
+
+  public MinHeap(Comparer<T> comparer)
+    : base(comparer) {
+  }
+
+  public MinHeap(IEnumerable<T> collection)
+    : base(collection) {
+  }
+
+  public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
+    : base(collection, comparer) {
+  }
+  public MinHeap(MinHeap<T> original) : base(original) { }
+
+  protected override bool Dominates(T x, T y) {
+    return Comparer.Compare(x, y) <= 0;
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/HeuristicLab.Common.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 12876)
@@ -38,4 +38,5 @@
     <Compile Include="ExpressionExtender.cs" />
     <Compile Include="Extensions.cs" />
+    <Compile Include="Heap.cs" />
     <Compile Include="MostRecentlyUsedCache.cs" />
     <Compile Include="OnlineMeanAndVarianceEstimator.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/GaussianBandit.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/GaussianBandit.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/GaussianBandit.cs	(revision 12876)
@@ -12,9 +12,12 @@
     public int OptimalExpectedRewardArm { get; private set; }
     public int OptimalMaximalRewardArm { get; private set; }
-
+    public double MaxReward { get; private set; }
+    public double MinReward { get; private set; }
     private readonly Random random;
     private readonly double[] exp;
     private readonly double[] stdDev;
-    public GaussianBandit(Random random, int nArms) {
+    public GaussianBandit(Random random, int nArms, double minReward = double.NegativeInfinity, double maxReward = double.PositiveInfinity) {
+      this.MaxReward = maxReward;
+      this.MinReward = minReward;
       this.random = random;
       this.NumArms = nArms;
@@ -31,5 +34,5 @@
           OptimalExpectedRewardArm = i;
         }
-        var q = alglib.invnormaldistribution(0.99) * stdDev[i] + exp[i];
+        var q = alglib.invnormaldistribution(0.999) * stdDev[i] + exp[i];
         if (q > bestQ) {
           bestQ = q;
@@ -39,9 +42,12 @@
     }
 
-    // pulling an arm results in a truncated normally distributed reward 
-    // with mean expReward[i] and std.dev 0.1
+    // pulling an arm results in a normally distributed reward 
+    // with mean expReward[i] and std.dev 
     public double Pull(int arm) {
-      var z = Rand.RandNormal(random);
-      var x = z * stdDev[arm] + exp[arm];
+      double x;
+      do {
+        var z = Rand.RandNormal(random);
+        x = z * stdDev[arm] + exp[arm];
+      } while (x <= MinReward || x > MaxReward);
       return x;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj	(revision 12876)
@@ -41,4 +41,5 @@
     <Compile Include="BanditHelper.cs" />
     <Compile Include="BernoulliBandit.cs" />
+    <Compile Include="ParetoBandit.cs" />
     <Compile Include="GaussianBandit.cs" />
     <Compile Include="GaussianMixtureBandit.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/IBandit.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/IBandit.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/IBandit.cs	(revision 12876)
@@ -12,5 +12,5 @@
     int OptimalMaximalRewardArm { get; } // arm which is optimal for optimization of maximal reward
 
-    double Pull(int arm); // pulling an arm returns a regret
+    double Pull(int arm); // pulling an arm returns a reward
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/ParetoBandit.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/ParetoBandit.cs	(revision 12876)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/ParetoBandit.cs	(revision 12876)
@@ -0,0 +1,57 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // for test case 1 in Extreme Bandits paper (Carpentier, NIPS 2014)
+  public class ParetoBandit : IBandit {
+    private double[] alpha;
+    private double[] pZero;
+    public int NumArms { get { return alpha.Length; } }
+    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; }
+    public double MaxReward { get; private set; }
+    public double MinReward { get; private set; }
+    private readonly Random random;
+    public ParetoBandit(Random random, IEnumerable<double> alpha) : this(random, alpha, alpha.Select(_ => 0.0)) { }
+    public ParetoBandit(Random random, IEnumerable<double> alpha, IEnumerable<double> pZero) { // probability of a zero reward
+      this.alpha = alpha.ToArray();
+      this.pZero = pZero.ToArray();
+      this.random = random;
+
+      // find optimal arms using empirical estimates
+      var bestExpReward = double.NegativeInfinity;
+      var bestMaxReward = double.NegativeInfinity;
+      for (int k = 0; k < NumArms; k++) {
+        double expReward = 0.0;
+        double maxReward = double.NegativeInfinity;
+        for (int i = 0; i < 100000; i++) {
+          var r = Pull(k);
+          expReward += r;
+          maxReward = Math.Max(maxReward, r);
+        }
+        expReward /= 100000;
+
+        if (expReward > bestExpReward) {
+          bestExpReward = expReward;
+          OptimalExpectedRewardArm = k;
+          OptimalExpectedReward = expReward;
+        }
+        if (maxReward > bestMaxReward) {
+          bestMaxReward = maxReward;
+          OptimalMaximalRewardArm = k;
+        }
+      }
+    }
+
+    public double Pull(int arm) {
+      if (random.NextDouble() < pZero[arm]) return 0.0;
+      var u = random.NextDouble();
+      return Math.Pow(1.0 - u, (-1 / alpha[arm]));
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 12876)
@@ -47,5 +47,5 @@
     </Reference>
     <Reference Include="HeuristicLab.Random-3.3">
-      <HintPath>..\..\..\..\..\Program Files\HeuristicLab 3.3\HeuristicLab.Random-3.3.dll</HintPath>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     </Reference>
     <Reference Include="System" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 12876)
@@ -13,5 +13,5 @@
     private const string grammarString = @"
 G(A):
-A -> l | r | m | ?(A)(A) | lA | rA | mA 
+A -> l | r | m | ?(A)(A) | lA | rA | mA |?(A)(A)A
 ";
     // for tree-based GP in HL we need a different grammar for the same language
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs	(revision 12876)
@@ -57,5 +57,9 @@
         // var alg = new SequentialSearch(problem, 25, random, 0,
         //   new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new UCB1TunedPolicy()));
-        var policy = new GenericPolicy(problem);
+        //var policy = new GenericPolicy(problem);
+        //var policy = new GenericGrammarPolicy(problem, new ExtremeHunterPolicy());
+        //var policy = new GenericGrammarPolicy(problem, new UCB1Policy());
+        //var policy = new GenericGrammarPolicy(problem, new ActiveLearningPolicy(0.1));
+        var policy = new GenericGrammarPolicy(problem, new ExtremeHunterPolicy(1.0E-2, 1E-2, 1));
         var alg = new SequentialSearch(problem, 23, random, 0,
           policy);
@@ -78,10 +82,10 @@
             Console.SetCursorPosition(0, 0);
             Console.WriteLine(iterations);
-            WriteAlleleStatistics();
+            //WriteAlleleStatistics();
             Console.WriteLine(globalStatistics.BestSentenceQuality);
             Console.WriteLine(globalStatistics.BestSentence);
             Console.WriteLine(globalStatistics);
-            //alg.PrintStats();
-            policy.PrintStats();
+            alg.PrintStats();
+            //policy.PrintStats();
             //ResetAlleleStatistics();
           }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs	(revision 12874)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs	(revision 12876)
@@ -17,15 +17,41 @@
       var nArms = 20;
 
-      // ThresholdAscent only works for rewards in [0..1] so far
-
-      Console.WriteLine("Thompson (Gaussian est variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 1, 1)));
-      Console.WriteLine("Thompson (Gaussian fixed variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 0.1)));
-      Console.WriteLine("GaussianThompson (compat)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
-      Console.WriteLine("GaussianThompson"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GaussianThompsonSamplingPolicy());
-      Console.WriteLine("UCBNormal"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new UCBNormalPolicy());
-      Console.WriteLine("Random"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new RandomPolicy());
-
-    }
-
+      // some of the policies are specific to rewards in [0..1], e.g. Treshold Ascent or UCB1
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new ExtremeHunterPolicy());
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new IntervalEstimationPolicy());
+      //TestPolicyGaussianUnknownVariance(randSeed, nArms, new UCBPolicy(10));
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new UCBNormalPolicy());
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new UCB1TunedPolicy());
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new UCB1Policy(10));
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new ActiveLearningPolicy(10));
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new ChernoffIntervalEstimationPolicy());
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new BoltzmannExplorationPolicy(100));
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new EpsGreedyPolicy(0.1));
+      TestPolicyGaussianUnknownVariance(randSeed, nArms, new RandomPolicy());
+    }
+
+    [TestMethod]
+    // test case I as described in Extreme Bandits paper
+    public void ComparePoliciesExtremeBandits1() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+      TestPolicyExtremeBandit1(randSeed, new RandomPolicy());
+      TestPolicyExtremeBandit1(randSeed, new ExtremeHunterPolicy());
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(10000));
+      TestPolicyExtremeBandit1(randSeed, new EpsGreedyPolicy(0.1));
+      // TestPolicyExtremeBandit1(randSeed, new ThresholdAscentPolicy());
+    }
+
+    [TestMethod]
+    // test case II as described in Extreme Bandits paper
+    public void ComparePoliciesExtremeBandits2() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+      TestPolicyExtremeBandit2(randSeed, new RandomPolicy());
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy());
+      TestPolicyExtremeBandit2(randSeed, new UCB1Policy(10000));
+      TestPolicyExtremeBandit2(randSeed, new EpsGreedyPolicy(0.1));
+      // TestPolicyExtremeBandit2(randSeed, new ThresholdAscentPolicy());
+    }
 
     [TestMethod]
@@ -189,14 +215,22 @@
     }
     private void TestPolicyGaussianUnknownVariance(int randSeed, int nArms, IBanditPolicy policy) {
-      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianBandit(banditRandom, nActions));
+      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianBandit(banditRandom, nActions, 0, 10));
+    }
+
+    private void TestPolicyExtremeBandit1(int randSeed, IBanditPolicy policy) {
+      TestPolicy(randSeed, 3, policy, (banditRandom, nActions) => new ParetoBandit(banditRandom, new double[] { 5, 1.1, 2 })); // 3 arms
+    }
+    private void TestPolicyExtremeBandit2(int randSeed, IBanditPolicy policy) {
+      TestPolicy(randSeed, 3, policy, (banditRandom, nActions) => new ParetoBandit(banditRandom, new double[] { 1.5, 1.1, 3 }, new double[] { 0.0, 0.8, 0.0 })); // 3 arms
     }
 
 
     private void TestPolicy(int randSeed, int nArms, IBanditPolicy policy, Func<Random, int, IBandit> banditFactory) {
-      var maxIt = 1E5;
-      var reps = 10; // independent runs
-      var regretForIteration = new Dictionary<int, List<double>>();
-      var numberOfPullsOfSuboptimalArmsForExp = new Dictionary<int, double>();
-      var numberOfPullsOfSuboptimalArmsForMax = new Dictionary<int, double>();
+      var maxIt = 1E4;
+      var reps = 30; // independent runs
+      //var regretForIteration = new Dictionary<int, List<double>>();
+      //var numberOfPullsOfSuboptimalArmsForExp = new Dictionary<int, double>();
+      //var numberOfPullsOfSuboptimalArmsForMax = new Dictionary<int, double>();
+      //var bestRewardForIteration = new Dictionary<int, List<double>>();
       var globalRandom = new Random(randSeed);
       var banditRandom = new Random(globalRandom.Next()); // bandits must produce the same rewards for each test
@@ -210,4 +244,5 @@
         var totalPullsOfSuboptimalArmsExp = 0.0;
         var totalPullsOfSuboptimalArmsMax = 0.0;
+        var bestReward = double.NegativeInfinity;
         var actionInfos = Enumerable.Range(0, nArms).Select(_ => policy.CreateActionInfo()).ToArray();
         for (int i = 0; i <= maxIt; i++) {
@@ -220,35 +255,45 @@
           if (selectedAction != b.OptimalMaximalRewardArm) totalPullsOfSuboptimalArmsMax++;
           totalRegret += b.OptimalExpectedReward - reward;
-
-          if (i == nextLogStep) {
-            nextLogStep *= 2;
-            if (!regretForIteration.ContainsKey(i)) {
-              regretForIteration.Add(i, new List<double>());
-            }
-            regretForIteration[i].Add(totalRegret / i);
-
-            if (!numberOfPullsOfSuboptimalArmsForExp.ContainsKey(i)) {
-              numberOfPullsOfSuboptimalArmsForExp.Add(i, 0.0);
-            }
-            numberOfPullsOfSuboptimalArmsForExp[i] += totalPullsOfSuboptimalArmsExp;
-
-            if (!numberOfPullsOfSuboptimalArmsForMax.ContainsKey(i)) {
-              numberOfPullsOfSuboptimalArmsForMax.Add(i, 0.0);
-            }
-            numberOfPullsOfSuboptimalArmsForMax[i] += totalPullsOfSuboptimalArmsMax;
+          bestReward = Math.Max(bestReward, reward);
+
+          if (i + 1 == nextLogStep) {
+            nextLogStep += 100;
+            //if (!regretForIteration.ContainsKey(i)) {
+            //  regretForIteration.Add(i, new List<double>());
+            //}
+            //regretForIteration[i].Add(totalRegret / i);
+            //
+            //if (!numberOfPullsOfSuboptimalArmsForExp.ContainsKey(i)) {
+            //  numberOfPullsOfSuboptimalArmsForExp.Add(i, 0.0);
+            //}
+            //numberOfPullsOfSuboptimalArmsForExp[i] += totalPullsOfSuboptimalArmsExp;
+            //
+            //if (!numberOfPullsOfSuboptimalArmsForMax.ContainsKey(i)) {
+            //  numberOfPullsOfSuboptimalArmsForMax.Add(i, 0.0);
+            //}
+            //numberOfPullsOfSuboptimalArmsForMax[i] += totalPullsOfSuboptimalArmsMax;
+            //
+            //if (!bestRewardForIteration.ContainsKey(i)) {
+            //  bestRewardForIteration.Add(i, new List<double>());
+            //}
+            //bestRewardForIteration[i].Add(bestReward);
+            Console.WriteLine("{0};{1,8};{2,7:F5};{3,7:F2};{4,7:F2};{5:F2};{6:F2};{7:F2};{8:F2}",
+              policy, i + 1, totalRegret, totalPullsOfSuboptimalArmsExp, totalPullsOfSuboptimalArmsMax, bestReward,
+              totalRegret / (i + 1), totalPullsOfSuboptimalArmsExp / (i + 1), totalPullsOfSuboptimalArmsMax / (i + 1));
           }
         }
       }
       // print
-      foreach (var p in regretForIteration.Keys.OrderBy(k => k)) {
-        Console.WriteLine("iter {0,8} regret avg {1,7:F5} min {2,7:F5} max {3,7:F5} suboptimal pulls (exp) {4,7:F2} suboptimal pulls (max) {5,7:F2}",
-          p,
-          regretForIteration[p].Average(),
-          regretForIteration[p].Min(),
-          regretForIteration[p].Max(),
-          numberOfPullsOfSuboptimalArmsForExp[p] / (double)reps,
-          numberOfPullsOfSuboptimalArmsForMax[p] / (double)reps
-          );
-      }
+      //foreach (var p in regretForIteration.Keys.OrderBy(k => k)) {
+      //  Console.WriteLine("iter {0,8} regret avg {1,7:F5} min {2,7:F5} max {3,7:F5} suboptimal pulls (exp) {4,7:F2} suboptimal pulls (max) {5,7:F2} max rewards: {6}",
+      //    p,
+      //    regretForIteration[p].Average(),
+      //    regretForIteration[p].Min(),
+      //    regretForIteration[p].Max(),
+      //    numberOfPullsOfSuboptimalArmsForExp[p] / (double)reps,
+      //    numberOfPullsOfSuboptimalArmsForMax[p] / (double)reps,
+      //    string.Join(" ", bestRewardForIteration[p])
+      //    );
+      //}
     }
 
