Concepts / Differential Reward Estimation

Differential Reward Estimation

Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with differential reward estimation.

  • Programming

Why Two Estimates Matter

Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with differential reward estimation. Instead of maintaining only the value-function weights θ, the algorithm also maintains an average-reward estimate R̄. Its central control-flow question is not simply whether a reward has been observed. The algorithm must first determine which earlier estimate is ready to update, represented by the index τ, and then check whether τ is nonnegative.

Key point

A valid update uses the same temporal-difference error δ in two places: it changes R̄ and it changes θ.

The Algorithm’s Moving Parts

The algorithm maintains two kinds of information. The value-function weights θ support the value estimate q̂, while R̄ estimates the average reward. At each time step, the control flow includes action selection, observation of a reward and next state, selection of the next action, identification of an earlier estimate that is ready to update, and an update if τ is nonnegative.

Action selectionReward and next stateNext actionτearlier estimaten-step returnn adjusted reward termsδtemporal-difference errorR̄average-reward updateθvalue-function updatetake actionselectidentify ready estimateconstructcalculateapply βδapply αδ∇q̂
What happens from action selection through reward observation, n-step return construction, temporal-difference calculation, and parameter updates?

Delayed Eligibility at τ

The index τ identifies which earlier estimate is ready to update after the algorithm has collected the information required for the n-step calculation. The algorithm computes τ first and then tests the condition τ ≥ 0. If the condition is true, the update is allowed. If the condition is false, the update is skipped for that point in the control flow.

Time stepτcomputed firstτ ≥ 0Updateδ changes R̄ and θSkipno update at this pointsteptestyesno
How does the algorithm determine whether an earlier estimate is eligible for updating?
Worked example

Checking the Update Gate

Suppose a trace reaches the point where τ has already been computed. Determine whether the parameter update is allowed when τ is nonnegative and when τ is negative.

  1. 1
    Compute τ

    The algorithm identifies the earlier estimate that is ready to update before making the eligibility decision.

  2. 2
    Test the condition

    The update condition is τ ≥ 0.

  3. 3
    Apply or skip

    A nonnegative τ permits the update. A negative τ means the update is skipped at that point.

Result

The sign of τ controls whether the update stage is entered; it does not itself change R̄ or θ.

Building the Differential Error

When an update is allowed, the algorithm calculates the temporal-difference error δ from an n-step return. The error uses n reward terms, and those reward terms are adjusted by the current average-reward estimate R̄. This is the differential part of the method: the reward information used by the n-step calculation is interpreted relative to the current estimate of average reward.

Sτ, Aτestimate being updatedReward term 1adjusted by R̄Reward term nadjusted by R̄Later state-actioninformationpart of n-step calculationδtemporal-difference errorestimate against returnn-step termn-step termn-step information
How do rewards and later state-action information map back to the earlier state-action estimate selected by τ?
Key point

The n-step calculation is delayed with respect to the earlier estimate it updates. The important trace relationship is that the collected n-step reward information is used to calculate δ for the estimate associated with τ.

One Error, Two Parameter Updates

Formula
Formula

After δ has been calculated, the algorithm uses it twice. First, R̄ changes by βδ. Second, θ changes by αδ multiplied by the gradient of the estimated action value for the state-action pair selected by τ. The symbols α and β are different because the algorithm specifies separate positive step sizes for the value-function weights and the average-reward estimate.

δone temporal-differenceerrorβδaverage-reward adjustmentR̄updated estimateαδ∇q̂value-function adjustmentθupdated weightsscale by βaddscale by α and gradientadd
How does the same temporal-difference error δ change the average-reward estimate and the value-function weights?
Worked example

Tracing a Permitted Update

Trace the parameter stage after a valid update has produced a temporal-difference error δ.

  1. 1
    Start with δ

    The error has been calculated from the n-step reward terms adjusted by the current R̄.

  2. 2
    Update R̄

    Apply R̄ ← R̄ + βδ. This changes the average-reward estimate.

  3. 3
    Update θ

    Apply θ ← θ + αδ ∇q̂(Sτ, Aτ, θ). This changes the value-function weights associated with the selected state-action estimate.

  4. 4
    Check the shared input

    Both updates use the same δ, but they use different update expressions and separate step sizes.

Result

A valid update changes both R̄ and θ; changing only one of them does not match the stated update sequence.

Ordinary and Differential n-Step Sarsa

AspectSemi-gradient n-step SarsaDifferential semi-gradient n-step Sarsa
Base methodUses semi-gradient n-step Sarsa updatesExtends semi-gradient n-step Sarsa
Additional estimateThe source description does not identify an average-reward estimateMaintains the average-reward estimate R̄
Reward treatmentThe source description does not identify differential reward adjustmentUses n reward terms adjusted by the current R̄
Parameter update described in this topicThe source description does not identify a second update to R̄A valid update changes both R̄ and θ

The differential method adds average-reward estimation to the semi-gradient n-step Sarsa process described in the source.

Semi-gradientn-step Sarsabase methodθ updatebase updateDifferential methodextensionR̄average-reward estimateAdjusted rewardsn reward termsR̄ and θvalid update changes bothusesmaintainsusesupdates
What additional estimate and computation does differential semi-gradient n-step Sarsa introduce compared with ordinary semi-gradient n-step Sarsa?

Reading an Expected Trace

A useful trace follows the algorithm in stages rather than treating the update as one indivisible operation. First record the selected action. Then record the observed reward and next state. Next record the selected next action and the computed τ. Only after checking τ ≥ 0 should the trace show the n-step return, the temporal-difference error δ, and the two parameter updates.

Trace stageWhat to look for
Action selectionAn action is taken.
ObservationA reward and next state are observed.
Next actionThe next action is selected.
Index calculationτ is computed before the update decision.
Eligibility testThe algorithm checks whether τ ≥ 0.
n-step calculationn reward terms are adjusted by the current R̄.
Error calculationδ is calculated.
Parameter updatesR̄ and θ are both updated when the update is valid.

Use this order when comparing an implementation or worked trace with the algorithm.

What do you think happens?

If a trace shows a calculated δ but only θ changes, does that represent a complete valid update?

  • Yes, because θ is the value-function parameter

  • No, because a valid update changes both R̄ and θ

  • Yes, if the reward was observed

  • No, because δ must always be zero

Reveal answer
Answer:

No, because a valid update changes both R̄ and θ.

The algorithm uses δ first in R̄ ← R̄ + βδ and then in θ ← θ + αδ ∇q̂(Sτ, Aτ, θ).

Diagnosing Trace Divergence

When a result differs from the expected algorithmic trace, compare the trace stage by stage. The source emphasizes the order of τ computation, the τ ≥ 0 condition, the n reward terms adjusted by R̄, and the use of δ in both parameter updates. A discrepancy at any of these points can change the later result.

  • Common mistake

    Updating before computing τ

    What it looks like

    The trace performs an update immediately after observing a reward and next state.

    Why it fails

    The algorithm computes τ before deciding whether an update is possible.

    Do this instead

    Record τ first, then test τ ≥ 0.

  • Common mistake

    Ignoring the τ ≥ 0 gate

    What it looks like

    The trace updates R̄ and θ even when τ is negative.

    Why it fails

    A valid update is allowed only when τ is nonnegative.

    Do this instead

    Skip the update when τ is negative.

  • Common mistake

    Using unadjusted reward terms

    What it looks like

    The n-step calculation uses reward terms without accounting for the current R̄.

    Why it fails

    The temporal-difference error uses n reward terms adjusted by the current average-reward estimate.

    Do this instead

    Check that the current R̄ is used when forming the n-step calculation.

  • Common mistake

    Updating only θ

    What it looks like

    The trace shows θ changing but leaves R̄ unchanged after a valid update.

    Why it fails

    The same δ is used to update both the average-reward estimate and the value-function weights.

    Do this instead
    Apply both R̄ ← R̄ + βδ and θ ← θ + αδ ∇q̂(Sτ, Aτ, θ).
  • Common mistake

    Confusing α and β

    What it looks like

    The same step-size symbol is used for both parameter updates.

    Why it fails

    The algorithm specifies α and β separately as positive step sizes.

    Do this instead

    Keep the R̄ update associated with β and the θ update associated with α.

ActionReward and next stateτindex calculationτ ≥ 0eligibility conditionAdjusted rewardsn termsδerror calculationR̄ and θboth updatesobservecontinue tracetestallowedcalculateupdate both
At which control-flow step, index calculation, reward target, or parameter update could an implementation first diverge from the expected trace?

Trace Practice

MEDIUM

Write the expected control-flow order for one update attempt. Your sequence should include action selection, reward and next-state observation, next-action selection, τ computation, the τ ≥ 0 test, n-step return construction using reward terms adjusted by R̄, δ calculation, and both parameter updates when the condition is satisfied.

Hints
  • The algorithm computes τ before deciding whether an update is possible.
  • The same δ is used in both parameter updates.
  • Use β with the R̄ update and α with the θ update.
Worked example

Self-Check for a Trace

A trace contains these events in order: action selection, reward and next-state observation, next-action selection, τ computation, τ ≥ 0 test, n-step calculation, δ calculation, R̄ update, and θ update. Decide whether this ordering matches the described control flow.

  1. 1
    Compare the early stages

    Action selection, observation, and next-action selection appear before the index decision.

  2. 2
    Check τ

    τ is computed before the condition τ ≥ 0 is tested.

  3. 3
    Check the error inputs

    The n-step calculation appears before δ, and its reward terms are intended to be adjusted by the current R̄.

  4. 4
    Check the updates

    After δ, the trace updates R̄ and then θ, matching the two stated update rules.

Result

The ordering matches the described control flow, provided the update stage is entered only when τ ≥ 0.

Key Takeaways

  1. 1
    Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with average-reward estimation.
  2. 2
    The algorithm computes τ before deciding whether an update is possible.
  3. 3
    The update is allowed when τ ≥ 0; otherwise the update is skipped at that point.
  4. 4
    The temporal-difference error δ is formed from n reward terms adjusted by the current R̄.
  5. 5
    A valid update changes both R̄ and θ, using separate positive step sizes β and α.

At a glance

  • Differential semi-gradient n-step Sarsa adds average-reward estimation to semi-gradient n-step Sarsa.
  • τ is computed before the algorithm tests whether an update can occur.
  • Only τ ≥ 0 permits the update stage.
  • The same δ updates R̄ through βδ and θ through αδ ∇q̂(Sτ, Aτ, θ).
  • When debugging a trace, inspect the order of τ computation, eligibility testing, reward adjustment, δ calculation, and both parameter updates.

Related Topics

Related concepts

More concepts starting with D