Working through Sutton and Barto's reinforcement learning book and van Hasselt's original Double Q-Learning (2010) paper to understand Double-Q learning. In the original paper, van Hasselt uses the game of roulette as an example of the problem of overestimation of Q-learning. In roulette the average expected return across all bets, given a bet of $1, is slightly less than one. This problem can thus be simplified as an episodic MDP (as done by Sutton and Barto) to show the principle.

Episodic MDP

Starting at A, you can go left or right. Grey boxes are terminal states. Reward for initial left or right is 0. From B, you have an option of actions (8 in the book) which each return a reward drawn from a normal distribution with $\mu=-0.1$ and $\sigma^2=1$. The expected value of going left is thus negative and it's always a bad choice.

Writing up the algorithm for Q-learning and Double-Q learning with $\epsilon=0.1$,$\gamma=1$,$\alpha=\frac{1}{n(s,a)^{0.8}}$ to match the original paper, it is easy to reproduce the results shown in Sutton and Barto. The image is averaging over 10,000 models showing the proportion of decisions going left from A at each round of training.

Q vs Double-Q

Because Q-learning has an overestimation bias, it first wrongly favors the left action, before eventually settling down, but still having a higher proportion of runs favoring left at asymptote than is optimal. Double-Q learning converges pretty quickly towards the optimal result.

That all makes sense; Double-Q learning was designed to compensate for the overestimation bias of Q-learning. But what about cases where overestimation helps? Let's flip this very simple toy problem on its head and set $\mu=+0.1$ and $\sigma^2=1$. The exact same problem, but now our expected return for going left is slightly positive, and going left is always the better choice.

In this case Q-learning converges very quickly to the correct result, and double-q learning asymptotically approaches the wrong decision.

Positive Reward

Let's keep going, for way more training rounds:

Double-Q slowly getting there

We can see that Double-Q learning is slowly approaching the correct solution but with hundreds of thousands more training rounds required than vanilla Q-learning, even on this toy problem.

What am I missing? Double-Q learning is quite popular now in deep Q-learning but from this toy example it seems to give only marginal improvements in learning convergence when it's problematic to overestimate rewards but very bad performance degradation in cases where overestimation is advantageous? Why does Double-Q converge so slowly? Given it's popularity, I must be missing something.

MWE: Notebook MWE

  • $\begingroup$ could you link to your code? would make reproducing / investigating this easier $\endgroup$
    – shimao
    Mar 20, 2021 at 16:27
  • $\begingroup$ @shimao added link to MWE notebook. $\endgroup$
    – Daniel
    Mar 20, 2021 at 17:47

1 Answer 1


Overestimation occurs when rewards are awarded stochastically. The larger the variance of these stochastic rewards, the more severe the overestimation. So when there is a specific problem where good states have stochastic rewards with large variance and bad states do not, the bias does indeed improve performance compared to an unbiased algorithm. That is the nature of being biased: in situations where you are correct you are more correct, and in situations where you are wrong you are more wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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