Semi-gradient n-Step Sarsa
Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with differential reward estimation.
Why the Update Is Delayed
Differential semi-gradient n-step Sarsa does not update the value estimate immediately after every action. It first follows the control flow of the algorithm: take an action, observe and store the next reward and state, select and store the next action, and compute τ. Only then does it decide whether an earlier estimate is ready for an update. The condition τ ≥ 0 is the checkpoint that permits the update.
The central control-flow rule is simple: when τ is negative, no δ, R̄, or θ update is calculated; when τ is nonnegative, the algorithm calculates δ and performs both parameter updates.
Control Flow Across Time
At each time step, the algorithm advances the experience sequence before deciding whether to update. The current action leads to a reward and next state. A next action is selected and stored. The algorithm then identifies which earlier state-action estimate is ready by computing τ = t − n + 1. This makes the method an n-step procedure: information from several time steps is used before the earlier estimate is changed.
The visual shows that selecting an action and storing new experience happen before the update decision. A common implementation error is to place the τ check too early, before the reward, next state, or next action has been stored.
The Delayed Update Check
The algorithm computes τ using τ = t − n + 1. This value identifies the earlier time index whose estimate may now be updated. The update is blocked while τ is negative. Once τ reaches zero or becomes positive, the algorithm is allowed to calculate the temporal-difference error and update its estimates.
Checking Update Eligibility
An implementation has computed τ from τ = t − n + 1. Trace what happens when the result is negative, then trace what changes when the result is nonnegative.
Negative τ: The earlier estimate is not ready. The loop continues without calculating δ and without changing R̄ or θ.
Nonnegative τ: The earlier estimate is ready. The algorithm calculates δ and proceeds to update R̄ followed by θ.
Debugging implication: If an implementation updates while τ is negative, the first divergence is at the τ ≥ 0 checkpoint.
The sign of τ determines whether the update portion of the control flow is entered.
How δ Reaches Both Estimates
When τ is nonnegative, the temporal-difference error δ combines n reward terms adjusted by the current average-reward estimate with later and earlier action-value estimates. The same δ then has two destinations. First, the average-reward estimate changes according to R̄ ← R̄ + βδ. Second, the value-function weights change according to θ ← θ + αδ ∇q̂(Sτ, Aτ, θ).
| Symbol | Role in the update |
|---|---|
| δ | Temporal-difference error used by both updates |
| R̄ | Average-reward estimate changed using βδ |
| θ | Value-function weights changed using αδ and the gradient |
| α | Step size for the value-function weight update |
| β | Step size for the average-reward update |
| ∇q̂(Sτ, Aτ, θ) | Gradient of the differentiable action-value function at the earlier state-action pair |
The two update destinations use separate step sizes and different update expressions.
The order is also part of the specified control flow: update R̄ first, then update θ. The symbols α and β are separate because the algorithm specifies separate positive step sizes for the value-function weights and the average-reward estimate.
Tracing a Complete Update
Consider a generated trace in which the loop has just stored a reward, next state, and next action. The algorithm now computes τ. Suppose τ is nonnegative. The trace enters the update branch: the n reward terms and the relevant action-value estimates are combined with the current R̄ to form δ, R̄ is changed using βδ, and θ is then changed using αδ and the gradient at (Sτ, Aτ).
Following the Update Branch
Trace the order of operations after the algorithm has selected and stored the next action and has found that τ is nonnegative.
Calculate the temporal-difference error: Use the n reward terms adjusted by the current average-reward estimate together with the later and earlier action-value estimates.
Update the average reward: Apply R̄ ← R̄ + βδ.
Update the value weights: Apply θ ← θ + αδ ∇q̂(Sτ, Aτ, θ).
Preserve the order: The average-reward estimate is updated before the value-function weights.
A valid update changes both R̄ and θ, using the same δ but different step sizes and update expressions.
A trace that changes θ but leaves R̄ unchanged is incomplete. A trace that changes R̄ but leaves θ unchanged is also incomplete when τ ≥ 0.
Debugging Control-Flow Divergence
When a result differs from the expected algorithmic trace, locate the first control-flow checkpoint where the implementation differs from the pseudocode. Check the sequence rather than inspecting only the final numerical update. The likely checkpoints are action selection, reward and state storage, next-action storage, τ calculation, the τ ≥ 0 condition, δ calculation, and the ordered updates to R̄ and θ.
Updating before checking whether τ is nonnegative.
The algorithm delays updates until τ is nonnegative.
Fix:
Compute τ first and continue without calculating δ, R̄, or θ updates when τ < 0.Skipping the next-action step in the trace.
The specified loop selects and stores the next action before deciding whether an update is available.
Fix:
Check that next-action selection occurs before the τ checkpoint.Updating only the value-function weights.
A valid update changes both the average-reward estimate and the value-function weights.
Fix:
After calculating δ, update R̄ first and θ second.Using one step size for both destinations without matching the specified updates.
The algorithm specifies separate positive step sizes α and β for the two updates.
Fix:
Use β in R̄ ← R̄ + βδ and α in θ ← θ + αδ ∇q̂(Sτ, Aτ, θ).Changing the update order.
The pseudocode explicitly updates the average-reward estimate first, followed by the value-function weights.
Fix:
Preserve the order R̄ update, then θ update.
An expected trace shows action selection, reward and state storage, next-action selection, τ calculation, and then an update. Your implementation shows the same first three steps but updates θ before checking τ ≥ 0. Identify the first divergent control-flow step and state what should happen instead.
Hints
- The algorithm computes τ before deciding whether an update is possible.
- When τ is negative, no δ, R̄, or θ update is calculated.
- When τ is nonnegative, R̄ is updated before θ.
Practical Trace Checklist
- Confirm that an action is taken at the current time step.
- Confirm that the next reward and state are observed and stored.
- Confirm that the next action is selected and stored.
- Recalculate τ using τ = t − n + 1.
- If τ < 0, verify that the loop continues without calculating δ or changing R̄ and θ.
- If τ ≥ 0, verify that δ uses the n reward terms adjusted by the current R̄ and the relevant action-value estimates.
- Verify that R̄ is updated with βδ before θ is updated with αδ and the gradient.
What to Remember
- Differential semi-gradient n-step Sarsa extends semi-gradient n-step Sarsa with differential reward estimation.
- The algorithm computes τ = t − n + 1 before deciding whether an update is available.
- When τ is negative, it continues without calculating δ or updating R̄ and θ.
- When τ is nonnegative, the same δ updates both R̄ and θ.
- The specified update order is R̄ first, then θ, and the first control-flow divergence is the most useful place to debug.
Key Takeaways
- Differential semi-gradient n-step Sarsa combines delayed n-step action-value updates with average-reward estimation.
- The condition τ ≥ 0 controls whether the algorithm enters the update branch.
- The temporal-difference error δ changes R̄ using βδ and θ using αδ with the action-value gradient.
- Rewards, states, and actions must be stored before the delayed update decision.
- To debug a divergent trace, find the first control-flow checkpoint that differs from the pseudocode.