This is a question about reinforcement learning with subgoals related to this post:

Reinforcement learning with subgoals

In the link above, we gave an assumption that a transition probability exists. My question now is therefore:

What if we do not need to learn the transition probabilities? We want to learn the Q values (say for Q learning or for SARSA) so that we can eventually learn the optimal policy. How will the current state representation ensure that learning will take place if a reward will only be given in the end?

figure from Andrew Ng, et al ICML

To expound:

We start at the state S and the aim is to finish in goal state G by visiting states 1, 2, 3, 4 sequentially. So, we can write the state like this: $(x,y,m)$. $x,y$ will be row and column number of the box (like coordinates). $m$ will be from 0 to 4, as it visits the numbered states sequentially. (top left corner would be $(1,1)$.)

Hence, the desired order would something be like $(5,1,0) \rightarrow (4,5,1) \rightarrow (2,2,2) \cdots (1,5,4)$. The last being the position of the goal, but only after passing through 4.

If reward can only be given when reaching the final state, and $-1$ is given as a penalty for each time step, how will this kind of state representation reinforce the good habit of passing through numbered states sequentially? Would it be necessary to put rewards for each time you get to a numbered state in order?

  • $\begingroup$ Can you explain what you mean by "the transition probability does not exist (and we do not need to learn it)"? Do you mean that the actions have known, deterministic outcomes? $\endgroup$ Jul 14 '16 at 20:29
  • $\begingroup$ Ahhh ... I'm sorry this caused confusion... There is a transition probability, but we do not need to learn it as I am going for a model-free approach. Something like Q-learning or SARSA, where you do not have to learn the transitions. $\endgroup$
    – cgo
    Jul 15 '16 at 5:58
  • $\begingroup$ I edited your post to reflect that clarification; feel free to roll it back if I've erred. $\endgroup$ Jul 15 '16 at 19:38

There's nothing special you need to do for either of these methods to work on a problem of this structure. (There are things you could do to speed convergence, but this is a separate, larger question.) Both methods use update rules based on both $r_{t+1}$ and $Q(s_{t+1},\cdot)$, so high $Q$ values will propagate backward from the goal state.

Q-learning takes as input a set of learning episodes—each a set of $(s, a, r, s')$ tuples—typically ending in an absorbing state.

Take a look at example 11.10 here. In this example and the associated table, a Q-learner observes the exact same episode until convergence. (This is atypical, but useful to build intuition.) Much like in your example, only a single state has a positive reward, though a few have negative and zero rewards. Check the table and note that as iterations grow, positive $Q$ value propagates backward from the goal state.

SARSA acts based on a policy, and updates $Q$ and the corresponding policy as tuples are observed. The update rule is different, since the agent uses $Q$ to select $a'$, but the intuition is similar. As the learner experiences more and more tuples, value will propagate out from the goal state.

That's how an agent will learn the sequence using either of these methods. Given infinite experience and certain restrictions, the $Q$ values will converge to values that reflect the optimal policy.

  • 1
    $\begingroup$ Thank you for your reply. I would like to clarify some points. Does this mean that in this current formulation, it is guaranteed that as time $\rightarrow \infty$, the agent will start in state S and go through states 1, 2, 3, 4 in order until reaching goal $G$? I find it a little bit difficult to follow how the $Q-$values will eventually converge to this. I just need to read this again and again until I am convinced. $\endgroup$
    – cgo
    Jul 21 '16 at 8:07
  • $\begingroup$ It isn't so much about time, as experience. The proofs of convergence for Q-learning and SARSA require that each state-action pair be visited infinitely often (Sutton & Barto). This won't happen in a single run: not every state is accessible from every other. $\endgroup$ Jul 21 '16 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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