Sarsa

One Next State, Three Backups

When an agent reaches a next state, several actions may be possible. Sarsa uses the value of the particular next action that was selected. Q-learning uses the highest-valued next action. Expected Sarsa takes a middle path: it considers all possible next actions and combines their values according to how likely they are under the relevant policy.

Tracing the Expected Backup

An Expected Sarsa update begins with the current state-action pair. The agent experiences a reward and reaches a next state. Once that next state is known, Expected Sarsa examines the actions available there. Instead of choosing only the action that happened to be sampled, it evaluates the possible next actions and weights each action-value estimate by that action’s likelihood under the current policy. The resulting expected next-action value is then used to update the earlier action-value estimate.

1. Start from the current state-action pair.
2. Observe the reward and the next state.
3. List the possible actions in the next state.
4. Use the relevant policy’s probability for each possible next action.
5. Combine the next-action values according to those probabilities.
6. Use the expected next-state value to improve the earlier action-value estimate.

Why Probabilities Matter

The current policy determines how much influence each possible next action has on the backup. An action with a high action-value estimate contributes strongly when the policy makes it likely, but an action with a lower value still contributes if the policy gives it some probability. Expected Sarsa therefore reflects the policy’s full distribution over next actions rather than representing the next state with one selected action or with only the best-valued action.

Sample, Average, or Maximum

Sarsa follows one realized next action. That makes its update depend on which action the agent happened to select. Expected Sarsa instead uses the possible next actions together, so its backup is policy-aware without reducing the next state to only its highest-valued action. Q-learning takes the greedy extreme by using the maximum next value.

Variance and Computation

A single sampled next action can make a Sarsa update depend heavily on that particular random choice. Expected Sarsa replaces that single-action backup with an average over the actions the policy might take. This removes the variance caused by random next-action selection from the update, although it requires additional computation to evaluate the possible actions and combine their values.

Policy Relationships

Expected Sarsa can be used on-policy or off-policy. It is on-policy when the policy that generates the agent’s behavior is also the target policy whose action probabilities supply the expected value. It is off-policy when one policy generates the experience while a different target policy supplies the action probabilities used for learning.

When the target policy is greedy, it assigns all probability to the action with the highest action-value estimate. The policy-weighted expectation then selects that maximum value, so this off-policy form of Expected Sarsa is exactly Q-learning.

Step Size in Practice

The step-size parameter controls how strongly a new update changes an existing action-value estimate. The reported cliff-walking results show an important contrast: for the deterministic state transitions described there, Expected Sarsa could safely use a step size of α = 1 without degradation of asymptotic performance. Sarsa performed well in the long run only at a small step size in that comparison, and that small value could make its short-term performance poor.

Common Reasoning Errors

• Treating Expected Sarsa as if it used only the next action that was selected.

  That is the sample-based route associated with Sarsa. Expected Sarsa evaluates the possible next actions and combines their values according to policy likelihood.

  Fix: Ask which actions are possible in the next state and how much probability the relevant policy assigns to each one.

• Confusing a policy-weighted expectation with the maximum action value.

  That describes the greedy maximum used by Q-learning, not the general Expected Sarsa backup.

  Fix: Retain every possible next action that has policy probability. Only when the target policy is greedy does the expectation become the maximum value.

• Assuming the behavior policy must always equal the target policy.

  Expected Sarsa can be on-policy or off-policy, depending on whether the behavior and target policies are the same or different.

  Fix: Identify which policy generated the experience and which policy supplies the action probabilities for the expected value.

• Ignoring the computational cost of the expectation.

  The variance reduction comes with additional computation because multiple possible next actions must be evaluated and combined.

  Fix: Compare both sides of the trade-off: more work per update and less variance from random next-action selection.

Check Your Understanding