  Value-based reinforcement-learning algorithms have shown strong results in
games, robotics, and other real-world applications. Overestimation bias is a
known threat to those algorithms and can lead to dramatic performance decreases
or even complete algorithmic failure. We frame the bias problem statistically
and consider it an instance of estimating the maximum expected value (MEV) of a
set of random variables. We propose the $T$-Estimator (TE) based on two-sample
testing for the mean, that flexibly interpolates between over- and
underestimation by adjusting the significance level of the underlying
hypothesis tests. A generalization, termed $K$-Estimator (KE), obeys the same
bias and variance bounds as the TE while relying on a nearly arbitrary kernel
function. We introduce modifications of $Q$-Learning and the Bootstrapped Deep
$Q$-Network (BDQN) using the TE and the KE, and prove convergence in the
tabular setting. Furthermore, we propose an adaptive variant of the TE-based
BDQN that dynamically adjusts the significance level to minimize the absolute
estimation bias. All proposed estimators and algorithms are thoroughly tested
and validated on diverse tasks and environments, illustrating the bias control
and performance potential of the TE and KE.
