source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/ThresholdAscentPolicy.cs @ 11730

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HeuristicLab.Algorithms.Bandits {
  /* see: Streeter and Smith: A simple distribution-free approach to the max k-armed bandit problem, Proceedings  of the 12th
 International Conference, CP 2006, Nantes, France, September 25-29, 2006. pp 560-574 */

  public class ThresholdAscentPolicy : BanditPolicy {
    const int numBins = 101;
    const double binSize = 1.0 / (numBins - 1);

    // for each arm store the number of observed rewards for each bin of size delta
    // for delta = 0.01 we have 101 bins
    // the first bin is freq of rewards  >= 0 // all
    // the second bin is freq of rewards > 0
    // the third bin is freq of rewards > 0.01
    // the last bin is for rewards > 0.99
    // 
    // (also see RewardBin function)
    private readonly int[,] armRewardHistogram; // for performance reasons we store cumulative counts (freq of rewards > lower threshold)


    private readonly int[] tries;
    private readonly int s;
    private readonly double delta;

    private int totalTries = 0;
    private int thresholdBin; // bin index of current threshold
    private const double maxTries = 1E6;

    public ThresholdAscentPolicy(int numActions, int s = 100, double delta = 0.05)
      : base(numActions) {
      this.thresholdBin = 1; // first bin to check is bin idx 1 == freq of rewards > 0
      this.s = s;
      this.delta = delta;
      this.armRewardHistogram = new int[numActions, numBins];
      this.tries = new int[numActions];
    }

    // maps a reward value to it's bin
    private static int RewardBin(double reward) {
      Debug.Assert(reward >= 0 && reward <= 1.0);
      // reward = 0 => 0
      // ]0.00 .. 0.01] => 1
      // ]0.01 .. 0.02] => 2
      // ...
      // ]0.99 .. 1.00] => 100
      if (reward <= 0) return 0;
      return (int)Math.Ceiling((reward / binSize));
    }


    private double U(double mu, int n, int k) {
      //var alpha = Math.Log(2.0 * totalTries * k / delta);
      double alpha = Math.Log(2) + Math.Log(maxTries) + Math.Log(k) - Math.Log(delta); // totalTries is max iterations in original paper
      return mu + (alpha + Math.Sqrt(2 * n * mu * alpha + alpha * alpha)) / n;
    }


    public override int SelectAction() {
      Debug.Assert(Actions.Any());
      UpdateThreshold();
      int bestAction = -1;
      double bestQ = double.NegativeInfinity;
      int k = Actions.Count();
      foreach (var a in Actions) {
        if (tries[a] == 0) return a;
        double mu = armRewardHistogram[a, thresholdBin] / (double)tries[a]; // probability of rewards > T 
        double q = U(mu, tries[a], k);
        if (q > bestQ) {
          bestQ = q;
          bestAction = a;
        }
      }
      Debug.Assert(Actions.Contains(bestAction));
      return bestAction;
    }

    private void UpdateThreshold() {
      while (thresholdBin < (numBins - 1) && Actions.Sum(a => armRewardHistogram[a, thresholdBin]) >= s) {
        thresholdBin++;
        // Console.WriteLine("New threshold {0:F2}", T);
      }
    }

    public override void UpdateReward(int action, double reward) {
      Debug.Assert(Actions.Contains(action));
      totalTries++;
      tries[action]++;
      // efficiency: we can start at the current threshold bin because all bins below that are not accessed in select-action
      for (var idx = thresholdBin; idx <= RewardBin(reward); idx++)
        armRewardHistogram[action, idx]++;
    }

    public override void DisableAction(int action) {
      base.DisableAction(action);
      totalTries -= tries[action];
      tries[action] = -1;
    }

    public override void Reset() {
      base.Reset();
      totalTries = 0;
      thresholdBin = 1;
      Array.Clear(tries, 0, tries.Length);
      Array.Clear(armRewardHistogram, 0, armRewardHistogram.Length);
    }

    public override void PrintStats() {
      for (int i = 0; i < tries.Length; i++) {
        if (tries[i] >= 0) {
          Console.Write("{0,6}", tries[i]);
        } else {
          Console.Write("{0,6}", "");
        }
      }
      Console.WriteLine();
    }
    public override string ToString() {
      return string.Format("ThresholdAscentPolicy({0},{1:F2})", s, delta);
    }

  }
}