On the Estimation Bias in Double Q-Learning
  Double Q-learning is a classical method for reducing overestimation bias,
which is caused by taking maximum estimated values in the Bellman operation.
Its variants in the deep Q-learning paradigm have shown great promise in
producing reliable value prediction and improving learning performance.
However, as shown by prior work, double Q-learning is not fully unbiased and
suffers from underestimation bias. In this paper, we show that such
underestimation bias may lead to multiple non-optimal fixed points under an
approximate Bellman operator. To address the concerns of converging to
non-optimal stationary solutions, we propose a simple but effective approach as
a partial fix for the underestimation bias in double Q-learning. This approach
leverages an approximate dynamic programming to bound the target value. We
extensively evaluate our proposed method in the Atari benchmark tasks and
demonstrate its significant improvement over baseline algorithms.
