Self-correcting Q-Learning
This work provides an incremental improvement to reinforcement learning algorithms by mitigating the maximization bias for practitioners using Q-learning and its variants.
This paper tackles the problem of maximization bias in Q-learning, which causes overestimation of action values, and proposes Self-correcting Q-learning to balance the overestimation of Q-learning and the underestimation of Double Q-learning. The new algorithm theoretically converges like Q-learning but is more accurate, outperforming Double Q-learning in high-variance reward domains and converging faster than Q-learning in low-variance domains. Self-correcting DQN also outperforms DQN and Double DQN on several Atari 2600 tasks.
The Q-learning algorithm is known to be affected by the maximization bias, i.e. the systematic overestimation of action values, an important issue that has recently received renewed attention. Double Q-learning has been proposed as an efficient algorithm to mitigate this bias. However, this comes at the price of an underestimation of action values, in addition to increased memory requirements and a slower convergence. In this paper, we introduce a new way to address the maximization bias in the form of a "self-correcting algorithm" for approximating the maximum of an expected value. Our method balances the overestimation of the single estimator used in conventional Q-learning and the underestimation of the double estimator used in Double Q-learning. Applying this strategy to Q-learning results in Self-correcting Q-learning. We show theoretically that this new algorithm enjoys the same convergence guarantees as Q-learning while being more accurate. Empirically, it performs better than Double Q-learning in domains with rewards of high variance, and it even attains faster convergence than Q-learning in domains with rewards of zero or low variance. These advantages transfer to a Deep Q Network implementation that we call Self-correcting DQN and which outperforms regular DQN and Double DQN on several tasks in the Atari 2600 domain.