Answers.Body: <p>The true answers are 1 and 3.</p>
  <p>1 is true because the required conditions for tabular Q-learning to converge is that each state action pair will be visited infinitely often, and Q-learning learns directly about the greedy policy, <span class="math-container">$\pi(a|s) := \arg \max_a Q_\pi(s,a)$</span>,  and because Q-learning converges to the optimal Q-value function we know that the policy will be optimal (because the optimal policy is the greedy policy wrt the optimal Q-function).</p>
  <p>3 is true because Q-learning is by definition an off-policy algorithm, because we learn about the greedy policy whilst following some arbitrary policy.</p>
  <p>2 is false because SARSA is on-policy, so it will be learning the Q-function under the random policy.</p>
  <p>4 is false because SARSA is strictly on-policy, for reasons analogous to why Q-learning is off-policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-09T17:50:28.830Z
Answers.Text: So a completely random policy counts as a policy too? Isn't that as good as not having a policy and sampling from the action space itself?
Answers.UserDisplayName: stoic-santiago
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-09T18:05:54.183Z
Answers.Text: That’s exactly what the random policy does, it picks from all viable actions in the given state with equal probability. It’s good for guaranteeing exploration in off-policy algorithms.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-10T02:43:04.563Z
Answers.Text: Great, thanks! Also, when would SARSA converge to the optimal Q values? From what I remember, it should happen when (i) all state-action pairs are visited infinitely often (ii) the policy converges to the greedy policy. Could you confirm/elaborate more on this?
Answers.UserDisplayName: stoic-santiago
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-10T09:07:55.843Z
Answers.Text: Yes, that is correct. In practice you would learn about an $\epsilon$-greedy policy which is not technically optimal but very close to it.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-09T17:48:43.087Z
Answers.LastActivityDate: 2022-05-28T10:25:51.873Z
Answers.LastEditDate: 2022-05-28T10:25:51.873Z
Answers.UserDisplayName: David
Body: <p>Here's another interesting multiple-choice question that puzzles me a bit.</p>
  <blockquote>
  <p>In tabular MDPs, if using a decision policy that visits all states an <strong>infinite</strong> number of times, and in each state, <strong>randomly</strong> selects an action, then:</p>
  <ol>
  <li>Q-learning will converge to the optimal Q-values</li>
  <li>SARSA will converge to the optimal Q-values</li>
  <li>Q-learning is learning off-policy</li>
  <li>SARSA is learning off-policy</li>
  </ol>
  </blockquote>
  <p><em>My thoughts, and question:</em> Since the actions are being sampled randomly from the action space, learning definitely seems to be <strong>off-policy</strong> (correct me if I'm wrong, please!). So that rules 3. and 4. as incorrect. Coming to the first two options, I'm not quite sure whether Q-learning and/or SARSA would converge in this case. All that I'm able to understand from the question is that the agent <strong>explores more than it exploits</strong>, since it visits all states (an infinite number of times) and also takes random actions (and not the best action!). How can this piece of information help me deduce if either process converges to the optimal Q-values or not?</p>
  <hr />
  <p>Source: <a href="http://web.stanford.edu/class/cs234/slides/lecture5.pdf" rel="nofollow noreferrer">Slide 2/55</a></p>
  
Tags: <reinforcement-learning><q-learning><convergence><sarsa>
Title: When do SARSA and Q-Learning converge to optimal Q values?
UserDisplayName: stoic-santiago
ThreadText: # When do SARSA and Q-Learning converge to optimal Q values?
  
  (Asked by: username_0 on 2020-08-09)
  
  Here's another interesting multiple-choice question that puzzles me a bit.
  
  > In tabular MDPs, if using a decision policy that visits all states an **infinite** number of times, and in each state, **randomly** selects an action, then:
  >
  > 1. Q-learning will converge to the optimal Q-values
  > 2. SARSA will converge to the optimal Q-values
  > 3. Q-learning is learning off-policy
  > 4. SARSA is learning off-policy
  
  *My thoughts, and question:* Since the actions are being sampled randomly from the action space, learning definitely seems to be **off-policy** (correct me if I'm wrong, please!). So that rules 3. and 4. as incorrect. Coming to the first two options, I'm not quite sure whether Q-learning and/or SARSA would converge in this case. All that I'm able to understand from the question is that the agent **explores more than it exploits**, since it visits all states (an infinite number of times) and also takes random actions (and not the best action!). How can this piece of information help me deduce if either process converges to the optimal Q-values or not?
  
  ---
  
  Source: [Slide 2/55](http://web.stanford.edu/class/cs234/slides/lecture5.pdf)
  
  **Tags:** reinforcement-learning, q-learning, convergence, sarsa
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-09. Score: 5 | Accepted answer
  
  The true answers are 1 and 3.
  
  1 is true because the required conditions for tabular Q-learning to converge is that each state action pair will be visited infinitely often, and Q-learning learns directly about the greedy policy, $\pi(a|s) := \arg \max\_a Q\_\pi(s,a)$, and because Q-learning converges to the optimal Q-value function we know that the policy will be optimal (because the optimal policy is the greedy policy wrt the optimal Q-function).
  
  3 is true because Q-learning is by definition an off-policy algorithm, because we learn about the greedy policy whilst following some arbitrary policy.
  
  2 is false because SARSA is on-policy, so it will be learning the Q-function under the random policy.
  
  4 is false because SARSA is strictly on-policy, for reasons analogous to why Q-learning is off-policy.
  
  > **Comments:**
  > **username_0**: So a completely random policy counts as a policy too? Isn't that as good as not having a policy and sampling from the action space itself?  
  > **username_1**: That’s exactly what the random policy does, it picks from all viable actions in the given state with equal probability. It’s good for guaranteeing exploration in off-policy algorithms.  
  > **username_0**: Great, thanks! Also, when would SARSA converge to the optimal Q values? From what I remember, it should happen when (i) all state-action pairs are visited infinitely often (ii) the policy converges to the greedy policy. Could you confirm/elaborate more on this?  
  > **username_1**: Yes, that is correct. In practice you would learn about an $\epsilon$-greedy policy which is not technically optimal but very close to it.  
  
  ---
  
  