On-policy and off-policy reinforcement learning

Sarsa, Q-learning, and Expected Sarsa all use experience to improve action-value estimates. Their important difference is how they extract learning information from the next state. Sarsa uses the next action that was actually selected. Expected Sarsa considers the expected value of the possible next actions under a policy. That distinction determines how much randomness enters each update and whether the method is on-policy or off-policy.

Suppose an agent has reached a next state and its behavior policy can select more than one action there. Sarsa allows the action actually selected in that experience to determine the next-action contribution to the update. If a different action is selected on another experience, the contribution can change even when the next state and its estimated action values have not changed.

Expected Sarsa takes a broader view of that same next state. Instead of allowing one sampled action to represent the whole next state, it combines the values of the possible next actions according to their probabilities under the relevant policy. The update therefore uses an expected next-action value.

The randomly selected next action can make Sarsa's target fluctuate. One experience may select an action with a relatively high estimated value, while another may select a different action with a lower estimated value. The update then inherits randomness from the action-selection event.

Expected Sarsa removes this particular source of variance by calculating the expected value of the possible next actions instead of using only the action sampled in one experience. This does not make the method free: calculating the expectation requires additional computation. The trade-off is extra work per update in exchange for removing the variance caused by random next-action selection.

Expected Sarsa is on-policy when the policy used to generate the agent's behavior is also the target policy whose action values are being evaluated. In that case, the probabilities used to form the expected next-action value come from the same policy that generated the experience.

Expected Sarsa is off-policy when one policy generates the experience while a different target policy supplies the next-action probabilities used for learning. This gives Expected Sarsa flexibility: it can evaluate or improve the policy producing behavior, or it can learn about another target policy.

The step-size parameter controls how strongly each new experience changes an action-value estimate. The source reports an important difference in the deterministic state transitions of the cliff-walking setting. Expected Sarsa can safely use a step size of α = 1 without degradation of asymptotic performance, whereas Sarsa performs well in the long run only at a small step size in that comparison.

That small step size can make Sarsa's short-term performance poor. The reason is connected to the earlier distinction: Sarsa receives targets affected by the random sampled next action, so a large step size can make each noisy target strongly influence learning. Expected Sarsa pays more computation to average over possible next actions, and the reported results show that its performance is less constrained by the step-size choice in this setting.