On the Estimation Bias in Double Q-Learning
Authors: Zhizhou Ren
Guangxiang Zhu
Hao Hu
Beining Han
Jianglun Chen
Chongjie Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Double Q-Learning
Estimation Bias

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.

On the Estimation Bias in Double Q-Learning
Zhizhou Ren't Guangxiang Zhu?, Hao Hu², Beining Han", Jianglun Chen', Chongjie Zhang?
'Department of Computer Science, University of Illinois at Trrbna-Chhamprr "Institute for Interdisciplinary Information Sciences. Tsinghua University com
zhizhour@illinoie edu, guangxiangzzu@outioom {hu-h19, hbn18, chen-jl187@maill tsinghua. edu. cn chongj ientjinghtsnna..... www.eiinghuuuu.....o.oo edu. cn
Abstract
Double Q-learning is classical method for reducing overestimation bias, which is caused by taking maximum estimated values in the Bellman operation. 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. this paper, we show that such underestimation bias may lead to multiple non-optimal fixed points under concerns of converging to non- non-optimal stationary solutions, we propose simple but effective approach 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.
approximate Bellman operator. To address the
Introduction
Value-based reinforcement learning with neural networks function approximators has become widely-used paradigm and shown great promise in solving complicated Docision-making problems in various real-world applications, including robotics control (Lillicrap 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 baased value function approximation has attracted growth of attention in recent years (Van Hasselt et al.) 2018 Fu al., 2019 Achiam al.) 2019 Dong et al. 20200. One of the phenomena of interest is that Q-learning (Watkins] 1989 is known to suffer from overestimation issues, since it takes 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 opt- mization procedure. Although a deep neural network may have 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). 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 approx- imation error value prediction, which cannot eliminated by simply increasing sample size and
Work done while Zhizhou was undergraduate at Tsinghua University.
35th Conference on Neural Information Processing Systems (NcurIPS 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), 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 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 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 default implementation for stabilizing deep Q-learning algorithms (Hessel et al. (0188). In continuous control domains, a famous variant named clipped double Q- learning (Fujimoto et al. 2018) also shows great success 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.c., the expected deviation from target values in single step of Bellman operation (Lan et al., 2020 Chen et al., 202T). 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.
2 Background
Markov Decision Process (MDP; [ellman 1957) is a classical framework to formalize an agent- environment interaction system which can be defined as a tuple M AS 7). 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. 7 is the discount factor. The goal of reinforcement learning is to construct a policy : S + A maximizing cumulative rewards
(*()) = E Σ yt R(s,, (sx)) So = 8,8111 ~ P(-|s,,
Another quantity of interest can be defined through the Bellman equation Q" a) R(s, + -lBx//-((ls.aa) (s']. The optimal value function Q' corresponds to the unique solution of the Bellman optimality equation, (* a) R(s, a) + 7 Es>PP())s,a) [maaxa/ Q' (s',,a)), Q-learning algorithms are based on the Bellman optimality operator T stated as follows:
(TQ) = R(s, a) +
E P()
max Q(s' ((o' a'EAA
(I)
By iterating this operator, value iteration is proved to converge to the optimal value function Q", To extend Q-learning methods real-world applications, function approximation is indispensable to deal with high-ding nigh-dimensional state space. Deep Q-learning (Mnih et al. 2015) considers a sample-based objective function and deploys an iterative optimization framework
[
y Qo, (++r d'E
27
0 1 = arg min
E (SA),"")~
(2)
in which ④ denotes the parameter space of the value network, and 0, E θ 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. is
asymptotically equivalent to applying the Bellman optimality operator T. but the underlying optimization is usually inefficient in practice, In deep Q-learing, Eq. 2 is optimized by mini-bate gradient descent and thus its value estimation suffers from unavoidable approximation errors.
3 On the Effects of Underestimation Bias in Double Q-Learning
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-poin 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.
3.1 Modeling Approximation Error in Q-Learning
In Q-learning with function approximation, the ground truth Bellman optimality operator T is
approximated by regression problem through Bellman error minimization (see Eq. (T) and Eq. (
which may suffer from unavoidable approximation errors. Following Thrun and Schwartz (9933 and
Lan al. (2020), formalize underlying approximation errors set of random noises e(f) (s a) on the regression outcomes:
( (TQ a) + (s,
(3)
In this model, double Q-learning Van Hasselt 2010) can be modeled by two estimator instances (0 he with separated noise terms {e] )EE[1,2> For simplification, we introduce a policy function N (s) = arg max, Q(9h) (s,a) to override the state value function as follows:
(s) Q (s, x (s) argmax,c A (s.a))
Vi E (1,2), o (++ (s,a) R(s,a) + E. [V)
(8,0) a)
approximation enoor
Largel vallue
minor difference of Eq. from the definition double Q-learning given by Van Hasselt (010)) is the usage of a unified target value (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 stochastic operator T to denote the Q-iteration procedure (+++1) + TQ(", e.g., the updating rules stated as Eq. (3) and Eq. (4) We call such an operator T as stochastic Bellman operator, since it approximates the ground truth Bellman optimality operator 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 (()), We define the stationary point of state-values (t) as the fixed point of a stochastic Bellman operator T.
Definition (Approximate Fixed Points). Let T denote a stochastic Bellman operator, such as what stated in Eq. B and Eq. (4). A state-value function V is regarded as approximate fixed point under a stochastic Bellman operator T if satisfies [[ V, where TV 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., - (TVV())) The approximate fixed points stated in Definition 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. and Eg. (4) must have approximate fixed points in arbitrary MDPs.
3

---

Ro,0=111
1=
V(6o)
V(s1)
т T(au (so)
120
100.162
100.0
62.2%
R 1l
130.
80
101.159
100.0
92.9%
1300
<= 1.0 7 0.99
110.0
100.0
100.0%
550
1002
1905
Vil
(a) A simple construction
(b) Numerical solutions of fixed points (c) Visualizing non con-monotonicityy
Figure I: (a) A simple infinite-horizon MDP where double Q-learning stated as (4) has multiple approximate fixed points. Ra,j is shorthand of R(s;, az). (b) The numerical solutions of the fixed points produced by double Q-learning in the MDP presented above. ग denotes the expected policy generated by the corresponding fixed point under the perturbation of noise e(s, a). A formal description of fř refers to Definition 2 in Appendix [A.3 (c) The relation between the input state-value (so) and the expected output state-value E[V (++ (so)] generated by double Q-learning in the
constructed MDP, in which we assume (s) = 100.
3.2 Existence of Multiple Approximate Fixed Points in Double Q-Learning Algorithms
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 presents a simple MDP in which double Q-eaaming stated as Eq. 4 has multiple approximate fixed points. For simplicity, this MDP is set be fully deterministic and contains only two states. All actions on state 81 lead to a self-loop and produce a unit reward signal. On state Sp, the result of executing action do is self-loop with slightly larger reward signal than choosing action a1 which leads to state $1. The only challenge for decision making in this MDP is to distinguish the outcomes of executing action ag and a state Sg- To make the example more accessible, assume the approximation eπrоrs {e(*) (s, a))c,saa noises sampled from a uniform distribution Uniform( e). This simplification is also adopted by Thrun and Schwartz (1933) and Lan al. (220)) in case studies. Here, select the magnitude of noise as c = 1.0 and the discount factor as = 0.99 to balance the scale of involved amounts.
set of independent random
Considering solve the equation [E[ V according the definition of the approximate fixed point (see Definition I the numerical solutions of such fixed points are presented in Table Tb 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 Ib). since the noise magnitude e = 1.0 is much smaller than the optimality gap Q" (so, ag) (so, a1 10. The other two fixed points are non-optimal and very close to ((5o. 4g) R (( a1) = 100. Intuitively, under the perturbation of approximation error, the agent cannot identify the correct maximum-vaa
action for policy improvement 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 decou- pled to two parts: (1) Computing target values TQ( according to the given MDP; (2) Perform an imprecise regression and some specific computations to obtain Q(++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 {(TQ()) (s, a))..a. Based on this notation, sufficient condition for the existence of multiple fixed points stated as follows.
Let fo (E(TQ) (aAa))) ([)) denote the expected output value of learning algorithm on state s. Assume fa(-) is differentiable. If the algorithmic procedure f.(-) satisfies Eq. (5), there exists an MDP such that has multiple approximate fixed points.
Proposition
3s, 3i, 3X ER
(x) > 1,
(S)
where X = =xx1)/11 denotes the input of the function fo.

---

The proof of Proposition is deferred to Appendix A.44 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 [c] visualizes the relation between the input state-value (sg) and the expected output state-value E[V (so)] while assuming (s;)
100 has converged to its stationary point. The minima point of the output value is located at the situation where ((()))))) is slightly smaller than (x1), since the expected policy derived by TV( 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 ( increases. During this process, a large magnitude of the first-order derivative could be found to meet the condition stated in Eq. (
Remark. In Appendix A.5]] [ we show that clipped double Q-learning, a popular variant of double Q-learning, has multiple fixed points in MDP slightly modified from Figure [a] Besides, the condition presented in Proposition does not hold in standard Q-learning that uses a single maximum operator (see Proposition 6 i Appendix). It remains open question whether standard Q-learning with overestimation bias has multiple fixed points.
3.3 Diagnosing Non-Optimal Fixed Points
In this section, 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 that, the non-optimal fixed points of double Q-learning would not overestimate the true maximum values. More specifically, every fixed- -xint 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 eı and e2 are independently generated in the double estimator stated in Eq. A Every approximate fixed point V is equal to the ground truth value function V * with respect a stochastic policy i.
The proof of Proposition 3 is deferred to Appendix A.3 In addition, the corresponding stochastic policy स can be interpreted as
+700)++E..VV IV(') +e(s,a)) )]
(als) P arg max d'EA
(TQ)(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 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 Tb as an example, due to the existence of the approximation error, the induced policy स suffers from remarkable uncertainty in determining the best action on state so. Around such non-optimal fixed points, the greedy action selection may be disrupted by approximation eгror 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 step of " graddinnt 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-omtimal approximate fixed points. Please refer section 5.1 for visualization of 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 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 we would introduce a perturbed target updating mechanism that uses external value estimation to rule out non-optimal fixed points.
5

---

Doubly Bounded Q-Learning through Abstracted Dynamic Programming
As discussed in the last section, the underestimation bias of double Q-learning may lead 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.
4.1 Algorithmic Framework
As discussed in section 3.3 the geometry property of non-optimal approximate fixed points of double
Q-learning is similar 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. (017). 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 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 follows:
1. Bootstrapping Estimator: As the default implementation of most temporal-differenee learning algorithms, the target value y Bants of transition sample (st, Ge, Fe, $1+1) is com- puted through bootstrapping the latest value function back-up Vonage parameterized by Ourget the successor state 8++1 follows:
Boots (st; 0z) = rt + VVouga (8++1),
where the computations of Vange 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 an abstracted MDP (Li al. 2006) constructed from the collected dataset. By utilizing state aggregation function ((s), we could discretize complex environment to 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 yP is computed as:
( at) = ri + (V)(((()))))
where ViDe 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 diseussed 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 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:
DB Vonge (st, az) = max
youge (st, az), y p (P
(7)
The targets values Doug would be used in training the parameterized value function Qu by minimizing
(Ro(se, ar) - yo..e (st, oz) oz))²
L(0; Ounyes)
E (
where D denotes the experience buffer. Note that, this estimator maintains two value functions using different data structures. Qo is the major value function which is used to generate the behavior policy for both exploration and evaluation. Vpp is an auxiliary value function computed by the abstracted dynamic programming, which is stored in discrete table. The only functionality of Vip is computing the auxiliary target value y used in Eq. 7 during training.

---

Remark. The name "doubly bounded" refers to the following intuitive motivation: Assume both basis estimators, yooas and ybP, are implemented by their conservative variants and do not tend to overestimate values. The doubly bounded target value y0 (8t, (z) 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-basee state aggregation. The learning procedure could make progress either of estimators can identify the correct direction for policy improvement.
Practical Implementation. To make sure the dynamic programming estimator does not overesti- mate the true values, we implement a tabular version of batch-constrained Q-learning SCCQ:Fujimooi et al. 2019) to obtain a conservative estimation. The abstracted MDP is constructed by a simple state aggregation based on low-resolution discretization, i.c., we only aggregate states that cannot be distinguished by visual information. We follow the suggestions given by Fujimoto et al. (2019) Lid 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
4.2 Underlying Bias- Variance Trade-Off
In general, there is no existing approach can completely eliminate the estimation bias in Q-lcarning algorithm. Our proposed method also focuses on the underlying bias-variance trade-off.
Provable Benefits Variance Reduction. The algorithmic structure of the proposed doubly bounded estimator could be formalized as a stochastic Bellman operator TDB;
(TPB max { (T (s), (s)).
(8)
where 7 Bonts is the stochastic Bellman operator corresponding to the back-end bootstrapping estimator (e.g., Eq. (4). DDP is an arbitrary deterministic value estimator such using abstracted dynamic programming. The benefits on variance reduction can be characterized as the following proposition. Proposition 4. Given an arbitrary stochastic operator FBoou and a deterministic estimator DPP,
WV Vs E S, Varl(TD8V) < Boots Borl(TBo (+)),
where (TD) is defined as Eq.
The proof of Proposition is deferred to Appendix A.6 with a deterministic lower bound cut-off, the variance of the outcome target values would be reduced, which may contribute improve the stability of training.
The intuition behind this statement is that,
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 conservative approximate dynamic programming as discussed in the previous section. The asymptotic behavior of cotch-constrained Q-learning does not tend to overestimate extrapolated values (Liu et al. 2020). The major risk of the dynamic programming module induced by the state aggregation, which refers to 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.
Experiments
In this section, we conduct experiments to demonstrate the effectiveness of our proposed method We first perform our method on the two-state MDP example discussed previous sections to visualize its algorithmic effects. And then, we set up performance comparison on Atari benchmark with several baseline algorithms. A detailed description of experiment settings is deferred Appendix B
OOur code is available at attttps://githuu wtt.tluu..oo..////////eee www./tttt//slstst Gittllub -wwndedd---eeannateeee Q-Laanning
7

---

Deable Q-Leaarning (5 Rporce)
Dauble Q-Leaaaing (10 Epechh)
Double Q-I.arning (18 Eporhs)
Dauble Q-Learning (20 Epochs)
Probabitte Denity
5 C F
30 107 Diaributional (iaa
D1 101
180 118
103
181 33 182 18
10 130
112
190
102
DM
Disribution Vir))
Dierilration Vlaa
Datribution
Figure 2: Visualization of the probability density of ((5)) learned by double Q-learning. In this section, all plotted distributions are estimated by 10 runs with random seeds. We utilize seaborn. distplot package to plot the kernel density estimation curves and histogram bins.
(9)6 Epocis)
V-"0g0100
U-2- Epechs)
Probabilty Demity
C 5
5
03
100 100
105
139 Voa)
110
112
189
1EL 38
108
130
112
18
181 DistrButton
181
12
100 123 (V)
110
112
12
334
109
1I2
Distrbuutinn
Distributinn Vagg
Vorg)
Figure 3: Visualization of the probability density of V (so) learned by doubly bounded Q-learning with imprecise dynamic programming planner. V /DP (so) denotes the value estimation given by dynamic programming, which serves as a lower bound in our method.
5.1 Tabular Experiments on a Two-State MDP
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 Ta In this MDP, the non-optimal fixed points would get stuck in V(so) z 100 and the optimal solution has (*() = 110. this tabular experiment, we implement double Q-lcarning and our algorithm with table-based Q-value functions. The Q-values applying Bellman operators as what are presented in Eq. and Eq. (8) To approximate practical scenarios, simulate the approximation error by entity-wist tist Gaussian noises N 0.5). Since the stochastic process induced by such noises suffers from high variance, we perform soft update Q((+1) (1 a))(() + (TQ(()) to make the visualization clear, in which refers to learning rate practice. We consider a 10 for all experiments presented this section. In this setting, we denote one epoch as af = 10 iterations. A detailed description for the tabular implementation
updated by iteratively
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 with values VDDP (so) {99.0, 99.5, 100.0, 100.5). The experiment results presented in Figure and Figure support our claims in previous sections:
1. The properties of non-optimal fixed points 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 escape these non-optimal regions by really slow rate. After 20 epochs (i.e., 10 iterations), there are nearly a third of runs cannot find the optimal solution.
2. The design of our doubly bounded estimator is similar to perturbation on value learning. As shown in Figure 3 when the estimation given by dynamic programming slightly higher than the non-optimal fixed points, such as Vip((s)) = 100.5, it is sufficient to help the agent escape from non-optimal stationary solutions. A tricky observation is that VDD((s) 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 (DD(ss) ) to be larger value.
100
5.2 Performance Comparison on Atari Benchmark
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-nttworks as basclines, including DQN (Mnih et al. 2015). double DQN (DDQN; Van Hasselt et al., 2016).
8

---

DB--AP-CCoon DB-ADP (ours)
Clipped DDQN
Ducling DDQN
Maxiin DQN
DDQN
Averaged DQN
DQN
Aveegge Egiiseee Return
Alien
HaikHeist
BottleZone
Frosthite
1200
2010
1000
2000
12:0
2000
033
151
453
TM
103
031
13
255
353
25
331
1M1
351
X01
10T
032
252
253
199
Timetops
Timestaps MsPacman
Itanetepss Qbert
Timestega
Average Epiiodde Return
Jameesond
Rumner
3000
240
40110
140
10000
1200
2000
1800
1800
321
233
081
35E
Timetops
Timesops
Timesiips
Timesitep
Average Epinade Return
Star Ganner
TimePHot
WizardOOWor
Zaxaon
150m
2000
120
6000
635
133
Timmstpps
Timmtops
Timunteps
Figure 4: Learning curves on a suite of Atari benchmark tasks. DB-ADP and DB-ADP-C refer to our proposed approach built upon double Q-learning and clipped double Q-learning, respectively.
dueling DDQN (Wang al. 2016), averaged DQN (Anschel al.
2017). maxmin DQN (Lan et al.
2020), and clipped double DQN adapted from Fujimoto et al. (2018). Our proposed doubly bounded target estimation DB is built upon 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 DB-ADP-C and DB-ADP according to our proposed method with 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 terms of sample efficiency and final performance. Another notable observation is that, although clipped double Q-Jearning can hardly improve the performance upon Double DQN, 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 al. 2019) that may reduce the propagation of the errors carried by abstracted dynamic programming.
5.3 Variance Reduction on Target Values
To support the theoretical claims in Proposition 4 we conduct experiment to demonstrate the ability of doubly bounded estimator on variance reduction. We evaluate the standard deviation the target values with respect training networks using different sequences of training batches. Table presennss the evaluation results on our proposed methods and baseline algorithms. The f-version corresponds to ablation study, where we train the network using proposed approach but evaluate the target values computed by bootstrapping estimators, i.c., using the target value formula of double DQN clipped double DQN. As shown in Table the standard deviation of target values significantly reduced by our approaches, which matches our theoretical analysis in Proposition 4 It demonstrates strength of our approach in improving training stability. detailed description of the evaluation metric is deferred to Appendix
5.4 An Ablation Study on the Dynamic Programming Module
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

---

TASK NAME
DB-ADP-C
DB-ADP-C
CDDQN
D2-ASP-C
38-ADC
ALIEN
0.006
0.008
0.010
Avernge Ephonde Returnn
Alien
1174
BankHeist
BANKHEIST
0.009
0.010
0.010
QBERT
0.008
0.010
0.011
TASK NAME
DB-ADP
DB-ADP
DDQN
ALIEN
0,008
0.009
0.012
8
210
BANKHEIST
0.009
0.011
0.013
QBERT
0.009
0.011
0.012
255
Timesteps
231
071
Timesteps
530
(a) Variance reduction on target values
(b) Ablation study on dynamic programming
Figure 5: (a) Evaluating the standard deviation of target values w.r.t. different training batches. The presented amounts are normalized by the value scale of corresponding runs. "f" refers to ablation studies. (b) An ablation study on the individual performance the dynamic programming module.
procedure and directly optimize the following objective distill the results of dynamic programming into a generalizable parametric agent:
LAD (0) =
E
[(oo(s), ac) - -y (st. oz)) =z))²
(st,,,)~
where y (st, at) denotes the target value directly by dynamic programming. 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 supplementary to each other.
6 Related Work
Correcting the estimation bias of Q-learning is a long-lasting problem which induces series of approaches (Lee et al. 2013 D Eramo al. 2016 Chen 2020 Zhang and Huang 2020), especially
following the methodology of double Q-learning Zhang et al. 2017i/Zu Zhu and Rigotti 2021). The most representative algorithm, clipped double Q-learing (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 using ensemble methods further reduce the error magnitude (Lan al. 2020
Kuznetsov et al.. 2020 Chen et al.] (02T). Statistical analysis of double Q-learning is also an active
area (Weng et
2020 Xiong et al. (2020) that deserves future studies.
Besides the variants 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
1017:Song et al. 2019; Kim et al.) 2019: Pan et al. (019). The characteristic of our approach is the usage of approximate dynamic programming. Our analysis would provide theoretical support for memory-bbsed approaches. such as episodic control (Blundell et al.) 2016)] Pritzel et al. 2017) Lin et al. 2018 Zhu et al., 20200 Hu al. [021], which usually designed for near-deterministic environments. Instead of using an explicit planner, Fujjia et al. (2020) adopts the trajectory return lower bound for value estimation. This simple technique also shows promise in improving the efficiency of continuous control with clipped double Q-learning.
7 Conclusion
In this paper, we reveal an interesting fact that, under the effects of approximation error, double Q-learming 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 significant improvement over baselines algorithms.
10

---

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. 2018AAA010000)) a grant from the Institute of Guo Qiang, Tsinghua University, and grant from Turing AI Institute of Nanjing.
References
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence in deep q-learning. arXiv preprint 1XXXv:9903.0889/ 2019.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning. International Conference on Machine Learning, pages 176-185. PMLR, 2017.
Kavosh Asadi and Michael Littman. alternative softmax operator for reinforcement leamning In International Conference on Machine Learning, pages 243-252, 2017.
Richard Bellman. Dynamic programming. Princeton University Press, 89:92, 1957.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv:1606.04466 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Luitzen Egbertus Jan Brouwer. Über abbildung von mannigfaltigkeiten. Mathematische annalen, 71 (1):97-115, 1911.
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Mare G Belle- mare. Dopamine: A research framework for deep reinforcement learning. arXiv preprint
arXiv:1812.061 10, 2018.
Gang Chen. Decorrelated double q-learning. arXiv preprint arXiv:2006.06956 2020.
Shi- Yong Chen, Yang Yu. Qing Da, Jun Tan, reinforcement learning in dynamic environment with application online recommendation. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1187-1196, 2018.
Huang, and Hai-Hong Tang. Stabilizing
Xinyue Chen, Che Wang, Zijian Zhou, and Keith Ross. Randomized ensembled double q-larnnig:: Learning fast without model. In International Conference Learning Representations, 2021.
Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann. Better exploration with optimistic actor critic. In Advances in Neural Information Processing Systems, pages 1785-1796, 2019.
Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International Conference on Machine Learning. pages 2627-2637. PMLR, 2020.
Carlo D'Eramo, Marcello Restelli, and Alessandro Nuara. Estimating maximum expected value through gaussian approximation. In International Conference on Machine Learning, pages 1032- 1040. PMLR, 2016.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforeement learning via soft updates. In Proceedings of the Thirty-Secome Conference on Uncertainty in Artificial Intelligence, pages 202-211, 2016.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep qelaarning algorithms. In International Conference Machine Learning, pages 2021-2030, 2019.

---

Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-
critic methods. In International Conference on Machine Learning, pages 1587-1596, 2018.
Scott Fujimoto, David Meger, and Doina Precup. Off- deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062, 2019.
Yasuhiro Fujita, Kota Uenishi, Avinash Ummadisingu, Prabhat Nagarajan, Shimpei Masuda, and Mario Ynocente Castro. Distributed reinforcement learning of targeted grasping with active vision for mobile manipulators. 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 9712-977 17119 IEEE, 2020.
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points points-online online stochastic gradient for tensor decomposition. In Conference on learning theory, pages 797-842. PMLR, 2015.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, pages 1861-1870, 2018.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining im- provements in deep reinforcement learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Hao Hu, Jianing Ye, Zhizhou Ren, Guangxiang Zhu, and Chongjie Zhang. Generalizable episodic memory for deep reinforcement learning. arXiv preprint arXiv:2 06469, 2021.
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon model accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 1181-1188 Citeseer, 2015.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Qt-opt: Scalable deep reinforcement learning for vision-bart based robotic manipulation. In Conference on Robot Learning. PMLR, 2018
Richard M Karp and Michael O Rabin. Efficient randomized pattern-matchie matching algorithms. IBM journal of research and development, ((():2244-60)) 1987.
Seungchan Kim, Kavosh Asadi, Michael Littman, and George Konidaris. Deepmellow: removing the need for a target network deep q-learning Proceedings of the 28th International Joint Conference Artificial Intelligence, pages 2733-2739, 2019.
Arsenii Kuznetsov, Pavel Shvechikov, Alexander Grishin, and Dmitry Vetrov. Controlling overesti- mation bias with truncated mixture of continuous distributional quantile critics, In International Conference on Machine Learning, 2020.
Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin q-learning: Controlling the estimation bias of g-laarning. In International Conference on Learning Representations, 2020.
Donghun Lee, Boris Defourny, and Warren B Powell. Bias-corrected q-learning control max- operator bias in q-learning. In 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pages 93- 99. IEEE, 2013.
Lihong Li, Thomas J Walsh, and Michael Littman. Towards a unified theory of state abstraction for mdps. ISAIM, 4:5, 2006.
Zhunan Li and Xinwen Hou. Mixing update q-value for deep reinforcement learning. In 2019 International Joint Conference on Neural Networks (IJCNN), pages 1-6. IEEE, 2019.
12

---

Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference Learning Representations, 2016.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2433-2439, 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. In Advances in Neural Information Processing Systems, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53)) 2015.
Andrew W Moore and Christopher G Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning, 13(1::003-130 1993.
Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen, Longbo Huang, and Yan Liu. Reinforcement learning with dynamic boltzmann softmax updates. arXiv preprint arXiv: urXiv:1903.05926 2019.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomènech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In Proceedings of the 34th International Conference on Machine Learning-Voie Volume 70, pages 2827-2836, 2017.
Martin Riedmiller. Neural fitted q iteration-first experiences with a data efficient neural reinforcement learning method. In European Conference on Machine Leurning, pages 317-328. Springer, 2005.
James E Smith and Robert L Winkler. The optimizer's curse: Skepticism and postdecision surprise in decision analysis. Management Science, 52(3):311 2006.
Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International Conference on Machine Learning, pages 5916-5925, 2019.
Mervyn Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Staristical Society: Series B (Methodologicall, 36(2):111-111)) 1974.
Richard H Thaler. The winner's curse. The Journal of Economic Perspectives, 2(1):191-202, 1988.
Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the 1993 Connectionist Models Summer School Hillsdale, NJ. Lawrence Erlbaum, 1993.
Hado Van Hasselt. Double q-learning. In Advances in neural information processing systems, pages 2613-2621, 2010.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 2094-2100, 2016.
Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:1812.00 026488 2018.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pages 1995-2003, 2016.
Chris Watkins. Learming from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
Wentao Weng, Harsh Gupta, Niao He, Lei Ying, and Srikant. The mean-squared error of double q-lcarning. In Advances in Neural Information Processing Systems, volume 33, 2020.
13

---

Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang, Finite-time analysis for double q-learming. In Advances Neural Information Processing Systems, volume 33, 2020.
Huihui Zhang and Wu Huang. Deep reinforcement learning with adaptive combined critics. 2020.
Zongzhang Zhang, Zhiyuan Pan, and Mykel J Kochenderfer. Weighted double q-learning. In Proceedings of the 26th International Joint Conference Artificial Intelligence, pages 3455-3461 2017.
Zhenpeng Zhou, Steven Kearnes, Li Li, Richard Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific reports, 9(1):1-10, 2019.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020.
Rong Zhu and Mattia Rigotti. Self-correcting q-learning, In Proceedings of the AAAI Conference Artificial Intelligence volume 35, pages 11185-11192 2021.
14


Reviews:
[{"review_id": "nw9pB_9o4Bu", "reviewer": "Reviewer_cSd4", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper propose a simple but effective approach as a partial fix for the underestimation bias in double Q-learning. In pecular, it presents a doubly bounded estimator in Eq. 7, which takes maximum over two different bias estimators. The main idea is to leverage an abstracted dynamic programming as a second value estimator to rule out non-optimal fixed points.\n\nOver all quality and clarity: its idea is clear, which is motived by the possible underestimation bias from double q-learning. This paper analyze non-optimal fixed points issue in both theoretically and empirically. And its experiment with a second value estimator does improve performance on a variety of Avari tasks.  \n\nOriginality/Significance: this work introduces a novel abstracted dynamic programming as a second value estimator to overcome the possible underestimation bias in double q-learning.\n\n\nSome issues:\nHow do you guarantee y^{DP} >= y^{Boots} in Eq.7 while you use abstracted MDP to get y^{DP}? Otherwise, it falls back to original double q-learning.  It is better to add the condition in  Lemma 4 to Proposition 4 in line 274. The variance result in Proposition 4 needs V^{DP} <=E[T^{Boots}] to make it holds. In addition, it seems it is not easy to satisfy both y^{DP} >= y^{Boots} and y^{DP} <= E(y^{Boots})?\n\nPossible lack of citation:\nDeep Reinforcement Learning With Adaptive Combined Critics, 2020\nDecorrelated double q-learning, 2020\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NO", "review_text": "", "extra_scores": {"ethical_concerns": "NO", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "mw7S0BB-xOf", "reviewer": "Reviewer_U61t", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1)\tThe existence of multiple approximate fixed points in double Q-learning. The examples used are so special that the existence of multiple approximate fixed points are unclear in practical games. Even if there is an approval in Proposition 2, the authors do not show the visualization of fixed points of the practical games.\n2)\tThe authors use a well-shaped perturbation mechanism to remove non-optimal saddle points. But what is a well-shaped perturbation mechanism? Maybe, different network initialization is a good perturbation. This paper lacks the definition and discussion of perturbation. \n3)\tThe paper lacks the Algorithm table for detailed descriptions. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper presents methodological work and does not have foreseeable direct societal implications.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "eEMXxwPMZYK", "reviewer": "Reviewer_GSge", "summary": "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.\nThis 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides a new interesting point of view on the estimation bias in Q-learning in terms of suboptimal fixed points of a stochastic Bellman operator. This insight might have future implication of use for the field. However, there is a little bit of disconnect between this theoretical development and the algorithm proposed by the authors, in the sense that the theoretical insights do not seem to help much in motivating the proposed Doubly bounded estimator and the new training algorithm proposed by the authors, except for motivating the analysis of variance reduction. To justify the absence of theoretical guarantees in regard to bias redction, the authors state that \"In general, there is no existing approach [that] can completely eliminate the estimation bias in Q-learning\nalgorithm.\" This might be right, however this statement should be qualified by specifying that there are methods to construct estimators that are guaranteed to still reduce the minimization bias of the double estimator. For instance, the papers [Zhu, R; Rigotti, M. 2021. Self-correcting Q-learning, AAAI 2021] and [D’Eramo, C.; Nuara, A.; and Restelli, M. 2016. Estimatingthe Maximum Expected Value through Gaussian Approximation. ICML 2016] each propose such an estimator. So, even if these methods are not guaranteeing a complete elimination of the estimation bias, they can still guarantee a reduction.\nThe experimental part on the Atari 2600 games show impressive speed up compared to DQN and Double DQN. It would be beneficial to the readership to know what criterion the authors used in order to select these specific games from Atari.\nIt would also be instructive to see a few benchmarks of the use of the new learning algorithm on classical RL tasks where the tabular case is \"exact\" in terms of state representations, to observe the behavior of the Doubly bounded estimator in this case.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The paper gives a good overview of the relevant literature, but is failing to cite some recent related work like the following published papers:\n- Zhu, R; Rigotti, M. 2021. Self-correcting Q-learning, AAAI 2021\n- D’Eramo, C.; Nuara, A.; and Restelli, M. 2016. Estimatingthe Maximum Expected Value through Gaussian Approximation. ICML 2016\n- Lee, D.; Defourny, B.; and Powell, W. 2013. Bias-Corrected Q-Learning to Control Max-Operator Bias in Q-Learning. IEEE ADPRL Symposium, 93–99\nIt would be nice if for completeness the authors considered citing these in relation to their work.\n2. The paper could benefit from some additional experiments, in particular on classical RL tasks to help tease apart the benefit of the individual components of the algorithm, in the same spirit as the ablation study at the end of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "4SAd3kSBeA3", "reviewer": "Reviewer_gAo6", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper investigates the important problem of biased estimate of the target value of the Q-Learning update. In particular, it describes an issue of Double Q-Learning that is not documented in literature, that causes the algorithm to incur in suboptimal fixed points in approximated settings. I think the paper conducts a reasonable analysis of the problem, and supports its claims with a simple, but meaningful, toy problem.\nHowever, despite a satisfying analysis of the problem, I consider the proposed solution not rigorous enough. Although the authors make some claims about the effectiveness of the method to escape suboptimal fixed points, these claims are not supported by theoretical reasons. The sketch of the analysis on the saddle point-nature of these fixed points, and the connection with perturbed gradient descent, are interesting considerations that I think deserve a deeper analysis. The absence of theoretical guarantees on the bias obtained by Doubly Bounded Q-Learning is an important weakness of this paper, as well as the absence of theoretical guarantees about the performance w.r.t. the quality of the approximation of the MDP model.\nThe empirical analysis on Atari games is not satisfying enough, as many results of the baseline are significantly different from the ones reported in literature [1,2]. In general, I am aware Atari experiments are extremely sensitive to the choice of hyperparameters, thus, I’d rather see more reliable benchmarks to complement them. A toy problem to study more rigorously the effect of Doubly Bounded Q-Learning would be desirable. Also, it would be nice to have some evidence of the estimate of the Q-function computed by Doubly Bounded Q-Learning w.r.t. other methods. I encourage authors submitting a revised version addressing these points. Overall, this work is promising, but it needs still much work to be recommendable for publication.\n\n[1] Van Hasselt, Hado, Arthur Guez, and David Silver. \"Deep reinforcement learning with double q-learning.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 30. No. 1. 2016.\n[2] Wang, Ziyu, et al. \"Dueling network architectures for deep reinforcement learning.\" International conference on machine learning. PMLR, 2016.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received mixed reviews, but the majority of reviewers were of the opinion the paper passes the threshold to be accepted.

The topic of the paper remains of interest to the community, and I think this paper might spark additional useful thoughts and investigations, so I'm also in favour of accepting the paper for presentation at the conference.
Decision: Accept (Poster)