Changeset 11730 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies

Timestamp:

01/02/15 16:08:21 (9 years ago)

Author:

gkronber

Message:

#2283: several major extensions for grammatical optimization

Location:

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

Files:

• BanditPolicy.cs (modified) (1 diff)
• BernoulliThompsonSamplingPolicy.cs (modified) (1 diff)
• BoltzmannExplorationPolicy.cs (added)
• ChernoffIntervalEstimationPolicy.cs (added)
• EpsGreedyPolicy.cs (modified) (2 diffs)
• Exp3Policy.cs (modified) (1 diff)
• GaussianThompsonSamplingPolicy.cs (modified) (5 diffs)
• GenericThompsonSamplingPolicy.cs (added)
• RandomPolicy.cs (modified) (1 diff)
• ThresholdAscentPolicy.cs (added)
• UCB1Policy.cs (modified) (1 diff)
• UCB1TunedPolicy.cs (modified) (1 diff)
• UCBNormalPolicy.cs (modified) (3 diffs)
• UCTPolicy.cs (added)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs

@@ -28 +28 @@
       Actions = Enumerable.Range(0, numInitialActions).ToArray();
     }
+
+    public abstract void PrintStats();
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs

@@ -55 +55 @@
       Array.Clear(failure, 0, failure.Length);
     }
+
+    public override void PrintStats() {
+      for (int i = 0; i < success.Length; i++) {
+        if (success[i] >= 0) {
+          Console.Write("{0,5:F2}", success[i] / failure[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+
+    public override string ToString() {
+      return "BernoulliThompsonSamplingPolicy";
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs

@@ -27 +27 @@
       if (random.NextDouble() > eps) {
         // select best
-        var maxReward = double.NegativeInfinity;
+        var bestQ = double.NegativeInfinity;
         int bestAction = -1;
         foreach (var a in Actions) {
           if (tries[a] == 0) return a;
-          var avgReward = sumReward[a] / tries[a];
-          if (maxReward < avgReward) {
-            maxReward = avgReward;
+          var q = sumReward[a] / tries[a];
+          if (bestQ < q) {
+            bestQ = q;
             bestAction = a;
           }
@@ -65 +65 @@
       Array.Clear(sumReward, 0, sumReward.Length);
     }
+    public override void PrintStats() {
+      for (int i = 0; i < sumReward.Length; i++) {
+        if (tries[i] >= 0) {
+          Console.Write(" {0,5:F2} {1}", sumReward[i] / tries[i], tries[i]);
+        } else {
+          Console.Write("-", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return string.Format("EpsGreedyPolicy({0:F2})", eps);
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs

@@ -52 +52 @@
       foreach (var a in Actions) w[a] = 1.0;
     }
+    public override void PrintStats() {
+      for (int i = 0; i < w.Length; i++) {
+        if (w[i] > 0) {
+          Console.Write("{0,5:F2}", w[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return "Exp3Policy";
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs

@@ -5 +5 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
+  
   public class GaussianThompsonSamplingPolicy : BanditPolicy {
     private readonly Random random;
-    private readonly double[] sumRewards;
-    private readonly double[] sumSqrRewards;
+    private readonly double[] sampleMean;
+    private readonly double[] sampleM2;
     private readonly int[] tries;
-    public GaussianThompsonSamplingPolicy(Random random, int numActions)
+    private bool compatibility;
+
+    // assumes a Gaussian reward distribution with different means but the same variances for each action
+    // the prior for the mean is also Gaussian with the following parameters
+    private readonly double rewardVariance = 0.1; // we assume a known variance 
+
+    private readonly double priorMean = 0.5;
+    private readonly double priorVariance = 1;
+
+
+    public GaussianThompsonSamplingPolicy(Random random, int numActions, bool compatibility = false)
       : base(numActions) {
       this.random = random;
-      this.sumRewards = new double[numActions];
-      this.sumSqrRewards = new double[numActions];
+      this.sampleMean = new double[numActions];
+      this.sampleM2 = new double[numActions];
       this.tries = new int[numActions];
+      this.compatibility = compatibility;
     }
 
@@ -24 +36 @@
       int bestAction = -1;
       foreach (var a in Actions) {
-        if (tries[a] == 0) return a;
-        var mu = sumRewards[a] / tries[a];
-        var stdDev = Math.Sqrt(sumSqrRewards[a] / tries[a] - Math.Pow(mu, 2));
-        var theta = Rand.RandNormal(random) * stdDev + mu;
+        if(tries[a] == -1) continue; // skip disabled actions
+        double theta;
+        if (compatibility) {
+          if (tries[a] < 2) return a;
+          var mu = sampleMean[a];
+          var variance = sampleM2[a] / tries[a];
+          var stdDev = Math.Sqrt(variance);
+          theta = Rand.RandNormal(random) * stdDev + mu;
+        } else {
+          // calculate posterior mean and variance (for mean reward)
+
+          // see Murphy 2007: Conjugate Bayesian analysis of the Gaussian distribution (http://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf)
+          var posteriorVariance = 1.0 / (tries[a] / rewardVariance + 1.0 / priorVariance);
+          var posteriorMean = posteriorVariance * (priorMean / priorVariance + tries[a] * sampleMean[a] / rewardVariance);
+
+          // sample a mean from the posterior 
+          theta = Rand.RandNormal(random) * Math.Sqrt(posteriorVariance) + posteriorMean;
+
+          // theta already represents the expected reward value => nothing else to do
+        }
         if (theta > maxTheta) {
           maxTheta = theta;
@@ -33 +61 @@
         }
       }
+      Debug.Assert(Actions.Contains(bestAction));
       return bestAction;
     }
@@ -38 +67 @@
     public override void UpdateReward(int action, double reward) {
       Debug.Assert(Actions.Contains(action));
-
-      sumRewards[action] += reward;
-      sumSqrRewards[action] += reward * reward;
       tries[action]++;
+      var delta = reward - sampleMean[action];
+      sampleMean[action] += delta / tries[action];
+      sampleM2[action] += sampleM2[action] + delta * (reward - sampleMean[action]);
     }
 
     public override void DisableAction(int action) {
       base.DisableAction(action);
-      sumRewards[action] = 0;
-      sumSqrRewards[action] = 0;
+      sampleMean[action] = 0;
+      sampleM2[action] = 0;
       tries[action] = -1;
     }
@@ -53 +82 @@
     public override void Reset() {
       base.Reset();
-      Array.Clear(sumRewards, 0, sumRewards.Length);
-      Array.Clear(sumSqrRewards, 0, sumSqrRewards.Length);
+      Array.Clear(sampleMean, 0, sampleMean.Length);
+      Array.Clear(sampleM2, 0, sampleM2.Length);
       Array.Clear(tries, 0, tries.Length);
+    }
+
+    public override void PrintStats() {
+      for (int i = 0; i < sampleMean.Length; i++) {
+        if (tries[i] >= 0) {
+          Console.Write(" {0,5:F2} {1}", sampleMean[i] / tries[i], tries[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return "GaussianThompsonSamplingPolicy";
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs

@@ -23 +23 @@
       // do nothing
     }
-
+    public override void PrintStats() {
+      Console.WriteLine("Random");
+    }
+    public override string ToString() {
+      return "RandomPolicy";
+    }
   }
 }

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

@@ -50 +50 @@
       Array.Clear(sumReward, 0, sumReward.Length);
     }
+    public override void PrintStats() {
+      for (int i = 0; i < sumReward.Length; i++) {
+        if (tries[i] >= 0) {
+          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return "UCB1Policy";
+    }
   }
 }

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

@@ -62 +62 @@
       Array.Clear(sumSqrReward, 0, sumSqrReward.Length);
     }
+    public override void PrintStats() {
+      for (int i = 0; i < sumReward.Length; i++) {
+        if (tries[i] >= 0) {
+          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return "UCB1TunedPolicy";
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs

@@ -24 +24 @@
       double bestQ = double.NegativeInfinity;
       foreach (var a in Actions) {
-        if (totalTries == 0 || tries[a] == 0 || tries[a] < Math.Ceiling(8 * Math.Log(totalTries))) return a;
+        if (totalTries <= 1 || tries[a] <= 1 || tries[a] <= Math.Ceiling(8 * Math.Log(totalTries))) return a;
         var avgReward = sumReward[a] / tries[a];
+        var estVariance = 16 * ((sumSqrReward[a] - tries[a] * Math.Pow(avgReward, 2)) / (tries[a] - 1)) * (Math.Log(totalTries - 1) / tries[a]);
+        if (estVariance < 0) estVariance = 0; // numerical problems
         var q = avgReward
-          + Math.Sqrt(16 * ((sumSqrReward[a] - tries[a] * Math.Pow(avgReward, 2)) / (tries[a] - 1)) * (Math.Log(totalTries - 1) / tries[a]));
+          + Math.Sqrt(estVariance);
         if (q > bestQ) {
           bestQ = q;
@@ -33 +35 @@
         }
       }
+      Debug.Assert(Actions.Contains(bestAction));
       return bestAction;
     }
@@ -58 +61 @@
       Array.Clear(sumSqrReward, 0, sumSqrReward.Length);
     }
+    public override void PrintStats() {
+      for (int i = 0; i < sumReward.Length; i++) {
+        if (tries[i] >= 0) {
+          Console.Write("{0,5:F2}", sumReward[i] / tries[i]);
+        } else {
+          Console.Write("{0,5}", "");
+        }
+      }
+      Console.WriteLine();
+    }
+    public override string ToString() {
+      return "UCBNormalPolicy";
+    }
   }
 }