Changeset 12893 for branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs

Timestamp:

08/24/15 13:56:27 (9 years ago)

Author:

gkronber

Message:

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs (modified) (6 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestBanditPolicies.cs

@@ -37 +37 @@
       var randSeed = 31415;
       TestPolicyExtremeBandit1(randSeed, new RandomPolicy());
+      TestPolicyExtremeBandit1(randSeed, new SingleArmPolicy(1));
       TestPolicyExtremeBandit1(randSeed, new ExtremeHunterPolicy());
       TestPolicyExtremeBandit1(randSeed, new UCB1Policy(10000));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(1000));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(100));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(10));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(2));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(1));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(0.5));
+      TestPolicyExtremeBandit1(randSeed, new UCB1Policy(0.1));
       TestPolicyExtremeBandit1(randSeed, new EpsGreedyPolicy(0.1));
-      // TestPolicyExtremeBandit1(randSeed, new ThresholdAscentPolicy());
+      TestPolicyExtremeBandit1(randSeed, new EpsGreedyPolicy(0.05));
+      TestPolicyExtremeBandit1(randSeed, new EpsGreedyPolicy(0.01));
     }
 
@@ -48 +57 @@
       CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
       var randSeed = 31415;
-      TestPolicyExtremeBandit2(randSeed, new RandomPolicy());
-      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy());
-      TestPolicyExtremeBandit2(randSeed, new UCB1Policy(10000));
-      TestPolicyExtremeBandit2(randSeed, new EpsGreedyPolicy(0.1));
-      // TestPolicyExtremeBandit2(randSeed, new ThresholdAscentPolicy());
+      //TestPolicyExtremeBandit2(randSeed, new RandomPolicy());
+      //TestPolicyExtremeBandit2(randSeed, new SingleArmPolicy(0));
+      //TestPolicyExtremeBandit2(randSeed, new SingleArmPolicy(1));
+      //TestPolicyExtremeBandit2(randSeed, new SingleArmPolicy(2));
+      // TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy());
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 1, minPulls: 30));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 2, minPulls: 30));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 0.5, minPulls: 30));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 5, minPulls: 30));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 1, minPulls: 100));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 2, minPulls: 100));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 0.5, minPulls: 100));
+      TestPolicyExtremeBandit2(randSeed, new ExtremeHunterPolicy(D: 5, minPulls: 100));
+      // TestPolicyExtremeBandit2(randSeed, new UCB1Policy(10000));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(1000));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(100));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(10));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(2));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(1));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(0.5));
+      //TestPolicyExtremeBandit2(randSeed, new UCB1Policy(0.1));
+      //TestPolicyExtremeBandit2(randSeed, new EpsGreedyPolicy(0.1));
+      //TestPolicyExtremeBandit2(randSeed, new EpsGreedyPolicy(0.05));
+      //TestPolicyExtremeBandit2(randSeed, new EpsGreedyPolicy(0.01));
+      //TestPolicyExtremeBandit2(randSeed, new ThresholdAscentPolicy());
+    }
+
+    [TestMethod]
+    // my own test case for ExtremeHunter
+    // using truncated normal distributions
+    public void ComparePoliciesExtremeBandits3() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+      TestPolicyExtremeBandit3(randSeed, new RandomPolicy());
+      TestPolicyExtremeBandit3(randSeed, new SingleArmPolicy(0));
+      TestPolicyExtremeBandit3(randSeed, new SingleArmPolicy(1));
+      TestPolicyExtremeBandit3(randSeed, new SingleArmPolicy(2));
+      TestPolicyExtremeBandit3(randSeed, new ExtremeHunterPolicy());
+      TestPolicyExtremeBandit3(randSeed, new UCB1Policy(3));
+      TestPolicyExtremeBandit3(randSeed, new EpsGreedyPolicy(0.1));
+    }
+
+    [TestMethod]
+    // a unit test to experiment with bandit policies for completing a GP sentence
+    public void ComparePoliciesSentenceCompletionProblem() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+
+
+      Func<Random, IBandit> sentenceCompletionBanditFactory = (banditRandom) => {
+        var problem = new SymbolicRegressionPoly10Problem();
+        return new SentenceBandit(banditRandom, problem, "a*b+c*d+e*f+E", 23);
+      };
+
+      // ignore number of arms
+
+      // var b = sentenceCompletionBanditFactory(new Random());
+      // all reference policies (always pulling one arm)
+      // for (int i = 0; i < b.NumArms; i++) {
+      //   TestPolicy(randSeed, new SingleArmPolicy(i), sentenceCompletionBanditFactory);
+      // }
+
+      // for the completition of a*b+c*d+e*f+a*g*i+E the arms 12, 15, and 19 are optimal
+      TestPolicy(randSeed, new SingleArmPolicy(12), sentenceCompletionBanditFactory);
+
+      TestPolicy(randSeed, new RandomPolicy(), sentenceCompletionBanditFactory);
+
+      TestPolicy(randSeed, new ExtremeHunterPolicy(), sentenceCompletionBanditFactory);
+      TestPolicy(randSeed, new ExtremeHunterPolicy(D: 0.5), sentenceCompletionBanditFactory);
+      TestPolicy(randSeed, new UCB1Policy(3), sentenceCompletionBanditFactory);
+      TestPolicy(randSeed, new UCB1Policy(1), sentenceCompletionBanditFactory);
+      TestPolicy(randSeed, new UCB1Policy(0.5), sentenceCompletionBanditFactory);
+      TestPolicy(randSeed, new ThresholdAscentPolicy(), sentenceCompletionBanditFactory);
+      TestPolicy(randSeed, new EpsGreedyPolicy(0.1), sentenceCompletionBanditFactory);
     }
 
@@ -206 +284 @@
 
     private void TestPolicyBernoulli(int randSeed, int nArms, IBanditPolicy policy) {
-      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new BernoulliBandit(banditRandom, nActions));
+      TestPolicy(randSeed, policy, (banditRandom) => new BernoulliBandit(banditRandom, nArms));
     }
     private void TestPolicyGaussian(int randSeed, int nArms, IBanditPolicy policy) {
-      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new TruncatedNormalBandit(banditRandom, nActions));
+      TestPolicy(randSeed, policy, (banditRandom) => new TruncatedNormalBandit(banditRandom, nArms));
     }
     private void TestPolicyGaussianMixture(int randSeed, int nArms, IBanditPolicy policy) {
-      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianMixtureBandit(banditRandom, nActions));
+      TestPolicy(randSeed, policy, (banditRandom) => new GaussianMixtureBandit(banditRandom, nArms));
     }
     private void TestPolicyGaussianUnknownVariance(int randSeed, int nArms, IBanditPolicy policy) {
-      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianBandit(banditRandom, nActions, 0, 10));
+      TestPolicy(randSeed, policy, (banditRandom) => new GaussianBandit(banditRandom, nArms, 0, 10));
     }
 
     private void TestPolicyExtremeBandit1(int randSeed, IBanditPolicy policy) {
-      TestPolicy(randSeed, 3, policy, (banditRandom, nActions) => new ParetoBandit(banditRandom, new double[] { 5, 1.1, 2 })); // 3 arms
+      TestPolicy(randSeed, policy, (banditRandom) => new ParetoBandit(banditRandom, new double[] { 5, 1.1, 2 }));
     }
     private void TestPolicyExtremeBandit2(int randSeed, IBanditPolicy policy) {
-      TestPolicy(randSeed, 3, policy, (banditRandom, nActions) => new ParetoBandit(banditRandom, new double[] { 1.5, 1.1, 3 }, new double[] { 0.0, 0.8, 0.0 })); // 3 arms
-    }
-
-
-    private void TestPolicy(int randSeed, int nArms, IBanditPolicy policy, Func<Random, int, IBandit> banditFactory) {
-      var maxIt = 1E4;
+      TestPolicy(randSeed, policy, (banditRandom) => new ParetoBandit(banditRandom, new double[] { 1.5, 1.1, 3 }, new double[] { 0.0, 0.8, 0.0 }, 0, 1));
+    }
+    private void TestPolicyExtremeBandit3(int randSeed, IBanditPolicy policy) {
+      TestPolicy(randSeed, policy, (banditRandom) => new Bandit(banditRandom, new IModel[]
+      {
+        new GammaModel(10, 1),   // exp=10, var=10
+        new GammaModel(6, 2),    // exp=12, var=24
+        new GammaModel(3, 3),    // exp= 9, var=27
+      }, 1, 2));
+    }
+
+
+    private void TestPolicy(int randSeed, IBanditPolicy policy, Func<Random, IBandit> banditFactory) {
+      var maxIt = 1E5;
       var reps = 30; // independent runs
       //var regretForIteration = new Dictionary<int, List<double>>();
@@ -240 +326 @@
       for (int r = 0; r < reps; r++) {
         var nextLogStep = 1;
-        var b = banditFactory(banditRandom, nArms);
-        var totalRegret = 0.0;
-        var totalPullsOfSuboptimalArmsExp = 0.0;
-        var totalPullsOfSuboptimalArmsMax = 0.0;
-        var bestReward = double.NegativeInfinity;
-        var actionInfos = Enumerable.Range(0, nArms).Select(_ => policy.CreateActionInfo()).ToArray();
-        for (int i = 0; i <= maxIt; i++) {
+        var b = banditFactory(banditRandom);
+        var totalReward = 0.0;
+        int totalPullsOfOptimalArmExp = 0;
+        int totalPullsOfOptimalArmMax = 0;
+        var maxReward = double.NegativeInfinity;
+        var actionInfos = Enumerable.Range(0, b.NumArms).Select(_ => policy.CreateActionInfo()).ToArray();
+        for (int i = 0; i <= maxIt + 1; i++) {
           var selectedAction = policy.SelectAction(policyRandom, actionInfos);
           var reward = b.Pull(selectedAction);
@@ -252 +338 @@
 
           // collect stats
-          if (selectedAction != b.OptimalExpectedRewardArm) totalPullsOfSuboptimalArmsExp++;
-          if (selectedAction != b.OptimalMaximalRewardArm) totalPullsOfSuboptimalArmsMax++;
-          totalRegret += b.OptimalExpectedReward - reward;
-          bestReward = Math.Max(bestReward, reward);
-
-          if (i + 1 == nextLogStep) {
-            nextLogStep += 100;
+          if (selectedAction == b.OptimalExpectedRewardArm) totalPullsOfOptimalArmExp++;
+          if (selectedAction == b.OptimalMaximalRewardArm) totalPullsOfOptimalArmMax++;
+          totalReward += reward;
+          maxReward = Math.Max(maxReward, reward);
+
+          if (i == nextLogStep) {
+            nextLogStep += 500;
             //if (!regretForIteration.ContainsKey(i)) {
             //  regretForIteration.Add(i, new List<double>());
@@ -279 +365 @@
             //bestRewardForIteration[i].Add(bestReward);
             Console.WriteLine("{0};{1,8};{2,7:F5};{3,7:F2};{4,7:F2};{5:F2};{6:F2};{7:F2};{8:F2}",
-              policy, i + 1, totalRegret, totalPullsOfSuboptimalArmsExp, totalPullsOfSuboptimalArmsMax, bestReward,
-              totalRegret / (i + 1), totalPullsOfSuboptimalArmsExp / (i + 1), totalPullsOfSuboptimalArmsMax / (i + 1));
+              policy, i, totalReward, totalPullsOfOptimalArmExp, totalPullsOfOptimalArmMax, maxReward,
+              totalReward / i, totalPullsOfOptimalArmExp / (double)i, totalPullsOfOptimalArmMax / (double)i);
           }
         }