On the Estimation Bias in Double Q-Learning
Year: 2022

Abstract:
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.

heading: 1 Introduction
text: Value-based reinforcement learning with neural networks as function approximators has become a widely-used paradigm and shown great promise in solving complicated decision-making problems in various real-world applications, including robotics control (Lillicrap et al., 2016), molecular structure design (Zhou et al., 2019), and recommendation systems (Chen et al., 2018). Towards understanding the foundation of these successes, investigating algorithmic properties of deep-learning-based value function approximation has attracted a growth of attention in recent years (Van Hasselt et al., 2018; Fu et al., 2019; Achiam et al., 2019; Dong et al., 2020). One of the phenomena of interest is that Q-learning (Watkins, 1989) is known to suffer from overestimation issues, since it takes a maximum operator over a set of estimated action-values. Comparing with underestimated values, overestimation errors are more likely to be propagated through greedy action selections, which leads to an overestimation bias in value prediction (Thrun and Schwartz, 1993). This overoptimistic behavior of decision making has also been investigated in the literature of management science (Smith and Winkler, 2006) and economics (Thaler, 1988).
In deep Q-learning algorithms, one major source of value estimation errors comes from the optmization procedure. Although a deep neural network may have a sufficient expressiveness power to represent an accurate value function, the back-end optimization is hard to solve. As a result of computational considerations, stochastic gradient descent is almost the default choice for training deep Q-networks. As pointed out by Riedmiller (2005) and Van Hasselt et al. (2018), a mini-batch gradient update may have unpredictable effects on state-action pairs outside the training batch. The high variance of gradient estimation by such stochastic methods would lead to an unavoidable approximation error in value prediction, which cannot be eliminated by simply increasing sample size and
†Work done while Zhizhou was an undergraduate at Tsinghua University.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
network capacity. Through the maximum operator in the Q-learning paradigm, such approximation error would propagate and accumulate to form an overestimation bias. In practice, even if most benchmark environments are nearly deterministic (Brockman et al., 2016), a dramatic overestimation can be observed (Van Hasselt et al., 2016).
Double Q-learning (Van Hasselt, 2010) is a classical method to reduce the risk of overestimation, which is a specific variant of the double estimator (Stone, 1974) in the Q-learning paradigm. Instead of taking the greedy maximum values, it uses a second value function to construct an independent action-value evaluation as a cross validation. With proper assumptions, double Q-learning was proved to slightly underestimate rather than overestimate the maximum expected values (Van Hasselt, 2010). This technique has become a default implementation for stabilizing deep Q-learning algorithms (Hessel et al., 2018). In continuous control domains, a famous variant named clipped double Qlearning (Fujimoto et al., 2018) also shows great success in reducing the accumulation of errors in actor-critic methods (Haarnoja et al., 2018; Kalashnikov et al., 2018).
To understand algorithmic properties of double Q-learning and its variants, most prior work focus on the characterization of one-step estimation bias, i.e., the expected deviation from target values in a single step of Bellman operation (Lan et al., 2020; Chen et al., 2021). In this paper, we present a different perspective on how these one-step errors accumulate in stationary solutions. We first review a widely-used analytical model introduced by Thrun and Schwartz (1993) and reveal a fact that, due to the perturbation of approximation error, both double Q-learning and clipped double Q-learning have multiple approximate fixed points in this model. This result raises a concern that double Q-learning may easily get stuck in some local stationary regions and become inefficient in searching for the optimal policy. Motivated by this finding, we propose a novel value estimator, named doubly bounded estimator, that utilizes an abstracted dynamic programming as a lower bound estimation to rule out the potential non-optimal fixed points. The proposed method is easy to be combined with other existing techniques such as clipped double Q-learning. We extensively evaluate our approach on a variety of Atari benchmark tasks, and demonstrate significant improvement over baseline algorithms in terms of sample efficiency and convergence performance.

heading: 2 Background
text: Markov Decision Process (MDP; Bellman, 1957) is a classical framework to formalize an agentenvironment interaction system which can be defined as a tupleM = 〈S,A, P,R, γ〉. We use S and A to denote the state and action space, respectively. P (s′|s, a) and R(s, a) denote the transition and reward functions, which are initially unknown to the agent. γ is the discount factor. The goal of reinforcement learning is to construct a policy π : S → A maximizing cumulative rewards
V π(s) = E [ ∞∑ t=0 γtR(st, π(st)) ∣∣∣∣ s0 = s, st+1 ∼ P (·|st, π(st)) ] .
Another quantity of interest can be defined through the Bellman equation Qπ(s, a) = R(s, a) + γEs′∼P (·|s,a) [V π(s′)]. The optimal value function Q∗ corresponds to the unique solution of the Bellman optimality equation, Q∗(s, a) = R(s, a) + γ Es′∼P (·|s,a) [maxa′∈AQ∗(s′, a′)]. Q-learning algorithms are based on the Bellman optimality operator T stated as follows:
(T Q)(s, a) = R(s, a) + γ E s′∼P (·|s,a) [ max a′∈A Q(s′, a′) ] . (1)
By iterating this operator, value iteration is proved to converge to the optimal value function Q∗. To extend Q-learning methods to real-world applications, function approximation is indispensable to deal with a high-dimensional state space. Deep Q-learning (Mnih et al., 2015) considers a sample-based objective function and deploys an iterative optimization framework
θt+1 = arg min θ∈Θ E (s,a,r,s′)∼D
[( r + γ max
a′∈A Qθt(s
′, a′)−Qθ(s, a) )2] , (2)
in which Θ denotes the parameter space of the value network, and θ0 ∈ Θ is initialized by some predetermined method. (s, a, r, s′) is sampled from a data distribution D which is changing during exploration. With infinite samples and a sufficiently rich function class, the update rule stated in
Eq. (2) is asymptotically equivalent to applying the Bellman optimality operator T , but the underlying optimization is usually inefficient in practice. In deep Q-learning, Eq. (2) is optimized by mini-batch gradient descent and thus its value estimation suffers from unavoidable approximation errors.

heading: 3 On the Effects of Underestimation Bias in Double Q-Learning
text: In this section, we will first revisit a common analytical model used by previous work for studying estimation bias (Thrun and Schwartz, 1993; Lan et al., 2020), in which double Q-learning is known to have underestimation bias. Based on this analytical model, we show that its underestimation bias could make double Q-learning have multiple fixed-point solutions under an approximate Bellman optimality operator. This result suggests that double Q-learning may have extra non-optimal stationary solutions under the effects of the approximation error.

heading: 3.1 Modeling Approximation Error in Q-Learning
text: In Q-learning with function approximation, the ground truth Bellman optimality operator T is approximated by a regression problem through Bellman error minimization (see Eq. (1) and Eq. (2)), which may suffer from unavoidable approximation errors. Following Thrun and Schwartz (1993) and Lan et al. (2020), we formalize underlying approximation errors as a set of random noises e(t)(s, a) on the regression outcomes:
Q(t+1)(s, a) = (T Q(t))(s, a) + e(t)(s, a). (3)
In this model, double Q-learning (Van Hasselt, 2010) can be modeled by two estimator instances {Q(t)i }i∈{1,2} with separated noise terms {e (t) i }i∈{1,2}. For simplification, we introduce a policy function π(t)(s) = arg maxaQ (t) 1 (s, a) to override the state value function as follows:
V (t)(s) = Q (t) 2 ( s, π(t)(s) = arg maxa∈AQ (t) 1 (s, a) ) ,
∀i ∈ {1, 2}, Q(t+1)i (s, a) = R(s, a) + γEs′ [ V (t)(s′) ] ︸ ︷︷ ︸
target value
+ e (t) i (s, a)︸ ︷︷ ︸
approximation error
. (4)
A minor difference of Eq. (4) from the definition of double Q-learning given by Van Hasselt (2010) is the usage of a unified target value V (t)(s′) for both two estimators. This simplification does not affect the derived implications, and is also implemented by advanced variants of double Q-learning (Fujimoto et al., 2018; Lan et al., 2020).
To establish a unified framework for analysis, we use a stochastic operator T̃ to denote the Q-iteration procedure Q(t+1) ← T̃ Q(t), e.g., the updating rules stated as Eq. (3) and Eq. (4). We call such an operator T̃ as a stochastic Bellman operator, since it approximates the ground truth Bellman optimality operator T and carries some noises due to approximation errors. Note that, as shown in Eq. (4), the target value can be constructed only using the state-value function V (t). We can define the stationary point of state-values V (t) as the fixed point of a stochastic Bellman operator T̃ . Definition 1 (Approximate Fixed Points). Let T̃ denote a stochastic Bellman operator, such as what are stated in Eq. (3) and Eq. (4). A state-value function V is regarded as an approximate fixed point under a stochastic Bellman operator T̃ if it satisfies E[T̃ V ] = V , where T̃ V denotes the output state-value function while applying the Bellman operator T̃ on V .
Remark. In prior work (Thrun and Schwartz, 1993), value estimation bias is defined by expected one-step deviation with respect to the ground truth Bellman operator, i.e., E[(T̃ V (t))(s)]−(T V (t))(s). The approximate fixed points stated in Definition 1 characterizes the accumulation of estimation biases in stationary solutions.
In Appendix A.2, we will prove the existence of such fixed points as the following statement. Proposition 1. Assume the probability density functions of the noise terms {e(s, a)} are continuous. The stochastic Bellman operators defined by Eq. (3) and Eq. (4) must have approximate fixed points in arbitrary MDPs.

heading: 3.2 Existence of Multiple Approximate Fixed Points in Double Q-Learning Algorithms
text: Given the definition of the approximate fixed point, a natural question is whether such kind of fixed points are unique or not. Recall that the optimal value function Q∗ is the unique solution of the Bellman optimality equation, which is the foundation of Q-learning algorithms. However, in this section, we will show that, under the effects of the approximation error, the approximate fixed points of double Q-learning may not be unique.
An Illustrative Example. Figure 1a presents a simple MDP in which double Q-learning stated as Eq. (4) has multiple approximate fixed points. For simplicity, this MDP is set to be fully deterministic and contains only two states. All actions on state s1 lead to a self-loop and produce a unit reward signal. On state s0, the result of executing action a0 is a self-loop with a slightly larger reward signal than choosing action a1 which leads to state s1. The only challenge for decision making in this MDP is to distinguish the outcomes of executing action a0 and a1 on state s0. To make the example more accessible, we assume the approximation errors {e(t)(s, a)}t,s,a are a set of independent random noises sampled from a uniform distribution Uniform(− , ). This simplification is also adopted by Thrun and Schwartz (1993) and Lan et al. (2020) in case studies. Here, we select the magnitude of noise as = 1.0 and the discount factor as γ = 0.99 to balance the scale of involved amounts.
Considering to solve the equation E[T̃ V ] = V according to the definition of the approximate fixed point (see Definition 1), the numerical solutions of such fixed points are presented in Table 1b. There are three different fixed point solutions. The first thing to notice is that the optimal fixed point V ∗ is retained in this MDP (see the last row of Table 1b), since the noise magnitude = 1.0 is much smaller than the optimality gap Q∗(s0, a0)−Q∗(s0, a1) = 10. The other two fixed points are non-optimal and very close to Q(s0, a0) ≈ Q(s0, a1) = 100. Intuitively, under the perturbation of approximation error, the agent cannot identify the correct maximum-value action for policy improvement in these situations, which is the cause of such non-optimal fixed points. To formalize the implications, we would present a sufficient condition for the existence of multiple extra fixed points.
Mathematical Condition. Note that the definition of a stochastic Bellman operator can be decoupled to two parts: (1) Computing target values T Q(t) according to the given MDP; (2) Perform an imprecise regression and some specific computations to obtain Q(t+1). The first part is defined by the MDP, and the second part is the algorithmic procedure. From this perspective, we can define the input of a learning algorithm as a set of ground truth target values {(T Q(t))(s, a)}s,a. Based on this notation, a sufficient condition for the existence of multiple fixed points is stated as follows.
Proposition 2. Let fs ({(T Q)(s, a)}a∈A) = E[(T̃ V )(s)] denote the expected output value of a learning algorithm on state s. Assume fs(·) is differentiable. If the algorithmic procedure fs(·) satisfies Eq. (5), there exists an MDP such that it has multiple approximate fixed points.
∃s, ∃i, ∃X ∈ R|A|, ∂ ∂xi fs(X) > 1, (5)
where X = {xi}|A|i=1 denotes the input of the function fs.
The proof of Proposition 2 is deferred to Appendix A.4. This proposition suggests that, in order to determine whether a Q-learning algorithm may have multiple fixed points, we need to check whether its expected output values could change dramatically with a slight alter of inputs. Considering the constructed MDP as an example, Figure 1c visualizes the relation between the input state-value V (t)(s0) and the expected output state-value E[V (t+1)(s0)] while assuming V (t)(s1) = 100 has converged to its stationary point. The minima point of the output value is located at the situation where V (t)(s0) is slightly smaller than V (t)(s1), since the expected policy derived by T̃ V (t) will have a remarkable probability to choose sub-optimal actions. This local minima suffers from the most dramatic underestimation among the whole curve, and the underestimation will eventually vanish as the value of V (t)(s0) increases. During this process, a large magnitude of the first-order derivative could be found to meet the condition stated in Eq. (5).
Remark. In Appendix A.5, we show that clipped double Q-learning, a popular variant of double Q-learning, has multiple fixed points in an MDP slightly modified from Figure 1a. Besides, the condition presented in Proposition 2 does not hold in standard Q-learning that uses a single maximum operator (see Proposition 6 in Appendix). It remains an open question whether standard Q-learning with overestimation bias has multiple fixed points.

heading: 3.3 Diagnosing Non-Optimal Fixed Points
text: In this section, we first characterize the properties of the extra non-optimal fixed points of double Q-learning in the analytical model. And then, we discuss its connections to the literature of stochastic optimization, which motivates our proposed algorithm in section 4.
Underestimated Solutions. The first notable thing is that, the non-optimal fixed points of double Q-learning would not overestimate the true maximum values. More specifically, every fixed-point solution could be characterized as the ground truth value of some stochastic policy as the follows: Proposition 3 (Fixed-Point Characterization). Assume the noise terms e1 and e2 are independently generated in the double estimator stated in Eq. (4). Every approximate fixed point V is equal to the ground truth value function V π̃ with respect to a stochastic policy π̃.
The proof of Proposition 3 is deferred to Appendix A.3. In addition, the corresponding stochastic policy π̃ can be interpreted as
π̃(a|s) = P [ a = arg max
a′∈A
( R(s, a′) + γEs′ [V (s′)]︸ ︷︷ ︸
(TQ)(s,a′)
+e(s, a′) )] ,
which is the expected policy generated by the corresponding fixed point along with the random noise e(s, a′). This stochastic policy, named as induced policy, can provide a snapshot to infer how the agent behaves and evolves around these approximate fixed points. To deliver intuitions, we provide an analogical explanation in the context of optimization as the following arguments.
Analogy with Saddle Points. Taking the third column of Table 1b as an example, due to the existence of the approximation error, the induced policy π̃ suffers from a remarkable uncertainty in determining the best action on state s0. Around such non-optimal fixed points, the greedy action selection may be disrupted by approximation error and deviate from the correct direction for policy improvement. These approximate fixed points are not necessary to be strongly stationary solutions but may seriously hurt the learning efficiency. If we imagine each iteration of target updating as a step of “gradient update” for Bellman error minimization, the non-optimal fixed points would refer to the concept of saddle points in the context of optimization. As stochastic gradient may be trapped in saddle points, Bellman operation with approximation error may get stuck around non-optimal approximate fixed points. Please refer to section 5.1 for a visualization of a concrete example.
Escaping from Saddle Points. In the literature of non-convex optimization, the most famous approach to escaping saddle points is perturbed gradient descent (Ge et al., 2015; Jin et al., 2017). Recall that, although gradient directions are ambiguous around saddle points, they are not strongly convergent solutions. Some specific perturbation mechanisms with certain properties could help to make the optimizer to escape non-optimal saddle points. Although these methods cannot be directly applied to double Q-learning since the Bellman operation is not an exact gradient descent, it motivates us to construct a specific perturbation as guidance. In section 4, we would introduce a perturbed target updating mechanism that uses an external value estimation to rule out non-optimal fixed points.

heading: 4 Doubly Bounded Q-Learning through Abstracted Dynamic Programming
text: As discussed in the last section, the underestimation bias of double Q-learning may lead to multiple non-optimal fixed points in the analytical model. A major source of such underestimation is the inherent approximation error caused by the imprecise optimization. Motivated by the literature of escaping saddle points, we introduce a novel method, named Doubly Bounded Q-learning, which integrates two different value estimators to reduce the negative effects of underestimation.

heading: 4.1 Algorithmic Framework
text: As discussed in section 3.3, the geometry property of non-optimal approximate fixed points of double Q-learning is similar to that of saddle points in the context of non-convex optimization. The theory of escaping saddle points suggests that, a well-shaped perturbation mechanism could help to remove non-optimal saddle points from the landscape of optimization (Ge et al., 2015; Jin et al., 2017). To realize this brief idea in the specific context of iterative Bellman error minimization, we propose to integrate a second value estimator using different learning paradigm as an external auxiliary signal to rule out non-optimal approximate fixed points of double Q-learning. To give an overview, we first revisit two value estimation paradigms as follows:
1. Bootstrapping Estimator: As the default implementation of most temporal-difference learning algorithms, the target value yBoots of a transition sample (st, at, rt, st+1) is computed through bootstrapping the latest value function back-up Vθtarget parameterized by θtarget on the successor state st+1 as follows:
yBootsθtarget (st, at) = rt + γVθtarget(st+1),
where the computations of Vθtarget differ in different algorithms (e.g., different variants of double Q-learning).
2. Dynamic Programming Estimator: Another approach to estimating state-action values is applying dynamic programming in an abstracted MDP (Li et al., 2006) constructed from the collected dataset. By utilizing a state aggregation function φ(s), we could discretize a complex environment to a manageable tabular MDP. The reward and transition functions of the abstracted MDP are estimated through the collected samples in the dataset. An alternative target value yDP is computed as:
yDP(st, at) = rt + γV ∗ DP(φ(st+1)), (6)
where V ∗DP corresponds to the optimal value function of the abstracted MDP.
The advantages and bottlenecks of these two types of value estimators lie in different aspects of error controlling. The generalizability of function approximators is the major strength of the bootstrapping estimator, but on the other hand, the hardness of the back-end optimization would cause considerable approximation error and lead to the issues discussed in section 3. The tabular representation of the dynamic programming estimator would not suffer from systematic approximation error during optimization, but its performance relies on the accuracy of state aggregation and the sampling error in transition estimation.
Doubly Bounded Estimator. To establish a trade-off between the considerations in the above two value estimators, we propose to construct an integrated estimator, named doubly bounded estimator, which takes the maximum values over two different basis estimation methods:
yDBθtarget(st, at) = max { yBootsθtarget (st, at), y DP(st, at) } . (7)
The targets values yDBθtarget would be used in training the parameterized value functionQθ by minimizing
L(θ; θtarget) = E (st,at)∼D
( Qθ(st, at)− yDBθtarget(st, at) )2 ,
where D denotes the experience buffer. Note that, this estimator maintains two value functions using different data structures. Qθ is the major value function which is used to generate the behavior policy for both exploration and evaluation. VDP is an auxiliary value function computed by the abstracted dynamic programming, which is stored in a discrete table. The only functionality of VDP is computing the auxiliary target value yDP used in Eq. (7) during training.
Remark. The name “doubly bounded” refers to the following intuitive motivation: Assume both basis estimators, yBoots and yDP, are implemented by their conservative variants and do not tend to overestimate values. The doubly bounded target value yDB(st, at) would become a good estimation if either of basis estimator provides an accurate value prediction on the given (st, at). The outcomes of abstracted dynamic programming could help the bootstrapping estimator to escape the non-optimal fixed points of double Q-learning. The function approximator used by the bootstrapping estimator could extend the generalizability of discretization-based state aggregation. The learning procedure could make progress if either of estimators can identify the correct direction for policy improvement.
Practical Implementation. To make sure the dynamic programming estimator does not overestimate the true values, we implement a tabular version of batch-constrained Q-learning (BCQ; Fujimoto et al., 2019) to obtain a conservative estimation. The abstracted MDP is constructed by a simple state aggregation based on low-resolution discretization, i.e., we only aggregate states that cannot be distinguished by visual information. We follow the suggestions given by Fujimoto et al. (2019) and Liu et al. (2020) to prune the unseen state-action pairs in the abstracted MDP. The reward and transition functions of remaining state-action pairs are estimated through the average of collected samples. A detailed description is deferred to Appendix B.5.

heading: 4.2 Underlying Bias-Variance Trade-Off
text: In general, there is no existing approach can completely eliminate the estimation bias in Q-learning algorithm. Our proposed method also focuses on the underlying bias-variance trade-off.
Provable Benefits on Variance Reduction. The algorithmic structure of the proposed doubly bounded estimator could be formalized as a stochastic Bellman operator T̃ DB:
(T̃ DBV )(s) = max { (T̃ BootsV )(s), V DP(s) } , (8)
where T̃ Boots is the stochastic Bellman operator corresponding to the back-end bootstrapping estimator (e.g., Eq. (4)). V DP is an arbitrary deterministic value estimator such as using abstracted dynamic programming. The benefits on variance reduction can be characterized as the following proposition.
Proposition 4. Given an arbitrary stochastic operator T̃ Boots and a deterministic estimator V DP, ∀V, ∀s ∈ S, Var[(T̃ DBV )(s)] ≤ Var[(T̃ BootsV )(s)],
where (T̃ DBV )(s) is defined as Eq. (8).
The proof of Proposition 4 is deferred to Appendix A.6. The intuition behind this statement is that, with a deterministic lower bound cut-off, the variance of the outcome target values would be reduced, which may contribute to improve the stability of training.
Trade-Off between Different Biases. In general, the proposed doubly bounded estimator does not have a rigorous guarantee for bias reduction, since the behavior of abstracted dynamic programming depends on the properties of the tested environments and the accuracy of state aggregation. In the most unfavorable case, if the dynamic programming component carries a large magnitude of error, the lower bounded objective would propagate high-value errors to increase the risk of overestimation. To address these concerns, we propose to implement a conservative approximate dynamic programming as discussed in the previous section. The asymptotic behavior of batch-constrained Q-learning does not tend to overestimate extrapolated values (Liu et al., 2020). The major risk of the dynamic programming module is induced by the state aggregation, which refers to a classical problem (Li et al., 2006). The experimental analysis in section 5.2 demonstrates that, the error carried by abstracted dynamic programming is acceptable, and it definitely works well in most benchmark tasks.

heading: 5 Experiments
text: In this section, we conduct experiments to demonstrate the effectiveness of our proposed method1. We first perform our method on the two-state MDP example discussed in previous sections to visualize its algorithmic effects. And then, we set up a performance comparison on Atari benchmark with several baseline algorithms. A detailed description of experiment settings is deferred to Appendix B.
1Our code is available at https://github.com/Stilwell-Git/Doubly-Bounded-Q-Learning.

heading: 5.1 Tabular Experiments on a Two-State MDP
text: To investigate whether the empirical behavior of our proposed method matches it design purpose, we compare the behaviors of double Q-learning and our method on the two-state MDP example presented in Figure 1a. In this MDP, the non-optimal fixed points would get stuck in V (s0) ≈ 100 and the optimal solution has V ∗(s0) = 110. In this tabular experiment, we implement double Q-learning and our algorithm with table-based Q-value functions. The Q-values are updated by iteratively applying Bellman operators as what are presented in Eq. (4) and Eq. (8). To approximate practical scenarios, we simulate the approximation error by entity-wise Gaussian noises N (0, 0.5). Since the stochastic process induced by such noises suffers from high variance, we perform soft update Q(t+1) = (1− α)Q(t) + α(T̃ Q(t)) to make the visualization clear, in which α refers to learning rate in practice. We consider α = 10−2 for all experiments presented in this section. In this setting, we denote one epoch as 1α(1−γ) = 10
4 iterations. A detailed description for the tabular implementation is deferred to Appendix B.2.
We investigate the performance of our method with an imprecise dynamic programming module, in which we only apply lower bound for state s0 with values V DP(s0) ∈ {99.0, 99.5, 100.0, 100.5}. The experiment results presented in Figure 2 and Figure 3 support our claims in previous sections:
1. The properties of non-optimal fixed points are similar to that of saddle points. These extra fixed points are relatively stationary region but not truly static. A series of lucky noises can help the agent to escape from non-optimal stationary regions, but this procedure may take lots of iterations. As shown in Figure 2, double Q-learning may get stuck in non-optimal solutions and it can escape these non-optimal regions by a really slow rate. After 20 epochs (i.e., 2 · 105 iterations), there are nearly a third of runs cannot find the optimal solution.
2. The design of our doubly bounded estimator is similar to a perturbation on value learning. As shown in Figure 3, when the estimation given by dynamic programming is slightly higher than the non-optimal fixed points, such as VDP(s0) = 100.5, it is sufficient to help the agent escape from non-optimal stationary solutions. A tricky observation is that VDP(s0) = 100 also seems to work. It is because cutting-off a zero-mean noise would lead to a slight overestimation, which makes the actual estimated value of V DP(s0) to be a larger value.

heading: 5.2 Performance Comparison on Atari Benchmark
text: To demonstrate the superiority of our proposed method, Doubly Bounded Q-Learning through Abstracted Dynamic Programming (DB-ADP), we compare with six variants of deep Q-networks as baselines, including DQN (Mnih et al., 2015), double DQN (DDQN; Van Hasselt et al., 2016),
dueling DDQN (Wang et al., 2016), averaged DQN (Anschel et al., 2017), maxmin DQN (Lan et al., 2020), and clipped double DQN adapted from Fujimoto et al. (2018). Our proposed doubly bounded target estimation yDB is built upon two types of bootstrapping estimators that have clear incentive of underestimation, i.e., double Q-learning and clipped double Q-learning. We denote these two variants as DB-ADP-C and DB-ADP according to our proposed method with or without using clipped double Q-learning.
As shown in Figure 4, the proposed doubly bounded estimator has great promise in bootstrapping the performance of double Q-learning algorithms. The improvement can be observed both in terms of sample efficiency and final performance. Another notable observation is that, although clipped double Q-learning can hardly improve the performance upon Double DQN, it can significantly improve the performance through our proposed approach in most environments (i.e., DB-ADP-C vs. DB-ADP in Figure 4). This improvement should be credit to the conservative property of clipped double Q-learning (Fujimoto et al., 2019) that may reduce the propagation of the errors carried by abstracted dynamic programming.

heading: 5.3 Variance Reduction on Target Values
text: To support the theoretical claims in Proposition 4, we conduct an experiment to demonstrate the ability of doubly bounded estimator on variance reduction. We evaluate the standard deviation of the target values with respect to training networks using different sequences of training batches. Table 5a presents the evaluation results on our proposed methods and baseline algorithms. The †-version corresponds to an ablation study, where we train the network using our proposed approach but evaluate the target values computed by bootstrapping estimators, i.e., using the target value formula of double DQN or clipped double DQN. As shown in Table 5a, the standard deviation of target values is significantly reduced by our approaches, which matches our theoretical analysis in Proposition 4. It demonstrates a strength of our approach in improving training stability. A detailed description of the evaluation metric is deferred to Appendix B.

heading: 5.4 An Ablation Study on the Dynamic Programming Module
text: To support the claim that the dynamic programming estimator is an auxiliary module to improving the strength of double Q-learning, we conduct an ablation study to investigate the individual performance of dynamic programming. Formally, we exclude Bellman error minimization from the training
procedure and directly optimize the following objective to distill the results of dynamic programming into a generalizable parametric agent:
LADP(θ) = E (st,at)∼D
[( Qθ(st, at)− yDP(st, at) )2] ,
where yDP(st, at) denotes the target value directly by dynamic programming. As shown in Figure 5b, without integrating with the bootstrapping estimator, the abstracted dynamic programming itself cannot outperform deep Q-learning algorithms. It remarks that, in our proposed framework, two basis estimators are supplementary to each other.

heading: 6 Related Work
text: Correcting the estimation bias of Q-learning is a long-lasting problem which induces a series of approaches (Lee et al., 2013; D’Eramo et al., 2016; Chen, 2020; Zhang and Huang, 2020), especially following the methodology of double Q-learning (Zhang et al., 2017; Zhu and Rigotti, 2021). The most representative algorithm, clipped double Q-learning (Fujimoto et al., 2018), has become the default implementation of most advanced actor-critic algorithms (Haarnoja et al., 2018). Based on clipped double Q-learning, several methods have been investigated to reduce the its underestimation and achieve promising performance (Ciosek et al., 2019; Li and Hou, 2019). Other recent advances usually focus on using ensemble methods to further reduce the error magnitude (Lan et al., 2020; Kuznetsov et al., 2020; Chen et al., 2021). Statistical analysis of double Q-learning is also an active area (Weng et al., 2020; Xiong et al., 2020) that deserves future studies.
Besides the variants of double Q-learning, using the softmax operator in Bellman operations is another effective approach to reduce the effects of approximation error (Fox et al., 2016; Asadi and Littman, 2017; Song et al., 2019; Kim et al., 2019; Pan et al., 2019). The characteristic of our approach is the usage of an approximate dynamic programming. Our analysis would provide a theoretical support for memory-based approaches, such as episodic control (Blundell et al., 2016; Pritzel et al., 2017; Lin et al., 2018; Zhu et al., 2020; Hu et al., 2021), which are usually designed for near-deterministic environments. Instead of using an explicit planner, Fujita et al. (2020) adopts the trajectory return as a lower bound for value estimation. This simple technique also shows promise in improving the efficiency of continuous control with clipped double Q-learning.

heading: 7 Conclusion
text: In this paper, we reveal an interesting fact that, under the effects of approximation error, double Q-learning may have multiple non-optimal fixed points. The main cause of such non-optimal fixed points is the underestimation bias of double Q-learning. Regarding this issue, we provide some analysis to characterize what kind of Bellman operators may suffer from the same problem, and how the agent may behave around these fixed points. To address the potential risk of converging to non-optimal solutions, we propose doubly bounded Q-learning to reduce the underestimation in double Q-learning. The main idea of this approach is to leverage an abstracted dynamic programming as a second value estimator to rule out non-optimal fixed points. The experiments show that the proposed method has shown great promise in improving both sample efficiency and convergence performance, which achieves a significant improvement over baselines algorithms.
Acknowledgments and Disclosure of Funding
The authors would like to thank Kefan Dong for insightful discussions. This work is supported in part by Science and Technology Innovation 2030 – “New Generation Artificial Intelligence” Major Project (No. 2018AAA0100904), a grant from the Institute of Guo Qiang, Tsinghua University, and a grant from Turing AI Institute of Nanjing.

Review summaries:
The estimation bias is a quite general problem in Reinforcement Learning originally examined in Q-learning and due to the fact that the Bellman operator has a max operation which causes a systematic overestimation of state-action values. Double Q-learning had first been proposed as a way of mitigating this maximization bias, at the expense however of an opposite minimization bias. This papers tackles the estimation bias in particular of Double Q-learning by proposing a new way of analyzing the problem from the perspective of the fixed points of a stochastic Bellman operator (where the stochastic components models the approximation error in minimizing the Bellman error). The main theoretical message of the paper is that the estimation bias is the result of suboptimal fixed points of the stochastic Bellman operator. Loosely based on this observation the authors then propose a "Doubly bounded estimator" which they show has a variance reduction effect. Although they do not provide any theoretical guarantees in regard to bias  reduction,t hey then test their algorithm on a few tasks of the Atari 2600 benchmark, empirically demonstrating that their algorithm results in faster rewards maximization compared to DQN, Double DQN.

This paper proposes a new problem of double Q-learning, that is, the multiple fixed points caused by underestimation bias. This problem may lead to the non-optimal model after value iterations. Meanwhile, the authors provide many mathematical approvals. To solve it, the authors integrate another value estimator to escape the saddle points and approve its effectiveness with experiments. 

This paper tries to address the possible underestimation issue of double Q-learning. Specifically, it shows underestimation bias may lead to multiple non-optimal fixed points, so it adds another target value from abstracted MDP to construct an integrated estimator, named doubly bounded estimator. It conducts serval experiments based on the standard Atari benchmark tasks, and the proposed doubly bounded estimator has shown promising results in bootstrapping the performance of double Q-learning algorithms.

This paper studies the effect of the underestimation induced by Double Q-Learning, a well-known method to solve the overestimation problem of Q-Learning. The paper shows that Double Q-Learning might incur in suboptimal fixed points under an approximated setting, e.g. Double DQN, and proposes a method, i.e, Doubly Bounded Q-Learning, to curb this problem. The method consists of computing the target of the Q-Learning update as a maximum operator between the application of the Bellman operator on an approximation of the value function, and the application of the Bellman operator on the optimal value function computed on a discrete abstraction of the original MDP. The method is evaluated on several Atari games.