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

Question

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?

Answer 1

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.