Expected Sarsa

One Next Action or All Possibilities

When an agent reaches a next state, several actions may be possible. Sarsa bases its update on the one next action that the agent actually selects. Expected Sarsa takes a broader view: it considers the possible next actions and combines their action-value estimates according to how likely they are under a policy. This replaces a single sampled next action with an expected next-action value.

The Update Path

The update begins with an earlier state-action pair and the experience obtained after taking that action: a reward and a next state. Once the next state is known, Expected Sarsa examines the actions available there. It does not use only the action sampled by the behavior process, and it does not keep only the action with the largest value. Instead, it combines the next action-values using their likelihood under the relevant policy. That combined value supplies the next-state information for updating the earlier estimate.

Sampled Versus Expected Backups

Sarsa's backup depends on the particular next action selected in that experience. If the policy can select different actions, different samples can produce different updates even when the current state and earlier action are the same. Expected Sarsa replaces that single-action dependence with a policy-weighted combination of possible next actions. The random selection of one next action therefore no longer adds variance to the update.

Why Probabilities Matter

The current policy's action probabilities are not decorative information. They determine how much each next action-value contributes to the expected value. A highly likely action has a larger influence, while an unlikely action has a smaller influence. An action with a lower value can still affect the backup if the policy assigns it some likelihood.

Relation to Q-Learning

Expected Sarsa can use different target policies. If the target policy is greedy, it assigns its target to the highest-valued next action. In that case, the policy-weighted expectation contains only the greedy action's contribution, so the Expected Sarsa target becomes the Q-learning target. This is why the source describes greedy-target off-policy Expected Sarsa as exactly Q-learning.

On-Policy and Off-Policy Use

Expected Sarsa is on-policy when the policy generating the behavior is also the policy whose action probabilities form the expectation. It is off-policy when one policy generates the experience while a different target policy supplies the expected next-action value. This flexibility lets Expected Sarsa learn about a target policy that is different from the policy producing the observed behavior.

Step Size and Variance

The step-size parameter controls how strongly an update changes an action-value estimate. In the reported deterministic cliff-walking setting, Expected Sarsa could safely use a step size of α = 1 without degradation of asymptotic performance. Sarsa, in contrast, performed well in the long run only at a small step size in that comparison, and the source reports that this small value could make Sarsa's short-term performance poor.

Expected Sarsa does pay for its lower selection variance with additional computation. Each update must calculate an expected next-action value rather than use only the sampled next action. The reported cliff-walking results show the trade-off: Expected Sarsa required more work per update but outperformed Sarsa and was less constrained by the step-size choice in that setting.

Mistakes in Identifying the Backup

• Treating Expected Sarsa as if it used only the next action that happened to be selected

  That is the sample-based route associated with Sarsa. Expected Sarsa considers the possible next actions under a policy.

  Fix: Identify the relevant policy and combine the possible next action-values according to that policy's action probabilities.

• Treating Expected Sarsa as identical to Q-learning in every configuration

  Expected Sarsa uses a policy-weighted expectation. It becomes Q-learning when the target policy is greedy, not in every policy configuration.

  Fix: Check whether the target policy is greedy before calling the backup a Q-learning backup.

• Ignoring the action probabilities

  The expected value is shaped by how likely each action is under the relevant policy.

  Fix: Use the policy's action likelihoods to determine each action's contribution.

• Assuming on-policy Expected Sarsa is the only form

  Expected Sarsa can also be off-policy, with one policy generating experience and another policy supplying the expectation.

  Fix: Compare the behavior policy with the target policy to classify the method.

Practice the Information Choice

Summary

1. Sarsa uses the value of the particular next action selected.
2. Expected Sarsa uses the policy-weighted expected value of the possible next actions.
3. Averaging over possible next actions removes variance caused by the random selection of one next action, at the cost of additional computation.
4. Expected Sarsa is on-policy when behavior and target policies match, and off-policy when they differ.
5. With a greedy target policy, Expected Sarsa becomes Q-learning because only the highest-valued next action contributes.
6. In the reported deterministic cliff-walking comparison, Expected Sarsa outperformed Sarsa and was less constrained by the step-size choice.