3
$\begingroup$

Sutton and Barto state in the 2018-version of "Reinforcement Learning: An Introduction" in the context of Expected SARSA (p. 133) the following sentences:

Expected SARSA is more complex computationally than Sarsa but, in return, it eliminates the variance due to the random selection of $A_{t+1}$. Given the same amount of experience we might expect it to perform slightly better than Sarsa, and indeed it generally does.

I have three questions concerning this statement:

  1. Why is the action selection random with Sarsa? Isn't it on-policy and therefore $\epsilon$-greedy?
  2. Because Expected-Sarsa is off-policy the experience it learns from can be from any policy that at least explores everything in the limit e.g. random action-selection with equal probabilities for every action. How can Exected-Sarsa learning from such policy be generally better than normal Sarsa learning from an $\epsilon$-greedy policy, especially with the same amount of experience?
  3. Probably more general: How can on-policy and off-policy algorithms be compared in such way (e.g. through variance) even though their concepts and assumptions are so different?
$\endgroup$
  • 1
    $\begingroup$ I guess that by "random selection" they mean the case when $A_{t+1}$ is actually randomly selected (that is, when you do not select the best action) when you use the $\epsilon$-greedy policy. $\endgroup$ – nbro Feb 21 '19 at 20:16
  • 1
    $\begingroup$ In this context, I think that by "variance" they mean how much "variation" of some "performance measure" or some metric these methods face when being executed, although I think they could have been more precise and unambiguous. They probably mean something specific, as they illustrate in figure 6.3. $\endgroup$ – nbro Feb 21 '19 at 20:40
2
$\begingroup$

Why is the action selection random with Sarsa?

A policy could be stochastic. In the case of SARSA, it is stochastic because of the use of $\epsilon$-greedy.

Isn't it on-policy and therefore ϵ-greedy?

I don't quite understand the question. SARSA is on-policy evaluation with $\epsilon$-greedy policy. Q-learning is off-policy evaluation with $\epsilon$-greedy policy. $\epsilon$-greedy is just a way to turn an action-value function into a policy.

Because Expected-Sarsa is off-policy the experience it learns from can be from any policy ... How can Exected-Sarsa learning from such policy be generally better than normal Sarsa learning from an ϵ-greedy policy, especially with the same amount of experience?

It is unfair to compare different natures of experiences because off-policy experience contains less useful information. Thus, both SARSA and Expected SARSA should use their own on-policy experience for comparison.

While Expected SARSA update step guarantees to reduce the expected TD error, SARSA could only achieve that in expectation (taking many updates with sufficiently small learning rate). Through this perspective, there is little doubt that Expected SARSA should be better.

Probably more general: How can on-policy and off-policy algorithms be compared in such way (e.g. through variance) even though their concepts and assumptions are so different?

Same as the previous answer, it is unfair to compare them without the same quality of experiences.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I would add that Expected SARSA can be used in either on-policy or off-policy approaches, it depends if the policy used to calculate the TD error is the same as that used to select actions (and if you are using some n-step off-policy approach, you may need to add importance sampling or look at the n-step Tree Backup algorithm). Some statements about Expected SARSA in Sutton & Barto make more sense when considering just the on-policy version - especially comparisons with normal SARSA $\endgroup$ – Neil Slater Feb 27 '19 at 10:21
  • $\begingroup$ I had some big misconceptions there. Thank you for the good clarification! $\endgroup$ – F.M.F. May 22 '19 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.