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);
+    }
+  }
+}
