Q-value estimation
Off-policy n-step Q(σ) separates the policy that generates experience from the policy whose value estimates are learned or evaluated.
Two policies, two jobs
Off-policy n-step Q(σ) separates the policy that generates experience from the policy whose value estimates are learned or evaluated. The behavior policy μ selects the actions used to generate an episode. The target policy π is the policy whose Q-values the procedure learns or evaluates. The algorithm connects these roles through stored policy information and policy ratios.
What the episode stores
The procedure processes an episode step by step. It stores an initial state and action, then repeatedly takes the current action, observes a reward, and stores the next state. Each episode stores states, actions, rewards, temporal-difference errors, policy probabilities, and policy ratios. These stored quantities are later read by the delayed n-step update.
If the next state is terminal, the algorithm records the terminal time T and stores the temporal-difference error δt as the reward minus the current Q-value. If the next state is not terminal, it selects and stores the next action using μ, stores σt+1, stores the next Q-value, and computes δt using the reward, the next Q-value, the policy-weighted action values, and the current Q-value.
The delayed update time
The algorithm does not immediately apply every new observation to the state-action pair that began the episode segment. At loop time t, it defines the update time τ as t − n + 1. This identifies the earlier state-action pair that is ready to receive an n-step correction. An update is considered only when τ is nonnegative.
Finding the state-action pair to update
Suppose the algorithm is at loop time t and uses an n-step procedure. Which stored pair is selected for the delayed correction?
Compute the update time: Use τ = t − n + 1.
Check readiness: The delayed update can proceed when τ is at least zero.
Select the stored pair: The correction is applied to Q(Sτ, Aτ), the estimate associated with the earlier state and action at time τ.
The current loop time t determines which earlier state-action estimate receives the n-step correction.
Accumulating the n-step return
When τ is nonnegative, the algorithm initializes G to Qτ, E to 1, and ρ to 1. It then processes the available temporal-difference errors from k = τ through the earlier of τ + n − 1 and T − 1. The return accumulator is changed once for every k in this permitted range. E and ρ are carried through the same range, so the return construction and the off-policy weighting must be traced together.
Tracing the accumulator
Trace the order of operations for one selected update time τ without assuming particular numeric rewards or Q-values.
Initialize: Begin with G equal to Qτ, E equal to 1, and ρ equal to 1.
Set the range: Use k from τ through the earlier of τ + n − 1 and T − 1.
Read each stored error: Process the stored temporal-difference error for each permitted k. Each error contributes to the ongoing construction of G.
Carry the auxiliary quantities: Track E and ρ as the range is processed. A wrong E changes later contributions, while a wrong ρ changes the size of the final correction.
The n-step return is an ordered accumulation, not a single jump directly from the episode to a final value.
Applying the correction
After the n-step return has been assembled, the selected estimate is Q(Sτ, Aτ). The update uses the difference between G and the current estimate, scales the change with α, and includes ρ for the off-policy setting. In conceptual form, Q(Sτ, Aτ) moves toward G; α controls how large that movement is, while ρ weights the update.
Tracing a complete selected update
Explain what must be known before changing Q(Sτ, Aτ).
Identify the pair: Use τ = t − n + 1 to identify the earlier state-action pair.
Confirm the return inputs: Check the stored temporal-difference errors in the permitted k range and reconstruct G from its initial value Qτ.
Confirm the weighting inputs: Check the evolving eligibility factor E and off-policy factor ρ.
Apply the correction: Use the current Q estimate, the accumulated return G, α, and ρ. The result is a corrected estimate for the selected state-action pair.
A final Q-value is the endpoint of the stored episode data, the delayed index τ, the return accumulation, and the update weighting.
Debugging an unexpected result
When an implementation produces an unexpected Q-value, debug in execution order rather than inspecting only the final update. The order narrows the search: first establish the episode boundary, then confirm which delayed update is being attempted, then inspect the stored values used to build G, and only afterward inspect the final update expression.
Treating μ and π as if they had the same role
Off-policy n-step Q(σ) explicitly separates the experience-generating behavior policy μ from the target policy π.
Fix:
Track μ as the policy used to select actions and π as the policy whose value estimates are learned or evaluated.Updating the wrong state-action pair
The delayed update is indexed by τ, which identifies the earlier state-action pair receiving the n-step correction.
Fix:
Calculate τ and verify that it is nonnegative before selecting Q(Sτ, Aτ).Skipping part of the permitted error range
G is changed once for every permitted k in that range.
Fix:
Check the complete k range and inspect every stored δ value used by the accumulator.Checking G but not E or ρ
E affects later contributions, while ρ affects the size of the final Q-value correction.
Fix:
Trace G, E, and ρ together from initialization through the permitted range.
Practice trace
A trace shows a nonterminal next state, a stored next action selected using μ, several stored temporal-difference errors, and an unexpected final Q-value. Write the inspection order you would use to locate the divergence. Include the episode boundary, τ, the k range, G, E, ρ, and the final update inputs.
Hints
- Begin with T and the terminal or nonterminal episode condition.
- Calculate τ = t − n + 1 and check whether τ is at least zero.
- Inspect the stored δ values before inspecting the final Q update.
- Check E and ρ as they evolve across the same range used to accumulate G.
What do you think happens?
If τ is negative, should the algorithm immediately apply the delayed correction to Q(Sτ, Aτ)?
Reveal answer
Answer: No, because the delayed update is processed only when τ is nonnegative.
The update time is τ = t − n + 1, and the algorithm starts the delayed accumulation when τ is nonnegative.
Key takeaways
- The behavior policy μ generates the episode, while the target policy π is the policy whose value estimates are learned or evaluated.
- The episode stores states, actions, rewards, temporal-difference errors, policy probabilities, and policy ratios for later calculations.
- The delayed update time is τ = t − n + 1, and the selected estimate is Q(Sτ, Aτ) when τ is nonnegative.
- G starts at Qτ and is accumulated across the permitted temporal-difference errors while E and ρ are carried through the same range.
- To debug an unexpected result, inspect T, τ, the stored δ values, the k range, E, ρ, and the final Q update in that order.
Key Takeaways
- μ generates experience; π supplies the policy whose Q-values are learned or evaluated.
- The algorithm stores episode quantities so that a delayed state-action update can use information from several steps.
- τ identifies the earlier state-action pair, while G accumulates information from the permitted temporal-difference errors.
- E and ρ must be traced with G because they influence later contributions and the final correction.
- Unexpected results are best located by checking stored quantities in execution order.