source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/TDPolicy.cs @ 11850

using System;
using System.Collections.Generic;
using System.Configuration;
using System.Diagnostics;
using System.Linq;
using System.Security.Policy;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using HeuristicLab.Algorithms.Bandits.BanditPolicies;
using HeuristicLab.Common;
using HeuristicLab.Problems.GrammaticalOptimization;

namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
  public class TDPolicy : GrammarPolicy {

    private readonly HashSet<string> done;
    private readonly Dictionary<string, double> v;
    private IGrammarPolicy epsGreedy;

    public TDPolicy(IProblem problem, bool useCanonicalRepresentation = false)
      : base(problem, useCanonicalRepresentation) {
      this.done = new HashSet<string>();
      this.v = new Dictionary<string, double>();
      this.epsGreedy = new GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.1), useCanonicalRepresentation);
    }

    public override bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
      // only select states that are not yet done
      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
      if (!afterStates.Any()) {
        // fail because all follow states have already been visited => also disable the current state
        done.Add(CanonicalState(curState));
        selectedStateIdx = -1;
        return false;
      }
      throw new NotImplementedException(); // TODO: remap indices of reduced action enumerable to indices of original enumerable (see genericgrammarpolicy)

      //return epsGreedy.TrySelect(random, curState, afterStates, out selectedState);

      var bestQ = double.NegativeInfinity;
      int idx = -1;
      selectedStateIdx = -1;
      foreach (var state in afterStates) {
        idx++;
        // try each state at least once
        if (GetTries(state) == 0) {
          selectedStateIdx = idx;
          return true;
        }
        var q = V(state);
        if (q > bestQ) {
          bestQ = q;
          selectedStateIdx = idx;
        }
      }

      Debug.Assert(selectedStateIdx > -1);
      return true;
    }

    private double V(string state) {
      var s = CanonicalState(state);
      if (v.ContainsKey(s)) return v[s];
      else return 0.0;
    }

    public override void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
      base.UpdateReward(stateTrajectory, reward);
      epsGreedy.UpdateReward(stateTrajectory, reward);
      // the last state could be terminal
      var lastState = stateTrajectory.Last();
      if (problem.Grammar.IsTerminal(lastState)) done.Add(CanonicalState(lastState));

      v[CanonicalState(lastState)] = V(lastState) + 1.0 / GetTries(lastState) * (reward - V(lastState));

      foreach (var p in stateTrajectory.Zip(stateTrajectory.Skip(1), Tuple.Create).Reverse()) {
        var cur = p.Item1;
        var next = p.Item2;

        v[CanonicalState(cur)] = V(cur) + 1.0 / GetTries(cur) * (V(next) - V(cur));
        //v[CanonicalState(cur.ToString())] = V(cur) + 0.1 * (V(next) - V(cur));
      }

    }

    public override double GetValue(string state) {
      return V(state);
    }

    public override void Reset() {
      base.Reset();
      epsGreedy.Reset();
      v.Clear();
      done.Clear();
    }
  }
}