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.
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.
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.
Let's keep going, for way more training rounds:
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
