On the Estimation Bias in Double Q-Learning
Authors: Zhizhou Ren
Guangxiang Zhu
Beining Han
Jianglun Chen
Chongjie Zhang
Venue:  (2021)
Keywords: Reinforcement learning
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 operator. 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 still suffers from underestimation bias. In this paper, we show that such underestimation bias may lead to multiple non-optimal fixed points under an approximated Bellman operation. To address the concerns of converging to non-optimal stationary solutions, we propose a simple and effective approach as a partial fix for underestimation bias in double Q-learning. This approach leverages real returns to bound the target value. We extensively evaluate the proposed method in the Atari benchmark tasks and demonstrate its significant improvement over baseline algorithms.

Under review as a conference paper at ICLR 2021
ON THE ESTIMATION BIAS IN DOUBLE Q-LEARNING
Anonymous authors Paper under double-bling blind review
ABSTRACT
Double Q-learning is a classical method for reducing overestimation bias, which is caused by taking maximum estimated values in the Bellman operator. 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 still suffers from underes- timation bias. In this paper, we show that such underestimation bias may lead to multiple non-optimal fixed points under an approximated Bellman operation. To address the concerns of converging to non-optimal stationary solutions, we pro- pose simple and effective approach as partial fix for underestimation bias in double Q-learning. This approach leverages real returns to bound the target value. We extensively evaluate the proposed method in the Atari benchmark tasks and demonstrate its significant improvement over baseline algorithms.
INTRODUCTION
Value-based reinforcement learning with neural networks as function approximators has become widely-used paradigm and shown great promise in solving complicated focision-makinn prob- lems various real-world applications, including robotics control (Lillicrap et al. (016)). molecular structure design (Zhou al. 2019), and recommendation systems (Chen et al. 2018). Towards un- derstanding the foundation of these successes, investigating algorithmic properties of deep-learning- based value function approximation has been seen 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 inter- est is that Q-learning (Watkins (989) known to suffer from overestimation issues, since it takes maximum operator over estimated action-values Comparing with underestimated values, overes- timation errors are more likely to be propagated through greedy action selections, which leads to an overestimation bias in value prediction (Thrun & Schwartz] 1993). This overoptimistic behavior of decision making has also been investigated in the literature of management science (Smith &
Winkler 2006) and economics (Thaler) 1988).
From a statistical perspective, the value estimation error may come from many sources, such as the stochasticity of the environment and the imperfection of the function expressivity. However, for deep Q-lcarning algorithms, even if most benchmark environments are nearly deterministic (Brockman al. 2016) and millions of samples (Hasselt et al. 2016). One cause of this problematic issue is the difficulty of optimization. Although deep neural network may have a sufficient expressiveness power 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 deep reinforcement learning algorithms. The high variance of such stochastic methods in gradient estimation would lead to an unavoidable approximation error in value prediction. This kind of approximation error cannot be addressed by simply increasing sample size and network capacity, which is major source of overestimation bias.
collected, the overestimation phenomenon is still dramatic
Double Q-learning a classical method to reduce the risk of overestimation, which is specific vari- ant of the double estimator (Stone) 1974) in the Q-learning paradigm. It uses a second value function to construct an independent action-valus evaluation as cross validation. With proper assumptions, double Q-learning was proved to underestimate rather than overestimate the maximum expected values (Van Hasselt 2010). However, in practice, obtaining two independent value estimators is usually intractable in large-scale tasks. which makes double Qllearning still suffer from overesti- mation in some situations. To address these empirical concerns, Fujimoto et al. (2018) proposed variant named clipped double Q-leaning, which takes the minimum
value estimations.

---

Under review as a conference paper at ICLR 2021
This approach implicitly penalizes regions with high uncertainty (Fujimoto al. 2019) and thus significantly repress the incentive of overestimation.
In this paper. first review analytical model adopted by prior work (Thrun & Schwartz 1993 Lan et al. 2020) and reveal a fact that, due to the existence underestimation biases, both double Q-learning and clipped double Q-learning have multiple approximated 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. To bootstrap the ability of double Q-learning, we propose a simple heuristic that utilizes real return signals as a lower bound estimation rule out the potential non- non-optimal fixed points. Benefiting from its simplicity, this method is easy to be combined with other existing techniques such as clipped double Q-learning. In the experiments on Atari benchmark tasks, we demonstrate that this simple approach is effective both in improving sample efficiency and convergence performance.
2 BACKGROUND
Markov Decision Process (MDP; Bellman 1957) is a classical framework to formalize an agent- environment interaction system which be defined tuple .M (S,A, R, 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 the agent. is the discount factor. The goal of reinforcement learning is to construct a policy S + A maximizing discounted cumulative rewards,
(*)))= = E Σ ,' R(st, (s:)) 8o 8,
P(-|se, (s:))
Another quantity of interest in policy learning can be defined through the Bellman equation Q (s, R(s, a) + -PEysP((lss.)) (V)) The optimal value function Q' corresponds to the unique solution of the Bellman optimality equation,
max Q a'EA
((s E x A, (s. = R(s,a)++ +y
E
Q-learning algorithms are based on the Bellman operator T stated as follows:
(TQ)(8,a) = R(s, a) P(-laa))))
E max Q6'','))
(1)
a'EAA
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 sample- based objective function and constructs an iterative optimization framework:
(r+ + max Qo. (s', a') ((oss'a')o(sso))) a'EA
0.+1 <- arg min 9EE
E (S,a,T,)))
in which θ denotes the parameter space of the value network, and 0, O is initialized by some predetermined method. D is the data distribution which is changing during exploration. With infinite samples and sufficiently rich function class, the update rule stated in Eq. (2) is asymptotically equivalent to applying the Bellman operator T, but the underlying optimization is usually inefficient in practice. In deep Q-learning, Eq. 22 is optimized by mini-batch gradient descent and thus its value estimation suffers from unavoidable approximation errors.
3 EFFECTS OF UNDERESTIMATION BIAS IN DOUBLE Q-LEARNING
In this section, we will first review a common analytical model used by previous work studying estimation bias (Thrun & 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-learnigg have multiple fixed point solutions under approximated Bell- man operation. This result suggests that double Q-learning may have extra non non-optimal stationary solutions under the effects of the approximation error.
2

---

Under review as a conference paper at ICLR 2021
3.1 MODELING APPROXIMATION ERROR IN Q- Q-LEARNING
Following Thrun & Schwartz 1993) and Lan et al. 2020), we formalize the underlying approxima- tion error (s, a) of target value regression as a set of random noises impacting on the Bellman operation.
(s.) (TQ()) (sQ (s,
where T denotes the ground truth Bellman operator using full information of the MDP (see Eq. ① and T denotes a stochastic operator with noisy outputs. The main purpose of introducing the ex- plicit noise term e(9) a) to emphasize that the approximation error discussed here different from the sampling error. In an information-theorriicc perspective, the sampling error can be reduced asymptotically as the sample size increases. However, there is a barrier of optimization difficulty to establish precise estimation in practice, which leads to an unavoidable approximation error in opti- mization. By integrating the noise term e!t) (s, into the Bellman operation, we set up analytical model to investigate how Q-learning algorithms interact with the inherent approximation error.
In this model, double Q-learning (Van Hasselt 2010) can be modeled by two estimator instances ( (1.2) with separated noise variables fe; hee(1.) For simplification, we introduce a policy function x (s) arg max, Q10) (s, override the state value function as follows:
Vi E (1,2),
2 (s,a) = R(s,a) +
E
(s)) (l
s'-P(a)).))
(4)
(() Q²4h (s, (()) Q000 9, arg m Q (s.a))
The difference of Eq. (4) from the definition of double Q-learning given by Van Hasselt (2010) is using a unified target value (s') for both two estimators. This simplification does not affect the derived implications of double Q-learning and is also implemented by advanced variants of double
Q-learning (Fujimoto et al. 2018 Lan et al. 2020).
Note that the target value be constructed only using the state-value function. Based on this observation, we can define the fixed point of a stochastic operators on the target value.
Definition 1 (Approximated Fixed Points). Let T denote a stochastic Bellman operator, such as what are stated in Eq. (3) and Eq. f A state-value function V is regarded as an approximated fixed point under a stochastic Bellman operator ' if satisfies E E[TV] = V, where TV denotes the output state-value function while applying the Bellman operator T on V.
The fixed point defined above is named approximated since they are not truly static, but is invariant under the stochastic Bellman operation in expectation. In Appendix A.2 we will prove the existence of such fixed points as the following statement.
Proposition 1. Assume the probability density functions the noise terms {e(s, a)} are continuous. The stochastic Bellman operators defined by Eq. 3 and Eq. (4) have approximated fixed points defined as Definition
3.2 EXISTENCE OF MULTIPLE APPROXIMATED FIXED POINTS DOUBLE Q-LEARNING
Given the definition of the approximated fixed point, 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 approximated fixed points of double Q-learning may not be unique.
Figure La illustrates a simple MDP in which double Q-learning stated as Eq. 4 has multiple ap- proximated fixed points. This MDP is fully deterministic and contains only two states so and 81- All actions state 81 lead to a self-loop and produce unit reward signal. On state 8p, the result of executing action ag a self-loop with a slightly larger reward signal than choosing action oj which leads to state $1. The only challenge for decision making in this MDP is to distinguish the outcomes of executing action ag and aj on state sy. To make the example more accessible, we assume the approximation errors (c(1) (s, (s..a)) a),,, are set of independent random variables following uniform
3

---

Under review as a conference paper at ICLR 2021
(su))
Ra.0=1.1
R1o=RR11=1
((so)
(s1)
*(oo(so)
100.162
100.0
62.2%
R =1
101.159
100.0
92.9%
c 1.0 7 0.99
110.0
100.0
100.0%
57.5
50.0
20.5
10.0
50.5
105.
1005
(a) A simple construction
(b) Numerical solutions fixed points
(c) Visualizing non-monotonicity
Figure 1: (a) A simple infinite-horizon MDP where double Q-leariing stated as Eq. (4) has multiple approximated fixed points. Ra, is shorthand of R(s;, ag)) (b) The numerical solutions of the fixed points produced by double Q-learning in the MDP presented above. ग refers to Definition 3 (c) The relation between the input state-value V (so) and the expected output state-value ((V(++)(ss))
generated by double Q-learning in the constructed MDP, in which we assume ((*(ss) 100.
distribution Uniform(-e, This simplification is also adopted by Thrun & Schwartz (1933) and Lan al. 2020) in studies. Here, select the magnitude of noise 1.0 and the discount factor as 0.99 to balance the scale of involved amounts.
Considering to solve the equation [] = V according to the definition of the approximated fixed point (see Definition [ 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 this MDP (see the last row of Table since the noise magnitude e = 1.0 is much smaller than the optimality gap ("(sp, 4n) Q"((s=' a1 = 10. The other two fixed points are non-optimal and very close to (s0,, ao) Q(so, 01) = 100, in which the agent cannot fully distinguish the difference between choosing ag and Ø₁ To illustrate this example,
first present a sufficient condition for a stochastic Bellman operator to have multiple fixed points, and then we give intuitive explanation to connect this condition with the constructed MDP.
Mathematical Condition. Note that the definition of the stochastic Bellman operator is a model of an imprecise target value regression. From this perspective, the input of a stochastic Bellman operator can be defined as set of ground truth target values {(TQ())) notation, a sufficient condition for the existence of multiple fixed points stated as follows.
) as),),,.. Based on this
Proposition 2. Let fa (((TQ) a))aea) = E[)) denote the expected output value of the stochastic Bellman operator T on state and assume fa(-) is differentiable. Ifa stochastic Bellman operator T satisfies Eq. (5) there exists MDP such that T has multiple fixed points.
3i, 3X E RAA,,
ffx(X)
(5)
Fx.
where X = (xx))!= denotes the input of the function f..
The proof of Proposition 2 is deferred to Appendix A.4 This proposition suggests that, in order to determine whether a given stochastic Bellman operator T may have multiple fixed points, we need to check whether its expected output values could change dramatically with a slight alter of the input values.
Intuitive Explanation. To provide the intuition for understanding the constructed MDP in Fig- ure [ we introduce simple property of a Bellman operator, named monotonicity, which helps to illustrate how the sufficient condition Eq. (5) are met in double Q-learning.
Definition 2 (Monotonicity). stochastic Bellman operator T is called approximately monotonic if it satisfies the following property:
VM, VV1 V/2 E S (V's E S, Vi(s) > Vi(()) = (VS S, S, {(( E((V))()))))))
Although this monotonicity property holds for vanilla Q-learning Watkins 1989) and recent vari- ant called maxmin Q-learning (Lan et al. 2020). absents from double Q -eearning (Van Hasselt, 2010) and famous variant called clipped double Q-learning (Fujimoto et al. 2018). The mono- tonicity property is not a sufficient condition for Eq. (5) but it is quite important for understanding the constructed example in Figure
4

---

Under review as a conference paper at ICLR 2021
Considering the constructed MDP as example, Figure Ic visualizes the relation between the input state-value V(0 (so) and the expected output state-value (=) while assuming (() 100 has converged its stationary point. The minima point of the output value is located the sit- uation where (su) is slightly smaller than (s1,, since the expected policy derived by TV(s) will have a remarkable probability 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 (so) increases. During this process, large magnitude of the first-order derivative could be found to meet the condition stated in Eq. (5)
heuristics to verify the condition in Eq. 5 is to check the nearby regions of the local minima and maxima in a non-monotonic function E[TV]. In Appendix A.5 we also show that clipped double Q-learning, another method with non-monotonicity, has multiple fixed points in an MDP slightly modified from Figure Ta
Implications facilitate discussions, we introduce a concept, named induced policy, to charac- terize how the agent behaves and evolves around these approximated fixed points.
Definition (Induced Policy). Given a target state-value function V, its induced policy ã is defined as a stochastic action selection according to the value estimation produced by stochastic Bellman operation,
((as)
arg max
R(s,d') +Y
E
+e),))))
stoP(())
(TQ)(a,a))
where (e1(8,0) )sssa are drawing from the same noise distribution as what is used by double Q- learning stated in Eq. (7).
Proposition 3. Assume the noise terms e1 and e2 are independently generated in the double estima- stated in Eq. (7) Every approximated fixed point V equal to the ground truth value function V with respect to an induced policy ã.
As shown by this proposition, the estimated value of non-optimal fixed point is corresponding to the value of stochastic policy, which revisits the incentive of double Q-learning to underestimate true maximum values. Based on Proposition 3] the concept of induced policy can provide snapshot infer the algorithmic properties of ap- proximated fixed points. Taking the third column of Table 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 sg. This phenomenon suggests that the approximation error would make the greedy action selection become competitive among actions with near-me near-maximum values. Once the approximation error leads the policy to select non-optimal action, the learning of the value function would get stuck in non-optimal fixed points. Note that, according to the characterization given by Definition 3] the stationary property of such kind of fixed points might be similar to that of saddle points in the literature optimization. Whether the agent gets stuck in non-optimal solutions depends on the actual behavior of approximation error. In section 4 will introduce a method to provide incentives for escaping non-mmtimal fixed points by reducing underestimation bias.
The proof of Proposition 3 deferred to Appendix A.3
3.3 APPROXIMATION ERROR IN DEEP Q-LEARNING
In the MDP example presented in the previous section, the noise terms (s, are modeled by set of uniform random variables Uniform( c), The noise magnitude = 1.0 seems to a bit large when it compares with the scale of one-step reward sig- nal, but it is actually quite small in terms of the scale of the value function. Considering an MDP only containing positive rewards, the scale of value functions would be in [0, Rmax/ (1 ]]] where Rmux denotes the upper bound of reward signals. In this setting, if the relative error of solving the target value regression achieves the order of 1/(1- (1_)),, the induced approximation error will reach the same scale of reward signals. Revisiting the MDP introduced in the previous section with the
Table 1: Evaluating the mean absolute TD-error of DDQN in WizardOfWor.
samples
QQ
TD-error
3M
0.310
0.014
5M
0.303
0.014
10M
0.471
0.015
5

---

Under review as a conference paper at ICLR 2021
discount factor y 0.99, the noise magnitude 1.0 is only 1% relative entor comparing to the scale of the value function, which finally leads to a 10% relative error in value estimation. is worth noticing that such small approximation error can cause significantly sub-optimal fixed points. Table | presents the scale of the estimation error of DDQN in a deterministic version of one Atari benchmark task. We evaluate the average absolute TD-error E[JQ TQ using a batch of transitions sampling from the replay buffer. The evaluation processed before the target value switches. As shown in Table the value estimation of DDQN suffers from constant approxima- tion error, which may cause the potential risk of multiple non-optinn non-optimal fixed points according to our analysis.
4 LOWER BOUNDED DOUBLE Q-LEARNING
As discussed in the last section, the underestimation bias of double Q-learning may lead to mul- tiple non-optimal fixed points in the analytical model. A major source of such underestimation is the inherent approximation error caused by the difficulty of optimization. this section, we will introduce simple heuristic, named lower bounded double Q-learning, which helps reduce the negative effects of underestimation.
The main idea is motivated by fact that the value prediction produced by double Q-learning does not tend to overestimate the true maximum value. It a major difference from the overestimation bias of vanilla Q-learning. When the environment is deterministic, the return values of collected trajectories can naturally serve as lower bound for value estimation. To utilize this lower bound, modify the objective function of deep Q-learning as follows.
(tre + 7 max VV((st)))VV((sss)) Q0(se, az)))
T((0)
(at (
where the target value is computed by taking the maximum over two sources of estimation. The first term (8(+)))) is the target state-value computed by the frozen parameter ô. The second term (+(++)1) is the discounted return value of the corresponding trajectory T in the replay buffer. For- mally, V, (5t+1) Hit 7*144441 where H denotes the length of the trajectory.
This lower bounded objective has three potential impacts on the value estimation:
Considering the non-optimal fixed points of double Q-learning discussed in the previous section, the values of these fixed points are corresponding to some sub-optimal polices which underestimate the optimal action-values (see Proposition B}. Under the effects of exploration, some of the collected trajectories may have higher returns than the current policy, which would provide an incentive to get rid of the non-optimal fixed points through the lower bounded objective.
When the return signal V, has approached the ground truth maximum value V*, the lower bounded objective will lead to an overestimation bias, since only underestimated values are cut off by the maximum operator. In practice, the effects of such overestimation bias are manageable, because all trajectories are collected by an exploratory policy which can hardly produce the ground truth maximum values.
In addition, when the environment carries high return values would cause additional risks of overestimation through the proposed lower bounded objective. In the other hand, our method excels addressing the issue of non-optimal fixed points, which is exacerbated by the environment stochasticity. This is because the environment stochasticity increases the difficulty of optimization in the target regression and leads to larger approximation error that generates non-optimal fixed points. From this perspective, our method a trade-off between the underestimation bias of double Q-learning and the overestimation of the trajectory-based lower-bound estimation. The effectiveness of such trade-off will investigated empirically in section 5
extent of stochasticity, the trajectories with
In this paper, we investigate two methods to compute the estimated target value ()($++1). The first choice V-DDON(s) (s') corresponds to the implementation proposed by double deep Q-network (DDQN; 6

---

Under review as a conference paper at ICLR 2021
Hasselt et al. 2016),
DDON (8') = Qi a max Qo(s' .a)) d'EA
It is an adaption of double Q-learning to the framework of deep Q-network (DQN; Mnih et al. 2015), in which the action selection target values are produced by the online parameter
An imperfection of the combination with DDQN is that, DDQN is known to suffer from overesti- mation sometimes since value predictions produced by 0 and 0 are not fully independent. When the overestimation happens, the real return signal V,, (st-1) cannot provide any benefits to the value prediction. To address these concerns, also adopt another advanced technique called clipped double Q-learning (Fujimoto et al. 2018):
CCDON (5) = min Qo, (', max Qo, (s', (d))))) d'EA
(E(1,2
This formulation of computing target values is adapted from its actor-critic version, and we name it clipped double deep Q-network (Clipped DDQN). This method uses shared objective function to optimize two copies of value networks Qe, and Qe in which the target values are computed by taking the minimum introduces underestimation bias (Ciosek al. 2019) which significantly repress the incentive of overestimation in all sources. This underestimated estimator is appropriate to combine with the lower bounded objective since the lower bound provide by trajectory returns can help to prevent the underestimation error from propagation.
two separated estimations Qù, and Qa This minimum operator will
5
EXPERIMENTS
Our experiment environments are based on the Atari benchmark tasks in OpenAI Gym (Brock- man et al., 2016). All baselines and approaches implemented using the same of hyper- parameters. detailed description of experiment settings is deferred to Appendix
Overall performance comparison. We investigated six variants of deep Q-learning algorithms, including DON (Mnih et al.] 2015), double DQN (DDON: Hasselt et al. (016). 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 lower bounded objective built upon two variants of double Q-learning which have clear incentive of underestimation. As shown in Figure 2 the proposed lower bounded objective has great promise in bootstrapping the performance of double Q-Jearning algorithms. The improvement can be observed both terms of sample efficiency and final performance. This advance may credit to the removal of potential non- optimal fixed points. Another notable observation is that, the effects of adopting clipped double Q-learning aivironment-depeedeent, since it has underestimation bias which cannot be fully eliminated by the lower bounded objective. In Appendix C reveal the superiority of the proposed method.
we present more experimental results to
Comparison with n-step bootstrapping. In addition to our proposed lower bounded objec-
Alien
Average Episode Return
tive, n-step bootstrapping (Sutton) 1988) also
1410
5-step
has potential to attenuate the issue of non-
1-step
optimal fixed points by utilizing real returns.
7-step
An advantage of our method is that the per-
500
5-step
formance of n-step bootstrapping is sensitive to the choice of the hyper- sapee--arreeter n. Figure 3, we evaluate the performance of DDQN with different values of n chosen by Hessel et al. 2018). The results indicate that our proposed lower bounded objective is compatible with n- step bootstrapping. The performance further improved by combing two approaches. More experimental results on the comparison with
3-step
1-stop
0M
2M
3M
4M
SM
Timesteps
Figure 3: Learning curves of DDQN with n-step bootstrapping.
be
n-step bootstrapping are provided in Appendix D

---

Under review as a conference paper at ICLR 2021
Clipped DDQN LB (ours)
Clipped DDQN DDQN
Dueling DDQN Averaged DQN
Maxmin DQN DQN
DDQN+ (ours)
Average Episode Return
Alien
BankHeist
BattleZone
30003
13000
12003
250
0M
2M
4M
6M
SM
10M
0M1
1M
2M
SM
0M
2M
4M
6M
8M
10M
T
Timesteps
Timesteps
T Timesteps
Average Episode Retara
Frostbite
MsPacman
RoadRunner
4800
50000
6080
3300
4500
3400
3180
1840
1.80
11003
011
251
4.9
6/1
851
10M
051
251
4M
6M
RM
19M1
051
1M
251
3M
4M
SM
Timesteps
Timesteps
Timestops
Average Episode Return
StarGunner
WizardOlWor
Zaxxon
seren
12500
10000
10000
30000
7503
400
20100
18060
4M
12M
16M
0.1
2M
10M
3M
6M
9M
12M
15M
Timesteps
Timesteps
Timestops
Figure 2: Learning curves suite of Atari benchmark tasks, in which the "+LB" version corre- sponds to the combination with the proposed lower bounded objective. All curves presented in this paper are plotted from the median performance over runs with random initialization. To make the comparison more clear, the curves are smoothed by averaging 10 most recent checkpoints. More experiment results are included in Appendix
Alien
BankHeist
Frostbite
Average Episode Return
1120
198
oUrS
4530
Rainbew
CS)
880
DON
6.5
Timestaps
Timestops
Timestopa
Figure 4: Learning curves on suite of stochastic Atari benchmark tasks with sticky actions, in which "ours" version corresponds to the combination of the proposed lower bounded objective with clipped double Q-learning and multi-step bootstrapping. "ours LB" corresponds to the ablation study without the lower bounded objective. The curves of Rainbow, C51, and DQN are released by Castro et al. 2018) using the same environment setting.
Performance comparison in stochastic environments with sticky actions The experiments pre- sented in Figure 2 and Figure 3 are based on the standard environment setting used by Mnih et al. (2015), in which the environment stochasticity only comes from the partial observability of visual observations. When the environment stochastic, the trajectories with high return values would cause additional risks of overestimation through the proposed lower bounded objective. To inves- tigate the performance of our method in stochastic environments, we adopt stochastic variant of Atari environment setting with sticky actions Machado al. (20T8), in which every environ-
8

---

Under review as a conference paper at ICLR 2021
ment step will execute the agent's previous action with probability 0.25. In this experiment, investigate two sfate-of-the-art baselines, Rainbow (Hessel et al. 2018) and C51 (Bellemare et al. 2017), which use distributional representation to address the optimization difficulty of environment stochasticity. To fairly compare with these state-of-the-art baselines that integrates many standard techniques, we also combine our proposed lower bounded objective with clipped double Q-learning and multi-step bootstrapping. As shown in Figure our proposed method still outperform basclines in stochastic environments. This result suggests that, comparing the overestimation bias intro- duced by the lower bounded objective, stuck in non-optimal fixed points is more critical issue for deep Q-learning algorithms. Another explanation is that the environment stochasticity may increase the difficulty of optimization and lead to larger approximation error for generating non-optimal fixed points. Our proposed method an effective trade-off between the risks of overestimation and non- optimal fixed points.
6 RELATED WORK
Correcting the estimation bias in double Q-learning is active topic which induces series of approaches. Weighted double Q-learning (Zhang et al. (017)) considers an importance weight pa- rameter integrate the overestimated and underestimated estimators. Clipped double Q-learning (Fujimoto et al. 2018), which uses minimum operator in target values, 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 CeeieiannneCCCeeeeeeee et al. 2019); Li & Hou (2019).
Besides the variants of double Q-learning, there are lots of other techniques proposed regarding the bias-variance trade-off Q-learning algorithms. Similar to our proposed approach, most of existing methods focus the construction of target values. Averaged DQN (Anschel et al., 2017) uses multiple historical copies of target networks to reduce the variance estimation. The target used by truncated quantile critics (TQC; Kuznetsov et al. 2020) is based on distributional representation of value functions, which contributes to reduce the overestimation of actor-critic methods. Using the softmax operator in Bellman operation is also considered as an effective approach to reduce the
effects of approximation error (Fox et al. 2016 Asadi & Littman 2017 Song et al. 2019 Kim
al. 2019).
The characteristic of our approach is the usage of real return signals, which uses the environment prior to break statistical barriers. Our method is a variant of self-imitation (Oh et al. 2018) and is integrated with the Bellman operation. The effectiveness of such a ground truth lower bound is also observed by a recent work (Fujita et al. 2020). When the environment carries stochasticity, taking the average return among similar states is a plausible approach to reducing the bias of the trajectory- based estimation. From this perspective, the proposed method is also related to the memory- approaches for nearly deterministic environments, such as episodic control (Blundell et al. 2016 Pritzel et al. 2017) and graph- based planning (Huang et al. 2019 Eysenbach et al. 2019).
7 CONCLUSION
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 hard cases are constructed. To address the potential risk of converging to non-optimal solutions, we propose an alternative objective function to reduce the underestimation in double Q- learning. The main idea of this approach is to leverage real environment returns lower bound for value estimation. Our proposed method is simple and easy to be combined with other advanced techniques in deep Q-learning. The experiments show that the proposed method has shown great promise in improving both sample efficiency and convergence performance. achieves a significant improvement over baselines algorithms Atari benchmark environments.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Joshua Achiam, Ethan Knight, and Picter Abbeel. Towards characterizing divergence in deep q- learning. arXiv preprint wwxiv:/903.0889. 2019.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning. In International Conference on Machine Learning, pp. 176-185. PMLR, 2017.
Kavosh Asadi and Michael I. Littman. An alternative softmax operator for reinforcement learning. In International Conference on Machine Learning, pp. 243-252, 2017. 2017.
Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. International Conference on Machine Learning, pp. 1149-458, 2017.
Richard Bellman. Dynamic programming. Princeton University Press, 89:92, 1957.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv:/606. 04460, 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech 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.0661 10, 2018.
Shi- Yong Chen, Yang Yu, Qing Da, Jun Tan, Hai- Kuan Huang, and Hai- Hai-Hong Tang. Stabilizing reinforcement learning in dynamic environment with application to online recommendation. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1187-1196, 2018.
Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann. Better exploration with optimistic actor critic. In Advances in Neural Information Processing Systems, pp. 1785-1796, 2019.
Will Dabney, Georg Ostrovski, David Silver, and Remi Munos. Implicit quantile networks for distributional reinforcement learning. In International Conference on Machine Learning, pp- 1096-1105, 2018.
Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International Conference Machine Learning, 2020.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. Advances in Neural Information Processing Systems, pp- 15246-15257, 2019.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. In Proceedings of the Thirty-Secome Conference on Uncertainty in Artificial Intelligence, pp. 202-211, 2016.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q- learning algorithms. In International Conference on Machine Learning, pp. 2021-2030, 2019.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596, 2018.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference Machine Learning, pp. 2052-2062. 2062, 2019.
10

---

Under review as a conference paper at ICLR 2021
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. arXiv preprint arXiv:2007.08082 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pp. 1861-1870, 2018.
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, pp. 2094 2100, 2016.
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 improvements in deep reinforcement learning. In Proceedings of the Thirty-Second AAAI Con- ference on Artificial Intelligence, 2018.
Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching. In Advances in Neural Information Processing Systems, pp. 1942-1952, 2019.
Seungchan Kim, Kavosh Asadi, Michael Littman, and George Konidaris. Deepmellow: removing the need for a target network in deep q-learning In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 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 q-learning. In International Conference on Learning Representations, 2020.
Zhunan Li and Xinwen Hou. Mixing update q-value for deep reinforcement learning. In 2019 International Joint Conference on Neural Networks (IJCNN), pp. 1-6. IEBE, 2019.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, In Inter- national Conference on Learning Representations, 2016.
Marlos C Machado, Mare G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 51 518(7540::59-5533 2015.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In International Conference on Machine Learning, pp. 3878-3887, 2018.
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 Mharning-Volume 70, pp. 2827-2836, 2017.
James E Smith and Robert L Winkler, The optimizer's ' curse: Skepticism and postdecision surprise in decision analysis. Management Science, 52(3):311 1-222. 2006.
Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International Conference on Machine Learning, pp. 5916-5925, 2019.
Mervyn Stone. Cross- volis-val choice and assessment of statistical predictions. Journal of the Royal Statistical Society: Series B (Methodological), 36(2):111-133, 1974.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9 44, 1988.
11

---

Under review as a conference paper at ICLR 2021
Richard H Thaler. The winner's curse. The Journal of Economic Perspectives, 2(1):191-20) 10022 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. Advances neural information processing systems, pp- 2613-2621, 2010.
Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo- dayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:1812.0264/ 2018.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003, 2016.
Chris Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
Zongzhang Zhang, Zhiyuan Pan, and Mykel Kochenderfer. Weighted double q-learning. In Pro- ceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 3455-3461, 2017.
Zhenpeng Zhou, Steven Kearne,, Li Li, Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific reports, 9(1):1-10, 2019.
12

---

Under review as a conference paper at ICLR 2021
A OMITTED STATEMENTS AND PROOFS
A.1 1
THE RELATION BETWEEN ESTIMATION BIAS AND APPROXIMATED FIXED POINTS
intuitive characterization of such fixed point solutions considering one-step estimation bias with respect to the maximum expected value, which is defined as
E(T, V2 E(TV)(() - (TV)
(6)
where (s) corresponds the precise state value after applying the ground truth Bellman op- eration. The amount of estimation bias & characterizes the deviation from the standard Bellman operator T, which can regarded as imaginary rewards fixed point solutions.
Every approximated fixed point solution under a stochastic Bellman operator can be characterized as the optimal value function modified MDP where only the reward function is changed.
Proposition 4. Let V denote approximation fixed point under stochastic Bellman operator T. Define modified MDP M (, R, based M, where the extra reward term is defined as
R(s a) = E(T, V = [((V)
(TV))s,
where & is the one-step - bias defined in Eq. (6) Then V is the optimal state-value function of the modified MDP M.
Proof. Define a value function Q based on V. V(s, E E SxxA A.
a() + R(s,a) +
E
(V('))
d'
We can verify Q is consistent with V. vs E,
(ss) (s))
(s) - (T))(s) max aEA
R(s,a) +7 + E
(((5))
sNm((1aa)
max aeA
R(s,a) + a) +
E
(V(3))]
max a
a).
Let TM denote the Bellman operator of M. We can verify Q satisfies Bellman optimality equation to prove the given statement, V(s, a) E S x A.
(s, = R(s, a) + R((s a) +7
a') .²) [(6')]
max Oss'
E
s(-s(-)s.))
C'EA
= R(s,a) + RR(s, a) +7
B
Q(s,a).
Thus we can see V is the solution of Bellman optimality equation in M.
A.2 THE EXISTENCE OF APPROXIMATED FIXED POINTS
The key technique for proving the existence of approximated fixed points is Brouwer's fixed point theorem.
Lemma 1. Let B = --L, -L)d denote a d-dimensional bounding box. For any continuous function
f: + B, there exists a fixed point such that (xx B.
13

---

Under review as a conference paper at ICLR 2021
Proof. refers to special case of Brouwer's fixed point theorem (Brouwer 1911
Lemma 2.
Let T denote the stochastic Bellman operator defined by Eq. 3 There exists real
range L, VV E [L, - E[TV] E [L., [
Proof. Let Rmax denote the range of the reward function for MDP M. Let Rg denote the range of the noisy term. Formally,
Rmax
[R(s.a)) a)),
(8,0)E8xA
Re max #ES
E max (e(s, a)l
aEA
Note that the Loo -nom of state value functions satisfies VV RIS
||[TV]]l S Rmax R. + Vl
can construct the range L (Bmax + Ro)/(1-1)) to prove the given statement.
Lemma 3. Let T denote the stochastic Bellman operator defined by Eq. 4 There exists real range L, VV E [L, E[TV)
E [L, [L)
Proof. Let Rmux denote the range of the reward function for MDP M. Formally,
Rmax
(R(s,a)]:
(AA
Note that the Loo -norm of state value functions satisfies VV Egss)
[|E[T]]]|> I Rausx + YV
We can construct the range L Rmax/ (1 - 7) to prove the given 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. ( have approximated fixed points defined as Definition
Proof. Let f(V) [[ denote the expected return of stochastic Bellman operation. This
function is continuous because all involved formulas only contain elementary functions. The given statement proved by combining Lemma and
A.3 THE INDUCED POLICY DOUBLE Q-LEARNING
Proposition 3. Assume the noise terms e1 and e2 independently generated in the double estima- tor stated in Eq. ( Every approximated fixed point V equal to the ground truth value function R with respect to induced policy ăt
Proof. Let denote an approximated fixed point under the stochastic Bellman operator T defined by Eq. By plugging the definition of the induced policy into the stochastic operator of double
Q-learning, we can get
(ss) [s)]
E (TQ2) (s. arg m
w (TQI)(s.))
(TQ2) (s, arg max (TT))(ss.)+
(TQ2)(s.a)
E a-)((
E a-s)(
R(s, a) + S
V(s') + (e)
R(s, + ((11.a)))) V(s))
E (+ss)
which matches the Bellman expectation equation.
14

---

Under review as a conference paper at ICLR 2021
As shown by this proposition, the estimated value of non-optimal fixed point is corresponding to the value of stochastic policy, which revisits the incentive of double Q-learning to underestimate true maximum values.
A.4 A SUFFICIENT CONDITION FOR MULTIPLE FIXED POINTS
([))V)(s) denote the expected output value of the stochastic Bellman operator on state 8, and assume fz(.) is differentiable. If stochastic Bellman operator T satisfies Eq. 5 there exists an MDP such that T has multiple fixed points.
Proposition Let fo (I(TT)(s.
3i 3E E
fx(x) >
(5)
dx.
where = =xx) denotes the input of the function fa.
Proof. Suppose Sa a function satisfying the given condition, and æ; and denote the corre- sponding point satisfying Eq. (5).
Let g(r)) denote the value of fs while only changes the input value of x; to x, so that g' ( >
Since fs is differentiable, can find small region EL < 5 < En around F such that Ve [RL g/ (x) 1. And then, we have g(āR) - g( > HR TL.
Consider to construct an MDP with only one state. We can use the action corresponding to to construct a self-loop transition with reward r. All other actions lead to a termination signal and an immediate reward where the immediate rewards correspond to other components of X. By setting the discount factor as y = Æa-Ey_ < and the reward as r = Øy (g( ØR (π(#R),
g(
can find both T and R are solutions of the equation = (g)),, in which و (T). and ( correspond to two fixed points of the constructed MDP.
A.5 A BAD CASE FOR CLIPPED DOUBLE Q-LEARNING
The stochastic Bellman operator corresponding to clipped double Q-learning is stated as follows.
Wi {1,2),
( (s,a) = R(s, a) +
E
[v(( + te o (s.
d'
(() min 2000) (s, arg max (1.2)
111) (s,
An MDP where clipped double Q-learingg has multiple fixed points is illustrated as Figure
100
R=.5=1.35
V(so)
V(si)
99
90.0
Ro. 100
100.491
100.0
S0
done
101.833
100.0
101.919
100.0
1.0
7 0.99
(a) A simple construction
(b) Numerical solutions of fixed points
(c) Visualizing non-monotonieity
Figure 5: (a) simple MDP where clipped double Q-learning stated as Eq. ( has multiple approx- imated fixed points. R,, is shorthand of R(s,, a.). (b) The numerical solutions of the fixed points produced by clipped double Q-learning in the MDP presented above. (c) The relation between the
input state-value (10) and the expected output state-value E ((((+))(sso) generated by clipped double Q-learning in the constructed MDP.
15

---

Under review as a conference paper at ICLR 2021
B EXPERIMENT SETTINGS
B.1 EVALUATION SETTINGS
All curves presented in this paper are plotted from the median performance of runs with ran- dom initialization. The shaded region indicates 60% population around median. The evaluation is processed in every 50000 timesteps. Every evaluation point averaged from trajectories. The evaluated policy is combined with a 0. % random execution.
B.2 HYPEER-PARAMETES
All algorithm investigated in this paper use the same set of htyper-parametent
Number of noop actions while starting a new episode: 30;
Number of stacked frames in observations: 4;
Scale of rewards: clipping to [-1,
Buffer size: 10;;
Batch size: 32;
Start training: after collecting 20000 transitions;
Training frequency: timesteps;
Target updating frequency: 8000 timesteps;
decaying: from 1.0 to 0.01 in the first 250000 timesteps;
Optimizer: Adam with 1.5 10-4;
Learning rate: 0.625 10-4
16

---

Under review as a conference paper at ICLR 2021
C ADDITIONAL EXPERIMENTS ON STANDARD ATARI BENCHMARK TASKS
DDQN LB (ours)
DDQN
Alien
Atlantis
BankHeist
Average Episoree Return
2000
109000
1860
59000
1000
1200
*9000
750
100
40000
504
400
38000
340
0.
231
4MM
6M
RM
10M
0M
2M
4M
6M
KM
10M
0M 2M
4M
6M
XM
10M
Timeesteps BattleZone
Timesteps
Timesteps
7540 BeamRider
Bow ling
Average Episode Retura
30000
10M
Timesteps Enduro
Timesteps
Timesteps Jamesbond
Frostbite
Average Episodee Return
1400
5000
500
1200
4000
3000
1340
038
2M
4M1
6M
RM
10M
0M
2M
6M
8M1
10M
0M
2M
4M
6M
8M
10M
Timesttpps
Timesteps
Timesteps
Krull
Ms Pacman
Qbert
Average Episnde Return
3000
3200
2400
4000
1020
2000
2000
0M
10M
2M
10M
XM
Timestteps Riverraid
Timesteps
Timesteps StarGunner
RoadR unner
Average Episode Retura
12500
3000
1800
2000
7500
3000
15000
1266
03
2M
4.1
6M
RM
10M
0M
2M
4M
6M
RM
10M
0M
2M
4M
6M
8M
10M
Timesteps
Timesteps
Timesteps
Average Episnde Return
TimePilot
WizardOrWor
Zaxxon
s00
4200
5000
2000
400
1500
6M
10M
2.5
10M
251
8M
Timesteps
Timesteps
Timesteps
Figure 6: Learning curves on a suite of Atari benchmark tasks for comparing DDQN with or without lower bounded objective.
17

---

Under review as a conference paper at ICLR 2021
D
ABLATION STUDIES ON MULTI-STEP BOOTSTRAPPING
Alien
BankHeist
Average Epiiode Return
Average Episods Return
mA
S-ttpp 1.8
3-stop
1200
1-step LB
153
1-step
5-ttpp
5-step
3-step
3-stop
1-step
330
1-step
0M
1M
2M
3M
4M
SM
6M
1M
2.M
3M
4M
SM
Timesteps Frostbite
Timesteps
Runner
Average Epixode Return
Average Episode Return
53000
6000
5-ttep L.8
43000
3-step + 1B
1-step L.B
30000
1-step LB
5-step
5-stop
3000
3-4tep
20000
3-step
1500
1-step
1-step
Timesteps
Timesteps
Average Episade Retura
00000
StarGunner
Average Episode Return
12580
Zaxxon
3-step
3-step
1-step LB
7500
LB
5.step
5-stop
20000
1000
3-step
3-step
I-step
1-step
0M
4M
RM
12M
16M
20M
0M
3M
6.1
9M
12M
15M
Timesteps
Timesteps
Figure 7: Learning curves on suite of Atari benchmark tasks for comparing DDQN with n-step bootstrapping and the proposed lower bounded objective.
18


Reviews:
[{"review_id": "qnEpfqqvRcb", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of learning a value function in a deterministic MDP and proposes a heuristic to reduce the bias of value estimates under the greedy policy. For this, they consider the class of Double Q-learning algorithms and describe a setting where estimation under this algorithm can lead to multiple fixed point solutions. They propose to control underestimation bias by estimating the next-state value as the maximum of either the current next-state value or the value of some trajectory in the replay buffer. They also propose another version that uses clipped target values. The two algorithms are evaluated on several Atari games and show, in some cases, improved transient behavior over double DQN. \n\nControlling for bias due to function approximation is an important problem, and one where general solutions could have a potentially large impact for RL and AI. Giving this subject the attention it deserves will require an understanding of the bias problem in stochastic settings. Many will be curious about what can be said about this problem and its solution(s) using formal mathematical language. The multiple-solutions hypothesis is a plausible approach to gaining a better understanding of bias, but there could also be other angles to explore. \n\nI think the current research this paper presents should be broadened to understand not just deterministic environments, but stochastic ones as well. The experimental results should also be questioned: why is there little to no asymptotic performance gain using the proposed method if it indeed produces an estimate with less bias? There are more questions the community would wish to answer with a paper like this; Where does underestimation bias come from, and how can it be controlled in general? Currently, however, the presentation and technical material are not sharp enough to answer such questions. Therefore, it is important that the authors continue to mature this work so that, when it is ready for publication, it will make a significant contribution.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "emBgDSCMqia", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analysed the underestimation bias induced by approximation error, by formalizing the underlying approximation, they theoretically proved the existence of multiple approximated fixed points which causes the converging to non-optimal solution. Besides, they proposed the lower bound double q-learning to overcome the underestimation bias. \n\nStrengths:\n1.The paper is well-organized and the algorithm is simple yet effective.\n\n2.The thought of formalizing the approximation error into noise is delighted which provides a way to theoretically analyze the effect of such error.\n\n3.The definition and existence prove of approximated fixed points would helps the algorithm design to overcome the underestimation bias.\n\nWeakness:\n1.Some experiment is hard to understand. Table1 shows the TD-error and the absolute state-action value which didn’t demonstrate the small approximation error would cause significant estimation error which would cause the sub-optimal fixed points.\n\n2.The effectiveness of lower bound double q-learning is doubtful. In MsPacman of Figure2, the algorithm shows slight performance decrease of Clipped DDQN, in some environment such as WizardOfWor, Zaxxon RoadRunner and BattleZone, these algorithms seems converge into same solutions. Besides, the algorithm would cause the overestimate the true maximum value. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "R13h2nrv5Y-", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission focused on the double Q-learning and investigated its underestimation bias issue. The authors claimed that using a double estimator can lead to multiple fixed points. To alleviate this issue, the authors proposed a correction approach by using the lower bound w.r.t. the real return. Finally, experiments on Atari games were conducted to show the improved performance, when compared with double DQN.\n\nThe authors aimed to analyze the underestimation issue in double Q-learning. The observation of multiple fixed points under the stochastic Bellman operator is interesting. The authors also tried to give more interpretation by providing sufficient conditions when this phenomenon happens. The proposed lower bounded double Q learning looks novel and reasonable. \n\nI am a bit confused about the authors' explanation on the multiple fixed points in Section 3.2. The authors claimed in the last paragraph that \"..due to the existence of the approximation error, the induced policy π˜ suffers from a remarkable uncertainty in determining the best action on state s0, which is the main cause of these extra fixed points. \" If this is indeed the case, the multiple fixed points are not necessarily linked to double Q-learning, as the approximation error can appear in any form of function approximation. \n\nFollowing the above point, I also don't quite understand the motivation about Definition 3. The authors claimed in Page 5 that \"The monotonicity property is not a sufficient condition for Eq. (5) but it usually becomes a source of risks in practice.\" I just do not see how Definition 3 is necessarily connected with Proposition 3. The authors provided empirical observation that \"During this process, a large magnitude of the first-order derivative could be found to meet the condition stated in Eq. (5)\" However, this part in the curve also corresponds to the case of underestimation vanishing. Is this a contradiction here?\n\nAnother concern I have is regarding the comparison w.r.t. multi-step learning: The authors plot in Figure 3 the performance of n-step bootstrapping vs. LB, which I really appreciate. Note that this comparison is for the game Alien only; therefore, I am wondering if the conclusion holds for other games? It would be more convincing if the authors can provide more experimental results, as it can reinforce the authors' claim that the lower bounded approach rather than multi step learning is the main factor for performance improvement.\n\nThere is a related work on correcting biases in DDQN as follows, which may need to be discussed as well. The authors there also showed the improved performance on Atari games.\n\nSong Z, Parr R, Carin L. Revisiting the softmax bellman operator: New benefits and new perspective, ICML 2019.\n\nMinor comments: \"...are meet...\" -> \"...are met...\" in Page 5.", "extra_scores": {}, "extra_text": {}}, {"review_id": "07u6jF0r1bB", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##################################\n\nSummary: This paper investigates the effects of approximation error in Q-learning - more specifically, the problem of having multiple non-optimal fixed points in double Q-learning. The authors claim that double Q-learning, which is a well-known approach to alleviate overestimation bias of Q-learning, can suffer from underestimation bias, and can lead to non-optimal fixed points. This paper provides theoretical evidence to support this claim. The main idea of this paper is to add real returns as a lower bound to the objective, and alleviate underestimation bias. Empirical results in Atari domains are presented. \n\n################################################\n\nPros\n\n1. This paper addresses an important problem in reinforcement learning - approximation errors and bias in Q-learning. The major focus of the RL community on estimation bias has been overestimation bias (van Hasselt 2010), but this paper brings up the issue of underestimation bias (Lan et al 2020). \n\n2. This paper formalizes a way to model approximation error in Bellman operators in Q-learning (by setting a random noises as approximation error), and derives multiple theoretical insights and propositions (Existence of multiple fixed points in double q-learning). \n\n3. The idea of having return signal V_\\tau (the returns gained from real trajectories) as a lower bound is simple and easy to implement. As for V(frozen\\theta), the authors use both DDQN and clipped-DDQN objective; they combined these two with the lower-bound objective, and showed the performance of DDQN-LB and clipped-DDQN-LB., which performs better than previous baselines in multiple Atari domains. \n\n4. Comparison with n-step bootstrapping (Figure3) is also helpful; the idea is compatible with n-step bootstrapping, so it can be combined to improve the performance. \n\n################################################\n\n\u0010\n\nQuestions\n\n1. Section 4: Choice of trajectory \\tau for return signal V_\\tau(s_{t+1}): this term is the discounted return of trajectory \\tau in the replay buffer. Is this just a return value of one trajectory? How do you address the stochasticity of having real return value of one trajectory? Or is this an average of multiple trajectories that start from s_{t+1}? \n\n2. Have you ever considered other baselines like duel-DQN or Rainbow to compare the performance of your approach? I don’t think the empirical results (comparison with DDQN, DDQN, cDDQN, maxmin DQN, etc)  are already sufficient, but I’m just curious how it performs well compared to SOTA baselines. \n\n\n###################################################\n\nReasons for score: I think this paper addresses an important problem in RL, and presents a simple yet effective approach to address this problem. This paper is also theoretically well supported. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is rejected.

I and the reviewers appreciate the changes made by the authors. The paper presents:
* An analysis (based on techniques from previous work) of double Q-learning which shows that in an analytic model, double Q-learning can have multiple sub-optimal "approximated" fixed points.
* Propose a modification of the update that uses collected trajectories to lower bound the optimal value.
* Experiments on several Atari games.

While the theoretical results on double Q-learning are interesting, the authors provide little theoretical analysis of their proposed approach. Doing so will significantly strengthen the paper. Additionally, reviewers had concerns about the experiments. R2 questions the parameter setting in the multi-step experiments. 
Decision: Reject