Answers.Body: <p>Your bias formula is a bit incorrect. You should subtract a true value, not an estimator.</p>
  <ol>
  <li><p><span class="math-container">$\mathrm{b}(\hat{\theta}) \stackrel{\text { def }}{=} \mathbb{E}[\hat{\theta}]-\theta$</span></p>
  </li>
  <li><p><span class="math-container">$\mathrm{b}\left(\max _{a} Q\right)=\mathbb{E}\left[\max _{a} Q\right]-\max _{a} q=\mathbb{E}\left[\max _{a} Q\right]-\max _{a} \mathbb{E}[Q]$</span></p>
  </li>
  <li><p><span class="math-container">$\mathbb{E}\left[\max _{a} Q\right] \geq \max _{a} \mathbb{E}[Q] \Rightarrow \mathrm{b}\left(\max _{a} Q\right) \geq 0$</span></p>
  </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-08T13:41:04.433Z
Answers.LastActivityDate: 2021-01-19T11:22:18.193Z
Answers.LastEditDate: 2021-01-19T11:22:18.193Z
Answers.UserDisplayName: Дмитрий Винник
Body: <p>In the textbook "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, the concept of Maximization Bias is introduced in section 6.7, and how Q-learning "over-estimates" action-values is discussed using an example. However, a formal proof of the same is not presented in the textbook, and I couldn't get it anywhere on the internet as well. </p>
  
  <p>After reading the paper on Double Q-learning by Hado van Hasselt (<a href="https://papers.nips.cc/paper/3964-double-q-learning.pdf" rel="noreferrer">link</a>), I could understand to some extent why Q-learning "over-estimates" action values. Here is my (vague, informal) construction of a mathematical proof:</p>
  
  <p>We know that Temporal Methods (just like Monte Carlo methods), use sample returns instead of real expected returns as estimates, to find the optimal policy. These sample returns converge to the true expected returns over infinite trials, provided all the state-action pairs are visited. Thus the following notation is used, </p>
  
  <p><span class="math-container">$$\mathbb{E}[Q()] \rightarrow q_\pi()$$</span>
  where <span class="math-container">$Q()$</span> is calculated from the sample return <span class="math-container">$G_t$</span> observed at every time-step. Over infinite trials, this sample return when averaged converges to it's expected value which is the true <span class="math-container">$Q$</span>-value under the policy <span class="math-container">$\pi$</span>. Thus <span class="math-container">$Q()$</span> is really an estimate of the true <span class="math-container">$Q$</span>-value <span class="math-container">$q_\pi$</span>.</p>
  
  <p>In section 3 on page 4 of the paper, Hasselt describes how the quantity <span class="math-container">$\max_a Q(s_{t+1}, a)$</span> approximates <span class="math-container">$\mathbb{E}[\max_a Q(s_{t+1}, a)]$</span> which in turn approximates the quantity <span class="math-container">$\max_a(\mathbb{E}[Q(s_{t+1},a)])$</span> in Q-learning. Now, we know that the <span class="math-container">$\max[]$</span> function is a convex function (<a href="https://math.stackexchange.com/questions/2435464/show-that-max-function-on-mathbb-rn-is-convex">proof</a>). From Jensen's inequality, we have
  <span class="math-container">$$\phi(\mathbb{E}[X]) \leq \mathbb{E}[\phi(X)]$$</span> where <span class="math-container">$X$</span> is a random variable, and the function <span class="math-container">$\phi()$</span> is a convex function. Thus,
  <span class="math-container">$$\max_a(\mathbb{E}[Q(s_{t+1},a)]) \leq \mathbb{E}[\max_a(Q(s_{t+1}, a)]$$</span></p>
  
  <p><span class="math-container">$$\therefore \max_a Q(s_{t+1}, a) \approx \max_a(\mathbb{E}[Q(s_{t+1},a)]) \leq \mathbb{E}[\max_a(Q(s_{t+1}, a)]$$</span></p>
  
  <p>The quantity on the LHS of the above equation appears (along with <span class="math-container">$R_{t+1}$</span>) as an estimate of the next action-value in the Q-learning update equation:
  <span class="math-container">$$Q(S_t,A_t) \leftarrow (1-\alpha)Q(S_t, A_t) + \alpha[R_{t+1} + \gamma\max_aQ(S_{t+1}, a)] $$</span></p>
  
  <p>Lastly, we note that the bias of an estimate <span class="math-container">$T$</span> is given by:
  <span class="math-container">$$b(T) = \mathbb{E}[T] - T$$</span>
  Thus the bias of the estimate <span class="math-container">$\max_a Q(s_{t+1},a)$</span> will always be positive:
  <span class="math-container">$$b(\max_a Q(s_{t+1},a)) = \mathbb{E}[\max_a Q(s_{t+1},a)] - \max_a Q(s_{t+1},a) \geq 0$$</span>
  In statistics literature, any estimate whose bias is positive is said to be an "over-estimate". Thus the action values are over-estimated by the Q-learning algorithm due to the <span class="math-container">$\max[]$</span> operator, thus resulting in a <span class="math-container">$maximization$</span>-<span class="math-container">$bias$</span>.</p>
  
  <p>Are the arguments made above valid? I am a student, with no rigorous knowledge of random processes. Thus, please forgive me if any of the steps above are totally unrelated, and doesn't make sense in a more mathematically rigorous fashion. Please let me know, if there is a much better proof than this failed attempt. </p>
  
  <p>Thank you so much for your precious time. Any help/suggestions/corrections are greatly appreciated!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T19:10:08.340Z
Comments.Text: when you take $\mathbb{E}$ of the $Q$ function, what are you taking expectation with respect to? The $Q$ function already is an expectation.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T04:00:54.577Z
Comments.Text: @DavidIreland, In TD methods, the Q function will not have any expectation, as we are just using sample returns instead of true expected values i.e., to say, instead of using $\mathbb{E}_\pi[G_t|S_t = s, A_t = a]$, we just use $G_t$, and then average them, which is then assigned to Q(). Thus, here $\mathbb{E}[Q()] = q_\pi()$. The approximation in Q-learning update equation occurs as we are using $\gamma\max_a Q()$ instead of $\gamma\max_a q_\pi()$
Comments.UserDisplayName: Jarvis1997
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T08:49:31.820Z
Comments.Text: Right, then your notation doesn’t make sense. You should write $\mathbb{E}[Q(s_{t+1}, a)] \rightarrow q(s_{t+1}, a)$
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T09:15:28.997Z
Comments.Text: @DavidIreland Thank you for the suggestion. Like you mentioned, I think it will be better to use different symbols. I have updated my post accordingly.
Comments.UserDisplayName: Jarvis1997
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T09:16:08.687Z
Comments.Text: I think the rest of your proof looks good as far as I can tell, good job :)
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T09:50:10.300Z
Comments.Text: @DavidIreland Following your suggestion, I have restructured my entire proof, to make it as less confusing as possible. I have also added another line from the paper that I have referred to, to convey what exactly $Q()$ is. I am truly thankful for your valuable time. Please let me know if you have any other suggestions / corrections that would help other readers. Thank you!
Comments.UserDisplayName: Jarvis1997
Tags: <reinforcement-learning><q-learning><proofs>
Title: Proof of Maximization Bias in Q-learning?
UserDisplayName: Jarvis1997
ThreadText: # Proof of Maximization Bias in Q-learning?
  
  (Asked by: username_0 on 2020-06-15)
  
  In the textbook "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, the concept of Maximization Bias is introduced in section 6.7, and how Q-learning "over-estimates" action-values is discussed using an example. However, a formal proof of the same is not presented in the textbook, and I couldn't get it anywhere on the internet as well.
  
  After reading the paper on Double Q-learning by Hado van Hasselt ([link](https://papers.nips.cc/paper/3964-double-q-learning.pdf)), I could understand to some extent why Q-learning "over-estimates" action values. Here is my (vague, informal) construction of a mathematical proof:
  
  We know that Temporal Methods (just like Monte Carlo methods), use sample returns instead of real expected returns as estimates, to find the optimal policy. These sample returns converge to the true expected returns over infinite trials, provided all the state-action pairs are visited. Thus the following notation is used,
  
  $$\mathbb{E}[Q()] \rightarrow q\_\pi()$$
  where $Q()$ is calculated from the sample return $G\_t$ observed at every time-step. Over infinite trials, this sample return when averaged converges to it's expected value which is the true $Q$-value under the policy $\pi$. Thus $Q()$ is really an estimate of the true $Q$-value $q\_\pi$.
  
  In section 3 on page 4 of the paper, Hasselt describes how the quantity $\max\_a Q(s\_{t+1}, a)$ approximates $\mathbb{E}[\max\_a Q(s\_{t+1}, a)]$ which in turn approximates the quantity $\max\_a(\mathbb{E}[Q(s\_{t+1},a)])$ in Q-learning. Now, we know that the $\max[]$ function is a convex function ([proof](https://math.stackexchange.com/questions/2435464/show-that-max-function-on-mathbb-rn-is-convex)). From Jensen's inequality, we have
  $$\phi(\mathbb{E}[X]) \leq \mathbb{E}[\phi(X)]$$ where $X$ is a random variable, and the function $\phi()$ is a convex function. Thus,
  $$\max\_a(\mathbb{E}[Q(s\_{t+1},a)]) \leq \mathbb{E}[\max\_a(Q(s\_{t+1}, a)]$$
  
  $$\therefore \max\_a Q(s\_{t+1}, a) \approx \max\_a(\mathbb{E}[Q(s\_{t+1},a)]) \leq \mathbb{E}[\max\_a(Q(s\_{t+1}, a)]$$
  
  The quantity on the LHS of the above equation appears (along with $R\_{t+1}$) as an estimate of the next action-value in the Q-learning update equation:
  $$Q(S\_t,A\_t) \leftarrow (1-\alpha)Q(S\_t, A\_t) + \alpha[R\_{t+1} + \gamma\max\_aQ(S\_{t+1}, a)] $$
  
  Lastly, we note that the bias of an estimate $T$ is given by:
  $$b(T) = \mathbb{E}[T] - T$$
  Thus the bias of the estimate $\max\_a Q(s\_{t+1},a)$ will always be positive:
  $$b(\max\_a Q(s\_{t+1},a)) = \mathbb{E}[\max\_a Q(s\_{t+1},a)] - \max\_a Q(s\_{t+1},a) \geq 0$$
  In statistics literature, any estimate whose bias is positive is said to be an "over-estimate". Thus the action values are over-estimated by the Q-learning algorithm due to the $\max[]$ operator, thus resulting in a $maximization$-$bias$.
  
  Are the arguments made above valid? I am a student, with no rigorous knowledge of random processes. Thus, please forgive me if any of the steps above are totally unrelated, and doesn't make sense in a more mathematically rigorous fashion. Please let me know, if there is a much better proof than this failed attempt.
  
  Thank you so much for your precious time. Any help/suggestions/corrections are greatly appreciated!
  
  **Tags:** reinforcement-learning, q-learning, proofs
  > **Comments:**
  > **username_1**: when you take $\mathbb{E}$ of the $Q$ function, what are you taking expectation with respect to? The $Q$ function already is an expectation.  
  > **username_0**: @DavidIreland, In TD methods, the Q function will not have any expectation, as we are just using sample returns instead of true expected values i.e., to say, instead of using $\mathbb{E}_\pi[G_t|S_t = s, A_t = a]$, we just use $G_t$, and then average them, which is then assigned to Q(). Thus, here $\mathbb{E}[Q()] = q_\pi()$. The approximation in Q-learning update equation occurs as we are using $\gamma\max_a Q()$ instead of $\gamma\max_a q_\pi()$  
  > **username_1**: Right, then your notation doesn’t make sense. You should write $\mathbb{E}[Q(s_{t+1}, a)] \rightarrow q(s_{t+1}, a)$  
  > **username_0**: @DavidIreland Thank you for the suggestion. Like you mentioned, I think it will be better to use different symbols. I have updated my post accordingly.  
  > **username_1**: I think the rest of your proof looks good as far as I can tell, good job :)  
  > **username_0**: @DavidIreland Following your suggestion, I have restructured my entire proof, to make it as less confusing as possible. I have also added another line from the paper that I have referred to, to convey what exactly $Q()$ is. I am truly thankful for your valuable time. Please let me know if you have any other suggestions / corrections that would help other readers. Thank you!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-01-08. Score: 3 | Accepted answer
  
  Your bias formula is a bit incorrect. You should subtract a true value, not an estimator.
  
  1. $\mathrm{b}(\hat{\theta}) \stackrel{\text { def }}{=} \mathbb{E}[\hat{\theta}]-\theta$
  2. $\mathrm{b}\left(\max \_{a} Q\right)=\mathbb{E}\left[\max \_{a} Q\right]-\max \_{a} q=\mathbb{E}\left[\max \_{a} Q\right]-\max \_{a} \mathbb{E}[Q]$
  3. $\mathbb{E}\left[\max \_{a} Q\right] \geq \max \_{a} \mathbb{E}[Q] \Rightarrow \mathrm{b}\left(\max \_{a} Q\right) \geq 0$
  
  
  ---
  
  