Answers.Body: <p>If we assume a tabular setting, then <a href="https://ai.stackexchange.com/a/21408/2444">Q-learning converges to the optimal state-action value function</a>, from which an optimal policy can be derived, provided a few conditions are met.</p>
  <p>In <em>finite MDPs</em>, there's at least one optimal (stationary) <em>deterministic</em> 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 <em>not</em> behave optimally.</p>
  <p>SARSA also converges to the optimal state-action value function, but the learning policy must eventually become greedy. See <a href="https://ai.stackexchange.com/q/18278/2444">this post</a> and theorem 1 (p. 294) of <a href="https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf" rel="nofollow noreferrer">this paper</a>.</p>
  <p>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 <em>optimal restricted policy</em>. See theorem 2 (p. 297) of <a href="https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf" rel="nofollow noreferrer">this paper</a> for more details.</p>
  <p>To answer your question directly, Q-learning can find an optimal stochastic policy, provided that it exists.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-25T18:40:12.247Z
Answers.Text: 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?
Answers.UserDisplayName: ketan dhanuka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-25T18:41:02.393Z
Answers.Text: @ketandhanuka Yes, as far as I remember, $\epsilon$ must eventually decay in order for SARSA to find the optimal value function.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-26T08:01:55.000Z
Answers.Text: $\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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-26T09:19:49.467Z
Answers.Text: @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](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf)) 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-26T09:32:00.040Z
Answers.Text: Maybe you're referring to another result about $\epsilon$-greedy policies in the context of SARSA. But, in [this paper](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf), what you say only applies to restricted rank-based randomized (RRR) policies, i.e. policies that choose actions according to their ranks.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-26T11:11:55.540Z
Answers.Text: Yes I meant the restricted policy. By "ranked" I meant that the policies can be compared, so optimality is well defined. I used the wrong terminology, sorry.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-25T18:31:32.070Z
Answers.LastActivityDate: 2022-05-26T09:17:25.373Z
Answers.LastEditDate: 2022-05-26T09:17:25.373Z
Answers.UserDisplayName: nbro
Body: <p>I was following a reinforcement learning course on coursera and in <a href="https://www.coursera.org/lecture/complete-reinforcement-learning-system/meeting-with-niko-choosing-the-learning-algorithm-ToRFI" rel="nofollow noreferrer">this</a> video at 2:57 the instructor says</p>
  <blockquote>
  <p>Expected SARSA and SARSA both allow us to learn an optimal
  <span class="math-container">$\epsilon$</span>-soft policy, but, Q-learning does not</p>
  </blockquote>
  <p>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.</p>
  <p>But, can't we use these action values generated by the Q-learning algorithm to form an <span class="math-container">$\epsilon$</span>-greedy policy?</p>
  <p>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 <span class="math-container">$\frac{\epsilon}{\text{number of actions}}$</span>. Because we do a similar thing with SARSA, where we infer the policy from the current estimate of action-values after each update.</p>
  
Tags: <reinforcement-learning><q-learning><policies><sarsa><deterministic-policy>
Title: Is Q-learning only capable of learning a deterministic policy?
UserDisplayName: ketan dhanuka
ThreadText: # Is Q-learning only capable of learning a deterministic policy?
  
  (Asked by: username_0 on 2022-05-25)
  
  I was following a reinforcement learning course on coursera and in [this](https://www.coursera.org/lecture/complete-reinforcement-learning-system/meeting-with-niko-choosing-the-learning-algorithm-ToRFI) 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.
  
  **Tags:** reinforcement-learning, q-learning, policies, sarsa, deterministic-policy
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-05-25. Score: 8 | Accepted answer
  
  If we assume a tabular setting, then [Q-learning converges to the optimal state-action value function](https://ai.stackexchange.com/a/21408/2444), 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](https://ai.stackexchange.com/q/18278/2444) and theorem 1 (p. 294) of [this paper](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf).
  
  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](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf) for more details.
  
  To answer your question directly, Q-learning can find an optimal stochastic policy, provided that it exists.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: @username_0 Yes, as far as I remember, $\epsilon$ must eventually decay in order for SARSA to find the optimal value function.  
  > **username_2**: $\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.  
  > **username_1**: @username_2 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](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf)) 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.  
  > **username_1**: Maybe you're referring to another result about $\epsilon$-greedy policies in the context of SARSA. But, in [this paper](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf), what you say only applies to restricted rank-based randomized (RRR) policies, i.e. policies that choose actions according to their ranks.  
  > **username_2**: Yes I meant the restricted policy. By "ranked" I meant that the policies can be compared, so optimality is well defined. I used the wrong terminology, sorry.  
  
  ---
  
  