Automatic Discovery and Transfer of MAXQ Hierarchies. Mehta, Ray, Tadepalli, Dietterich. ICML 2008.

  1. Presents HI-MAT (Hierarchy Induction via Models And Trajectories)
  2. Discovers MAXQ hierarchies by applying DBN models to successful trajectories
  3. “HI-MAT discovers subtasks by analyzing the causal and temporal relationships among the actions in the trajectory.”
  4. Is safe (under assumptions) and compact
  5. Results automatically found are comparable to hand made decompositions
  6. MAXQ develops a task hierarchy with relevant task variables for representing the value of the overall task (creating value functions for each subtask).  Learning the values of each component in the decomposition is simpler than learning the global value function.
  7. Hierarchical methods as good for transfer
  8. “In this paper, we focus on the asymmetric knowledge transfer setting where we are given access to solved source RL problems. The objective is to derive useful biases from these solutions that could speed up learning in target problems.”
  9. Given a DBN and a trajectory, creates a causally annotated trajectory (CAT)
  10. Based on CAT<s?> defines MAXQ subtasks
  11. Using successful trajectories ends up working better than just using DBNs
    1. <Although this probably undermines the case for transfer made earlier, as criteria for success is a something that can change when considering transfer>
    2. Although then says it also helps transfer
  12. In the MAXQ framework, have state and action sets, along with a task hierarchy H, which is a dag representing the task
    1. Leaf nodes in H correspond to primitive actions
  13. Each subtask T in H is a <X,S,G,C> tuple where:
    1. X is the relevant state features
    2. S is the admissible set of states 
    3. G defines termination/goal
    4. C defines the child tasks of this node
  14. T can be invoked any time the state is in S, and terminates when G is satisfied
  15. The “local policy” for T is a mapping from states in the task to children
  16. The global policy is a mapping of all T to a child
  17. The hierarchically optimal policy for a MAXQ graph is the hierarchical policy that has best expected reward
  18. A hierarchical policy is recursively optimal if the local policy in each T is optimal given that all its children are also recursively optimal
  19. Mentions HEXQ and VISA
    1. Based on changing values of state variables
  20. HEXQ uses a heuristic that orders state variables <features?> based on how often a change in their value leads to a subtask being completed
  21. VISA uses DBNs to analyze the influence of state variables on each other, and is more principled than HEXQ
    1. Variables are partitioned so there is acyclic influence between the variables in different clusters (strongly connected components)
    2. “Here, state variables that influence others are associated with lower-level subtasks.”
  22. Difference between VISA and HI-MAT (the algorithm for this paper) is the addition of successful trajectory information in addition to DBNs to construct heirarchies
  23. Empirical evidence that HI-MAT makes hierarchies that are exponentially more compact than VISA
    1. <I am confident that you could construct domains where they would work out the same, but the claim that in practice successful trajectories help makes a ton of sense as the algorithm can focus only on the parts of the entire exponentially sized state space that help solve the problem>
  24. An earlier paper by the author tries to generate hierarchies from trajectories, but without the DBN.
  25. Constrain consideration to stochastic shortest-path problems (“a known conjunctive goal”)
  26. Assume DBN represents conditional probabilites as trees <is this the normal representation?>
  27. Partitioning is done recursively working backwards from the goal
    1. Konidaris also does this, but in continuous spaces Says they are ” given a [my emphasis] successful trajectory that reaches the goal in the source MDP.” <Really just one?  I imagine if that is the case they will generate more trajectories themselves, especially because the domain is stochasitc>
  28. “With this in hand, our objective is to automatically induce a MAXQ hierarchy that can suitably constrain the policy space when solving a related target problem, and therefore achieve faster convergence in the target problem. This is achieved via recursive partitioning of the given trajectory into subtasks using a top-down parse guided by backward chaining from the goal. We use the DBNs along with the trajectory to define the termination predicate, the set of subtasks, and the relevant abstraction for each MAXQ subtask.”
  29. Empirical results on Taxi
  30. A variable <feature> is relevant to an action if R or T either check or change that variable.  If its not relevant it is declared irrelevant
  31. trajectory-relevant variables are those that are checked or changed during the entire trajectory
  32. A causal edge of variable v goes from actions a to b (a -v->b, where b follows a in the trajectory) iff v is trajectory-relevant to both a and b and irrelevant to all actions in between
    1. <I’m only reading about actions, where does state come into play?  Or is it wrapped into their definition of action somehow>
  33. Special actions END and START allow for causal edges from the start and to the terminal action <state?>
  34. A causally annotated trajectory (CAT) “is the original trajectory annotated with all the causal, source, and sink edges.” 
    1. Has cycles removed
  35. Define literal on the causal edge the value v has in a-v->b before b is executed
  36. Then compute something they call the DBN-closure.  Not groking how this works 100% <partially because they seem to have unorthodox naming conventions here – also when they say variable to they men the value of it or the feature…>, but for a feature look at variables that influence it, until no new variables can be added to this set.  Do the same thing, treating the reward and goal as a feature as well
    1. DBN-closure(GOAL) is the set of all features that influence the goal
  37. <Mostly skipping the exact description of the algorithm>
  38. For any goal that isn’t solved, find the corresponding subtask and where it exists in the CAT
  39. Then the literals on the causal edges that enter it are added to the unsolved goals <but when is the CAT segmented again? It must be before this.>
  40. <The partition is discussed at the end of the description, but it seems like it must happen first?>
  41. For every subtask in the partition, it has necessary fields defined for it in the tree H (children, termination condition, relevant features)
  42. A little bit on how primitive actions may be added to leaves even if they didnt exist in the trajectory <It really seems like the algorithm just makes due with one trajectory – how does this get reasonable coverage, especially in the case of stochastic domains which is considered in the paper>
  43. A DBN is called maximally sparse if any relationship that is removed from the DBN would change resulting distributions (if unnecessary features were in the DBN they could be removed without altering the predictions of the model)
  44. Primitive subtasks are just 1 action long <I guess I should have anticipated that>
  45. A trajectory is called non-redundant if no subsequence of actions in the trajectory can be removed with the remaining sequence still reaching the goal <I guess this the removal of cycles?  Still – this is a bit strange in the stochastic setting>
  46. If a trajectory is non-redundant, HI-MAT will produce a task hierarchy that is consistent with the trajectory <skipping the proof>
  47. A hierarchy H is safe wrt DBN models M if the state variables capture the value of any trajectory consistent with the sub-hierarchy rooted at that task node <I think basically this says that X, the features defined for a substask are sufficient to predict the expected reward of the trajectory?  Not the easiest paper to read, perhaps because of space restrictions>
  48. Assuming totally reasonable things: “If the DBN models are maximally sparse then the maximum size of the value function table for any task in the hierarchy produced by HI-MAT is the smallest over all safe hierarchies which are consistent with the trajectory.”
  49. For a trajectory of length L, the subtasks are bounded by 2L <why is that?>  And therefore the value can be represented in an O(L) factor over optimal, as opposed to size exponential in the dimension which occurs with a flat representation.
  50. Our analysis does not address state abstractions arising from the so-called funnel property of subtasks where many starting states result in a few terminal states. Funnel abstractions permit the parent task to ignore variables that, while relevant inside the child task, do not affect the terminal state.”
  51. Moving to empirical results
  52. Bitflip domain
  53. VISA has an exponentially sized hierarchy even after merging (and learns quite slowly)
  54. <Just to mention, HI-MAT starts with a sucessful trajectory and VISA does not (which is a big difference, I think Tom shows that a successful trace is the difference between tractable and intractable learning in factored domains), so keep in mind they aren’t really at parity>
    1. Ah: “This domain has been engineered to highlight the case when access to a successful trajectory allows for significantly more compact hierarchies than without. We expect that access to a solved instance will usually improve the compactness of the resulting hierarchy.>
  55. Then results with transfer, Taxi and Wargus <they got it working!?>
  56. In some algorithms there is “negative transfer” as the old policy actually makes it harder to learn the new
  57. In Wargus, HI-MAT is able to converge faster than the manually constructed hierarchy as it is able to find a more efficient representation
  58. Doesn’t work for disjunctive goals?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: