Answers.Body: <p>Q-learning uses an exploratory policy, derived from the current estimate of the <span class="math-container">$Q$</span> function, such as the <span class="math-container">$\epsilon$</span>-greedy policy, to select the action <span class="math-container">$a$</span> from the current state <span class="math-container">$s$</span>. After having taken this action <span class="math-container">$a$</span> from <span class="math-container">$s$</span>, the reward <span class="math-container">$r$</span> and the next state <span class="math-container">$s'$</span> are observed. At this point, to update the estimate of the <span class="math-container">$Q$</span> function, you use a <em>target</em> that assumes that the greedy action is taken from the next state <span class="math-container">$s'$</span>. The greedy action is selected by the <span class="math-container">$\operatorname{max}$</span> operator, which can thus be thought of as an <em>implicit</em> policy (but this terminology isn't common, AFAIK), so, in this context, the greedy action is the action associated with the highest <span class="math-container">$Q$</span> value for the state <span class="math-container">$s'$</span>.</p>
  
  <p>In SARSA, no <span class="math-container">$\operatorname{max}$</span> operator is used, and you derive a policy (e.g. the <span class="math-container">$\epsilon$</span>-greedy policy) from the current estimate of the <span class="math-container">$Q$</span> function to select both <span class="math-container">$a$</span> (from <span class="math-container">$s$</span>) and <span class="math-container">$a'$</span> (from <span class="math-container">$s'$</span>).</p>
  
  <p>To conclude, in all cases, the policies are implicit, in the sense that they are derived from the estimate of the <span class="math-container">$Q$</span> function, but this isn't a common terminology. See also <a href="https://ai.stackexchange.com/a/17626/2444">this answer</a>, where I describe more in detail the differences between Q-learning and SARSA, and I also show the pseudocode of both algorithms, which you should read (multiple times) in order to fully understand their differences.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-29T09:36:47.757Z
Answers.Text: Thank you for your answer, I also checked the link you provided and it was very helpful. But I'm still not sure what it means to "sample `A'` from policy"? Does it mean that for Q-learning I do need an explicit policy (`max Q`, greedy) because I know which `A'` I will take to compute target (the one that gives me the `max Q`, regardless of the action actually taken in the environment). And for SARSA, I pick the action with some probability and compute target based on that `A'` (actually taken in environment). Could you elaborate on that please?
Answers.UserDisplayName: Novak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-29T11:44:43.553Z
Answers.Text: @Novak To sample $a'$ from a policy is the same thing as to sample $a$ from the same or another policy. If $\pi(a | s)$ represents a distribution, then $a ~ pi(a | s)$ is a sample from that distribution (in a statistical sense). In the case of Q-learning, you **assume** that the agent will take the best action from $s'$. You don't necessarily know the specific action $a'$, but, in Q-learning, $a'$ will be the best action (by assumption, because you use the max). The only action taken is $a$. See the pseudocode in my [other answer](https://ai.stackexchange.com/a/17626/2444).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-29T11:45:48.110Z
Answers.Text: @Novak See also this question [What is the relation between a policy which is the solution to an MDP and a policy like -greedy?](https://ai.stackexchange.com/q/10492/2444) I had asked. (Btw, use the symbols `$` for MathJax notation).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-22T23:00:38.780Z
Answers.LastActivityDate: 2020-01-22T23:07:23.183Z
Answers.LastEditDate: 2020-01-22T23:07:23.183Z
Answers.UserDisplayName: nbro
Body: <p>I would much appreciate if you could point me in the right direction regarding this question about targets for SARSA and Q-learning (notation: <span class="math-container">$S$</span> is the current state, <span class="math-container">$A$</span> is the current action, <span class="math-container">$R$</span> is the reward, <span class="math-container">$S'$</span> is the next state and <span class="math-container">$A'$</span> is the action chosen from that next state).</p>
  
  <p><strong>Do we need an explicit policy for the Q-learning target to sample <span class="math-container">$A'$</span> from? And for SARSA?</strong></p>
  
  <p>I guess this is true for Q-learning since we need to get max Q-value which determines which action <span class="math-container">$A'$</span> we'll use for the update. For SARSA, we update the <span class="math-container">$Q(S, A)$</span> depending on which action was actually taken (no need for max). Please correct me if I'm wrong.</p>
  
Tags: <reinforcement-learning><comparison><q-learning><sarsa>
Title: Do we need an explicit policy to sample $A'$ in order to compute the target in SARSA or Q-learning?
UserDisplayName: Novak
ThreadText: # Do we need an explicit policy to sample $A'$ in order to compute the target in SARSA or Q-learning?
  
  (Asked by: username_0 on 2020-01-22)
  
  I would much appreciate if you could point me in the right direction regarding this question about targets for SARSA and Q-learning (notation: $S$ is the current state, $A$ is the current action, $R$ is the reward, $S'$ is the next state and $A'$ is the action chosen from that next state).
  
  **Do we need an explicit policy for the Q-learning target to sample $A'$ from? And for SARSA?**
  
  I guess this is true for Q-learning since we need to get max Q-value which determines which action $A'$ we'll use for the update. For SARSA, we update the $Q(S, A)$ depending on which action was actually taken (no need for max). Please correct me if I'm wrong.
  
  **Tags:** reinforcement-learning, comparison, q-learning, sarsa
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-01-22. Score: 3 | Accepted answer
  
  Q-learning uses an exploratory policy, derived from the current estimate of the $Q$ function, such as the $\epsilon$-greedy policy, to select the action $a$ from the current state $s$. After having taken this action $a$ from $s$, the reward $r$ and the next state $s'$ are observed. At this point, to update the estimate of the $Q$ function, you use a *target* that assumes that the greedy action is taken from the next state $s'$. The greedy action is selected by the $\operatorname{max}$ operator, which can thus be thought of as an *implicit* policy (but this terminology isn't common, AFAIK), so, in this context, the greedy action is the action associated with the highest $Q$ value for the state $s'$.
  
  In SARSA, no $\operatorname{max}$ operator is used, and you derive a policy (e.g. the $\epsilon$-greedy policy) from the current estimate of the $Q$ function to select both $a$ (from $s$) and $a'$ (from $s'$).
  
  To conclude, in all cases, the policies are implicit, in the sense that they are derived from the estimate of the $Q$ function, but this isn't a common terminology. See also [this answer](https://ai.stackexchange.com/a/17626/2444), where I describe more in detail the differences between Q-learning and SARSA, and I also show the pseudocode of both algorithms, which you should read (multiple times) in order to fully understand their differences.
  
  > **Comments:**
  > **username_0**: Thank you for your answer, I also checked the link you provided and it was very helpful. But I'm still not sure what it means to "sample `A'` from policy"? Does it mean that for Q-learning I do need an explicit policy (`max Q`, greedy) because I know which `A'` I will take to compute target (the one that gives me the `max Q`, regardless of the action actually taken in the environment). And for SARSA, I pick the action with some probability and compute target based on that `A'` (actually taken in environment). Could you elaborate on that please?  
  > **username_1**: @Novak To sample $a'$ from a policy is the same thing as to sample $a$ from the same or another policy. If $\pi(a | s)$ represents a distribution, then $a ~ pi(a | s)$ is a sample from that distribution (in a statistical sense). In the case of Q-learning, you **assume** that the agent will take the best action from $s'$. You don't necessarily know the specific action $a'$, but, in Q-learning, $a'$ will be the best action (by assumption, because you use the max). The only action taken is $a$. See the pseudocode in my [other answer](https://ai.stackexchange.com/a/17626/2444).  
  > **username_1**: @Novak See also this question [What is the relation between a policy which is the solution to an MDP and a policy like -greedy?](https://ai.stackexchange.com/q/10492/2444) I had asked. (Btw, use the symbols `$` for MathJax notation).  
  
  ---
  
  