Value Function Estimation in Reinforcement Learning
The n-Step TD Algorithm waits for several steps of experience before updating an earlier state's value estimate.
Why Delayed Updates Matter
The n-Step TD Algorithm does not immediately update a state's value estimate after the first reward. It waits for several steps of experience, combines the observed rewards, and then updates an earlier state's estimate. This creates a direct connection between delayed evidence and value estimation: first calculate an n-step return G for the state at time τ, then move V(Sτ) toward that return.
The state being updated is not necessarily the state observed most recently. The algorithm uses the time index τ to identify the earlier state whose estimate has become eligible for an update.
Tracing the Delayed Index
The time index τ identifies the earlier state whose estimate is being considered for updating. The algorithm gathers experience while time t is still before the episode's terminal time T. It then calculates τ. Only an eligible τ proceeds to return calculation and value-function updating. If τ is negative, the implementation is trying to update an earlier state that has not yet become eligible in the indexing scheme. If τ is nonnegative, the update may proceed, provided the return and terminal-state logic are also correct.
Building the n-Step Return
The n-step return G is the target used for the state at time τ. It combines discounted rewards observed over multiple steps. When the n-step boundary occurs before the episode terminates, the return also includes a later value estimate. That later estimate is the bootstrapped part of the target: instead of waiting for the entire episode, the algorithm uses the value estimate available at the boundary.
A Delayed Target for an Earlier State
Suppose the algorithm is evaluating Sτ after observing several rewards, and the n-step boundary occurs before the episode terminates.
Locate the target state: The target is the state Sτ, not automatically the most recently observed state.
Collect the reward evidence: Use the observed rewards between time τ and the n-step boundary. Their contributions are discounted and combined.
Check termination: Because the boundary occurs before the episode terminates, include a later value estimate at the boundary as the bootstrapped continuation term.
Form G: The resulting n-step return contains the discounted reward sequence followed by the appropriate later value estimate.
G is the target used to update V(Sτ). The return contains a bootstrapped value estimate only when the n-step boundary occurs before the episode terminates.
Moving the Value Estimate
V(Sτ) ← V(Sτ) + α[G - V(Sτ)]The update does not replace the old estimate directly with G. It moves V(Sτ) by α times the difference between G and the current estimate. The step size α is restricted to the interval (0, 1], so the update uses a controlled fraction of that difference. If G is above the current estimate, the estimate moves upward; if G is below it, the estimate moves downward.
Applying the Update
Assume an eligible state Sτ has current estimate V(Sτ) = 4, the constructed n-step return is G = 10, and the step size is α = 0.5.
Find the difference: The difference between the target and the current estimate is G - V(Sτ) = 10 - 4 = 6.
Scale the difference: Multiply the difference by α: 0.5 × 6 = 3.
Move the estimate: Add the scaled difference to the old estimate: 4 + 3.
The updated estimate is V(Sτ) = 7. The estimate moves halfway from 4 toward the target 10.
Terminal-State Control Flow
The terminal time T has two related roles. It limits how far the reward sum can extend, and it determines when the repeated process ends. The algorithm gathers the next reward and state only while the current time is before T. After identifying τ, it updates only when τ is eligible. When termination prevents a later value estimate from existing at the n-step boundary, the return must not add a continuation value beyond the terminal state.
Updating whenever a reward is observed, without checking τ.
A negative τ represents an earlier state that has not yet become eligible in the algorithm's indexing scheme.
Fix:
Check τ before calculating the return and applying the value update.Continuing to gather experience after the terminal time T.
The terminal time limits the reward sum and determines when the repeated process ends.
Fix:
Use T as the boundary for gathering experience and stop the repeated process at the terminal condition.Adding a bootstrapped value estimate after the episode has terminated.
The continuation term is used when the n-step boundary occurs before the episode terminates.
Fix:
Include the later value estimate only when the boundary occurs before termination.Replacing V(Sτ) directly with G.
The algorithm moves the current estimate by a step-size-controlled fraction of the difference.
Fix:
Apply V(Sτ) ← V(Sτ) + α[G - V(Sτ)].
Debug the algorithm in this order: verify that T correctly limits experience, verify that τ identifies the intended earlier state, verify that updates occur only for an eligible τ, and finally verify whether the conditional continuation term belongs in G.
Function Approximation from Examples
Function approximation uses available examples from a desired function to construct a broader representation that can generalize beyond the examples themselves. In reinforcement learning, the desired function can be a value function.
The desired function, the examples, and the approximation are different things. The desired function is the function the learner is trying to represent, such as a value function. The examples are the evidence available to the learner; they do not constitute a complete description of the desired function. The approximation is the generalized representation constructed from those examples. Its purpose is not merely to store the examples, but to represent the function more broadly.
| Part | Role | What it is not |
|---|---|---|
| Desired function | The function the learner is trying to represent; in reinforcement learning, it can be a value function. | Not the same as the limited examples available to the learner. |
| Examples | Available evidence from the desired function. | Not a complete description of the desired function. |
| Approximation | A broader representation constructed from the examples. | Not merely a storage list containing only the examples. |
Supervised Learning Connection
Function approximation is an instance of supervised learning. Supervised learning is also studied in artificial neural networks, pattern recognition, and statistical curve fitting. This relationship matters because reinforcement learning does not need an entirely new approach to generalization. Reinforcement learning methods can be combined with generalization methods already studied in these related fields.
Methods from machine learning, artificial neural networks, pattern recognition, and statistical curve fitting can take the role of a function approximator within reinforcement learning algorithms. They are not equally convenient in practice, so the choice of method still matters.
Check Your Reasoning
An implementation has gathered enough experience for an earlier state, but it performs no update. What should you inspect first: the value of τ, the terminal time T, or the choice of approximation method? Explain the order in which you would inspect them and why.
Hints
- Start with the condition that determines whether the earlier state is eligible.
- Then inspect whether the terminal time is preventing the process from gathering or using the needed experience.
- Only after the update control flow is correct should you investigate how values are represented more broadly.
Explain the difference between these three statements: the desired value function exists, examples from it are available, and an approximation is constructed. Then state why the approximation is useful for states not represented directly by the examples.
Hints
- Treat the desired function as the object being represented.
- Treat examples as evidence rather than as the complete function.
- Treat the approximation as the generalized representation built from that evidence.
Key Takeaways
- The n-Step TD Algorithm waits for several steps before updating an earlier state estimate.
- The index τ identifies the state Sτ being updated; an update should not occur while τ is negative.
- The n-step return G combines discounted rewards and includes a later value estimate when the boundary occurs before termination.
- The update moves V(Sτ) toward G by α[G - V(Sτ)] rather than replacing the estimate directly.
- Function approximation uses examples of a desired value function to build a broader representation and connects reinforcement learning with supervised-learning methods.
Key Takeaways
- n-step TD delays an update so that an earlier state can use several steps of reward information.
- τ determines which earlier state's value estimate is updated, while T controls terminal-state behavior.
- G is formed from discounted rewards and, when appropriate, a bootstrapped later value estimate.
- The update moves the current estimate toward G using the step size α.
- Function approximation generalizes from available examples of a desired value function and can use methods from supervised learning and related fields.