Maxmin Q-learning: Controlling the Estimation Bias of Q-learning

Q-learning (Watkins, 1989) is one of the most popular reinforcement learning algorithms. One of the reasons for this widespread adoption is the simplicity of the update. On each step, the agent updates its action value estimates towards the observed reward and the estimated value of the maximal action in the next state. This target represents the highest value the agent thinks it could obtain from the current state and action, given the observed reward.

Unfortunately, this simple update rule has been shown to suffer from overestimation bias (Thrun & Schwartz, 1993; van Hasselt, 2010). The agent updates with the maximum over action values might be large because an action’s value actually is high, or it can be misleadingly high simply because of the stochasticity or errors in the estimator. With many actions, there is a higher probability that one of the estimates is large simply due to stochasticity and the agent will overestimate the value. This issue is particularly problematic under function approximation, and can significant impede the quality of the learned policy (Thrun & Schwartz, 1993; Szita & Lőrincz, 2008; Strehl et al., 2009) or even lead to failures of Q-learning (Thrun & Schwartz, 1993). More recently, experiments across several domains suggest that this overestimation problem is common (Hado van Hasselt et al., 2016).

Double Q-learning (van Hasselt, 2010) is introduced to instead ensure underestimation bias. The idea is to maintain two unbiased independent estimators of the action values. The expected action value of estimator one is selected for the maximal action from estimator two, which is guaranteed not to overestimate the true maximum action value. Double DQN (Hado van Hasselt et al., 2016), the extension of this idea to Q-learning with neural networks, has been shown to significantly improve performance over Q-learning. However, this is not a complete answer to this problem, because trading overestimation bias for underestimation bias is not always desirable, as we show in our experiments.

Several other methods have been introduced to reduce overestimation bias, without fully moving towards underestimation. Weighted Double Q-learning (Zhang et al., 2017) uses a weighted combination of the Double Q-learning estimate, which likely has underestimation bias, and the Q-learning estimate, which likely has overestimation bias. Bias-corrected Q-Learning (Lee et al., 2013) reduces the overestimation bias through a bias correction term. Ensemble Q-learning and Averaged Q-learning (Anschel et al., 2017) take averages of multiple action values, to both reduce the overestimation bias and the estimation variance. However, with a finite number of action-value functions, the average operation in these two algorithms will never completely remove the overestimation bias, as the average of several overestimation biases is always positive. Further, these strategies do not guide how strongly we should correct for overestimation bias, nor how to determine—or control—the level of bias.

The overestimation bias also appears in the actor-critic setting (Fujimoto et al., 2018; Haarnoja et al., 2018). For example, Fujimoto et al. (2018) propose the Twin Delayed Deep Deterministic policy gradient algorithm (TD3) which reduces the overestimation bias by taking the minimum value between two critics. However, they do not provide a rigorous theoretical analysis for the effect of applying the minimum operator. There is also no theoretical guide for choosing the number of estimators such that the overestimation bias can be reduced to 0.

In this paper, we study the effects of overestimation and underestimation bias on learning performance, and use them to motivate a generalization of Q-learning called Maxmin Q-learning. Maxmin Q-learning directly mitigates the overestimation bias by using a minimization over multiple action-value estimates. Moreover, it is able to control the estimation bias varying from positive to negative which helps improve learning efficiency as we will show in next sections. We prove that, theoretically, with an appropriate number of action-value estimators, we are able to acquire an unbiased estimator with a lower approximation variance than Q-learning. We empirically verify our claims on several benchmarks. We study the convergence properties of our algorithm within a novel Generalized Q-learning framework, which is suitable for studying several of the recently proposed Q-learning variants. We also combine deep neural networks with Maxmin Q-learning (Maxmin DQN) and demonstrate its effectiveness in several benchmark domains.

We formalize the problem as a Markov Decision Process (MDP), $(\mathcal{S},\mathcal{A},\mathrm{P},r,\gamma)$, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $\mathrm{P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is the transition probabilities, $r:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ is the reward mapping, and $\gamma\in[0,1]$ is the discount factor. At each time step $t$, the agent observes a state $S_{t}\in\mathcal{S}$ and takes an action $A_{t}\in\mathcal{A}$ and then transitions to a new state $S_{t+1}\in\mathcal{S}$ according to the transition probabilities $\mathrm{P}$ and receives a scalar reward $R_{t+1}=r(S_{t},A_{t},S_{t+1})\in\mathbb{R}$. The goal of the agent is to find a policy $\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ that maximizes the expected return starting from some initial state.

Q-learning is an off-policy algorithm which attempts to learn the state-action values $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ for the optimal policy. It tries to solve for

The optimal policy is to act greedily with respect to these action values: from each $s$ select $a$ from $\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}(s,a)$. The update rule for an approximation $Q$ for a sampled transition $s_{t},a_{t},r_{t+1},s_{t+1}$ is:

where $\alpha$ is the step-size. The transition can be generated off-policy, from any behaviour that sufficiently covers the state space. This algorithm is known to converge in the tabular setting (Tsitsiklis, 1994), with some limited results for the function approximation setting (Melo & Ribeiro, 2007).

In this section, we briefly discuss the estimation bias issue, and empirically show that both overestimation and underestimation bias may improve learning performance, depending on the environment. This motivates our Maxmin Q-learning algorithm described in the next section, which allows us to flexibly control the estimation bias and reduce the estimation variance.

The overestimation bias occurs since the target $\max_{a^{\prime}\in\mathcal{A}}Q(s_{t+1},a^{\prime})$ is used in the Q-learning update. Because $Q$ is an approximation, it is probable that the approximation is higher than the true value for one or more of the actions. The maximum over these estimators, then, is likely to be skewed towards an overestimate. For example, even unbiased estimates $Q(s_{t+1},a^{\prime})$ for all $a^{\prime}$, will vary due to stochasticity. $Q(s_{t+1},a^{\prime})=Q^{*}(s_{t+1},a^{\prime})+e_{a^{\prime}}$, and for some actions, $e_{a^{\prime}}$ will be positive. As a result, $\mathbb{E}[\max_{a^{\prime}\in\mathcal{A}}Q(s_{t+1},a^{\prime})]\geq\max_{a^{\prime}\in\mathcal{A}}\mathbb{E}[Q(s_{t+1},a^{\prime})]=\max_{a^{\prime}\in\mathcal{A}}Q^{*}(s_{t+1},a^{\prime})$.

This overestimation bias, however, may not always be detrimental. And, further, in some cases, erring towards an underestimation bias can be harmful. Overestimation bias can help encourage exploration for overestimated actions, whereas underestimation bias might discourage exploration. In particular, we expect more overestimation bias in highly stochastic areas of the world; if those highly stochastic areas correspond to high-value regions, then encouraging exploration there might be beneficial. An underestimation bias might actually prevent an agent from learning that a region is high-value. Alternatively, if highly stochastic areas also have low values, overestimation bias might cause an agent to over-explore a low-value region.

We show this effect in the simple MDP, shown in Figure 1. The MDP for state $A$ has only two actions: Left and Right. It has a deterministic neutral reward for both the Left action and the Right action. The Left action transitions to state $B$ where there are eight actions transitions to a terminate state with a highly stochastic reward. The mean of this stochastic reward is $\mu$. By selecting $\mu>0$, the stochastic region becomes high-value, and we expect overestimation bias to help and underestimation bias to hurt. By selecting $\mu<0$, the stochastic region becomes low-value, and we expect overestimation bias to hurt and underestimation bias to help.

We test Q-learning, Double Q-learning and our new algorithm Maxmin Q-learning in this environment. Maxmin Q-learning (described fully in the next section) uses $N$ estimates of the action values in the targets. For $N=1$, it corresponds to Q-learning; otherwise, it progresses from overestimation bias at $N=1$ towards underestimation bias with increasing $N$. In the experiment, we used a discount factor $\gamma=1$; a replay buffer with size $100$; an $\epsilon$-greedy behaviour with $\epsilon=0.1$; tabular action-values, initialized with a Gaussian distribution $\mathcal{N}(0,0.01)$; and a step-size of $0.01$ for all algorithms.

The results in Figure 2 verify our hypotheses for when overestimation and underestimation bias help and hurt. Double Q-learning underestimates too much for $\mu=+1$, and converges to a suboptimal policy. Q-learning learns the optimal policy the fastest, though for all values of $N=2,4,6,8$, Maxmin Q-learning does progress towards the optimal policy. All methods get to the optimal policy for $\mu=-1$, but now Double Q-learning reaches the optimal policy the fastest, and followed by Maxmin Q-learning with larger $N$.

In this section, we develop Maxmin Q-learning, a simple generalization of Q-learning designed to control the estimation bias, as well as reduce the estimation variance of action values. The idea is to maintain $N$ estimates of the action values, $Q^{i}$, and use the minimum of these estimates in the Q-learning target: $\max_{a^{\prime}}\min_{i\in\{1,\ldots,N\}}Q^{i}(s^{\prime},a^{\prime})$. For $N=1$, the update is simply Q-learning, and so likely has overestimation bias. As $N$ increase, the overestimation decreases; for some $N>1$, this maxmin estimator switches from an overestimate, in expectation, to an underestimate. We characterize the relationship between $N$ and the expected estimation bias below in Theorem 1. Note that Maxmin Q-learning uses a different mechanism to reduce overestimation bias than Double Q-learning; Maxmin Q-learning with $N=2$ is not Double Q-learning.

The full algorithm is summarized in Algorithm 1, and is a simple modification of Q-learning with experience replay. We use random subsamples of the observed data for each of the $N$ estimators, to make them nearly independent. To do this training online, we keep a replay buffer. On each step, a random estimator $i$ is chosen and updated using a mini-batch from the buffer. Multiple such updates can be performed on each step, just like in experience replay, meaning multiple estimators can be updated per step using different random mini-batches. In our experiments, to better match DQN, we simply do one update per step. Finally, it is also straightforward to incorporate target networks to get Maxmin DQN, by maintaining a target network for each estimator.

We now characterize the relation between the number of action-value functions used in Maxmin Q-learning and the estimation bias of action values. For compactness, we write $Q^{i}_{sa}$ instead of $Q^{i}(s,a)$. Each $Q^{i}_{sa}$ has random approximation error $e^{i}_{sa}$

We assume that $e^{i}_{sa}$ is a uniform random variable $U(-\tau,\tau)$ for some $\tau>0$. The uniform random assumption was used by Thrun & Schwartz (1993) to demonstrate bias in Q-learning, and reflects that non-negligible positive and negative $e^{i}_{sa}$ are possible. Notice that for $N$ estimators with $n_{sa}$ samples, the $\tau$ will be proportional to some function of $n_{sa}/N$, because the data will be shared amongst the $N$ estimators. For the general theorem, we use a generic $\tau$, and in the following corollary provide a specific form for $\tau$ in terms of $N$ and $n_{sa}$.

Recall that $M$ is the number of actions applicable at state $s^{\prime}$. Define the estimation bias $Z_{MN}$ for transition $s,a,r,s^{\prime}$ to be

where

Theorem 1 is a generalization of the first lemma in Thrun & Schwartz (1993); we provide the proof in Appendix A as well as a visualization of the expected bias for varying $M$ and $N$. This theorem shows that the average estimation bias $E[Z_{MN}]$, decreases as $N$ increases. Thus, we can control the bias by changing the number of estimators in Maxmin Q-learning. Specifically, the average estimation bias can be reduced from positive to negative as $N$ increases. Notice that $E[Z_{MN}]=0$ when $t_{MN}=\frac{1}{2}$. This suggests that by choosing $N$ such that $t_{MN}\approx\frac{1}{2}$, we can reduce the bias to near $0$.

Furthermore, $Var[Q_{sa}^{min}]$ decreases as $N$ increases. This indicates that we can control the estimation variance of target action value through $N$. We show just this in the following Corollary. The subtlety is that with increasing $N$, each estimator will receive less data. The fair comparison is to compare the variance of a single estimator that uses all of the data, as compared to the maxmin estimator which shares the samples across $N$ estimators. We show that there is an $N$ such that the variance is lower, which arises largely due to the fact that the variance of each estimator decreases linearly in $n$, but the $\tau$ parameter for each estimator only decreases at a square root rate in the number of samples.

In this section, we first investigate robustness to reward variance, in a simple environment (Mountain Car) in which we can perform more exhaustive experiments. Then, we investigate performance in seven benchmark environments.

In this section, we show Maxmin Q-learning is convergent in the tabular setting. We do so by providing a more general result for what we call Generalized Q-learning: Q-learning where the bootstrap target uses a function $G$ of $N$ action values. The main condition on $G$ is that it maintains relative maximum values, as stated in Assumption 1. We use this more general result to prove Maxmin Q-learning is convergent, and then discuss how it provides convergence results for Q-learning, Ensemble Q-learning, Averaged Q-learning and Historical Best Q-learning as special cases.

Many variants of Q-learning have been proposed, including Double Q-learning (van Hasselt, 2010), Weighted Double Q-learning (Zhang et al., 2017), Ensemble Q-learning (Anschel et al., 2017), Averaged Q-learning (Anschel et al., 2017), and Historical Best Q-learning (Yu et al., 2018). These algorithms differ in their estimate of the one-step bootstrap target. To encompass all variants, the target action-value of Generalized Q-learning $Y^{GQ}$ is defined based on action-value estimates from both dimensions:

where $t$ is the current time step and the action-value function $Q_{s}^{GQ}(t)$ is a function of $Q_{s}^{1}(t-K),\ldots,Q_{s}^{1}(t-1),\ldots,Q_{s}^{N}(t-K),\ldots,Q_{s}^{N}(t-1)$:

For simplicity, the vector $(Q^{GQ}_{sa}(t))_{a\in\mathcal{A}}$ is denoted as $Q^{GQ}_{s}(t)$, same for $Q^{i}_{s}(t)$. The corresponding update rule is

For different $G$ functions, Generalized Q-learning reduces to different variants of Q-learning, including Q-learning itself. For example, Generalized Q-learning can be reduced to Q-learning simply by setting $K=1$, $N=1$ with $G(Q_{s})=\max_{a\in A}Q_{sa}$. Double Q-learning can be specified with $K=1$, $N=2$, and $G(Q_{s}^{1},Q_{s}^{2})=Q^{2}_{s,\arg\max_{a^{\prime}\in A}Q_{sa^{\prime}}^{1}}$.

We can verify that Assumption 1 holds for Maxmin Q-learning. Set $K=1$ and set $N$ to be a positive integer. Let $Q_{s}=(Q^{1}_{s},\ldots,Q^{N}_{s})$ and define $G^{MQ}(Q_{s})=\max_{a\in A}\min_{i\in\{1,\ldots,N\}}Q^{i}_{sa}$. It is easy to check that part (i) of Assumption 1 is satisfied. Part (ii) is also satisfied because

As shown above, because the function $G$ for Maxmin Q-learning satisfies Assumption 1, then by Theorem 2 it converges. Next, we apply Theorem 2 to Q-learning and its variants, proving the convergence of these algorithms in the tabular case. For Q-learning, set $K=1$ and $N=1$. Let $G^{Q}(Q_{s})=\max_{a\in A}Q_{sa}$. It is straightforward to check that Assumption 1 holds for function $G^{Q}$. For Ensemble Q-learning, set $K=1$ and set $N$ to be a positive integer. Let $G^{EQ}((Q^{1}_{s},\ldots,Q^{N}_{s}))=\max_{a\in A}\frac{1}{N}\sum_{i=1}^{N}Q^{i}_{sa}$. Easy to check that Assumption 1 is satisfied. For Averaged Q-learning, the proof is similar to Ensemble Q-learning except that $N=1$ and $K$ is a positive integer. For Historical Best Q-learning, set $N=1$ and $K$ to be a positive integer. We assume that all auxiliary action-value functions are selected from action-value functions at most $K$ updates ago. Define $G^{HBQ}$ to be the largest action-value among $Q_{sa}(t-1),\ldots,Q_{sa}(t-K)$ for state $s$. Assumption 1 is satisfied and the convergence is guaranteed.

Overestimation bias is a byproduct of Q-learning, stemming from the selection of a maximal value to estimate the expected maximal value. In practice, overestimation bias leads to poor performance in a variety of settings. Though multiple Q-learning variants have been proposed, Maxmin Q-learning is the first solution that allows for a flexible control of bias, allowing for overestimation or underestimation determined by the choice of $N$ and the environment. We showed theoretically that we can decrease the estimation bias and the estimation variance by choosing an appropriate number $N$ of action-value functions. We empirically showed that advantages of Maxmin Q-learning, both on toy problems where we investigated the effect of reward noise and on several benchmark environments. Finally, we introduced a new Generalized Q-learning framework which we used to prove the convergence of Maxmin Q-learning as well as several other Q-learning variants that use $N$ action-value estimates.