Concepts / Semi-gradient methods

Semi-gradient methods

Episodic Semi-gradient Sarsa learns a value function by updating value-function weights θ during episodes.

  • Programming

Learning One Episode at a Time

Episodic Semi-gradient Sarsa learns a value function by changing the value-function weights θ during episodes. It begins with arbitrarily initialized weights. For each episode, the algorithm obtains an initial state and action, takes the current action, observes a reward and a next state, and then updates θ. The crucial decision is whether that next state is terminal.

Currentstate-actionS, AReward and next stateR, S′Terminal testTerminal updateReward targetEpisode endsNext actionA′Nonterminal updateReward and estimated valueNext state-actionS′, A′take Ainspect S′terminalafter updatenonterminalchoose A′after update
How does the update path differ when the next state is terminal versus nonterminal?

The Two Update Paths

After the current action is taken, the algorithm has two immediately available observations: the reward R and the next state S′. It first tests whether S′ is terminal. That test determines which semi-gradient update rule is used.

Definition

Terminal update: use the observed reward as the target component, update θ, and end the episode. No next action is selected after this path.

Definition

Nonterminal update: choose a next action A′ using the estimated values q̂(S′, ·, θ), include the estimated value of that next state-action pair with the reward in the target, update θ, and continue with S′ and A′.

Current estimateq̂(S, A, θ)Next estimated valueq̂(S′, A′, θ)Update targetTerminal or nonterminalWeights θUpdated value functionRewardRNext stateS′compare with targettarget componentif nonterminalinclude estimated valueupdate
How do the current estimate, observed transition, and next action determine the update path for θ?

Tracing Weight Changes

Worked example

A symbolic three-transition episode

Trace the control flow of an episode whose transitions are represented symbolically. The first transition reaches a nonterminal state, the second also reaches a nonterminal state, and the third reaches a terminal state.

  1. 1
    Start

    Begin with arbitrarily initialized value-function weights θ0. Obtain the episode's initial state and action.

  2. 2
    First transition

    Take the current action and observe R1 and S1. Because S1 is nonterminal, choose A1 using q̂(S1, ·, θ0), use the nonterminal target path, and produce updated weights θ1. Continue with S1 and A1.

  3. 3
    Second transition

    Take A1 and observe R2 and S2. Because S2 is nonterminal, choose A2 using q̂(S2, ·, θ1), use the nonterminal target path, and produce updated weights θ2. Continue with S2 and A2.

  4. 4
    Third transition

    Take A2 and observe R3 and a terminal S3. Use the observed reward as the terminal target component, update θ to produce θ3, and end the episode. Do not choose A3.

Result

The episode changes the weights after each transition: θ0 becomes θ1, then θ2, then θ3. The first two transitions continue with a next state-action pair; the final transition ends the episode through the terminal update path.

θ0Initial weightsθ1After nonterminaltransitionθ2After nonterminaltransitionθ3After terminal transitionEpisode endtransition 1transition 2terminal transition 3stop
How does the weight vector θ change after each transition from the beginning to the end of an episode?

The symbols θ0, θ1, θ2, and θ3 represent successive versions of the weight vector in this trace. The important point is the order of operations: observe R and S′, test whether S′ is terminal, select the corresponding target path, update θ, and then either stop or advance to the next state-action pair.

Debugging the Control Flow

  • Common mistake

    Choosing a next action after a terminal transition.

    What it looks like

    The trace observes a terminal S′ and then selects A′ before updating θ.

    Why it fails

    The terminal path uses the observed reward as the target component and ends the episode. A′ belongs to the nonterminal path.

    Do this instead

    After observing R and terminal S′, apply the terminal update, then end the episode.

  • Common mistake

    Using the terminal path merely because a reward was observed.

    What it looks like

    The trace sees R and immediately ends, without checking whether S′ is terminal.

    Why it fails

    Both terminal and nonterminal transitions provide a reward. The terminal test on S′ determines the update rule.

    Do this instead

    Inspect S′ first. If it is nonterminal, choose A′ and include its estimated value.

  • Common mistake

    Advancing to S′ without advancing to A′ on a nonterminal transition.

    What it looks like

    The trace chooses A′ but continues with S′ and the old action.

    Why it fails

    The nonterminal path continues with the pair S′ and A′.

    Do this instead

    After the nonterminal update, replace the current state-action pair with S′ and A′.

  • Common mistake

    Inspecting only the final weights when a trace is wrong.

    What it looks like

    The final θ differs from the expected result, so every update is reconsidered at once.

    Why it fails

    A later difference may have started at an earlier control-flow decision.

    Do this instead

    Find the first divergence. Check R and S′ immediately after the action, then verify the terminal decision, selected target path, and destination after the update.

Best practice

For a reliable trace, record the current state and action, the observed reward and next state, the terminal decision, the target path, the updated weights, and the next destination. For a nonterminal transition, also record the selected A′ and confirm that it was chosen from q̂(S′, ·, θ).

Practice the Terminal Decision

MEDIUM

A transition produces reward R and next state S′. In one case S′ is nonterminal; in another case S′ is terminal. For each case, describe whether A′ is selected, what kind of target component is used, what happens to θ, and whether the episode continues.

Hints
  • Start with the terminal test on S′.
  • The terminal path uses the observed reward as the target component.
  • The nonterminal path selects A′ using q̂(S′, ·, θ) and includes its estimated value.

What do you think happens?

A transition reaches a terminal next state. What should happen immediately after the weight update?

  • Choose A′ and continue with S′ and A′

  • End the episode

  • Recheck the previous state and action

Reveal answer
Answer:

End the episode

A terminal transition uses the observed reward as the target component, updates θ, and ends the episode. Selecting A′ and continuing belong to the nonterminal path.

Key Takeaways

  1. 1
    Episodic Semi-gradient Sarsa begins with arbitrarily initialized value-function weights θ and updates them during an episode.
  2. 2
    The terminal test on S′ selects the update rule.
  3. 3
    A terminal transition uses the observed reward as the target component, updates θ, and ends the episode.
  4. 4
    A nonterminal transition chooses A′ using q̂(S′, ·, θ), includes the estimated next value, updates θ, and continues with S′ and A′.
  5. 5
    When debugging, locate the first control-flow divergence by checking R, S′, the terminal decision, the target path, and the destination after the update.

At a glance

  • The algorithm learns a value function by changing θ during episodes.
  • The terminal test is the central branch in the update process.
  • Terminal transitions stop after using the reward target component; nonterminal transitions select A′ and continue.
  • A complete trace follows the weights and control flow after every transition.
  • The first incorrect terminal decision or state-action advance is usually the most useful debugging point.

Related Topics

Related concepts

More concepts starting with S