Multi-Step Value Estimation

In reinforcement learning, accurately estimating the value of states is crucial for learning optimal policies. Multi-step value estimation represents a powerful approach that interpolates between two fundamental methods: single-step bootstrapping (which updates after observing just one transition) and Monte Carlo methods (which wait until the episode terminates to update).

The core insight is that instead of immediately bootstrapping from the next state's value estimate, we can look ahead n steps into the future, accumulating actual rewards before bootstrapping from a more distant state. This n-step lookahead often accelerates learning by incorporating more observed trajectory information while still avoiding the high variance of waiting for complete episodes.

The n-Step Return:

For a state visited at time t, the n-step return is computed as:

$$G_t^{(n)} = r_{t+1} + \gamma \cdot r_{t+2} + \gamma^2 \cdot r_{t+3} + \ldots + \gamma^{n-1} \cdot r_{t+n} + \gamma^n \cdot V(S_{t+n})$$

Where:

• rₜ₊ᵢ represents the reward received i steps after the current state
• γ (gamma) is the discount factor that reduces the weight of future rewards
• V(Sₜ₊ₙ) is the current value estimate of the state reached after n steps

Value Update Rule:

Once the n-step return is computed, the value estimate is updated using:

$$V(S_t) \leftarrow V(S_t) + \alpha \cdot (G_t^{(n)} - V(S_t))$$

Where α (alpha) is the learning rate controlling how much we adjust our estimate toward the observed return.

Edge Cases:

When the trajectory is shorter than n steps (near episode termination), we use all available steps and bootstrap from the terminal state's value (or simply use accumulated rewards if the trajectory ends).

Your Task:

Implement a function that takes a sequence of states and rewards from a trajectory, along with current value estimates, and computes updated value estimates using n-step temporal difference learning. Process each state in the sequence, computing its n-step return and applying the update rule.