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), 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). 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!

  • 2
    $\begingroup$ when you take $\mathbb{E}$ of the $Q$ function, what are you taking expectation with respect to? The $Q$ function already is an expectation. $\endgroup$ Jun 15 '20 at 19:10
  • $\begingroup$ @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()$ $\endgroup$ Jun 16 '20 at 4:00
  • 1
    $\begingroup$ Right, then your notation doesn’t make sense. You should write $\mathbb{E}[Q(s_{t+1}, a)] \rightarrow q(s_{t+1}, a)$ $\endgroup$ Jun 16 '20 at 8:49
  • $\begingroup$ @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. $\endgroup$ Jun 16 '20 at 9:15
  • $\begingroup$ I think the rest of your proof looks good as far as I can tell, good job :) $\endgroup$ Jun 16 '20 at 9:16

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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.