Differential Reward Estimation
Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with differential reward estimation.
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.
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.
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.
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.
Compute τ: The algorithm identifies the earlier estimate that is ready to update before making the eligibility decision.
Test the condition: The update condition is τ ≥ 0.
Apply or skip: A nonnegative τ permits the update. A negative τ means the update is skipped at that point.
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.
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
R̄ ← R̄ + βδθ ← θ + αδ ∇q̂(Sτ, Aτ, θ)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.
Tracing a Permitted Update
Trace the parameter stage after a valid update has produced a temporal-difference error δ.
Start with δ: The error has been calculated from the n-step reward terms adjusted by the current R̄.
Update R̄: Apply R̄ ← R̄ + βδ. This changes the average-reward estimate.
Update θ: Apply θ ← θ + αδ ∇q̂(Sτ, Aτ, θ). This changes the value-function weights associated with the selected state-action estimate.
Check the shared input: Both updates use the same δ, but they use different update expressions and separate step sizes.
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
| Aspect | Semi-gradient n-step Sarsa | Differential semi-gradient n-step Sarsa |
|---|---|---|
| Base method | Uses semi-gradient n-step Sarsa updates | Extends semi-gradient n-step Sarsa |
| Additional estimate | The source description does not identify an average-reward estimate | Maintains the average-reward estimate R̄ |
| Reward treatment | The source description does not identify differential reward adjustment | Uses n reward terms adjusted by the current R̄ |
| Parameter update described in this topic | The source description does not identify a second update to R̄ | A valid update changes both R̄ and θ |
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 stage | What to look for |
|---|---|
| Action selection | An action is taken. |
| Observation | A reward and next state are observed. |
| Next action | The next action is selected. |
| Index calculation | τ is computed before the update decision. |
| Eligibility test | The algorithm checks whether τ ≥ 0. |
| n-step calculation | n reward terms are adjusted by the current R̄. |
| Error calculation | δ is calculated. |
| Parameter updates | R̄ 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?
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.
Updating before computing τ
The algorithm computes τ before deciding whether an update is possible.
Fix:
Record τ first, then test τ ≥ 0.Ignoring the τ ≥ 0 gate
A valid update is allowed only when τ is nonnegative.
Fix:
Skip the update when τ is negative.Using unadjusted reward terms
The temporal-difference error uses n reward terms adjusted by the current average-reward estimate.
Fix:
Check that the current R̄ is used when forming the n-step calculation.Updating only θ
The same δ is used to update both the average-reward estimate and the value-function weights.
Fix:
Apply both R̄ ← R̄ + βδ and θ ← θ + αδ ∇q̂(Sτ, Aτ, θ).Confusing α and β
The algorithm specifies α and β separately as positive step sizes.
Fix:
Keep the R̄ update associated with β and the θ update associated with α.
Trace Practice
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.
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.
Compare the early stages: Action selection, observation, and next-action selection appear before the index decision.
Check τ: τ is computed before the condition τ ≥ 0 is tested.
Check the error inputs: The n-step calculation appears before δ, and its reward terms are intended to be adjusted by the current R̄.
Check the updates: After δ, the trace updates R̄ and then θ, matching the two stated update rules.
The ordering matches the described control flow, provided the update stage is entered only when τ ≥ 0.
Key Takeaways
- Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with average-reward estimation.
- The algorithm computes τ before deciding whether an update is possible.
- The update is allowed when τ ≥ 0; otherwise the update is skipped at that point.
- The temporal-difference error δ is formed from n reward terms adjusted by the current R̄.
- A valid update changes both R̄ and θ, using separate positive step sizes β and α.
Key Takeaways
- 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.