Subgoal Identifications in Reinforcement Learning: A Survery. Chiu, Soo. Advances In Reinforcement Learning 2011.


Not familiar with this (RL) journal, but as a survey (looking for references) its probably fine.  The references seem like they are from top people so useful for references to mine at the very least.

  1. From the perspective of working on a high-dimensional problem that can’t be tackled at once in its entirety
  2. Abstraction as dimension reduction.  The way abstraction is defined here is through the definition of subtasks, where it is fairly easy to determine if certain features aren’t related to the task
  3. Options
  4. Hierarchies of Abstract Machines / HAM
  5. Two forms of optimality when working with subtasks
    1. Recursive optimality: each subtask optimally achieves the goal state of the subtask
    2. Hierarchical optimality: each subtask is optimal wrt to the overall goal
  6. Although recursive optimality yields poorer results, the advantage is that it makes the planning easier, whereas hierarchical optimality doesn’t change the problem difficulty
  7. MAXQ and followup work, read:
    1. Andre, D. & Russell, S. J. (2002). State abstraction for programmable reinforcement learning
      agents, AAAI/IAAI, pp. 119–125.
    2. Marthi, B., Russell, S. J. & Andre, D. (2006). A compact, hierarchical q-function
      decomposition, UAI, AUAI Press.
  8. <Stuff from Andy’s students is all over this paper>
  9. More papers deal with solving subtasks than finding them, still
  10. Existing algorithms for finding subtasks fall under these categories:
    1. Subgoals as states needed to a task (high visit frequency (perhaps just on successful trajectories), reward gradient)
    2. Subgoals as states that provide access to other regions (related to graph cut, for example based on flow)
    3. Subtasks based on factored state space
  11. References for a number of papers that do state abstration by merging them.
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: