Concepts / n-Step Semi-Gradient Sarsa for Control

n-Step Semi-Gradient Sarsa for Control

Episodic semi-gradient n-step Sarsa estimates action values while an episode unfolds.

  • Programming

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.

Key point

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.

EpisodeCollect experiencetτ = t − n + 1delayed indexτ ≥ 0eligible updateUpdate θstate-action at τTterminal timeDelayed updatesthrough terminal experiencebeginadvancetestyesepisode endscontinue pending work
How do the environment time t, delayed update time τ, terminal time T, and update condition interact during an episode?

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.

tcurrent environment timeSτstored stateτt − n + 1Aτstored actionQ̂(Sτ, Aτ)estimate updatedcalculateselectsselectsforms pairforms pair
Which state-action estimate is updated when the environment has advanced to a later time t?
Worked example

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?

  1. 1
    Calculate τ

    Use τ = t − n + 1. With t = 4 and n = 3, τ = 2.

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

  3. 3
    Check eligibility

    Because τ is at least zero, an eligible stored state-action pair exists for this update.

Result

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.

Formula, step by step
  1. 1
    Begin with the reward immediately after the update time, Rτ+1.
  2. 2
    Continue through the reward at min(τ+n,T), applying the appropriate discount to each later reward.
  3. 3
    Include the bootstrap estimate at τ+n only when τ+n is less than the terminal time T.
  4. 4
    Use this resulting G as the target for the current estimated action value.
Rτ+1first rewardRτ+2 … Rmin(τ+n,T)discounted rewardsτ+n < Tbootstrap conditionQ̂(Sτ+n,Aτ+n)bootstrap estimateGn-step targetdiscount and addthen testyesno bootstrap if falsediscount and add
How are rewards and a possible bootstrap estimate combined into the n-step return?
Worked example

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?

  1. 1
    Limit the reward range

    The rewards included in G stop at Rmin(τ+n,T), so the terminal time limits the available sequence.

  2. 2
    Apply discounting

    The included rewards are combined with their appropriate discount factors.

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

Result

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.

Formula, step by step
  1. 1
    Start with the current weight vector θ.
  2. 2
    Compute the difference between the n-step target G and the current estimated action value Q̂(Sτ,Aτ).
  3. 3
    Use the gradient of the estimated action value with respect to θ to identify the semi-gradient direction.
  4. 4
    Scale the adjustment by the step-size parameter α and add it to θ.
Sτ,Aτselected pairG − Q̂differenceθadjusted weightsQ̂(Sτ,Aτ)current valueθcurrent weightsGn-step targetevaluatecomparecomparescale and applyadjust
How do the selected state-action pair, target G, and current weight vector combine to update θ?
Key point

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.

Episode activeT not reachedAvailable rewardsthrough min(τ+n,T)θupdated from pending workTterminal timeEligible τ valuesdelayed updatesterminal state reachedlimits returndoes not eraseprocess
What changes at terminal time T, and which delayed updates remain after the terminal state is reached?

Implementation Checks

  • Common mistake

    Updating before τ is eligible.

    What it looks like

    Applying an update when τ is negative during the early part of the episode.

    Why it fails

    A negative τ does not identify an eligible stored state-action pair for the delayed update.

    Do this instead

    Perform the update only when τ is at least zero.

  • Common mistake

    Updating the current time instead of the delayed time.

    What it looks like

    Using the state-action pair at t when the algorithm has calculated τ = t − n + 1.

    Why it fails

    The current action is not necessarily the state-action estimate whose n-step return is now available.

    Do this instead

    Use the stored state and action associated with τ.

  • Common mistake

    Ignoring the terminal time when constructing G.

    What it looks like

    Continuing the reward sequence beyond T or always adding a bootstrap estimate.

    Why it fails

    The return is bounded by min(τ+n,T), and bootstrapping is conditional on τ+n being less than T.

    Do this instead

    Use T to limit the rewards and apply the stated bootstrap condition.

  • Common mistake

    Discarding all delayed updates when T is set.

    What it looks like

    Ending processing immediately when the terminal state is reached.

    Why it fails

    Earlier eligible state-action pairs may still have delayed updates waiting to be applied.

    Do this instead

    Continue processing the eligible delayed updates using the terminal-bounded returns.

  • Common mistake

    Changing the order of the main operations.

    What it looks like

    Updating θ before calculating τ or before forming G.

    Why it fails

    The update depends on the delayed index and its corresponding n-step return.

    Do this instead

    Preserve the order: initialize, collect experience, calculate τ, form G for eligible τ, and update θ.

τdelayed estimatetcurrent timeτ ≥ 0eligibleEvery tno eligibility testUpdate θuse stored pairMisaligned updatewrong estimatetestpassusecauses
Why must the update use τ and the condition τ ≥ 0 rather than updating every current time t?
Best practice

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

MEDIUM

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?

  • τ = 1, so the update is eligible

  • τ = 4, so the update is eligible

  • τ = 1, so the update is not 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.

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

Related Topics

Related concepts

More concepts starting with N