Index: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/ActionInfos/DefaultPolicyActionInfo.cs	(revision 12290)
+++ 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 12290)
+++ 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 12290)
+++ 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 12290)
+++ 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 12290)
+++ 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 12290)
+++ 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)";
+    }
+  }
+}
