Semi-gradient methods
Episodic Semi-gradient Sarsa learns a value function by updating value-function weights θ during episodes.
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.
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.
Terminal update: use the observed reward as the target component, update θ, and end the episode. No next action is selected after this path.
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′.
Tracing Weight Changes
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.
Start: Begin with arbitrarily initialized value-function weights θ0. Obtain the episode's initial state and action.
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.
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.
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.
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.
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
Choosing a next action after a terminal transition.
The terminal path uses the observed reward as the target component and ends the episode. A′ belongs to the nonterminal path.
Fix:
After observing R and terminal S′, apply the terminal update, then end the episode.Using the terminal path merely because a reward was observed.
Both terminal and nonterminal transitions provide a reward. The terminal test on S′ determines the update rule.
Fix:
Inspect S′ first. If it is nonterminal, choose A′ and include its estimated value.Advancing to S′ without advancing to A′ on a nonterminal transition.
The nonterminal path continues with the pair S′ and A′.
Fix:
After the nonterminal update, replace the current state-action pair with S′ and A′.Inspecting only the final weights when a trace is wrong.
A later difference may have started at an earlier control-flow decision.
Fix:
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.
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
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?
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
- Episodic Semi-gradient Sarsa begins with arbitrarily initialized value-function weights θ and updates them during an episode.
- The terminal test on S′ selects the update rule.
- A terminal transition uses the observed reward as the target component, updates θ, and ends the episode.
- A nonterminal transition chooses A′ using q̂(S′, ·, θ), includes the estimated next value, updates θ, and continues with S′ and A′.
- When debugging, locate the first control-flow divergence by checking R, S′, the terminal decision, the target path, and the destination after the update.
Key Takeaways
- 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.