2
$\begingroup$

I was following a reinforcement learning course on coursera and in this video at 2:57 the instructor says

Expected SARSA and SARSA both allow us to learn an optimal $\epsilon$-soft policy, but, Q-learning does not

From what I understand, SARSA and Q-learning both give us an estimate of the optimal action-value function. SARSA does this on-policy with an epsilon-greedy policy, for example, whereas the action-values from the Q-learning algorithm are for a deterministic policy, which is always greedy.

But, can't we use these action values generated by the Q-learning algorithm to form an $\epsilon$-greedy policy?

We can, for instance, in each state, give the maximum probability to the action with the greatest action-value and the rest of the actions can have probability $\frac{\epsilon}{\text{number of actions}}$. Because we do a similar thing with SARSA, where we infer the policy from the current estimate of action-values after each update.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

If we assume a tabular setting, then Q-learning converges to the optimal state-action value function, from which an optimal policy can be derived, provided a few conditions are met.

In finite MDPs, there's at least one optimal (stationary) deterministic policy, but there can also be optimal stochastic policies - specifically, if two or more actions have the same optimal value, then you can stochastically choose between them. However, if you stochastically choose between all actions (including non-optimal ones), then you will not behave optimally.

SARSA also converges to the optimal state-action value function, but the learning policy must eventually become greedy. See this post and theorem 1 (p. 294) of this paper.

So, even in SARSA, if you want to behave optimally, you can't just arbitrarily choose any stochastic policy derived from this found optimal value function (note also that SARSA is on-policy). However, SARSA can also find an optimal restricted policy. See theorem 2 (p. 297) of this paper for more details.

To answer your question directly, Q-learning can find an optimal stochastic policy, provided that it exists.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So if I understand the post correctly, even in SARSA we decrease exploration (by decreasing epsilon in case of epsilon greedy) as time progresses to ensure that we have the optimal value function? $\endgroup$
    – ketan dhanuka
    Commented May 25, 2022 at 18:40
  • 1
    $\begingroup$ @ketandhanuka Yes, as far as I remember, $\epsilon$ must eventually decay in order for SARSA to find the optimal value function. $\endgroup$
    – nbro
    Commented May 25, 2022 at 18:41
  • 1
    $\begingroup$ $\epsilon$-greedy policies with a fixed $\epsilon$ can be ranked. So SARSA will converge on the optimal $\epsilon$-greedy policy (i.e. the optimal polciy given that a specific $\epsilon$ value applies) even without decaying $\epsilon$. Sometimes this is desirable, for instance in online scenarios that never complete learning. $\endgroup$
    – Neil Slater
    Commented May 26, 2022 at 8:01
  • 1
    $\begingroup$ @NeilSlater I updated my answer to improve the precision of my explanations. SARSA converges to the optimal value function with decaying behaviour policies, but it can also converge to a policy called (here) an optimal restricted policy, which is the optimal policy that chooses actions according to the their rank (as far as I understand it). I am not sure if it's correct to say that SARSA converges to an optimal $\epsilon$-greedy policy, though - $\epsilon$-greedy policies don't choose actions according to their rank. $\endgroup$
    – nbro
    Commented May 26, 2022 at 9:19
  • $\begingroup$ Maybe you're referring to another result about $\epsilon$-greedy policies in the context of SARSA. But, in this paper, what you say only applies to restricted rank-based randomized (RRR) policies, i.e. policies that choose actions according to their ranks. $\endgroup$
    – nbro
    Commented May 26, 2022 at 9:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .