Changeset 11747 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits

Timestamp:

01/12/15 21:23:01 (10 years ago)

Author:

gkronber

Message:

#2283: implemented test problems for MCTS

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits

Files:

• BanditPolicies/ActiveLearningPolicy.cs (added)
• BanditPolicies/BernoulliPolicyActionInfo.cs (modified) (2 diffs)
• BanditPolicies/BoltzmannExplorationPolicy.cs (modified) (2 diffs)
• BanditPolicies/DefaultPolicyActionInfo.cs (modified) (3 diffs)
• BanditPolicies/MeanAndVariancePolicyActionInfo.cs (modified) (2 diffs)
• BanditPolicies/ModelPolicyActionInfo.cs (modified) (2 diffs)
• BanditPolicies/ThresholdAscentPolicy.cs (modified) (3 diffs)
• BanditPolicies/UCB1Policy.cs (modified) (2 diffs)
• BanditPolicies/UCTPolicy.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits.csproj (modified) (1 diff)
• IBanditPolicyActionInfo.cs (modified) (1 diff)
• Models/GaussianMixtureModel.cs (modified) (4 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs

@@ -9 +9 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   public class BernoulliPolicyActionInfo : IBanditPolicyActionInfo {
+    private double knownValue;
     public bool Disabled { get { return NumSuccess == -1; } }
     public int NumSuccess { get; private set; }
     public int NumFailure { get; private set; }
     public int Tries { get { return NumSuccess + NumFailure; } }
-    public double Value { get { return NumSuccess / (double)(Tries); } }
+    public double Value {
+      get {
+        if (Disabled) return knownValue;
+        else
+          return NumSuccess / (double)(Tries);
+      }
+    }
     public void UpdateReward(double reward) {
       Debug.Assert(!Disabled);
@@ -22 +29 @@
       else NumFailure++;
     }
-    public void Disable() {
+    public void Disable(double reward) {
       this.NumSuccess = -1;
       this.NumFailure = -1;
+      this.knownValue = reward;
     }
     public void Reset() {
       NumSuccess = 0;
       NumFailure = 0;
+      knownValue = 0.0;
     }
     public void PrintStats() {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs

@@ -13 +13 @@
     private readonly Func<DefaultPolicyActionInfo, double> valueFunction;
 
-    public BoltzmannExplorationPolicy(double eps) : this(eps, DefaultPolicyActionInfo.AverageReward) { }
+    public BoltzmannExplorationPolicy(double beta) : this(beta, DefaultPolicyActionInfo.AverageReward) { }
 
     public BoltzmannExplorationPolicy(double beta, Func<DefaultPolicyActionInfo, double> valueFunction) {
@@ -25 +25 @@
       // select best
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      Debug.Assert(myActionInfos.Any(a => !a.Disabled));
+
+      // try any of the untries actions randomly
+      // for RoyalSequence it is much better to select the actions in the order of occurrence (all terminal alternatives first)
+      //if (myActionInfos.Any(aInfo => !aInfo.Disabled && aInfo.Tries == 0)) {
+      //  return myActionInfos
+      //  .Select((aInfo, idx) => new { aInfo, idx })
+      //  .Where(p => !p.aInfo.Disabled)
+      //  .Where(p => p.aInfo.Tries == 0)
+      //  .SelectRandom(random).idx;
+      //}
 
       var w = from aInfo in myActionInfos

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs

@@ -9 +9 @@
   // stores information that is relevant for most of the policies
   public class DefaultPolicyActionInfo : IBanditPolicyActionInfo {
+    private double knownValue;
     public bool Disabled { get { return Tries == -1; } }
     public double SumReward { get; private set; }
     public int Tries { get; private set; }
     public double MaxReward { get; private set; }
-    public double Value { get { return SumReward / Tries; } }
+    public double Value {
+      get {
+        if (Disabled) return knownValue;
+        else
+          return Tries > 0 ? SumReward / Tries : 0.0;
+      }
+    }
     public DefaultPolicyActionInfo() {
       MaxReward = double.MinValue;
@@ -25 +32 @@
       MaxReward = Math.Max(MaxReward, reward);
     }
-    public void Disable() {
+    public void Disable(double reward) {
       this.Tries = -1;
       this.SumReward = 0.0;
+      this.knownValue = reward;
     }
     public void Reset() {
@@ -33 +41 @@
       Tries = 0;
       MaxReward = 0.0;
+      knownValue = 0.0;
     }
     public void PrintStats() {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs

@@ -11 +11 @@
     public bool Disabled { get { return disabled; } }
     private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
+    private double knownValue;
     public int Tries { get { return estimator.N; } }
     public double SumReward { get { return estimator.Sum; } }
     public double AvgReward { get { return estimator.Avg; } }
     public double RewardVariance { get { return estimator.Variance; } }
-    public double Value { get { return AvgReward; } }
+    public double Value {
+      get {
+        if (disabled) return knownValue;
+        else
+          return AvgReward;
+      }
+    }
 
     public void UpdateReward(double reward) {
@@ -22 +29 @@
     }
 
-    public void Disable() {
+    public void Disable(double reward) {
       disabled = true;
+      this.knownValue = reward;
     }
 
     public void Reset() {
       disabled = false;
+      knownValue = 0.0;
       estimator.Reset();
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs

@@ -10 +10 @@
   public class ModelPolicyActionInfo : IBanditPolicyActionInfo {
     private readonly IModel model;
+    private double knownValue;
     public bool Disabled { get { return Tries == -1; } }
-    public double Value { get { return model.SampleExpectedReward(new Random()); } }
+    public double Value {
+      get {
+        if (Disabled) return knownValue;
+        else
+          return model.SampleExpectedReward(new Random());
+      }
+    }
 
     public int Tries { get; private set; }
@@ -28 +35 @@
     }
 
-    public void Disable() {
+    public void Disable(double reward) {
       this.Tries = -1;
+      this.knownValue = reward;
     }
 
     public void Reset() {
       Tries = 0;
+      knownValue = 0.0;
       model.Reset();
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs

@@ -28 +28 @@
       public int Tries { get; private set; }
       public int thresholdBin = 1;
-      public double Value { get { return rewardHistogram[thresholdBin] / (double)Tries; } }
+      private double knownValue;
+
+      public double Value {
+        get {
+          if (Disabled) return knownValue;
+          if(Tries == 0.0) return 0.0;
+          return rewardHistogram[thresholdBin] / (double)Tries;
+        }
+      }
 
       public bool Disabled { get { return Tries == -1; } }
@@ -38 +46 @@
       }
 
-      public void Disable() {
+      public void Disable(double reward) {
+        this.knownValue = reward;
         Tries = -1;
       }
@@ -45 +54 @@
         Tries = 0;
         thresholdBin = 1;
+        this.knownValue = 0.0;
         Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
       }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs

@@ -5 +5 @@
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
@@ -11 +12 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int bestAction = -1;
       double bestQ = double.NegativeInfinity;
       int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
 
+      var bestActions = new List<int>();
       int aIdx = -1;
       foreach (var aInfo in myActionInfos) {
         aIdx++;
         if (aInfo.Disabled) continue;
-        if (aInfo.Tries == 0) return aIdx;
-        var q = aInfo.SumReward / aInfo.Tries + Math.Sqrt((2 * Math.Log(totalTries)) / aInfo.Tries);
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+
+          q = aInfo.SumReward / aInfo.Tries + 0.5 * Math.Sqrt((2 * Math.Log(totalTries)) / aInfo.Tries);
+        }
         if (q > bestQ) {
           bestQ = q;
-          bestAction = aIdx;
+          bestActions.Clear();
+          bestActions.Add(aIdx);
+        } else if (q == bestQ) {
+          bestActions.Add(aIdx);
         }
       }
-      Debug.Assert(bestAction > -1);
-      return bestAction;
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
     }
 

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs

@@ -5 +5 @@
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Common;
+
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   /* Kocsis et al. Bandit based Monte-Carlo Planning */
@@ -22 +24 @@
 
       int aIdx = -1;
+      var bestActions = new List<int>();
       foreach (var aInfo in myActionInfos) {
         aIdx++;
         if (aInfo.Disabled) continue;
-        if (aInfo.Tries == 0) return aIdx;
-        var q = aInfo.SumReward / aInfo.Tries + 2.0 * c * Math.Sqrt(Math.Log(totalTries) / aInfo.Tries);
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          q = aInfo.SumReward / aInfo.Tries + 2.0 * c * Math.Sqrt(Math.Log(totalTries) / aInfo.Tries);
+        }
         if (q > bestQ) {
+          bestActions.Clear();
           bestQ = q;
-          bestAction = aIdx;
+          bestActions.Add(aIdx);
         }
+        if (q == bestQ) {
+          bestActions.Add(aIdx);
+        }
+
       }
-      Debug.Assert(bestAction > -1);
-      return bestAction;
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
     }
 

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

@@ -48 +48 @@
     <Compile Include="BanditPolicies\BoltzmannExplorationPolicy.cs" />
     <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
+    <Compile Include="BanditPolicies\ActiveLearningPolicy.cs" />
     <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
     <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs

@@ -11 +11 @@
     int Tries { get; }
     void UpdateReward(double reward);
-    void Disable();
+    void Disable(double reward);
     // reset causes the state of the action to be reinitialized (as after constructor-call)
     void Reset();

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianMixtureModel.cs

@@ -9 +9 @@
 namespace HeuristicLab.Algorithms.Bandits.Models {
   public class GaussianMixtureModel : IModel {
-    private readonly double[] componentMeans;
-    private readonly double[] componentVars;
-    private readonly double[] componentProbs;
+    private double[] componentMeans;
+    private double[] componentVars;
+    private double[] componentProbs;
+    private readonly List<double> allRewards = new List<double>();
 
     private int numComponents;
@@ -17 +18 @@
     public GaussianMixtureModel(int nComponents = 5) {
       this.numComponents = nComponents;
-      this.componentProbs = new double[nComponents];
-      this.componentMeans = new double[nComponents];
-      this.componentVars = new double[nComponents];
+
+      Reset();
     }
 
@@ -29 +29 @@
 
     public void Update(double reward) {
-      // see http://www.cs.toronto.edu/~mackay/itprnn/ps/302.320.pdf Algorithm 22.2 soft k-means
-      throw new NotImplementedException();
+      allRewards.Add(reward);
+      throw new NotSupportedException("this does not yet work");
+      if (allRewards.Count < 1000 && allRewards.Count % 10 == 0) {
+        // see http://www.cs.toronto.edu/~mackay/itprnn/ps/302.320.pdf Algorithm 22.2 soft k-means
+        Reset();
+        for (int i = 0; i < 20; i++) {
+          var responsibilities = allRewards.Select(r => CalcResponsibility(r)).ToArray();
+
+
+          var sumWeightedRewards = new double[numComponents];
+          var sumResponsibilities = new double[numComponents];
+          foreach (var p in allRewards.Zip(responsibilities, Tuple.Create)) {
+            for (int k = 0; k < numComponents; k++) {
+              sumWeightedRewards[k] += p.Item2[k] * p.Item1;
+              sumResponsibilities[k] += p.Item2[k];
+            }
+          }
+          for (int k = 0; k < numComponents; k++) {
+            componentMeans[k] = sumWeightedRewards[k] / sumResponsibilities[k];
+          }
+
+          sumWeightedRewards = new double[numComponents];
+          foreach (var p in allRewards.Zip(responsibilities, Tuple.Create)) {
+            for (int k = 0; k < numComponents; k++) {
+              sumWeightedRewards[k] += p.Item2[k] * Math.Pow(p.Item1 - componentMeans[k], 2);
+            }
+          }
+          for (int k = 0; k < numComponents; k++) {
+            componentVars[k] = sumWeightedRewards[k] / sumResponsibilities[k];
+            componentProbs[k] = sumResponsibilities[k] / sumResponsibilities.Sum();
+          }
+        }
+      }
+    }
+
+    private double[] CalcResponsibility(double r) {
+      var res = new double[numComponents];
+      for (int k = 0; k < numComponents; k++) {
+        componentVars[k] = Math.Max(componentVars[k], 0.001);
+        res[k] = componentProbs[k] * alglib.normaldistribution((r - componentMeans[k]) / Math.Sqrt(componentVars[k]));
+        res[k] = Math.Max(res[k], 0.0001);
+      }
+      var sum = res.Sum();
+      for (int k = 0; k < numComponents; k++) {
+        res[k] /= sum;
+      }
+      return res;
     }
 
@@ -44 +89 @@
 
     public void Reset() {
-      Array.Clear(componentMeans, 0, numComponents);
-      Array.Clear(componentVars, 0, numComponents);
-      Array.Clear(componentProbs, 0, numComponents);
+      var rand = new Random();
+      this.componentProbs = Enumerable.Range(0, numComponents).Select((_) => rand.NextDouble()).ToArray();
+      var sum = componentProbs.Sum();
+      for (int i = 0; i < componentProbs.Length; i++) componentProbs[i] /= sum;
+      this.componentMeans = Enumerable.Range(0, numComponents).Select((_) => Rand.RandNormal(rand)).ToArray();
+      this.componentVars = Enumerable.Range(0, numComponents).Select((_) => 0.01).ToArray();
     }