4
$\begingroup$

The usual reinforcement learning task is that an agent starts from a start position with the ultimate aim to reach a goal. More often than not, RL algorithms involve planning and learning optimal policies to reach this goal and rewards are only awarded when the goal is attained. Sometimes, there is a penalty for each time step when the goal is not reached.

Now, I am interested in a reinforcement learning task with a start and goal, but with one additional requirement: there are some subgoals that need to be achieved.

The subgoals will have to be achieved first (and perhaps in a certain order) before the actual goal will be achieved.

I want to ask:

  1. If this is a totally new field/area, or a modification of the existing RL that I know.
  2. What added conditions can be put in place to include the "subgoals" as specified?
  3. Please send some references.
Improve this question
$\endgroup$
3
  • $\begingroup$ I wonder if there's something you're leaving out: Is there some reason you can't account for these subgoals in a standard MDP state space and transition function? Meaning, add dimensions to your state space corresponding to the goals already achieved. (E.g. Link cannot transition to the state of having the Master Sword unless he's in the state of standing behind it with all three pendants in hand.) $\endgroup$
    – Sean Easter
    Jun 22, 2016 at 2:07
  • $\begingroup$ I am interested in learning this. This is exactly the same scenario I am troubled with. I am relatively new to this, and I do not know how you can put the \emph{ three pendants in hand} into the state function. $\endgroup$
    – cgo
    Jun 22, 2016 at 5:02
  • $\begingroup$ Answer below. A small note: There is no 'state function.' The state space of an MDP is a set; the transition function is just that, a function. $\endgroup$
    – Sean Easter
    Jun 24, 2016 at 1:40

2 Answers 2

Reset to default
7
$\begingroup$

Sure, standard MDPs can hack that. You just need to carefully define the state space so that it includes all possible states, and ensure that the transition function reflects that order.

Consider a simple, square grid with length three on each side. The agent begins at the bottom left. The reward for the top-right—where the Master Sword resides—is some positive constant; other rewards are uniformly $0$.

There's little to this problem. You can be in any of nine states, and can transition to each state from any of its adjacent states. You can index them by an integer, or row and column. Row and column is intuitive: You can quickly tell from the row and column indices of two states whether a move between the two is legal. So, we'll define each state as a tuple $(i,j)$. Value iteration, or any planning algorithm, would make short work of it.

Let's add the possibility that the top-right is not a terminal state, and that the agent can move about after retrieving the sword. Changing the state space is easy enough: States are now $(i,j,m)$, $m$ being a boolean indicating whether the sword has been retrieved. (If it helps, you can think of this as two grids, one corresponding to having the sword, one not.)

Our transition function also needs an upgrade, since our agent will never drop the sword. (It's very precious.) Easy enough: $T(s,a,s') = 0$ for any $s = (i_0,j_0,1), s' = (i_1,j_1,0)$.

Now, say that in each square in the diagonal from the top-left to bottom-right are the pendants of Courage, Power and Wisdom, respectively, and that the agent must collect these, in order, prior to retrieving the Master Sword. The new states are $(i,j,n)$, $n$ being the number of artifacts (pendants & sword) retrieved.

You can visualize this state space as a stack of grids; gathering the next pendant or sword is loosely like 'moving up' a level. (We're up to 45 states total.) Your transition function should again account for this, returning $0$ for any transition that would represent giving up an artifact. Value iteration would propagate value out and down from the Master Sword.

If unordered gathering is allowed, we'll need more states still. Before, having the Pendant of Power implied having the Pendant of Courage. Since that's no longer the case, we'll need a boolean for each pendant and the Master Sword; states are now $(i,j,c,p,w,m)$ tuples, with any state with $m=1$ having $c = p = w = 1$.

Important point being, your state space is, intuitively, just a list of unique, exclusive conditions. This representation can capture order, once you put enough thought into your problem's full realm of possible states, and adjust your transition function accordingly.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This is very intuitive and clever. Thanks. Can you point me to a paper (or book) where I can find this kind of example? $\endgroup$
    – cgo
    Jul 14, 2016 at 6:32
  • $\begingroup$ @cgo I don't know of one offhand, sadly. I improvised this example myself, and I've never worked directly through examples in a reinforcement learning text. Though, you might try the Sutton & Barto book. $\endgroup$
    – Sean Easter
    Jul 14, 2016 at 20:27
1
$\begingroup$

Research has been targeted at RL with subgoals. It is sometimes referred to as hierarchical reinforcement learning [0]. Most works formalize this using the options framework [1]. For example environments, see these [2] [3].

A thing that is relatively recent is enforcing the subgoals somehow.

[0] https://www.youtube.com/watch?v=e8b0yC6COJ8

[1] Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. RS Sutton, D Precup, S Singh. 1999

[2] Building Portable Options: Skill Transfer in Reinforcement Learning. GD Konidaris, AG Barto. 2007

[3] Modular multitask reinforcement learning with policy sketches. J Andreas, D Klein, S Levine. 2017

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.