How N-step Temporal-Difference Methods Extend TD Learning in Reinforcement AI

Reinforcement Learning Overview

Reinforcement learning (RL) trains an agent to select actions in complex environments by maximizing cumulative rewards. The agent observes the current state, takes an action, receives a reward, and updates its knowledge to improve future decisions.

Note: Readers are expected to be familiar with Monte‑Carlo methods and basic temporal‑difference (TD) learning.

TD vs. Monte‑Carlo and the Need for n‑step Methods

Both one‑step TD and Monte‑Carlo (MC) use the same state‑update rule, but differ in how many future steps are waited for before updating a state:

One‑step TD (n=1) updates a state using only the immediate next state.

MC waits until the end of an episode, effectively using n equal to the remaining number of steps.

This raises the question of whether an intermediate n value can be chosen. The answer is yes; the resulting approach is called n‑step bootstrapping.

n‑step Return and Update Rule

The n‑step return

Gₜ^{(n)} = R_{t+1} + γR_{t+2} + … + γ^{n-1}R_{t+n} + γ^{n}V(S_{t+n})

is the discounted sum of rewards from time t+1 to t+n plus the estimated value of state S_{t+n}.

The TD update becomes V(Sₜ) ← V(Sₜ) + α[ Gₜ^{(n)} – V(Sₜ) ].

Three‑step TD Walk‑through

Assume a trajectory that reaches state S₃. The three‑step TD update proceeds as follows:

Generate the trajectory up to S₃.

Update S₀ with the sum of rewards R₁, R₂, R₃ and the value of S₃.

Generate S₄ and update S₁ with R₂, R₃, R₄ plus the value of S₄.

Generate S₅ and update S₂ with R₃, R₄, R₅ plus the value of S₅.

Repeat until the episode terminates.

Special‑case handling:

If fewer than n steps remain, truncate the n‑step return and sum only the available rewards.

When n → ∞, the algorithm reduces to Monte‑Carlo.

Extension to Sarsa, Q‑learning, and Expected Sarsa

The same n‑step idea applies to Sarsa, Q‑learning, and Expected Sarsa by replacing the one‑step look‑ahead with an n‑step look‑ahead in their update formulas; all other components remain unchanged.

Choosing the Best n Value

Although one‑step TD often converges faster than MC, n=1 is not universally optimal. Sutton and Barto illustrate cases where larger n values improve learning speed. In a maze example, a one‑step Sarsa agent only updates actions that directly reach the goal, while a ten‑step Sarsa agent propagates the final reward back through ten preceding actions, allowing faster learning.

The optimal n in TD learning is problem‑dependent; it should be treated as a hyper‑parameter and tuned for each task.

Illustrative Maze Example

In the first episode of a Sarsa agent navigating a maze, the goal state X yields reward R=1; all other steps yield R=0. All action‑values are initialized to zero.

One‑step Sarsa updates only after each step using the next state’s information. Consequently, only actions that can reach X in a single step receive a meaningful update.

Ten‑step Sarsa uses the reward from the final step and propagates it back ten steps, updating a larger set of actions and enabling the agent to learn more from the same episode.

Thus, larger n values can accelerate learning in such settings.

Conclusion

n‑step TD methods bridge the gap between one‑step TD and Monte‑Carlo. The best n is task‑specific; treating n as a tunable hyper‑parameter is recommended.

References

RLBook: http://incompleteideas.net/book/RLbook2020.pdf