Value Prediction
A backup shifts an estimated value at a particular state toward a backed-up value or target.
A Common Shape for Prediction
Value prediction methods may look different because they obtain their learning targets in different ways. Their shared structure is the backup: take an estimated value for a state and shift it toward a backed-up value, also called the target for that state. This common pattern lets us compare several prediction methods by asking one central question: what target is each method using?
A backup shifts an estimated value at a particular state toward a backed-up value or target.
A backup describes the update pattern. The target on the right side is what changes from one prediction method to another.
Tracing a Backup
The notation s ↦→ g means that state s is the state being backed up and g is the target toward which its estimated value is shifted. The notation does not by itself identify how g was obtained. That information comes from the prediction method being used.
Reading s ↦→ g
Interpret the backup notation s ↦→ g.
Identify s: s is the particular state whose estimated value is being updated.
Identify g: g is the backed-up value or target used to guide the update.
Read the arrow: The arrow indicates that the estimate for s is shifted toward g rather than that the estimate is necessarily replaced by g.
The notation means: back up state s toward target g.
Three Experience-Based Targets
Monte Carlo, TD(0), and n-step TD use the same backup pattern but choose different targets. Monte Carlo uses the return Gₜ. TD(0) uses the one-step target Rₜ₊₁ + γ v̂(Sₜ₊₁, θₜ). n-step TD uses the n-step return G⁽ⁿ⁾ₜ. The target therefore tells us what information the method uses for its backup.
| Method | Backup target | Target source |
|---|---|---|
| Monte Carlo | Gₜ | Return from the episode |
| TD(0) | Rₜ₊₁ + γ v̂(Sₜ₊₁, θₜ) | One reward plus a current estimate of the next state |
| n-step TD | G⁽ⁿ⁾ₜ | An n-step return |
The backup pattern is shared, but the target changes.
Model-Based and Sampled Backups
Dynamic programming policy evaluation also uses a backup, but its target is obtained differently. It backs up an arbitrary state and uses an expected target under policy π. By contrast, the experience-based methods described here obtain targets from sampled experience, such as a completed episode return or a one-step transition. The shared idea is still to move an estimate toward a target; the difference is whether the target comes from an expectation supplied by a model or from observed experience.
Gradient Monte Carlo Updates
The Gradient Monte Carlo Algorithm evaluates a policy by adjusting the weights of a differentiable value-function approximation. It generates a complete episode using policy π. For each nonterminal time step t, it takes the return Gₜ from that episode and compares it with the current approximation v̂(Sₜ, θ). The resulting difference is combined with the gradient of the approximation, scaled by α, and added to the parameter vector θ.
θ ← θ + α [Gₜ − v̂(Sₜ, θ)] ∇v̂(Sₜ, θ)
One State and One Return
Apply the Gradient Monte Carlo parameter update to one visited state Sₜ when the current estimate is v̂(Sₜ, θ), the observed return is Gₜ, the gradient is ∇v̂(Sₜ, θ), and the step size is α.
Compute the difference: Find Gₜ − v̂(Sₜ, θ). A positive difference means the return is above the current estimate; a negative difference means it is below the estimate.
Combine with the gradient: Multiply the difference by ∇v̂(Sₜ, θ), which identifies how the parameters affect the approximation at Sₜ.
Scale the change: Multiply by α to control the size of the parameter adjustment.
Update the weights: Add the resulting adjustment to θ.
The new parameter vector is θ plus α times the return-estimate difference times the approximation gradient.
Why the Return Can Teach
The Gradient Monte Carlo Algorithm does not first need the exact value of Sₜ. It obtains a sample return Gₜ from a completed episode and uses that return as a target. Gₜ is an unbiased estimate of vπ(Sₜ) because the true state value is the expected return after that state. A single return can differ from the true value, but across repeated episodes the returns average to the true value in expectation.
What do you think happens?
If one sampled return Gₜ is higher than the current estimate v̂(Sₜ, θ), should the update push the approximation upward at that state?
Reveal answer
Answer: Yes, because the return-estimate difference is positive.
The update uses the difference between Gₜ and v̂(Sₜ, θ). A positive difference contributes an adjustment in the direction given by the approximation gradient, scaled by α.
Convergence Conditions
The convergence guarantee is conditional. If the target Uₜ is unbiased for the policy value at every time step, meaning E[Uₜ] = vπ(Sₜ), and the step size α decreases according to the usual stochastic approximation conditions, then the parameter sequence θₜ is guaranteed to converge to a local optimum.
Common Backup Mistakes
Treating the backup notation as if it specifies a particular algorithm.
The notation identifies the state being backed up and its target, but Monte Carlo, TD(0), n-step TD, and dynamic programming can use different targets.
Fix:
After identifying s and g, determine how g was obtained.Confusing the current estimate with the target.
For Gradient Monte Carlo, Gₜ is the target and v̂(Sₜ, θ) is the current approximation being corrected.
Fix:
Label the return as the target and compare it with the current estimate.Thinking a Gradient Monte Carlo update directly replaces a state value.
The differentiable approximation is represented by parameters, so the algorithm changes θ using the approximation gradient.
Fix:
Apply the parameter update involving the return-estimate difference, α, and the gradient.Forgetting that the convergence result is conditional.
The guarantee requires an unbiased target and a decreasing step size satisfying the usual stochastic approximation conditions.
Fix:
State both conditions when stating the convergence guarantee.
Check Your Understanding
For each item, identify the state being backed up and the target being used. Then explain whether the target comes from a complete episode, a one-step sampled transition, an n-step return, or an expected model-based calculation.
Hints
- In s ↦→ g, read the symbol on the left as the state and the symbol on the right as the target.
- Match Gₜ with Monte Carlo, Rₜ₊₁ + γ v̂(Sₜ₊₁, θₜ) with TD(0), and G⁽ⁿ⁾ₜ with n-step TD.
- For dynamic programming policy evaluation, look for the expected target under policy π.
Explain in your own words why a single Gₜ can be used to improve an approximate value even though it may not equal vπ(Sₜ). Include the meaning of unbiasedness in your answer.
Hints
- The true state value is the expected return after the state.
- A single sampled return can vary, while its expectation equals the true state value.
- The Gradient Monte Carlo update uses the difference between Gₜ and the current approximation.
Key Takeaways
- A backup shifts an estimated value for a state toward a backed-up value or target.
- In s ↦→ g, s is the state being backed up and g is the target.
- Monte Carlo uses Gₜ, TD(0) uses Rₜ₊₁ + γ v̂(Sₜ₊₁, θₜ), and n-step TD uses G⁽ⁿ⁾ₜ.
- Dynamic programming uses an expected target under policy π, while experience-based methods use targets obtained from sampled experience.
- Gradient Monte Carlo uses complete-episode returns to update the parameters of a differentiable value-function approximation.
- The convergence guarantee requires unbiased targets and step sizes satisfying the usual stochastic approximation conditions; under those conditions, the parameters converge to a local optimum.
Key Takeaways
- A backup is an update that shifts an estimated state value toward a target.
- The notation s ↦→ g identifies the state s and the target g, not a particular prediction algorithm.
- Monte Carlo, TD(0), and n-step TD differ mainly in how they construct their targets.
- Gradient Monte Carlo uses episode returns as unbiased targets and changes approximation parameters rather than directly replacing a table entry.
- With unbiased targets and suitable decreasing step sizes, the parameter sequence is guaranteed to converge to a local optimum.