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

Timestamp:

01/20/15 20:25:00 (10 years ago)

Author:

gkronber

Message:

#2283: separated value-states from done-states in GenericGrammarPolicy and removed disabling of actions from bandit policies

Location:

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

Files:

• BanditPolicies/ActiveLearningPolicy.cs (modified) (2 diffs)
• BanditPolicies/BoltzmannExplorationPolicy.cs (modified) (1 diff)
• BanditPolicies/ChernoffIntervalEstimationPolicy.cs (modified) (3 diffs)
• BanditPolicies/DefaultPolicyActionInfo.cs (modified) (3 diffs)
• BanditPolicies/EpsGreedyPolicy.cs (modified) (1 diff)
• BanditPolicies/GenericThompsonSamplingPolicy.cs (modified) (1 diff)
• BanditPolicies/MeanAndVariancePolicyActionInfo.cs (modified) (1 diff)
• BanditPolicies/ModelPolicyActionInfo.cs (modified) (3 diffs)
• BanditPolicies/ModifiedUCTPolicy.cs (added)
• BanditPolicies/RandomPolicy.cs (modified) (1 diff)
• BanditPolicies/ThresholdAscentPolicy.cs (modified) (4 diffs)
• BanditPolicies/UCB1Policy.cs (modified) (3 diffs)
• BanditPolicies/UCB1TunedPolicy.cs (modified) (1 diff)
• BanditPolicies/UCBNormalPolicy.cs (modified) (1 diff)
• BanditPolicies/UCTPolicy.cs (modified) (3 diffs)
• GrammarPolicies/GenericGrammarPolicy.cs (modified) (5 diffs)
• GrammarPolicies/GenericTDPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits.csproj (modified) (3 diffs)
• IBanditPolicyActionInfo.cs (modified) (1 diff)

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

@@ -11 +11 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       const double delta = 0.1;
-      int k = myActionInfos.Where(a => !a.Disabled).Count();
+      int k = myActionInfos.Count();
       var bestActions = new List<int>();
       var us = new List<double>();
@@ -20 +20 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         double u;

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

@@ -37 +37 @@
 
       var w = from aInfo in myActionInfos
-              select aInfo.Disabled
-                ? 0.0
-                : Math.Exp(beta * valueFunction(aInfo));
+              select Math.Exp(beta * valueFunction(aInfo));
 
       var bestAction = Enumerable.Range(0, myActionInfos.Count()).SampleProportional(random, w);

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

@@ -21 +21 @@
       // select best
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int k = myActionInfos.Count(a => !a.Disabled);
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       double bestQ = double.NegativeInfinity;
       var bestActions = new List<int>();
@@ -28 +28 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -46 +45 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

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; }
@@ -16 +14 @@
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
           return Tries > 0 ? SumReward / Tries : 0.0;
       }
@@ -26 +22 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
-
       Tries++;
       SumReward += reward;
       MaxReward = Math.Max(MaxReward, reward);
     }
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.SumReward = 0.0;
-      this.knownValue = reward;
-    }
+
     public void Reset() {
       SumReward = 0.0;
       Tries = 0;
       MaxReward = 0.0;
-      knownValue = 0.0;
-    }
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", SumReward / Tries, Disabled);
     }
 

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

@@ -35 +35 @@
         foreach (var aInfo in myActionInfos) {
           aIdx++;
-          if (aInfo.Disabled) continue;
 
           var q = valueFunction(aInfo);

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

@@ -22 +22 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
-        //if (aInfo.Tries == 0) return aIdx;
         var q = aInfo.SampleExpectedReward(random);
         if (q > bestQ) {

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

@@ -39 +39 @@
       estimator.Reset();
     }
-
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", AvgReward, Disabled);
-    }
   }
 }

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 {
-        if (Disabled) return knownValue;
-        else
-          return model.SampleExpectedReward(new Random());
+        return model.SampleExpectedReward(new Random());
       }
     }
@@ -26 +22 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       Tries++;
       model.Update(reward);
@@ -35 +30 @@
     }
 
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.knownValue = reward;
-    }
-
     public void Reset() {
       Tries = 0;
-      knownValue = 0.0;
       model.Reset();
     }
 
-    public void PrintStats() {
-      model.PrintStats();
-    }
-
     public override string ToString() {
-      return string.Format("disabled {0} model {1}", Disabled, model);
+      return string.Format("model {1}", model);
     }
   }

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

@@ -17 +17 @@
       return actionInfos
         .Select((aInfo, idx) => Tuple.Create(aInfo, idx))
-        .Where(p => !p.Item1.Disabled)
         .SelectRandom(random).Item2;
     }

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

@@ -28 +28 @@
       public int Tries { get; private set; }
       public int thresholdBin = 1;
-      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; } }
 
       public void UpdateReward(double reward) {
@@ -46 +42 @@
       }
 
-      public void Disable(double reward) {
-        this.knownValue = reward;
-        Tries = -1;
-      }
-
       public void Reset() {
         Tries = 0;
         thresholdBin = 1;
-        this.knownValue = 0.0;
         Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
-      }
-
-      public void PrintStats() {
-        if (Tries >= 0) {
-          Console.Write("{0,6}", Tries);
-        } else {
-          Console.Write("{0,6}", "");
-        }
       }
 
@@ -101 +83 @@
       var bestActions = new List<int>();
       double bestQ = double.NegativeInfinity;
-      int k = myActionInfos.Count(a => !a.Disabled);
-      var totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      var totalTries = myActionInfos.Sum(a => a.Tries);
       int aIdx = -1;
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -118 +99 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

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

@@ -13 +13 @@
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       var bestActions = new List<int>();
@@ -19 +19 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -31 +30 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

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

@@ -37 +37 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

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

@@ -33 +33 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

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

@@ -21 +21 @@
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       int aIdx = -1;
@@ -27 +27 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -38 +37 @@
           bestQ = q;
           bestActions.Add(aIdx);
-        }
-        if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -9 +10 @@
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
   // this represents grammar policies that use one of the available bandit policies for state selection
-  public class GenericGrammarPolicy : IGrammarPolicy {
-    protected Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state 
-    private readonly bool useCanonicalState;
+  // any bandit policy can be used to select actions for states
+  // a separate datastructure is used to store visited states and to prevent revisiting of states
+  public sealed class GenericGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
 
-    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
-      this.useCanonicalState = useCanonicalState;
+    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
       this.problem = problem;
       this.banditPolicy = banditPolicy;
       this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
     }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
 
     public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
       // fail if all states are done (corresponding state infos are disabled)
-      if (afterStates.All(s => GetStateInfo(s).Disabled)) {
+      if (afterStates.All(s => Done(s))) {
         // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
+        MarkAsDone(curState);
 
-        GetStateInfo(curState).Disable(afterStates.Select(afterState => GetStateInfo(afterState).Value).Max());
         selectedStateIdx = -1;
         return false;
       }
 
-      selectedStateIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
 
       return true;
     }
+
+
 
     private IBanditPolicyActionInfo GetStateInfo(string state) {
@@ -47 +72 @@
     }
 
-    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       foreach (var state in stateTrajectory) {
         GetStateInfo(state).UpdateReward(reward);
@@ -53 +78 @@
         // only the last state can be terminal
         if (problem.Grammar.IsTerminal(state)) {
-          GetStateInfo(state).Disable(reward);
+          MarkAsDone(state);
         }
       }
     }
 
-    public virtual void Reset() {
+
+    public void Reset() {
       stateInfo.Clear();
+      done.Clear();
     }
 
@@ -74 +101 @@
     }
 
-    protected string CanonicalState(string state) {
-      if (useCanonicalState) {
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
         return problem.CanonicalRepresentation(state);
       } else

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

@@ -49 +49 @@
     <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
     <Compile Include="BanditPolicies\ActiveLearningPolicy.cs" />
+    <Compile Include="BanditPolicies\ModifiedUCTPolicy.cs" />
     <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
     <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />
@@ -66 +67 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
       <SubType>Code</SubType>
@@ -72 +74 @@
       <SubType>Code</SubType>
     </Compile>
-    <Compile Include="GrammarPolicies\TDPolicy.cs" />
     <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />

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

@@ -1 +1 @@
 namespace HeuristicLab.Algorithms.Bandits {
   public interface IBanditPolicyActionInfo {
-    bool Disabled { get; }
+    //bool Disabled { get; }
     double Value { get; }
     int Tries { get; }
     void UpdateReward(double reward);
-    void Disable(double reward);
+    //void Disable(double reward);
     // reset causes the state of the action to be reinitialized (as after constructor-call)
     void Reset();
-    void PrintStats();
   }
 }