Changeset 12298 for branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies

Timestamp:

04/10/15 16:12:08 (10 years ago)

Author:

gkronber

Message:

#2283: experiments with q-learning

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs (modified) (4 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs

@@ -48 +48 @@
       foreach (var afterState in afterStates) {
         if (!Done(afterState)) {
-          if (GetTries(afterState) == 0) 
-            activeAfterStates[idx] = double.PositiveInfinity;
-          else
-            activeAfterStates[idx] = GetValue(afterState);
+          activeAfterStates[idx] = CalculateValue(afterState);
           actionIndexMap[idx] = originalIdx;
           idx++;
@@ -58 +55 @@
       }
 
+
       //var eps = Math.Max(500.0 / (GetTries(curState) + 1), 0.01);
       //var eps = 10.0 / Math.Sqrt(GetTries(curState) + 1);
-      var eps = 0.2;
+      var eps = 0.01;
       selectedStateIdx = actionIndexMap[SelectEpsGreedy(random, activeAfterStates.Take(idx), eps)];
 
+      UpdateValue(curState, afterStates);
+
       return true;
     }
+
+    private double CalculateValue(string chain) {
+      var features = problem.GetFeatures(chain);
+      var sum = 0.0;
+      foreach (var f in features) {
+        // if (GetTries(f.Id) == 0)
+        //   sum = 0.0;
+        // else
+        sum += GetValue(f.Id) * f.Value;
+      }
+      return sum;
+    }
+
+    private void UpdateValue(string curChain, IEnumerable<string> alternatives) {
+      const double gamma = 1;
+      const double alpha = 0.01;
+      var maxNextQ = alternatives
+          .Select(CalculateValue).Max();
+
+      var delta = gamma * maxNextQ - CalculateValue(curChain);
+
+      foreach (var f in problem.GetFeatures(curChain)) {
+
+        Q[f.Id] = GetValue(f.Id) + alpha * delta * f.Value;
+      }
+    }
+
+    private void UpdateLastValue(string terminalChain, double reward) {
+      const double alpha = 0.01;
+      var delta = reward - CalculateValue(terminalChain);
+      foreach (var f in problem.GetFeatures(terminalChain)) {
+        Q[f.Id] = GetValue(f.Id) + alpha * delta * f.Value;
+      }
+    }
+
 
     private int SelectBoltzmann(Random random, IEnumerable<double> qs, double beta = 10) {
@@ -121 +156 @@
 
     public void UpdateReward(IEnumerable<string> chainTrajectory, double reward) {
-      const double gamma = 0.95;
-      const double minAlpha = 0.01;
-      var reverseChains = chainTrajectory.Reverse();
-      var terminalChain = reverseChains.First();
-
-      var terminalState = CalcState(terminalChain);
-      T[terminalState] = GetTries(terminalChain) + 1;
-      double alpha = Math.Max(1.0 / GetTries(terminalChain), minAlpha);
-      Q[terminalState] = (1 - alpha) * GetValue(terminalChain) + alpha * reward;
-
-      foreach (var chain in reverseChains.Skip(1)) {
-
-        var maxNextQ = followStates[chain]
-          //.Where(s=>!Done(s))
-          .Select(GetValue).Max();
-        T[CalcState(chain)] = GetTries(chain) + 1;
-
-        alpha = Math.Max(1.0 / GetTries(chain), minAlpha);
-        Q[CalcState(chain)] = (1 - alpha) * GetValue(chain) + gamma * alpha * maxNextQ; // direct contribution is zero
-      }
+      // // only updates the last chain because we already update values after each step
+      // var reverseChains = chainTrajectory.Reverse();
+      // var terminalChain = reverseChains.First();
+      // 
+      // UpdateValue(terminalChain, reward);
+      // 
+      // foreach (var chain in reverseChains.Skip(1)) {
+      // 
+      //   var maxNextQ = followStates[chain]
+      //     //.Where(s=>!Done(s))
+      //     .Select(GetValue).Max();
+      // 
+      //   UpdateValue(chain, maxNextQ);
+      // }
+      var terminalChain = chainTrajectory.Last();
+      UpdateLastValue(terminalChain, reward);
       if (problem.Grammar.IsTerminal(terminalChain)) MarkAsDone(terminalChain);
     }
+
 
     public void Reset() {
       Q.Clear();
+      T.Clear();
       done.Clear();
       followStates.Clear();
@@ -160 +193 @@
 
 
-    public int GetTries(string state) {
-      var s = CalcState(state);
-      if (T.ContainsKey(s)) return T[s];
+    public int GetTries(string fId) {
+      if (T.ContainsKey(fId)) return T[fId];
       else return 0;
     }
 
-    public double GetValue(string chain) {
-      var s = CalcState(chain);
-      if (Q.ContainsKey(s)) return Q[s];
+    public double GetValue(string fId) {
+      // var s = CalcState(chain);
+      if (Q.ContainsKey(fId)) return Q[fId];
       else return 0.0; // TODO: check alternatives
     }
 
-    private string CalcState(string chain) {
-      var f = problem.GetFeatures(chain);
-      // this policy only works for problems that return exactly one feature (the 'state')
-      if (f.Skip(1).Any()) throw new ArgumentException();
-      return f.First().Id;
-    }
+    // private string CalcState(string chain) {
+    //   var f = problem.GetFeatures(chain);
+    //   // this policy only works for problems that return exactly one feature (the 'state')
+    //   if (f.Skip(1).Any()) throw new ArgumentException();
+    //   return f.First().Id;
+    // }
 
     public void PrintStats() {
       Console.WriteLine(Q.Values.Max());
-      var topTries = Q.Keys.OrderByDescending(key => T[key]).Take(50);
-      var topQs = Q.Keys.Where(key => key.Contains(",")).OrderByDescending(key => Q[key]).Take(50);
-      foreach (var t in topTries.Zip(topQs, Tuple.Create)) {
-        var id1 = t.Item1;
-        var id2 = t.Item2;
-        Console.WriteLine("{0,30} {1,6} {2:N4} {3,30} {4,6} {5:N4}", id1, T[id1], Q[id1], id2, T[id2], Q[id2]);
-      }
-
+      // var topTries = Q.Keys.OrderByDescending(key => T[key]).Take(50);
+      // var topQs = Q.Keys/*.Where(key => key.Contains("E"))*/.OrderByDescending(key => Q[key]).Take(50);
+      // foreach (var t in topTries.Zip(topQs, Tuple.Create)) {
+      //   var id1 = t.Item1;
+      //   var id2 = t.Item2;
+      //   Console.WriteLine("{0,30} {1,6} {2:N4} {3,30} {4,6} {5:N4}", id1, T[id1], Q[id1], id2, T[id2], Q[id2]);
+      // }
+
+      foreach (var option in new String[]
+      {
+        "a*b", "c*d", "a*b+c*d", "e*f", "a*b+c*d+e*f",
+        "a*b+a*b", "c*d+c*d",
+        "a*a", "a*b","a*c","a*d","a*e","a*f","a*g","a*h","a*i","a*j",
+        "a*b","c*d","e*f","a*c","a*f","a*i","a*i*g","c*f","c*f*j",
+        "b+c","a+c","b+d","a+d",
+        "a*b+c*d+e*f", "a*b+c*d+e*f+a", "a*b+c*d+e*f+b", "a*b+c*d+e*f+c", "a*b+c*d+e*f+d","a*b+c*d+e*f+e",  "a*b+c*d+e*f+f", "a*b+c*d+e*f+g", "a*b+c*d+e*f+h", "a*b+c*d+e*f+i", "a*b+c*d+e*f+j", 
+        "a*b+c*d+e*f+a*g*i+c*j*f"
+      }) {
+        Console.WriteLine("{0,-10} {1:N5}", option, CalculateValue(option));
+      }
+
+      // var topQs = Q.Keys/*.Where(key => key.Contains("E"))*/.OrderByDescending(key => Math.Abs(Q[key])).Take(10);
+      // foreach (var t in topQs) {
+      //   Console.WriteLine("{0,30} {1:N4}", t, Q[t]);
+      // }
     }
   }