# Model free reinforcement learning with subgoals: how to reinforce learning with only one reward?

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? 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?

• 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? Jul 14, 2016 at 20:29
• 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.
– cgo
Jul 15, 2016 at 5:58
• I edited your post to reflect that clarification; feel free to roll it back if I've erred. Jul 15, 2016 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.

• 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.
– cgo
Jul 21, 2016 at 8:07
• 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. Jul 21, 2016 at 13:45