n-Step Semi-Gradient Sarsa for Control
The algorithm separates the current environment time t from the delayed update time τ.
Why the Update Is Delayed
Episodic semi-gradient n-step Sarsa estimates action values while an episode unfolds. The algorithm does not necessarily update the state-action pair associated with the action being taken at the current environment time. Instead, it stores states, actions, and rewards, waits until enough experience is available to form an n-step return, and then updates an eligible earlier estimate.
The central timing distinction is between t, the current environment time, and τ, the delayed update time. The current time tells the algorithm where experience collection has reached. The delayed time identifies which stored state-action estimate is ready to update.
The Two Time Indices
At environment time t, the algorithm has just progressed to a particular point in the episode and can collect another transition. The update time is calculated as τ = t − n + 1. This makes τ earlier than t when the algorithm is waiting for an n-step return. Early in the episode, τ can be negative, which means that no stored state-action pair is yet eligible for updating.
Finding the Updated Pair
Suppose the algorithm is using n = 3 and has reached environment time t = 4. Which stored estimate does the update time identify?
Calculate τ: Use τ = t − n + 1. With t = 4 and n = 3, τ = 2.
Interpret τ: The update is associated with the stored state-action pair at time 2, not automatically with the pair at the current environment time 4.
Check eligibility: Because τ is at least zero, an eligible stored state-action pair exists for this update.
The update targets the state-action estimate associated with time 2 while the environment has advanced to time 4.
Building the n-Step Return
Once τ is eligible, the algorithm constructs the n-step return G for the state-action pair at time τ. The return combines the rewards beginning with Rτ+1 and continuing through Rmin(τ+n,T), with discounting applied to those rewards. If τ + n is less than T, the return also includes a bootstrap estimate at the later time τ + n. If the episode has already reached its terminal time before that point, the return is formed from the available rewards without that later bootstrap condition.
G = Rτ+1 + γRτ+2 + … + γ^(min(τ+n,T)−τ−1)Rmin(τ+n,T) + [γ^n Q̂(Sτ+n, Aτ+n) when τ+n < T]
A Return Near the End of an Episode
Suppose an update is selected at τ and the episode terminates at T before τ + n. What determines G?
Limit the reward range: The rewards included in G stop at Rmin(τ+n,T), so the terminal time limits the available sequence.
Apply discounting: The included rewards are combined with their appropriate discount factors.
Check the bootstrap condition: Because τ + n is not less than T in this situation, the later bootstrap estimate is not included by the stated condition.
Near the terminal end of an episode, G uses the available discounted rewards and does not add the bootstrap estimate when τ + n is not less than T.
Updating the Weight Vector
After G has been constructed, the semi-gradient rule adjusts the weight vector θ using the difference between the target G and the current estimated action value for the state-action pair selected by τ. The update therefore has three ingredients: the n-step target G, the current estimate for the stored pair at τ, and the feature information used by the weight-vector representation.
θ ← θ + α [G − Q̂(Sτ,Aτ)] ∇θ Q̂(Sτ,Aτ)
The update is semi-gradient because the adjustment uses the difference between G and the current estimate while following the gradient of the estimated action value with respect to θ. The target G is treated as the return used to correct the estimate.
Terminal Timing and Pending Work
When the terminal state is reached, the algorithm records the terminal time T. That changes how later returns are bounded: the reward range ends at the terminal time, and the bootstrap estimate is included only when τ + n is less than T. Reaching T does not mean that every earlier state-action estimate has already been updated. Delayed updates associated with eligible τ values still need to be processed using the experience that has been collected.
Implementation Checks
Updating before τ is eligible.
A negative τ does not identify an eligible stored state-action pair for the delayed update.
Fix:
Perform the update only when τ is at least zero.Updating the current time instead of the delayed time.
The current action is not necessarily the state-action estimate whose n-step return is now available.
Fix:
Use the stored state and action associated with τ.Ignoring the terminal time when constructing G.
The return is bounded by min(τ+n,T), and bootstrapping is conditional on τ+n being less than T.
Fix:
Use T to limit the rewards and apply the stated bootstrap condition.Discarding all delayed updates when T is set.
Earlier eligible state-action pairs may still have delayed updates waiting to be applied.
Fix:
Continue processing the eligible delayed updates using the terminal-bounded returns.Changing the order of the main operations.
The update depends on the delayed index and its corresponding n-step return.
Fix:
Preserve the order: initialize, collect experience, calculate τ, form G for eligible τ, and update θ.
When reviewing an implementation, write down the meaning of every index beside the corresponding operation. Mark t as the current environment time, τ as the delayed update time, and T as the terminal time. Then verify that the return uses the τ-based reward range and that θ is updated only for an eligible τ.
Trace It Yourself
An episodic n-step Sarsa process has reached t = 5 with n = 4. Determine τ, decide whether an update is eligible, and state which stored state-action pair is selected. Then suppose the episode terminal time satisfies T = 6. Identify the final reward index used in G and decide whether the bootstrap condition τ + n < T is true.
Hints
- First calculate τ = t − n + 1.
- Compare τ with zero before selecting the stored pair.
- The final reward index is min(τ+n,T).
- Check the bootstrap condition separately from the reward limit.
What do you think happens?
With t = 5 and n = 4, what is τ and is the update eligible?
Reveal answer
Answer: τ = 2, so the update is eligible.
Using τ = t − n + 1 gives τ = 5 − 4 + 1 = 2. Since τ is at least zero, the stored state-action pair at time 2 is eligible.
- The algorithm's control flow is a timing discipline: collect experience at t, calculate τ = t − n + 1, wait until τ is at least zero, construct G from the terminal-bounded discounted reward sequence and a conditional bootstrap estimate, and then adjust θ for the state-action pair at τ.
Key Takeaways
- n-step semi-gradient Sarsa separates the current environment time t from the delayed update time τ.
- The delayed index is τ = t − n + 1, and an update occurs only when τ is at least zero.
- The n-step return G uses discounted rewards through min(τ+n,T) and includes a bootstrap estimate only when τ+n is less than T.
- The semi-gradient update adjusts θ using the difference between G and the current estimated action value for the pair at τ.
- Reaching terminal time T limits return construction but does not eliminate pending delayed updates.