Changeset 12876

Timestamp:

08/17/15 19:13:19 (9 years ago)

Author:

gkronber

Message:

#2283: implemented first crude version of extreme hunter algorithm in branch

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr

Files:

• GrammaticalOptimization.sln (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/ActionInfos/ExtremeHunterActionInfo.cs (added)
• HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/Policies/ExtremeHunterPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits/Policies/IntervalEstimationPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/Policies/UCBPolicy.cs (added)
• HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs (modified) (3 diffs)
• HeuristicLab.Common/Heap.cs (added)
• HeuristicLab.Common/HeuristicLab.Common.csproj (modified) (1 diff)
• HeuristicLab.Problems.Bandits/GaussianBandit.cs (modified) (3 diffs)
• HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj (modified) (1 diff)
• HeuristicLab.Problems.Bandits/IBandit.cs (modified) (1 diff)
• HeuristicLab.Problems.Bandits/ParetoBandit.cs (added)
• HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs (modified) (1 diff)
• Main/Program.cs (modified) (2 diffs)
• Test/TestBanditPolicies.cs (modified) (4 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/GrammaticalOptimization.sln

@@ -1 +1 @@
 
 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 +64 @@
   ProjectSection(SolutionItems) = preProject
     local.testsettings = local.testsettings
+    Performance1.psess = Performance1.psess
   EndProjectSection
 EndProject
@@ -122 +121 @@
     HideSolutionNode = FALSE
   EndGlobalSection
+  GlobalSection(Performance) = preSolution
+    HasPerformanceSessions = true
+  EndGlobalSection
 EndGlobal

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs

@@ -27 +27 @@
       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;
     }

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj

@@ -31 +31 @@
   </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 +40 @@
   <ItemGroup>
     <Compile Include="ActionInfos\BernoulliPolicyActionInfo.cs" />
+    <Compile Include="ActionInfos\ExtremeHunterActionInfo.cs" />
     <Compile Include="ActionInfos\DefaultPolicyActionInfo.cs" />
     <Compile Include="ActionInfos\MeanAndVariancePolicyActionInfo.cs" />
@@ -45 +50 @@
     <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" />

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ActiveLearningPolicy.cs

@@ -9 +9 @@
 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 +33 @@
           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);

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/ChernoffIntervalEstimationPolicy.cs

@@ -35 +35 @@
           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);

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs

@@ -10 +10 @@
   // 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 +28 @@
         } 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) {

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs

@@ -9 +9 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   // policy for k-armed bandit (see Auer et al. 2002)
+  // specific to Bernoulli distributed rewards
   public class UCB1TunedPolicy : IBanditPolicy {
 

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs

@@ -201 +201 @@
         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 +213 @@
         // 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 +223 @@
         // 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));
         }

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Common/HeuristicLab.Common.csproj

@@ -38 +38 @@
     <Compile Include="ExpressionExtender.cs" />
     <Compile Include="Extensions.cs" />
+    <Compile Include="Heap.cs" />
     <Compile Include="MostRecentlyUsedCache.cs" />
     <Compile Include="OnlineMeanAndVarianceEstimator.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/GaussianBandit.cs

@@ -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 +34 @@
           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 +42 @@
     }
 
-    // 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;
     }

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/HeuristicLab.Problems.Bandits.csproj

@@ -41 +41 @@
     <Compile Include="BanditHelper.cs" />
     <Compile Include="BernoulliBandit.cs" />
+    <Compile Include="ParetoBandit.cs" />
     <Compile Include="GaussianBandit.cs" />
     <Compile Include="GaussianMixtureBandit.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.Bandits/IBandit.cs

@@ -12 +12 @@
     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
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

@@ -47 +47 @@
     </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" />

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs

@@ -13 +13 @@
     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

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs

@@ -57 +57 @@
         // 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 +82 @@
             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();
           }

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs

@@ -17 +17 @@
       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 +215 @@
     }
     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 +244 @@
         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 +255 @@
           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])
+      //    );
+      //}
     }