Q-learning [1]} and its deep learning based successors inaugurated by DQN [2]} are model-free, value function based reinforcement learning algorithms. Their popularity stems from their intuitive, easy-to-implement update rule derived from the Bellman equations. At each time step, the agent updates its Q-value towards the expectation of the current reward plus the value corresponding to the maximal action in the next state. This state-action value represents the maximum sum of reward the agent believes it could obtain from the current state by taking the current action. Unfortunately [3]}, [4]} have shown that this simple rule suffers from overestimation bias: due to the maximization operator in the update rule, upwards and downwards errors do not cancel each other out, but upwards errors accumulate. The overestimation bias is particularly problematic under function approximation and have contributed towards learning sub-optimal policies [3]}, [6]}, [7]}.
