Concepts / Q-value estimation

Q-value estimation

Off-policy n-step Q(σ) separates the policy that generates experience from the policy whose value estimates are learned or evaluated.

  • Programming

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.

Behavior policy μselects actionsEpisodestates, actions, rewardsPolicy ratiosoff-policy weightingQ-valuesupdated estimateTarget policy πvalue estimates learnedgeneratesstores policy informationconnects target roleweights updatesupplies n-step information
How does the behavior policy generate experience while the target policy determines which Q-values are learned, and where do policy ratios connect them?

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.

StatesSτ, Sτ+1, ...Return accumulator Greads delayed informationActionsAτ, Aτ+1, ...Rewardsobserved rewardsTD errorsδτ, δτ+1, ...Policyprobabilitiesstored policy informationPolicy ratiosoff-policy factorshelps computeprovides value contextidentifies estimateaccumulatecarry off-policy weightingsupport policy correction
Where are states, actions, rewards, temporal-difference errors, and policy ratios stored at each time step, and which later calculation reads them?

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.

Worked example

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?

  1. 1
    Compute the update time

    Use τ = t − n + 1.

  2. 2
    Check readiness

    The delayed update can proceed when τ is at least zero.

  3. 3
    Select the stored pair

    The correction is applied to Q(Sτ, Aτ), the estimate associated with the earlier state and action at time τ.

Result

The current loop time t determines which earlier state-action estimate receives the n-step correction.

Loop time tcurrent stepτ = t − n + 1candidate update timeτ ≥ 0update ready?Q(Sτ, Aτ)estimate to correctcalculatetestyes
How does the current loop time identify the earlier state-action pair that is ready for an 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.

G = Qτinitial accumulatorδτfirst permitted errorEeligibility factorGaccumulated returnδτ+1next permitted errorρoff-policy factorδkthrough min(τ+n−1,T−1)processcontinuecontinue through rangecarry throughcarry throughcomplete accumulation
How are rewards and successive temporal-difference errors combined over multiple steps to accumulate the n-step return G?
Worked example

Tracing the accumulator

Trace the order of operations for one selected update time τ without assuming particular numeric rewards or Q-values.

  1. 1
    Initialize

    Begin with G equal to Qτ, E equal to 1, and ρ equal to 1.

  2. 2
    Set the range

    Use k from τ through the earlier of τ + n − 1 and T − 1.

  3. 3
    Read each stored error

    Process the stored temporal-difference error for each permitted k. Each error contributes to the ongoing construction of G.

  4. 4
    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.

Result

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.

Q(Sτ, Aτ)current estimateαstep sizeQ(Sτ, Aτ)corrected estimateGn-step returnρoff-policy weightmove toward Gtarget informationcontrols sizeweights correction
How does the accumulated return G change one selected state-action pair, and which step-size and current estimate are used?
Worked example

Tracing a complete selected update

Explain what must be known before changing Q(Sτ, Aτ).

  1. 1
    Identify the pair

    Use τ = t − n + 1 to identify the earlier state-action pair.

  2. 2
    Confirm the return inputs

    Check the stored temporal-difference errors in the permitted k range and reconstruct G from its initial value Qτ.

  3. 3
    Confirm the weighting inputs

    Check the evolving eligibility factor E and off-policy factor ρ.

  4. 4
    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.

Result

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.

Episode boundarycheck TUpdate time τt − n + 1TD errors δstored sequencek rangepermitted indicesE and ρevolving factorsQ updatefinal expressionthenthenthenthenthen
In what order should stored rewards, states, actions, TD errors, policy ratios, and intermediate returns be checked to locate where a result diverged from expectation?
  • Common mistake

    Treating μ and π as if they had the same role

    What it looks like

    Assuming the policy that selected an observed action is automatically the policy whose Q-values are being evaluated.

    Why it fails

    Off-policy n-step Q(σ) explicitly separates the experience-generating behavior policy μ from the target policy π.

    Do this instead

    Track μ as the policy used to select actions and π as the policy whose value estimates are learned or evaluated.

  • Common mistake

    Updating the wrong state-action pair

    What it looks like

    Using the current loop time t as the update index instead of calculating τ = t − n + 1.

    Why it fails

    The delayed update is indexed by τ, which identifies the earlier state-action pair receiving the n-step correction.

    Do this instead

    Calculate τ and verify that it is nonnegative before selecting Q(Sτ, Aτ).

  • Common mistake

    Skipping part of the permitted error range

    What it looks like

    Using only one stored temporal-difference error when several k values fall between τ and the earlier of τ + n − 1 and T − 1.

    Why it fails

    G is changed once for every permitted k in that range.

    Do this instead

    Check the complete k range and inspect every stored δ value used by the accumulator.

  • Common mistake

    Checking G but not E or ρ

    What it looks like

    Concluding that the return is correct without checking the eligibility factor or off-policy factor.

    Why it fails

    E affects later contributions, while ρ affects the size of the final Q-value correction.

    Do this instead

    Trace G, E, and ρ together from initialization through the permitted range.

Practice trace

MEDIUM

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τ)?

  • Yes, because every loop time produces an update

  • No, because the delayed update is processed only when τ is nonnegative

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

  1. 1
    The behavior policy μ generates the episode, while the target policy π is the policy whose value estimates are learned or evaluated.
  2. 2
    The episode stores states, actions, rewards, temporal-difference errors, policy probabilities, and policy ratios for later calculations.
  3. 3
    The delayed update time is τ = t − n + 1, and the selected estimate is Q(Sτ, Aτ) when τ is nonnegative.
  4. 4
    G starts at Qτ and is accumulated across the permitted temporal-difference errors while E and ρ are carried through the same range.
  5. 5
    To debug an unexpected result, inspect T, τ, the stored δ values, the k range, E, ρ, and the final Q update in that order.

At a glance

  • μ 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.

Related Topics

Related concepts

More concepts starting with Q