Answers.Body: <p>The first one is the update rule that we use in the <span class="math-container">$Q$</span>-learning algorithm.</p>
  
  <p>The second one is the "definition" of <span class="math-container">$Q(s, a)$</span> values, although I would personally write it as follows, with an expectation around the reward, to also support cases where rewards might be non-deterministic;</p>
  
  <p><span class="math-container">$$Q(s, a) \doteq \mathbb{E} \left[ r(s, a) \right] + \gamma \max_a Q(s', a)$$</span></p>
  
  <p>Here, the <span class="math-container">$Q(s', a)$</span> itself would also be similarly defined, and again that one is also assumed to be a "ground-truth" value.</p>
  
  <p>In practice, when learning, we do not actually know what any of these <span class="math-container">$Q$</span>-values exactly are; that's why we're doing learning in the first place, we're trying to learn what these values are! More precisely, when we wish to assign a new value to <span class="math-container">$Q(s, a)$</span>, the definition tells us that we should use <span class="math-container">$Q(s', a)$</span> for that, but we can't because we don't know exactly what the correct <span class="math-container">$Q(s', a$</span>) value is either. </p>
  
  <p>We do generally have some <span class="math-container">$Q(S_{t+1}, a)$</span> values, but they're generally going to be only <strong>approximations</strong>, resulting from the previous steps of our own learning process (or maybe even randomly initialised values if we only just started training!). There may also be an additional approximation error in stochastic environments, where the true <span class="math-container">$Q(s', a)$</span> value may be a weighted average over multiple different possible successor states <span class="math-container">$s'$</span>, but during the training we only observed a single concrete successor state <span class="math-container">$S_{t+1}$</span>.</p>
  
  <p>So, we can follow the definition and use <span class="math-container">$Q(S_{t+1}, a)$</span> as an approximation of <span class="math-container">$Q(s', a)$</span>, but we know that it's just an approximation and not entirely reliable. Therefore, instead of fully applying the definition and completely replacing our <span class="math-container">$Q(s, a)$</span> value based on it, we <strong>interpolate</strong> between our current estimate <span class="math-container">$Q(s, a)$</span> and the new one that we should have according to the definition + our approximations. We only slightly shift towards it. The learning rate <span class="math-container">$\alpha$</span> determines how much we shift towards it. Normally we use a learning rate <span class="math-container">$0 &lt; \alpha &lt; 1$</span>. Note that if you were to use <span class="math-container">$\alpha = 1$</span>, you would actually recover the definition for <span class="math-container">$Q$</span>-values again (except it would still use some observations to estimate unknown quantities).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T10:00:58.560Z
Answers.Text: I think that the definition of the $Q(s,a)$ as you have defined them would only hold if we were following the optimal policy. I don't think for a general policy $\pi$ that you definition would hold - it should be $Q_\pi(s,a) = \mathbb{E}[r + V_\pi(s') | s, a]$
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T10:07:59.777Z
Answers.Text: @DavidIreland I left the policy that I'm defining it for off yeah, implicitly assuming that it would be for the optimal policy. But the definition would actually work for any greedy policy. In the context of $Q$-learning we do always try to learn about greedy policies.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T10:13:27.277Z
Answers.Text: I agree that it would hold for any greedy policy, but generally we want to learn an $\epsilon$-greedy policy to make sure we are exploring sufficiently. I guess once it is considered to be performing optimally (or close to) and you want to use it (e.g. playing Atari games) you could then just always choose the greedy action.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T10:18:53.433Z
Answers.Text: @DavidIreland Normally you'd use an $\epsilon$-greedy policy (or some other form of exploratory policy) to generate experience for training, yes. But in $Q$-learning, you do not aim to learn anything about that policy. You just use it to generate experience, which you then use to learn about a completely different policy (a policy that's greedy with respect to your $Q$-values). This is why $Q$-learning is an **off-policy** algorithm; it learns about a policy that's different from the one used to generate experience.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T10:27:28.883Z
Answers.Text: Ah sorry, in your answer I thought you were talking about the general definition of $Q(s,a)$ - not specifically in the context of Q-learning. My bad.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T09:52:07.450Z
Answers.LastActivityDate: 2020-05-22T09:52:07.450Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I have seen two deep Q-learning formulas:</p>
  
  <p><span class="math-container">$$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]$$</span></p>
  
  <p>and this one</p>
  
  <p><span class="math-container">$$Q(s, a)=r(s, a)+\gamma \max _{a} Q\left(s^{\prime}, a\right)$$</span></p>
  
  <p>Which one is correct?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T09:42:09.173Z
Comments.Text: Both are correct. The second one however is used in the deterministic case because applying the second one to stochastic environments with probabilistic state transitions will not cause the Q values to converge.
Comments.UserDisplayName: calveeen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T09:53:55.180Z
Comments.Text: @calveeen It's not just about stochastic environments. It's also about the fact that the $Q(S_{t+1}, a)$ values being used for bootstrapping may be inaccurate even in deterministic environments (they're our own estimates which are probably not 100% accurate). Stochastic environments do make this worse though, yes.
Comments.UserDisplayName: Dennis Soemers
Tags: <reinforcement-learning><q-learning><deep-rl>
Title: Do we have two Q-learning update formulas?
UserDisplayName: dato nefaridze
ThreadText: # Do we have two Q-learning update formulas?
  
  (Asked by: username_0 on 2020-05-22)
  
  I have seen two deep Q-learning formulas:
  
  $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right)+\alpha\left[R\_{t+1}+\gamma \max \_{a} Q\left(S\_{t+1}, a\right)-Q\left(S\_{t}, A\_{t}\right)\right]$$
  
  and this one
  
  $$Q(s, a)=r(s, a)+\gamma \max \_{a} Q\left(s^{\prime}, a\right)$$
  
  Which one is correct?
  
  **Tags:** reinforcement-learning, q-learning, deep-rl
  
  > **Comments:**
  > **username_1**: Both are correct. The second one however is used in the deterministic case because applying the second one to stochastic environments with probabilistic state transitions will not cause the Q values to converge.  
  > **username_2**: @username_1 It's not just about stochastic environments. It's also about the fact that the $Q(S_{t+1}, a)$ values being used for bootstrapping may be inaccurate even in deterministic environments (they're our own estimates which are probably not 100% accurate). Stochastic environments do make this worse though, yes.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-05-22. Score: 2 | Accepted answer
  
  The first one is the update rule that we use in the $Q$-learning algorithm.
  
  The second one is the "definition" of $Q(s, a)$ values, although I would personally write it as follows, with an expectation around the reward, to also support cases where rewards might be non-deterministic;
  
  $$Q(s, a) \doteq \mathbb{E} \left[ r(s, a) \right] + \gamma \max\_a Q(s', a)$$
  
  Here, the $Q(s', a)$ itself would also be similarly defined, and again that one is also assumed to be a "ground-truth" value.
  
  In practice, when learning, we do not actually know what any of these $Q$-values exactly are; that's why we're doing learning in the first place, we're trying to learn what these values are! More precisely, when we wish to assign a new value to $Q(s, a)$, the definition tells us that we should use $Q(s', a)$ for that, but we can't because we don't know exactly what the correct $Q(s', a$) value is either.
  
  We do generally have some $Q(S\_{t+1}, a)$ values, but they're generally going to be only **approximations**, resulting from the previous steps of our own learning process (or maybe even randomly initialised values if we only just started training!). There may also be an additional approximation error in stochastic environments, where the true $Q(s', a)$ value may be a weighted average over multiple different possible successor states $s'$, but during the training we only observed a single concrete successor state $S\_{t+1}$.
  
  So, we can follow the definition and use $Q(S\_{t+1}, a)$ as an approximation of $Q(s', a)$, but we know that it's just an approximation and not entirely reliable. Therefore, instead of fully applying the definition and completely replacing our $Q(s, a)$ value based on it, we **interpolate** between our current estimate $Q(s, a)$ and the new one that we should have according to the definition + our approximations. We only slightly shift towards it. The learning rate $\alpha$ determines how much we shift towards it. Normally we use a learning rate $0 < \alpha < 1$. Note that if you were to use $\alpha = 1$, you would actually recover the definition for $Q$-values again (except it would still use some observations to estimate unknown quantities).
  
  > **Comments:**
  > **username_3**: I think that the definition of the $Q(s,a)$ as you have defined them would only hold if we were following the optimal policy. I don't think for a general policy $\pi$ that you definition would hold - it should be $Q_\pi(s,a) = \mathbb{E}[r + V_\pi(s') | s, a]$  
  > **username_2**: @DavidIreland I left the policy that I'm defining it for off yeah, implicitly assuming that it would be for the optimal policy. But the definition would actually work for any greedy policy. In the context of $Q$-learning we do always try to learn about greedy policies.  
  > **username_3**: I agree that it would hold for any greedy policy, but generally we want to learn an $\epsilon$-greedy policy to make sure we are exploring sufficiently. I guess once it is considered to be performing optimally (or close to) and you want to use it (e.g. playing Atari games) you could then just always choose the greedy action.  
  > **username_2**: @DavidIreland Normally you'd use an $\epsilon$-greedy policy (or some other form of exploratory policy) to generate experience for training, yes. But in $Q$-learning, you do not aim to learn anything about that policy. You just use it to generate experience, which you then use to learn about a completely different policy (a policy that's greedy with respect to your $Q$-values). This is why $Q$-learning is an **off-policy** algorithm; it learns about a policy that's different from the one used to generate experience.  
  > **username_3**: Ah sorry, in your answer I thought you were talking about the general definition of $Q(s,a)$ - not specifically in the context of Q-learning. My bad.  
  
  ---
  
  