Is Expected SARSA an off-policy or on-policy algorithm?

Question

I understand that SARSA is an On-policy algorithm, and Q-learning an off-policy one. Sutton and Barto's textbook describes Expected Sarsa thusly:

In these cliff walking results Expected Sarsa was used on-policy, but in general it might use a policy different from the target policy to generate behavior, in which case it becomes an off-policy algorithm.

I am fundamentally confused by this - specifically, how do we define when Expected SARSA adopts or disregards policy. The Coursera Course states that it is On-Policy, further confusing me.

My confusions became realized when tackling the Udacity course, specifically a section visualizing Expected SARSA for simple a gridworld (See section 1.11 and 1.12 in link below). Note that the course defines Expected Sarsa as on-policy. https://www.zhenhantom.com/2019/10/27/Deep-Reinforcement-Learning-Part-1/

You'll notice the calculation for the new state value Q(s0,a0) as

Q(s0, a0) <— 6 + 0.1( -1 + [0.1 x 8] + [0.1 x 7] + [0.7 x 9] + [0.1 x 8] - 6) = 6.16.

This is also the official answer. But this would mean that it is running off policy, given that it is stated that the action taken at S1 corresponds to a shift right, and hence expected SARSA (On policy) should yield you.

Q(s0, a0) <— 6 + 0.1( -1 + [0.1 x 8] + [0.1 x 7] + [0.1 x 9] + [0.7 x 8] - 6) = 6.1

The question does state

(Suppose that when selecting the actions for the first two timesteps in the 100th episode, the agent was following the epsilon-greedy policy with respect to the Q-table, with epsilon = 0.4.)

But as this same statement existed for the regular SARSA example (which also yields 6.1 as A1 is shift right, as before), I disregarded it.

Any advice is welcome.

Answer 1

Expected SARSA can be used either on-policy or off-policy.

The policy that you use in the update step determines which it is. If the update step uses a different weighting for action choices than the policy that actually took the action, then you are using Expected SARSA in an off-policy way.

Q-learning is a special case of Expected SARSA, where the target policy is greedy with respect to the action values, so there is only ever one $r_{t+1} + \gamma \text{max}_{a'} Q(s_{t+1}, a')$ term to add with a probability $1$.

You can also use Expected SARSA, similarly to SARSA, where the behaviour policy and target policy are identical. It is not identical to SARSA though, because it calculates the TD Target over all possible actions $r_{t+1} + \gamma \sum_{a'} \pi(a'|s_{t+1}) Q(s_{t+1}, a')$

You can construct Expected SARSA updates where $\pi(a|s)$ is different when selecting which action to explore in the environment (behaviour) and when updating the Q values (target). For instance, you can decide to explore using $\epsilon$-greedy with $\epsilon=0.1$ and update the value function with $\epsilon=0.01$.