In Sutton & Barto's RL book at page 165 for Example 8.1, they say:

enter image description here

Figure 8.3 shows why the planning agents found the solution so much faster than the nonplanning agent. Shown are the policies found by the n = 0 and n = 50 agents halfway through the second episode. Without planning (n = 0), each episode adds only one additional step to the policy, and so only one step (the last) has been learned so far. With planning, again only one step is learned during the first episode, but here during the second episode an extensive policy has been developed that by the end of the episode will reach almost back to the start state.

I have the following question:

Why, without planning (n = 0), each episode adds only one additional step to the policy? What does "adding one additional step to the policy" mean?


1 Answer 1


What does "adding one additional step to the policy" mean?

This is an informal shorthand for how many backup steps from a non-zero reward or learned value will receive a meaningful update. That is, an update with actual data other than the initial bootstrap.

This is due to three things:

  • Bootstrap updates in basic TD only look one timestep ahead, e.g. from $s,a$ to $s',a'$, with the update $Q(s, a) = Q(s, a) + \alpha(r + \gamma Q(s', a') - Q(s, a))$

  • Only the last step in the example environment has a non-zero reward.

  • Only values that have already received at least one "meaningful" update are themselves useful in bootstrapping real data back to earlier time steps. Without such an update, they only have initial arbitrary values.

With background planning, as in Dyna, there is a chance of choosing to base the update on a state, action pair that has already been updated with some non-zero* data, whilst the agent is exploring elsewhere.

Without background planning, and only using single-step backups, initially only the ends of episodes will receive updates with meaningful data.

You can also use multi-step backups, or eligibility traces - as in TD($\lambda$) - to increase the number of steps that get updated at once. These options each have their own pros and cons.

* Technically it is not non-zero that matters, but "different from other experience". Initially the agent experiences a bunch of states and actions that all look the same to it in terms of its estimates of expected future reward. Before an agent can learn to choose between actions it needs to experience results that are different between them.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .