Convergent and Efficient Deep Q Learning Algorithm
Authors: Zhikang T. Wang
Masahito Ueda
Venue: ICLR 2022 Poster (2022)
Keywords: DQN
reinforcement learning
convergence

Abstract: Despite the empirical success of the deep Q network (DQN) reinforcement learning algorithm and its variants, DQN is still not well understood and it does not guarantee convergence. In this work, we show that DQN can indeed diverge and cease to operate in realistic settings. Although there exist gradient-based convergent methods, we show that they actually have inherent problems in learning dynamics which cause them to fail even for simple tasks. To overcome these problems, we propose a convergent DQN algorithm (C-DQN) that is guaranteed to converge and can work with large discount factors (0.9998). It learns robustly in difficult settings and can learn several difficult games in the Atari 2600 benchmark that DQN fails to solve.

Published as a conference paper at ICLR 2022
CONVERGENT AND EFFICIENT DEEP Q NETWORK AL- GORITHM
Zhikang T. Wang & Masahito Ueda"
Department of Physics and Institute for Physics of Intelligence University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan (wang, ueda] @cat phys. .s........... u-tokyo. ac. ip
ABSTRACT
Despite the empirical success of the deep Q network (DQN) reinforcement learn- ing algorithm and its variants, DQN is still not well understood and it does not guarantee convergence. In this work, we show that DQN can indeed diverge and cease operate in realistic settings. Although there exist gradient-based con- vergent methods, we show that they actually have inherent problems in learning dynamics which cause them to fail even in simple tasks. To overcome these prob- lems, we propose a convergent DQN algorithm (C-DQN) that is guaranteed to converge and can work with large discount factors (~ 0.9998). It learns robustly in difficult settings and can learn several difficult games in the Atari 2600 bench- mark that DQN fails solve.
INTRODUCTION
With the development of deep learning, reinforcement learning (RL) that utilizes deep neural net- works has demonstrated great success recently, finding applications in various fields including robotics, games, and scientific research (Levine et al., 2018 Berner et al.) 2019: Fööel et al.) 2018 Wang et al. 2020). One of the most efficient RL strategy is Q-learning (Watkins) 1989), ) and the combination of Q-learning and deep learning leads to the DQN algorithms (Mnih al. 2015 Hes- sel et al. 2018, [Riedmiller 2005), which hold records on many difficult RL tasks (Badia et al. 2020). However, unlike supervised learning, Q-learning,
more generally temporal difference (TD) learning, does not guarantee convergence when function approximations such as neural net- works are used, and result, their success is actually empirical, and the performance relies heavily on hyperparameter tuning and technical details involved. This happens because the agent uses its own prediction construct the learning objective, a.k.a. bootstrapping, and as it generalizes, its pre- dictions over different data interfere with each other, which can make its learning objective unstable in the course of training and potentially lead instability and divergence.
This convergeeeee problem was pointed out decades ago by the pioneering works of Baird 1995) and Tsitsiklis & Van Roy (1997), and it has been empirically investigated for DQN by Van Hassell et al. (2018). We have also observed the divergence of DQN in our experiments, as in Fig. 6 The non-convergence problem often shows up as instability in practice and it places significant obstacles to the application of DQN to complicated tasks. It makes the training with deeper neural networks more difficult, limits the time horizon for planning, and makes the results sometimes unstable and sensitive to hyperparameters. This state of affairs is not satisfactory especially for those scientific applications that require convergence and generality. Although convergent gradient- based methods have also been proposed (Sutton et al., 2009 Bhatnagar et al. 2009 Feng et al. 2019 Ghiassian et al., 2020), they cannot easily be used with deep non-linear neural networks as they either re- quire linearity or involve computationally heavy operations, and they often show worse empirical performance compared with TD methods.
In this work, we show that the Snlov-menttooedd gradient-based methods actually have inherent problems in learning dynamics which hamper efficient learning, and we propose a convergent DQN
RRIKEN Center for Emergent Matter Science (CEMS), Wako, Saitama 351-0198, Japan

---

Published as a conference paper at ICLR 2022
(C-DQN) algorithm by modifying the loss of DQN. Because increase of loss upon updating the target network of DQN is a necessary condition for its divergence, we construct a loss that does not increase upon the update of the target network, and therefore, the proposed algorithm converges in the sense that the loss monotonically decreases. In See. 2 we present the background. In Sec. 3 discuss the inefficiency issues in the previous gradient-based methods and demonstrate using toy problems, In Sec. f we propose C-DQN and show its convergence. In Sec. [ we show the results of C-DQN on the Atari 2600 benchmark (Bellemare al.] 2013) and in Sec. we present the conclusion and future prospect. To our knowledge, the proposed C-DQN algorithm is the first convergent RL method that is sufficiently efficient and scalable obtain successful results on the standard Atari 2600 benchmark using deep neural networks, showing its efficacy in dealing with realistic and complicated problems.
BACKGROUND
Reinforcement learning involves Markov decision process (MDP), where the state 8, of envi- ronment at time step / makes a transition to the next state 81+1 conditioned on the action of the agent az time I, producing a reward r, depending the states. The process can terminate terminal states sT, and the transition of states can be either probabilistic or deterministie. The goal is to find a policy (s)) to determine the actions az+i ~ (8(++)) in order to maximizes the return En Tr+is i.e. the sum of future rewards. In practice, a discounted return Di=0 7rre+s is often used instead, with the discount factor < 1 and 7 = 1, so that the expression is convergent for T - oo and that rewards far into the future can be ignored, giving an effective time horizon r-q. The value function is defined as the expected return for a state st following a policy π, and the Q function is defined as the expected return for state-action pair (st, az):
T--
T-- > T244
Vi (s)) = Ba, ((0,400))
TTets (x) = E (( Σ
(I)
with 0:-; ~ (8(+5) in the evaluation of the expectation. When the Q function is maximized by policy, we say that the policy is optimal and denote the Q function and the policy by Q* and n², respectively. The optimality implies that Q* satisfies the Bellman equation (Sutton & Barto 2018)
Q' (Sc, a4) rr + 7TEss4 max Q" (8(++11)aa))
The policy n² is greedy with respect to Q", i.c. x (s) = arg max,3 Q* as) Q-learning uses this recursive relation to learn Q*. In this work we only consider the deterministic case and drop the notation Ex,,, [+] where appropriate.
When the space of state-action pairs is small and finite, we can write down the values of an arbitrarily initialized Q function for all state-action pairs into table, and iterate over the values using
AQ(s), a:) (r2 + y max Q(5L-1 a') Q( Q(s..
(3)
where a is the learning rate. This is called Q-table learning and it guarantees convergence to Q" If the space of a) is large and Q-table learning is impossible, function approximation is used instead, representing the Q function as Qo with learnable parameter B. The learning rule is
A a Qo az) (r: + 7 max Qo(s+41, - Q0(s).a)))
(4)
which can be interpreted as modifying the value of Qo(s,, az) following the gradient so that Qo(st,a;) approaches the target value It + y maxx' Q0(s(+1, However, this iteration may not converge, because the term max.' Q0(sc+1, a') also 0-dependent and may change together with Qo a.). Specifically,
exponential divergence occurs if y <VoQo(s a.) Va max.' (0(5 a')+,,aa== > ||VoQe(s,, 1 is always satisfied and the value of max,/ Q0(5 a') is not constrained by other means! [ This can be serious issue for realistic tasks, because the adja- cent states 8; and $1+1 often have similar representations and (o .) close to ToQo(st41,
'This can be shown by checking the Bellman error = rt + 7 max. Qa(st+1, a') - Qa at), for which we have A8, ade (+VoQo(s), max,' Qo(s+t1, a') //VoQo )I') up to the first order of A following Eq. 4. As Ad, proportional to 6, with the same sign, it can increase exponentially.
2

---

Published as a conference paper at ICLR 2022
The DQN algorithm uses deep neural network with parameters A as Qo (Mnih et al., 2015), and to stabilize learning, it introduces a target network with parameters 0, and replace the term max, Q0(#++1, a') by max (8(s++1, a'), so that the target value r3 + y max Q8(#++1, a') does not change simultaneously with Qo. The target network 0 is then updated by copying from 0 for ev- ery few thousand iterations of This technique reduces fluctuations in the target value and dramati- cally improves the stability of learning, and with the use of offline sampling and adaptive optimizers, it can learn various tasks such as video games and simulated robotic control (Mnih et al. 2015 Lil- lierap et al. 2015). Nevertheless, the introduction of the target network is not well well-prineipled, and it does not really preclude the possibility of divergence. As result, DQN sometimes requires a significant amount of hyperparameter tuning in order to work well for a new task, and in some cases, the instability in learning can be hard diagnose discount factor y that is very close to In an attempt to solve this problem. Durugkar & Stone (017)) considered only updating 0 in direction that is perpendicular to Va max,' (e((5++1. however, this strategy is not satisfactory in general and can lead to poor performance, as shown in Pohlen et al. (2018).
remove, and usually one cannot use
One way of approaching this problem is to consider the mean squared Bellman error (MSBE), which originally proposed by Baird (1995) and called the residual gradient (RG) algorithm. The Bellman error, or Bellman residual, TD error, is given by (0) == T2 + y max,' Q0(s++1, a') - Qo (8t, az).
Given a dataset S of state-action data, &, a function of 0, and we can minimize the MSBE loss
LMSBE ()= == EE [6(00]]
Σ (E
Qo(s,, ax) - Tt max Q0 Q0(5 (5)
S
a'
and in practice the loss is minimized via gradient descent. If LMSBE becomes zero, we have 6, = 0 and the Bellman equation is satisfied, implying Qo = Q-. Given fixed dataset S, the convergence of the learning process simply follows the convergence of the optimization of the loss. This strategy can be used with neural networks straightforwardly. There have also been many improvements on this strategy including [Sutton et al. (2008) 2009); [Bhatnagar al. (2009); Dai et al. (2018); Feng cet al. (2019); Ghiassian et al. ( Touati et al. (2018), and they are often referred to as gradient- TD methods. Many of them have focused on how to evaluate the expectation term in Eq. (2) and make it converge to the same solution found by TD, or Q-learning. However, most of these methods often do not work well for difficult problems, and few of them have been successfully demonstrated on standard RL. benchmarks, especially the Atari 2600 benchmark. In the following we refer to the strategy of simply minimizing LMSBE as the RG algorithm, or RG learning.
INEFFICIENCY OF MINIMIZING THE MSBE
3.1 ILL-CONDITIONNESS THE LOSS
In the following we show that minimizing LMSBE may not lead to efficient learning by considering the case of deterministic tabular problems, for which all the gradient-TD TD methods mentioned above duce to RG learning. For a tabular problem, the Q function values for different state-action pairs can be regarded as independent variables. Suppose we have a trajectory of experience {(s:, ae r N-1 obtained by following the greedy policy with respect Q, i.e. a; arg max, Q(st, d'), and sN is a terminal state. Taking = 1, the MSBE loss is given by
TN Σ
I LASBE-
(Q(s). - - ((1)+)))4))) (Q(SN-1,aN-)) - -
(6)
Despite the simple quadratic form, the Hessian matrix of LMSBE with variables (Q(s,. ac) a ill-conditioned, and therefore does not allow efficient gradient descent optimization. The condition number x of a Hessian matrix is defined by K. == Daml smallest eigenvalues. We have numerically found that x of the Hessian of LMSRE in Eq. (6) grows as O(N2). To find analytic expression, add an additional term Q(50, )² to LASSES that the
N-1 is
[Amall where Amax and Amin are the largest and
3

---

Published as a conference paper at ICLR 2022
127
103
PCEE Griibe
Q--0 IP C4lbl
127
27
362 037
351
309
TE
1044
38"
12"
HCEC Fooce
Q--11
39 387
387
387
Figure 1: Left: the cliff walking task, where the agent is supposed to go to the lower right corner as quickly as possible and avoid the grey region. The red arrows show the optimal policy. In this example the system has the height of 4 and the width of 10. Right: results of learning the cliff walking task in a tabular setting, using randomly sampled state-action pair data. The upper plots show the result with width 10 and 7 = 0.9, and the lower show the result with width 20 and 0.95. IQ Q²13 the squared distance between the learned Q function and the optimal Q Both Q-table learning and RG use the learning rate of 0.5, averaged over 10 repeated runs.
Hessian matrix becomes
2
-2
NxN
The eigenvectors of this Hessian matrix that have the form of standing waves are given by (sin kx
sin 2km N+I sin Nen T for h E (1, ...,., and the corresponding eigenvalues are given N+1
N+1
bor by 4 - 4 cos N+1.
Therefore, we have T-00s N+T
14005 wir O(N²). See appendix for the details.
With 7 1, if the states form cycle, i.e., 8N-1 makes a transition to 8p, the loss becomes LMSBE = 1 N |Σ (Q: - T2 -Q2+1)2 (QN-1 TN-1 - -Qo)² 2 where Q(s a³) is denoted by Q+- Then, the Hessian matrix is cyclic and the eigenvectors have the form of periodic waves: (sin 2k , sin 4kr N ... sin 2N and (cos 2& 4km
N cos N :...0 cos 2Nk= for k E {1, 2, 2......... J. N with have have O ( By interpreting 1-y the effective time horizon, or the effective size of the problem, we see that λ is quadratic in the size of the problem, which the same its dependence on N in the case of 7 above. In practice, K is usually 10ah ~ 10 and we therefore conclude that the loss is ill-conditioned.
corresponding eigenvalues given by 2(1 + 72) cos 2k5 N.
At the limit of N +
(1-7)2- Using 7
(1+>)²
The Ill-conditionedness has two important implications. First, as gradient descent converges rate of (1x) the required learning time is quadratic in the problem size, i.c. O(N*), for the RG algorithm. contrast, Q-learning only requires (NN steps straightforwardly propagates re- ward information from s;-1 to s; at each iteration step. Therefore, the RG algorithm is significantly less computationally efficient than Q-learning. Secondly, the ill-conditionedness implies that a small LMSBE does not necessarily correspond to small distance between the learned Q and the optimal Q*, which may explain why LMSBE not a useful indicator of performance (Geist et al. 2017).
Cliff walking By way of illustration, we consider tabular task, the cliff walking problem in Sutton Barto (2018), as illustrated in Fig. [ The agent starts the lower left corner in the grid and can move into nearby blocks. If it enters white block, it receives a reward -1; if it enters a grey block which is the cliff, it receives reward 100 and the process terminates;
Although in the deterministic case momentum can be used to accelerate gradient descent to convergence rate of O(YR), ). cannot straigy be applied to stochastic gradient descent since requires a large momentum factor (v==1y² (Polyak 1964 which results unacceptably large noise.
IQ 1 is defined by (a.)) [)( Q" (=) where the taken all state-action pairs.
4

---

Published as a conference paper at ICLR 2022
enters the goal, it terminates with zero reward. To learn this task, initialize Q for all state- action pairs to be zero, and we randomly sample a state-action pair as (5t,a)) and find the next state $1+1 to update Q via Eq. (3), which is the Q-table learning, or to minimize the associated loss (Qo(s,,()) - Tr - ? max, (5 d²))² following the gradient, which is RG learning. As shown in Fig. 1 RG learns significantly more slowly than Q-table learning, and as shown in the right plots, given a fixed value of LMSBE, RG's distance to the optimal solution Q* is also larger than that of Q-table learning, showing that Q-table learning approaches Q" more efficiently. To investigate the dependence on the size of the problem, we consider a width of 10 of the system with y = 0.9, and its doubled size-a width of 20 with = 0.95. The results are presented in the upper and lower plots in Fig. | Notice that the agent learns by random sampling from the state-action space, and doubling the system size reduces the sampling efficiency by factor of 2. As the learning time of Q-learning is linear and RG is quadratic in the deterministic case, their learning time should respectively become 4 times and 8 times for the double-sized system. We have confirmed that the experimental results approximately coincide with this prediction and therefore support our analysis of the scaling property above.
3.2 TENDENCY OF MAINTAINING THE AVERAGE PREDICTION
Besides the issue of the ill-conditionedness, the update rule of RG learning still has a serious problem which can lead to unsatisfactory learning behaviour. To show this, we first denote Q, ((t aq) and Q1+1 = max,' Q($++1, ). and given that they initially satisfy Q: = 7Q1+1. with an observed transition from s, S1+1 with a non-zero reward rr. repeatedly applying the Q-table learning rule in Eq. (3) leads to AQ: = rt and AQ--1 = 0, and thus A (Q+ + Q++1) rt. On the other hand, in the case of RG, minimizing LMSBE using the gradient results in the following learning rule
AQ(s), u1) = a rrx + y max Q( - Q(s1,
A max Q( = -7AQ(se at); a'
o'
(8)
and therefore whenever Qi is modified, Q++1 changes simultaneously, and we have
A (Qt + Q++1) (1-
Due to the condition y R 1, A (Q, Q--1) can be very small, which is different from Q-learning. since the sum of the predicted Q. i.e. Σ. Qt almost does not change. This occurs because there is an additional degree of freedom when one modifies Qe and Qr+1 to satisfy the Bellman equation: Q-learning tries to keep Q(+1 fixed, while RG follows the gradient and keeps Q2 + 7, tQ fixed, except for the case where 8t+1 is terminal and Q++1 is a constant. This has important implications on the learning behaviour of RG as heuristically explained below.
If the average of Q(s, a) is initialized above that of Q* a) and the transitions among the states can form loops, the learning time of RG additionally scales as ( due to Eq. (9) regardless of the finite size of the problem. As shown in Fig. 2 in the cliff walking task with width 10, Q-table learning has roughly the same learning time for different 7, while RG scales roughly as O and
does not learn for 7 = This is because the policy arg max Q(s, a') of RG prefers non-terminal states and goes into loops, since the transitions to terminal states are associated with Q values below what the agent initially expects. Then, Eq. (g) controls the learning dynamics of the sum of all Q values, i.e. ({s,,) Q(s, with the learning target being E(s.)) Q" a), and the learning time scales as ( ). For 7 = 1, A E(..)))) Q(s,a) is always zero and E(..,) Q* (s. a) cannot be learned, which results in failure of learning.
A more commonly encountered failure mode appears when Q is initialized below Q*, in which case the agent only learns to obtain a small amount of reward and faces difficulties in consistently improv-
ing its performance. A typical example is shown in Fig. B where Q is initialized to be zero and the agent learns from its observed state transitions in an online manner following the c-greedy policy B
We see that while Q-table learning can solve the problem easily without the help of non-zero c, RG cannot find the optimal policy with e = 0, and it learns slowly and relies on non-zero e values. This is because when RG finds rewards, Q (8, a) for some states increase while the other Q(s, a) values
e-greedy means that for probability a random action used; otherwise arg max, Q(2, a') used.
5

---

Published as a conference paper at ICLR 2022
12.5
10.0
10.
7.5
10-
5.0-
10F
-05-
107
1.00
10"
102
301
122
10"
10'
4ppate staps
-2.0
10f 10
107 100 10
Figure 2: Results of cliff walking in Fig. D with dif- ferent 7, with system's width of 10, averaged over 10 runs. RG with y converge within reasonable computational budgets.
Figure 3: Left: one-way cliff walking task, where the agent starts the lower left corner, and at each step it is allowed to move to the right obtain reward of 2, or move up and terminate with reward of 1. It terminates upon reaching the goal. Right: performance of the learned greedy policy and min Q(s, a) for online Q-table learning and RG, following the e-greedy policy for different values of e, with y 1 and a learning rate of 0.5, averaged over 100 trials.
does not
decrease and may become negative, and the negative values become smaller than the reward asso- ciated with the termination, i.e. -1, it will choose termination its best action. Therefore, it relies on the exploration strategy to correct its behaviour at those states with low Q(s, a) values and find the optimal policy. Generally, when unexpected positive reward is found in learning, accord- ing to the learning rule in Eq. (B). with an increase r, in Q(s,, 4z), max, Q(s(+1, d') decreases simultaneously by Tt, and the action 8 ie. arg max, 1(5+11, ,a), is perturbed, which may make the agent choose a worse action that leads to ri less reward, and therefore the performance may not improve on the whole. In such cases, the performance of RG crucially relies the explo- ration strategy so that the appropriate action at 8t+1 can be rediscovered. In practice, especially for large-scale problems, efficient exploration is difficult in general and one cannot enhance exploration easily without compromising the performance, and therefore, RG often faces difficulties in learning and performs worse than Q-learning for difficult and realistic problems.
Remark Although the above discussion is based on the tabular case, we believe that the situation not generally better when function approximations are involved. With the above issues in mind, it be understood why most of the currently successful examples of gradient-TD methods have tunable hyperparameters that can reduce the methods to conventional TD learning, which has Q- learning-style update rule. If the methods get closer to conventional TD without divergence, they typically achieve better efficiency and better quality of the learned policy. When the agent simply learns from the gradient of the loss without using techniques like target networks, the performance can be much worse. This probably explains why the performance of the PCL algorithm (Nachum al. 2017) sometimes deteriorates when the value and the policy neural networks are combined into a unified Q network, and it has been reported that the performance of PCL can be improved by using a target network (Gao et al., (2018). Note that although illccondiionnenness may be resolved by a second-order optimizer or the Retrace loss (Munos et al.) 20166] Badia et al.) (020), the issue in Sec. 3.2 may not be resolved, because will likely converge to the same solution as the one found by gradient descent and thus have the same learning behaviour. A rigorous analysis of the issue in
Sec. 3.2 is definitely desired and is left for future work.
CONVERGENT DQN ALGORITHM
4.1 INTERPRETING DQN FITTED VALUE ITERATION
As we find that Q-learning and the related conventional TD methods and DQN have learning dynam- ies that is preferable to RG. we wish to minimally modify DQN so that can maintain its learning dynamics while being convergent. To proceed, we first cast DQN into the form of fitted value itera- tion (FVI) (Ernst et al. 2005 Munos & Szepesvári 2008). With initial parameters d of the target network, the DQN loss for a transition (8t, at Tt, 11+1) and network parameters 0 defined as
(0; 0.) = (Qo(st, ar) - rt - max Qq, (s)),,
(10)

---

Published as a conference paper at ICLR 2022
and DQN learns by iterating over the target network
LDow(0;0;) 13 (DDev(0; 0.)].
0++1 - arg min LooN (0; 0z),
(11)
and 0, is used the parameter of the trained network for sufficiently large In practice, the minimum in Eq. (II) is found approximately by stochastic gradient descent, but for simplicity, here consider the case where the minimum exact. When DQN diverges, the loss is supposed to diverge with iterations, which means we have ming LDON 0.+1)= > ming LDQ 0.) for some
4.2 CONSTRUCTING A NON-INCREASING SERIES
Theorem 1. The minimum of Luev(t; 0.) with target network 0, is upper bounded by LMSBE(0;) (6.).
This relation can be derived immediately from LDov(0,;0.) (0,) and ming LOON 0.) S LDov(0,; 0.), giving ming LDox(0: 0.) S LMs.
When DQN diverges, ming LDQN (0;0.) 0.) diverges with increasing and therefore LMSBE (0c) must also diverge. Therefore at each iteration, while the minimizer 0.+1 minimizes the i-th DQN loss LpoN( ( 0.). it can increase the upper bound the (i+ (++h) DQN loss, ie. LMsnE 19)+ We want both T-DON and LASBE decrease in learning and define the convergent DQN (C-DQN) loss
LCDON 0.) == E max { (DDNN(e: 0.), (NSSE(())]
(12)
where (MSHE(() == (Qo(8s, a+) ) rt - maxa" (0(+11,,a')) and LMSBE = E [[MsHE]- Theorem 2. The C-DQN loss satisfies ming LCDØN(0: 0.41) S ming LCDeN(0; 0.), given 0.+1 = arg ming Lcnow(0;0.)) 0.).
We have
min LCDON(0; 0c+1) S LcDeN(0++1:04+..) = (0++1)) 6
(13)
TmMsn (0++1) S E max { ( (0:+0:0000))) 0.), (0sne(0++1)) TcDgN((0+113 S min LCD@N 0,).).
(14)
Therefore, obtain the desired non-increasing condition ming L0 0.41) ming LO 0.). which means that the iteration 0 + arg ming LCDON((: 0) is convergent, in the sense that the loss is bounded from below and non-increasing.
s
C-DQN as defined above is convergent for given fixed dataset. Although the analysis starts from the assumption that 0. exactly minimizes the loss, in fact, not necessary. In practice. at the moment when the target network Ô updated by 0, the loss immediately becomes equal to LMSRE (0) which is bounded from above by the loss (C) 0) before the target network update. Therefore, as long the loss is consistently optimized during the optimization process, the non-increasing property of the loss holds throughout training. We find that it suffices to simply replace the loss used in DQN by Eq. 12 to implement C-DQN. As we empirically find that LMSBE in RG is always much smaller than LDON. we expect C-DQN to put more emphasis on the DQN loss and to have learning behaviour similar to DQN. C-DQN can also be augmented by various extensions of DQN, such as double Q-leariin, distributional DQN and soft Q-learning (Van Hasselt et al.) 2016 Bellemare al. 2017 Haarnoja al. 2017), by modifying the losses EDON and EMSRE accordingly. The mean squared loss can also be replaced by the Huber loss (smooth ě1 loss) as commonly used in DQN implementations. More discussions on the properties of C-DQN are provided in the appendix.
EXPERIMENTS
5.1
COMPARISON OF C-DQN, DQN AND RG
We focus on the Atari 2600 benchmark as in Mnih et al. (013). and use the ducling network ar- chitecture and prioritized sampling, with double Q-learning where applicable (Wang et al. 2016
7

---

Published as a conference paper at ICLR 2022
20
10a
2000
C-OON
10a
1500
C-DQN DQN
100
1000
10*
C:DON
C-DON
10a
10r
RG
3.0
10"
30'
10*
frames
frames
frames
Frames
Figure 4: Training performance and training loss on games Pong (left) and Space Invaders (right).
reward
750
600
1,000
800
DON randimm
DON EURO
CDDON random
WP
0.125
0.100
500
600
g.007 g
250
C-DON
400-
0.050
DQN
D2N randem
200
0.925
2
3.4
X101
frames
=100
Figure 5: Training perfor- mance and loss on Space In- vaders when half of the data are randomly discarded.
Figure 6: Training performance and training loss on Space In- vaders when the memory adopts random replacement strategy (left) and when the memory is smaller and adopts different strate- gies (middle and right).
Schaul et al. 2015 Van Hasselt et al.
2016). We refer to the combination of the original DQN and these techniques as DQN, and similarly for C-DQN and RG. Details of experimental settings are given in the appendix and our codes are available in the supplementary material.
As C-DQN, DQN and RG only differ in their loss functions, we follow the hyperparameter settings in Hessel et al. (2018) for all the three algorithms and compare them on two well-known games, Pong and Space Invaders, and the learning curves for performance and loss are shown in Fig. We see that both C-DQN and DQN can learn the tasks, while RG almost does not learn, despite that RG has much smaller loss. This coincides with our prediction in Sec. 3 which explains why there are very few examples of successful applications of RG to realistic problems. The results show that C-DQN as a convergent method indeed performs well in practice and has performance comparable to DQN for standard tasks. Results for few other games are given in the appendix.
5.2 LEARNING FROM INCOMPLETE TRAJECTORIES OF EXPERIENCE
To give an example in which DQN is prone to diverge, we consider learning from incomplete tra- jectories of experience, i.e. given a transition (st, dt 81+1) in the dataset, the subsequent transition ($1+1, a1+1, St42) may be absent from the dataset. This makes DQN prone to diverge because while DQN learns Qs(s; a,) based on max.' (p( a'), there is possibility that max,' Q0(8 aa)) has to be inferred and cannot be directly learned from any data. To create such setting, we ran- domly discard half of the transition data collected by the agent and keep the other experimental settings unchanged, except that the mean squared error is used instead of the Huber loss to allow for divergence in gradient. We find that whether or not DQN diverges or not is task-dependent in general, with larger probability to diverge for more difficult tasks, and the result for Space Invaders is shown in Fig. 5) We see that while DQN diverges, C-DQN learns stably and the speed of its learn- ing only slightly reduced. This confirms that C-DQN convergent regardless of the structure of the learned data, and implies that C-DQN may be potentially more suitable for offline learning and learning from observation when compared with DQN.
A similar situation arises when one does not use the first-in-fisst-out (FIFO) strategy to replace old data in the replay memory (i.e. the dataset) with new data when the dataset is full, but replaces old data randomly with new data. In Fig. 6 we show that conventional DQN can actually diverge in this simple setting. In the existing DQN literature, this replacement strategy is often ignored, while here it can been seen to be an important detail that affects the results, and in practice, FIFO almost always used. However, FIFO makes the memory data less diverse and less informative, and it increases the possibility of the oscillation of the co-evolvement of the policy and the replay memory, and as a result, a large size of the replay memory is often necessary for learning. In Fig. 6 show that when the size of the replay memory is reduced by factor of 10, C-DQN from utilizing the random replacement strategy while DQN cannot, and C-DQN can reach a higher performance. Note that DQN does not diverge in this case, probably because the replay memory is
benefit
8

---

Published as a conference paper at ICLR 2022
Skiing fy 0.900)
Tennis (yys
PrivateEye (192019905)
Venture Ey = sesse)
C-DON
DON
20
15000
10000
750-
5000
20
Figure 7: Training performance on several difficult games in Atari 2600, with learning rate 4x 10 Each line represents a single run and the shaded regions show the standard deviation. The discount factors are shown in the titles and all DQN agents have significant instabilities or divergence in loss.
less off off-policy when it small, which alleviates divergence. The result opens up a new possibility of RL of only storing and learning important data to improve efficiency, which cannot be realized stably with DQN but is possible with C-DQN.
5.3 DIFFICULT GAMES IN ATARI 2600
In this section we consider difficult games in Atari 2600. While DQN often becomes unstable when the discount factor gets increasingly close to 1, in principle, C-DQN can work with any y. However, we find that a large y does not always result in better performance in practice, because large requires the agent to learn to predict rewards that are far in the future, which are often irrelevant for learning the task. We also notice that when y larger than 0.9999, the order of magnitude of (1 7) gets close to the intrinsic noise caused by the finite learning rate and learning can stagnate. Therefore, we require y to satisfy 0.99 S 7 S 0.9998, and use a simple heuristic algorithm to evaluate how frequent reward signals appear so to determine y for each task, which is discussed in detail in the appendix. We also take this opportunity to evaluate the mean ju of Q and the scale of the reward signal using sampled trajectories, and make our agent learn the normalized value Q- instead of the original Q. We do not clip the reward and follow Pohlen et al. (2018) to make the neural network learn a transformed function which squashes the Q function approximately by the square root.
With C-DQN and large values, several difficult tasks which previously could not be solved by simple DQN variants can now be solved, as shown in Fig. 7 We find that especially for Skiing, Private Eye and Venture, the agent significantly benefits from large and achieves a higher best performance in training, even though Private Eye and Venture are partially observable tasks and not fully learnable, which leads to unstable training performance. Evaluation of the test performance and details of the settings are given in the appendix. Notably, we find that C-DQN achieves the tfateoof-hhe-art test performance on Skiing despite the simplicity of the algorithm.
6 CONCLUSION AND FUTURE PERSPECTIVES
We have discussed the inefficiency issues regarding RG and gradient-'DD methods, and addressed the long-standing problem of convergence in Q-learning by proposing a convergent DQN algorithm, and we have demonstrated the effectiveness of C-DQN on the Atari 2600 benchmark. With the stability of C-DQN, we can now consider the possibility of tuning Y freely without sacrificing stability, and consider the possibility of learning only important state transitions to improve efficiency. C-DQN can be applied to difficult tasks for which DQN suffers from instability. It may also be combined with other strategies that involve target networks and potentially improve their stability.
There are many outstanding issues concerning C-DQN. The loss used in C-DQN is non-smooth, and it is not clear how this affects the optimization and the learning dynamics. In our experiments this does not appear to be a problem, but deserves further investigation. When the transitions are stochastic, the loss LMSBE used in C-DQN does not converge exactly to the solution of the Bellman equation, and therefore it would be desirable if C-DQN can be improved so that stochastic transitions can be learned without bias. It would be interesting to investigate how it interplays with DQN extensions such as distributional DQN and soft Q-learning, and it is not clear whether the target network in C-DQN can be updated smoothly in Lillierap et al. (0155)

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
All our experimental results can be reproduced exactly by our codes provided in the supplementary material, where the scripts and commands are organised according to the section numbers. We also present and discuss our implementation details in the appendix so that one can reproduce our results without referring to the codes.
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence in deep Q- learning. arXiv preprint arXiv:1903.08894 2019.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning. 71(1):89-129 2008.
Adrià Puigdomênech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International Conference on Machine Learning, pp. 507-517. PMLR, 2020.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. In International Conference on Machine Learning, pp. 449-458, PMLR, 2017.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung. Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1xXiv:1912006688 2019.
Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid Maei, and Csaba Szepesvári. Convergent temporal- -ifforeldiiferrecce learning with arbitrary smooth function approxi- mation. Advances in neural information processing systems, 22: 1204-1212 2009.
Aditya Bhatt, Max Argus, Artemij Amiranashvili, and Thomas Brox Crossnorm: Normalization for off- off-policy TD reinforcement learning. arXiv preprint arXiv:1902.05605. 2019.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Con- ference on Machine Learning, pp. 1125-1134. PMLR, 2018.
Ishan Durugkar and Peter Stone. TD learning with constrained gradients. Proceedings of the Deep Reinforcement Learning Symposium, NIPS 20/7, Long Beach, CA, USA, December 2017.
URL
aii
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847):580-556 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the Bellman equation. arXiv preprint 1905: 2019.
Thomas Fösel, Petru Tighineanu, Talitha Weiss, and Florian Marquardt. Reinforcement learning with neural networks for quantum feedback. Physical Review X, 833):031084, 2018
Scott Fujimoto, David Meger, and Doina Precup. An equivalence between loss functions and non- uniform sampling in experience replay. arXiv preprint 2000::000000004 2020.
10

---

Published as a conference paper at ICLR 2022
Yang Gao, Huazhe Xu, Ji Lin, Fisher Yu, Sergey Levine, and Trevor Darrell. Reinforcement learning 2018.
from imperfect demonstrations. arXiv preprint
Matthieu Geist, Bilal Piot, and Olivier Pietquin. Is the Bellman residual a bad proxy? In Advances 2017.
in Neural Information Processing Systems, pp.
Sina Ghiassian, Andrew Patterson, Shivam Garg, Dhawal Gupta, Adam White, and Martha White. Gradient eemporal-differene learning with regularized corrections. International Conference on Machine Learning, pp. 3524-3534. PMLR, 2020.
Tuomas Haarooja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. arXiv preprini arXiv:/702.088: 1702.00065... 2017.
Alexander Hans and Steffen Udluft. Efficient uncertainty propagation for reinforcement learning with limited data. In International Conference on Artificial Neural Networks, pp. 70-79. Springer, 2009.
Alexander Hans and Steffen Udluft. Ensemble usage for more reliable policy identification in rein- forcement learning. In ESANN, 2011.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018,
Tobias Johannink, Shikhar Bahl, Ashvin Nair, Jianlan Luo, Avinash Kumar, Matthias Loskyll, Juan Aparicio Ojea, Eugen Solowjow, and Sergey Levine. Residual reinforcement learning for robot control. In 2019 International Conference on Robotics and Automation (ICRA), pp. 6023- 6029, 2019. doi: 10.1
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 Twenty Eighth Interna- tional Joint Conference on Artificial Intelligence, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1eXi::1412.69880 6980, 2014.
Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz, and Deirdre Quillen. Learning hand- eye coordination for robotic grasping with deep learning and large-scale data collection. The International Journal of Robotics Research, 37(4-5):411-466 2018.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint 1509:::500002000 2015.
Marlos C Machado, Marc 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-5661 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature. 5 518(7540)5529-553 -332 2015.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Ma- chine Learning Research, 9(27):815855) 857, 2008 URL http: jmlr wrtpp//e/rgpppppe///.aa
munos08a html
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off- policy reinforcement learning. arXiv preprint
2016.
11

---

Published as a conference paper at ICLR 2022
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2775-2785, 2017.
Shota Ohnishi, Eiji Uchibe, Yotaro Yamaguchi, Kosuke Nakanishi, Yuji Yasui, and Shin Ishii. Con- strained deep Q-learning gradually approaching ordinary Q-learning. Frontiers in neurorobotics, 13:103, 2019.
Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Budden, Gabriel Barth-Maron, Hado Van Hasselt, John Quan, Mel Večerík, al. Observe and look further: Achieving consistent performance on atari. arXiv preprint arXiv: 1805. / 1593, 2018.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Martin Riedmiller. Neural fitted q iteration-fisst experiences with data efficient neural reinforce- ment learning method. In European Conference on Machine Learning, pp. 317-328. Springer, 2005.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05995 2015.
Ralf Schoknecht and Artur Merke. TD (0) converges provably faster than the residual gradient algorithm. In Proceedings of the 20th International Conference on Machine Learning (ICMI.- 03). pp. 680-687, 2003.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent O(N) temporal-difference algorithm for off-policy learning with linear function approximation. In NIPS, 2008.
Richard S Sutton, Hamid Reza Maei, Doina Precup. Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 993-1000, 2009.
learning
Ahmed Touati, Pierre-Luu Bacon, Doina Precup, and Pascal Vincent. Convergent tree backup and re- trace with function approximation. In International Conference on Machine Learning, pp. 4955- 4964. PMLR, 2018.
Volker Tresp. The wet game of chicken. Siemens AG, IC Technical Report, 1994.
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-differencc learning with function approximation. IEEE transactions on automatic control, 42(5):674-690, 1997.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
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.02644 2018.
Zhikang T Wang, Yuto Ashida, and Masahito Ueda. Deep reinforcement learning control of quantum cartpoles. Physical Review Letters, 125(10): 100401, 2020.
Ziyu Wang, Tom Schaul, Mateo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003. PMLR, 2016.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
Shangtong Zhang, Wendelin Boehmer, and Shimon Whiteson. Deep residual reinforcement learn- ing. In Proceedings of the 19th International Conference Autonomous Agents and gultiAgent Systems, AAMAS '20, pp. 1611-1619, Richland, SC, 2020. International Foundation for Au- tonomous Agents and Multiagent Systems. ISBN 9781450375184
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with a target network. arXiv preprint arXiv:2101.08866 2021.
12

---

Published as a conference paper at ICLR 2022
A CONVERGENCE OF C-DQN IN STOCHASTIC SETTINGS
When the transition of states stochastic, it is well-known that the minimum of LUSBE does not exactly correspond to the solution of the Bellman equation, because we have
LMSBE(0) Beeti [ as) - 7 -mmax Qo(s)+,,a))
= (Rolse 0e) - -r= - -BBeet max Q6 (0(8))1, + 72 Varau4a (max a'
(15)
where Var(-) represents the variance, and it can be seen that only the first term on the last line corre- sponds the solution of the Bellman equation. Because C-DQN involves LMSBE, if the underlying task is stochastic, C-DQN may not converge to the optimal solution due to the bias in LMSBE- In fact, both the minimum of MSBBE and the solution of the Bellman equation are stationary points for unique and different. If parameters 0 and 0, satisfy 0 0, arg min LDON(:: ; 0t), i.e., if they are the converging point of DQN, then we consider an infinitesimal change 80 of 0 following the gradient of LMSBE in an attempt to reduce LMSBE. Because we have LMSBE LoOv(0; 0) = LDON(0; 0.), as 0 - 50 moves away from the minimum Logv( (0; 0.), we have
C-DQN. To show this, we first assume that the minimum of LOON and that of LuSBE
Logx(0 + 50; 0.) LogN(0; 0.) = LMSRE(()) LM (0 + +0),
(16)
and therefore for 0 + 80, I.DON is larger than LUSBE, and C-DQN will choose to optimize T.DgN instead of TAMBEE and the parameter will return to the minimum 0, which is the converging point of DQN. On the other hand, given 0 = 0, = arg min LMSBE(-), if we change by an infinitesimal amount 60 in an attempt to reduce Lo 0.), we similarly have
LMSBE(O (0 + 80) LMSAE (0) = LnON(0; (1; 0.) Lnov(0 50; 0.),
(17)
and therefore, for the same reason C-DQN will choose to optimize LMSBE and the parameter will return to 0. Therefore, C-DQN can converge to both the converging points of DQN and RG. More generally, C-DQN may converge somewhere between the converging points of DQN and RG. tries to minimize both the loss functions simultaneously. and it stops if this goal cannot be achieved, i.e. if a decrease of one loss increases the other. Interestingly, this does not seem to be severe problem as demonstrated by the successful application of C-DQN to the Atari 2600 benchmark (see Sec. (.. because the tasks include large amount of noise-like behaviour and subtitles such as partially observable states.
A.1 A CASE STUDY: THE WET-CHICKEN BENCHMARK
To investigate the behaviour of C-DQN more closely, we consider stochastic toy prob- lem, which is known as the wer-chicken benchmark (Tresp) 1994; Hans & Udluft 2009 2011] In the problem, canoeist paddles 1 = 20, and the goal of the canoeist is to
river starting position x = 0, and
there is a waterfall at position x get as close as possible the waterfall without reaching it. The canoeist can choose to paddle back, hold the position, or drift forward, which corresponds to a change of -1, O, or +1 in his/her position x, and there is random turbulence = Uniform(-2.53 +2.5), uniformly distributed random number, that also contributes to the change in x and stochastically perturbs æ at each step. The reward is equal to the position xr, and x is reset back to 0 if he/she reaches the waterfall at = 20. The task does not involve the end of an episode, and the per- formance is evaluated as the average reward per step. This task is known to be highly stochastic, because the effect of the stochastic perturbation is often stronger than the effect of the action of the agent, and the stochasticity can lead to states that have dramatically different Q function values.
To learn this task, we generate a dataset of 20000 transitions using random actions, and we train neural network on this dataset using the DQN, the C-DQN and the RG algorithms to learn the Q values. The results are shown in Fig. g In the left panel of Fig. g it can be seen that while RG significantly underperforms DQN, the performance of C-DQN lies between DQN and RG and is only slightly worse than DON. This shows that when the task is highly stochastic, although C-DQN
13

---

Published as a conference paper at ICLR 2022
15
QeDgge Quags
14
Qeaig Quci
13
150
Qoase
reward
12
distance
125
Oeage Qoogl - QeDgy QuG
-Qugg Qual
11
100
10
50
C-DQN
DON (NFQ)
25
RG
0
500
1000
1500
2000
500
1000
1500
2000
epoch
epoch
Figure 8: Performance on the wet-chicken benchmark training on dataset generated by the random policy (left) and the distances among the learned functions (right). The experiment is repeated for 10 times, and the standard error of the performance and the standard deviation of the distances are shown as the shaded regions.
may not reach the optimal solution as DQN can do, C-DQN still behaves robustly and produces reasonably satisfactory results, while RG fails dramatically.
To obtain further details of the learned Q functions, we estimate the distance between the functions. The distance QQ1 Q21 between two Q functions Q1 and Q2 is estimated as
V ((ra)) (Q((z, a) Q2(1, a))2 where the summation on the position ær is taken over the dis- crete set (0, 1, 2, 19... In the right panel of Fig. g show the estimated distances among the learned Q functions of DQN, C-DQN and RG. We see that the distance between QDON and QCDeN increases rapidly in the beginning and then slowly decreases, implying that DQN learns quickly the beginning, and C-DQN catches up later and reduces its distance to DQN. Notably, we find that the value [QcDeV QDovl (QCDOV- QRaI DQooN QRai always converges zero, indicating that the solution found by C-DQN, i.c. QCDON. lies exactly on the line from QDON to QRG. which is consistent with our argument that C-DQN converges somewhere between the converging points of DQN and RG.
Concerning the experimental details, the neural network includes hidden layers, each which has 128 hidden units and uses the ReLU as the activation function, and the network is optimized using the Adam optimizer (Kingma & Ba, 2014) with default hyperparameters. We use the batch size of 200, and the target network is updated after each epoch, which makes the DQN algorithm essentially the same as the neural fitted Q (NFQ) iteration algorithm (Riedmiller) 2005). The training includes 2000 epochs, and the learning rate is reduced by factor of 10 and 100 at the 1000th and the 1500th epochs. The discount factor 7 is set to be 0.97. The position x and the reward are normalized by 20 before training, and the evaluation of the performance is done every 5 epochs, using 300 time steps and repeated for 200 trials. The entire experiment is repeated for 10 times including the data generation process.
B ADDITIONAL EXPERIMENTAL RESULTS
In this section we present additional experimental results. In Sec. B.I we present the results of applying C-DQN to the problem of measurement feedback cooling of quantum quartic oscillators in Wang et al. 2020), where we show that the final performances are more consistent regarding different random seeds and have smaller variance compared with the results of DQN, Concerning the Atari 2600 benchmark, in Sec. B.2 results for several other games are presented. In Sec. B.3 show that C-DQN allows for more flexible update periods of the target network. In Sec. B.4 we
report the test performance of C-DQN on the difficult Atari 2600 games shown in Sec. 5.3 and in Sec. B.5 we discuss the results of C-DQN the game Skiing.
14

---

Published as a conference paper at ICLR 2022
B.1 RESULTS ON MEASUREMENT FEEDBACK COOLING OF QUANTUM QUARTIC OSCILLATOR
To show the stability of C-DQN compared with DQN for problems with practical significance, we reproduce the results in Wang et al. (2020), which trains RI controller to do measurement feed- back cooling of a one-dimensional quantum quartic oscillator the problem setting performances for C-DQN and DQN are shown Fig. 9 where each curve represents a different experiment with different random seed. As shown in Fig. 9 different C-DQN experiments have similar learning curves and final performances; however, in sharp contrast, those of the DQN exper- iment have apparently different fluctuating learning curves and the performances some of the repetitions cannot reach a final performance that is comparable to the best-perforning ones. The results show that compared with DQN, the outcome of the training procedure of C-DQN is highly stable and reproducible, which can greatly benefit practical applications.
numerical simulation. Details of given in Wang al. (2020) and in our supplementary codes. The training
unstable, and
Convergent DQN
DQN
12.5
12.5
10.0
10.0
eneggy
7.5
enegy
7.5
5.0
2.5
0.0
0
200000
400000
200000 400000 600000 800000 simulation time
simulation time
Figure 9: Training performance C-DQN and DQN on the task of measurement feedback cooling of quartic oscillators. The vertical axis shows the energy of the cooled quartic oscillator, and smaller energy represents better performance. The horizontal axis shows the simulated time of the oscillator system that is used to train the agent. Each curve represents a separate trial of the experiment.
B.2 EXPERIMENTAL RESULTS ON OTHER GAMES
In addition to the results in Sec. 5.1 we present results on other Atari 2600 games comparing C-DQN and DQN, which are shown Fig. I0
In general, we find that the loss value of C-DQN is almost always smaller than DQN, and for relatively simple tasks, C-DQN has performance comparable to DQN, but for more difficult tasks, they show different performances with relatively large variance. Specifically, we find that C-DQN has better performance for tasks that require more precise learning and control such as Atlantis, and for tasks that are unstable and irregular such as Video Pinball. However, for tasks that are highly stochastic and partially observable such Fishing Derby and Time Pilor, C-DQN may perform less well compared with DQN, probably because the term LMSBE in LCDOV does not properly account for stochastic transitions.
B.3 MORE FLEXIBLE UPDATE PERIODS FOR THE TARGET NETWORK
As C-DQN has a better convergence property, allows for shorter update periods of the target network. Specifically, convergence of C-DQN is obtained long the loss decreases during the optimization process after an update of the target network. One period of the update of the target network consists of N₂ iterations of gradient descent on minimizing T-CDov(0; 0.) or Logw( (0; 0,) with the target network 0,, and then using 0 as the next target network 0,+1. where Nç represents the update period of the target network. In previous works on DQN, N₂ is set to 2000 or 2500 (Hessel et al. 2018 Mnih et al.) 2015), and DQN may experience instability for too small Na- However, we empirically find that for many tasks in Atari 2600, N₂ can be reduced to 200 or even 20 without instability for C-DON. Therefore, find that C-DON requires less fine tuning the
15

---

Published as a conference paper at ICLR 2022
Atlantis
Breakout
800000
10a
revard
C-DON
roward
DON
1o.
200
10a
0.0
6.5
1.0
1.5
2.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
fruemss
x10*
frames
>30*
frattes
X10F
Fames
>10
Fishing Derby
Freeway
25
10"
10t
roward
-25
rowara
20
10a
10"
-75
10r
0.0
2.0
0.5
1.0
2.0
0.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
>10*
%10*
>10*
x10
Time Pilot
Video Pinball
50,000
10000
400000
10a
remard
10a
300000
200000
4000
100000
2000
0.5
3.0
0.5
1.0
0.0
0.5
1.0
1.5
0.5
1.0
1.5
2.0
frames
x30
Figure 10: Training performance and training loss of C-DQN and DQN on several other Atari 2600 games, using the same experimental settings as in Sec. 5.1
hyperparameter N₂ compared with DQN. The experimental results on Spuce Invaders and Hero are shown in Fig. [ using the experimental settings in Sec. 5.1. We see that C-DQN has generally higher performance compared to DQN when Ng becomes small, and the performance of DQN is sometimes unstable and is sensitive to the value of Ng.
1250
25000
C-DON 3011
10a
20000
DON
750
C DON Nt
10*
560
10000
250
DON 10 200
20
5000
10a
0.0
02
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
0.0
0.2
0.6
0.5
0.8
1.0
0.2
0.4
0.6
0.8
1.0
frames
X00
frames
x1.0
x100
<107
Figure 11: Training performance using different update periods of the target network on games Space Invaders (left) and Hero (right). In the game Hero, there appears to be local optimum with reward 13000 where the learning can fail to make progress, which is also seen in Fig. 15
B.4 TEST PERFORMANCE ON DIFFICULT ATARI GAMES
In this section we report the test performance of the agents in Sec. 5.3 and compare with existing works. As the learned policy of the agents has large fluctuations in performance due to noise, local optima, and insufficient learning when the task is difficult, instead of using the agent the end of training, we use the best-performing agent during training to evaluate the test performance. Specifically, we save checkpoint of the parameter 0 of the agent every 10 steps, and we choose the three best-performing agents by comparing their training performances, computed as the average of the 40 nearby episodes around each of the checkpoints. After the training, we carry out a separate validation process using 400 episodes to find the perforrennnnnn then, we evaluate the test performance the validated best agent by another 400 episodes, using a different random seed. The policy during evaluation is the e-greedy policy with 0.01,, with no-
among the three agents, and
16

---

Published as a conference paper at ICLR 2022
Table I: Test performance on difficult Atari 2600 games, corresponding the results Sec. 5.3 in the main text, evaluated using no-op starts and without sticky actions (Machado et al. 2018).
The DQN results are produced using the same experimental settings as the C-DQN experiments except for the loss function. Human results and results for Agent57 are due to BBadia et al. (2020).
and results for Rainbow DQN are due to Hessel al. (2018). The human results only represent
the performance of an average person, not human expert, and the human results correspond to reasonably adequate performance instead of the highest possible performance human.
Task
C-DQN
DQN
Human
Rainbow DQN
Agent57 (SOTA)
Skiing
-3697 +: 157
-29751 + 224
-4337
-12958
-4203 +: 608
Tennis
10.9 6.3
-2.6 = 1.4
-8.3
0.0
23.8 + 0.1
Private Eye
14730 = 37
7948 + 749
69571
4234
79716 + 29545
Venture
893 51
386 85
1188
5.5
2624 + 442
Skiing (+ 0.9996)
C-DON
010.79
5000
reward
100000
15000
25000
33000
frames
x10*
Figure 13: Training performance of C-DQN on Skiing with learning rate 2 10 following the experimental procedure in Sec. 5.3. The standard deviation among the three runs are shown as the shaded region.
Figure 12: A screenshot of the game Skiing in Atari 2600.
op starts (Mnih et al. 2015). The average of the test performances of the runs our experiments are shown Table 1 together with the standard error, compared with existing works and the human performance.
As we have basically followed the conventional way of training DQN Atari 2600 in Mnih et al. (2013) and Hessel et al. (2018), our C-DQN and the Rainbow DQN in Hessel et al. (2018) allow for fair comparison because they use the same amount of computational budget and similar neural network architecture 8 In Table [ we see that in these four difficult Atari 2600 games Rainbow DQN fails make progress in learning. and C-DQN can achieve performances higher than Rainbow DQN and show non-trivial learning behaviour. The results of Agent57 is for reference only, which represents the currently known best performance on Atari 2600 in general and does allow for a fair comparison with C-DQN, as it involves considerably more computation, more sophisticated methods and larger neural networks. We find that our result on the game Skiing exceptional, which is discussed in the next section.
B.5 THE ATARI GAME Skiing
In Table D one exceptional result is that C-DQN achieves performance higher than Agent57 on the game Skiing, actually using an amount of computation that is less than 0.1% that Agent57. We find that this performance is higher than any other known result so far and thus achieves the state-of-the-ar (SOTA) for this specific game. To elucidate the underlying reason, we describe this game first
oo starts mean that the start of each episode the no-operation action is executed randomly for 30 frames.
"In fact, fair comparison with Rainbow DQN can be made except for the case of Skingg because reward clipping adopted by Rainbow DQN does not permit the learning of Skiing. Nevertheless, this does not affect conclusion.
17

---

Published as a conference paper at ICLR 2022
A screenshot of the game Skiing is shown in Fig. 12 This game is similar to racing game. The player is required to go downhill and reach the goal as fast as possible, and the time elapsed before reaching the goal is the minus reward. At each time step, the player receives small minus reward which represents the accumulated time, until the goal is reached and the game ends. In addition, the player is required to pass through the gates along his/her way, which are represented by the two small flags shown in Fig. 12 and whenever the player fails to pass a gate, a 5-second penalty is added the elapsed time when the player reaches the final goal. The number of gates that have not been passed are shown at the top of the game screen. Using the standard setting in MMiih et al.) (2015), the number of state transitions for an episode of this game is 1300 for the random policy, 4500 when the player slows down significantly, and ~ 500 when the policy is near-optimal.
Since the penalty for not passing a gate is given only at the end of the game, the agent needs to relate the penalty at the end of the game to the events that happen early in the game, and therefore the discount factor y should be at least around
500 to make learning effective. However, the learning may still stagnate if 7 is not larger, because when is small, the agent prefers taking longer time before reaching the goal, so that the penalty at the end is delayed and the Q function for the states in the early game is increased, which will increase the episode length and make larger y necessary. Therefore, we have chosen to tune our hyperparameter setting so that y x 5000 is obtained on this game (see Sec. [E.3), and we find that our C-DQN agent successfully learns with the and produces a new record on this game 7 The large fluctuations in its training performance shown in Sec. 5.3 are mostly due to the noise coming from the finite learning rate. which can be confirmed by repeating the experiments with a smaller learning rate, shown in Fig. 13 However, in this case the learning easily gets trapped in local optima and the final test performance is worse. Note that in fact, we cannot fairly compare our result with Agent57. because we have tuned our hyperparameters so that the obtained y is in favour of this game, while Agent57 uses a more general bandit algorithm to adaptively determine 7.
C RELATED WORKS
In this section, we present some related works for further references. The slow convergence of RG compared with TD methods has been shown in Schoonnccht & Merke (2003). The O(N2) scaling property can also be derived by considering specific examples of Markov chains, such as the "Hall" problem as pointed out in Baird (1995). The convergence property of RG-like algorithms has been analysed in Antos et al. (2008). assuming that the underlying Markov process is 3-mixing, i.e. converges to stable distribution exponentially fast. However, this assumption is often impractical, which may have underlain the discrepancy between the theoretical results of RG and the experi- mental effectiveness. There is improved version of RG proposed in Zhang et al. 22020). and RG has been applied to robotics in Johannink et al. (019)). Concerning DQN, there have been many attempts stabilize the learning, remove the target network, and use larger >. Pohlen et al. 2018)) introduces a temporal consistency loss to reduce the difference between Qa and Q3 on 814-1. and the authors showed that the resulting algorithm can learn with y 0.999. variant of it is proposed in Ohnishi et al. (2019). Kim et al. (2019) and Bhatt et al. (2019) propose extensions for DQN and show that the resulting DON variants can sometimes operate without a target network when properly tuned. AAchaam et al. (2019) gives an analysis of the divergence and proposes to use a method similar to natural gradient descent to stabilize Q-learning: however, it computationally heavy as it uses second-order information, and therefore it cannot be used efficiently with large neu- ral networks. Recently, the strategy of using target networks in DQN has been shown to be useful for TD learning as well by Zhang et al. (2021). Some other works have been discussed in the main text and we do not repeat them here.
D CALCULATION DETAILS OF THE CONDITION NUMBER
In this section we provide the calculation details of Sec. 3.1 Given the loss function
2
L
Σ (Q T Q++1)2 + (QN-1 - -
(18)
N
Thee single highest performance we observed was around 3350, and the optimal performance this game is reported to he -3272 in Badia et al. (200))
18

---

Published as a conference paper at ICLR 2022
where Q(si, az) is denoted by Qu. add an additional term (Qo)² to it, and the loss function becomes
N-2
L
N
Q9 +
(Q: - -0 100
N
(19)
100 +
Σ
( -2r,Q + 2r, Q1+1 2Q,Q++1 + + Qi+1)
N
1=
+ (QN 1
2r
To calculate the condition number the Hessian matrix, we ignore the prefactor ate the second-order derivatives. From Eq. [9 it is straightforward obtain
N and only evalu-
8
= 4,
LE (0.1,...NN
iQ
(20)
0L
-2,
LE (0, I...N - 2}
aQ,0Q.+1
and therefore the Hessian matrix is
-2
2
(21)
-2
NxN
2hx The eigenvectors of this matrix be explicitly obtained due the special structure of the matrix,
which are given by (sin N+I. N+1 sin NET y" for E (1,2...NN) and the corresponding N+1 eigenvalues are given by 4 - 4 cos N+I To show this, we first simplify the Hessian matrix by
k
removing its constant diagonal which only contributes to constant 4 in the eigenvalues, and then we multiply the eigenvectors by the eigenvalues
2kT sin
NKT T (-4 cOs
AT
sin
sin
(22)
N +1
N +
N N+1
N ++1
0 KT
2KT
kn
3km
(N 1)kT
(N + 1)kT
T
-2 (sin
sin
N + ), (sin
+ sin
(sin
+ + sin
N +
+
N
+ 1
(23)
due to sin nks
Aet N+T cos N+T
sin (m-1)km 1)4 N+1
+ sin (m+1)ks
As we also have sin 0kr
N+1
N+T
sin (N+1)kT O, the product of the vector and the eigenvalue is exactly equal to the product N+1 of the vector and the Hessian matrix. As the vectors (sin N sin N sin N+1) linearly independent for [1,2,...NN) they are all the eigenvectors of the Hessian matrix, and therefore
2hr
4-4 Ns
the eigenvalues are cos N+I' The condition number is then k 4-4cus x-1
Using the Taylor
series expansion, the denominator in the expression of 4cos N
2x (N+1)
+ (T)) and
therefore for large N, K. R 4-1cos N
4-4cos O(N2).
When the state SN makes a transition to so, with the discount factor y, the loss is given by
L=
Σ
(Q-- - (QN-1- rN Qu))
(24)
N
1=0
Using the same calculation, the non-zero second-order derivatives are given by
LL = 2 27?
LE 1, -1
aQ
(25)
L
-2%
t E (0, 1...N 1},
QN Qo.
0Q,0Q++1
19

---

Published as a conference paper at ICLR 2022
and the Hessian matrix is eyclic.
Assuming that N is even, the eigenvectors are given by N cos 4km
(sin 2k 4kx sin 2Nkx ) and (cos 2km N
N sin N
N cos N 2Nkx for h E (1. M 2 J. with
eigenvalues given by 2(1 + 7 4y cos 2km ing the relation sin 2nka icity sin 2(N+1)kT sin 2kr and similarly cos 2nkI N
N The result can be similarly confirmed by notic-
N (-47 cos N= = -2y 2(m-1)4m
N + sin 2 and the period- N
(-47 cos 2 NO ) -2y(cos 2(n- 1)kr
N cos - and cos 21j+r = cos 2kr N', which proves that they are indeed the eigenvectors
N
and eigenvalues. At the limit of N + 0O, we have 2 cos 201+22447 (1+7)² 2(1+ cos $ 2(14))-17 (1-7)²
Using 7 R L, we obtain O |
E EXPERIMENTAL DETAILS ON ATARI 2600
E. GENERAL SETTINGS
We follow Mnih et al. (2015) to preprocess the frames of the games by taking the maximum of the recent two frames and changing them to the grey scale. However, instead of downscaling them to 84x84 84 images, we downscale exactly by a factor of 2, which results in 80x 105 images as in Ecoffet et al. (2021). This is to preserve the sharpness of the objects in the images and to preserve translational invariance of the objects. For each step of the agent, the agent stacks the frames seen in the recent 4 steps as the current observation, i.e. state 8t, and decides an action d, and executes the action repeatedly for 4 frames in the game and accumulates the rewards during the 4 frames as rı- Thus, the number of frames is 4 times the number of steps of the agent. One iteration of the gradient descent is performed for every 4 steps of the agent, and the agent executes the random policy for 50000 steps collect some initial data before starting the gradient descent. The replay memory stores 1 million transition data, using the first-in- first-out first-in-frst-out strategy unless otherwise specified. The neural network architecture is the same as the one in Wang et al. (2016), except that we use additional zero padding of 2 pixels at the edges of the input at the first convolutional layer, so that all pixels in the 80x 105 images are connected to the output. Following to Hessel et al. (018)., we set the update period of the target network to be 8000 steps, i.e. 2000 gradient descent iterations, using the Adam optimizer (Kingma
Ba 2014) with a mini-batch size of 32 and default 31, f2 hyperparameters, and we make the agent regard the loss of one life in the game as the end of an episode. The discount factor y is set to be 0.99 unless otherwise specified, and the reward clipping to [-1, 1] is applied except in Sec. 5.3 and E.3
Gradient of LCDØN upon updating the target network Although we use gradient descent to minimize LCDON, when we update the target network by copying from @ to 8, (ov 0,) is exactly equal to (f) and the gradient of LeDgN is undefined. In this case, we find that one may simply use the gradient computed from EDON without any problem, and one may rely on the later gradient descent iterations reduce the loss LCDDN- In our experiments, we further bypass this issue by using the parameters 0 at the previous gradient descent step instead of the current step to update 6, so that does not become exactly equal to Ô. This strategy is valid because the consecutive gradient descent steps are supposed to give parameters that minimize the loss almost equally well, and the parameters should have similar values. In our implementation of DQN, we also update the target network in this manner to have a fair comparison with C-DQN.
Loss As mentioned in Sec. 4.2, either the mean squared error or the Huber loss can be used to compute the loss functions DDN and EMSBE- In Sec. 5.2 we use one half of the mean squared error, and the loss functions are given by
EDN (0:0) 0)
1
max (Qo(se, at) - 7 max Q7 (2($))),aa))
2
n
(26)
(MSBE(()
1
(Qo(se,a)) at) -re - max Qo (0(5441,a')
2
20

---

Published as a conference paper at ICLR 2022
In Sec. 5.1 we use the Huber loss, and the loss functions given by EDON((; 0) Htuber (st, vx + max Qi Q5(s)+1, (0(s) az), ) Ti max Qo (o(s)11,
(0)
Huber
(27)
if x yl < 1, y if r yl 2 1.
v)
Huuber y)
2
In Sec. 5.3, we let the agents learn a normalized Q function Q = Q- and we use the strategy in Pohlen al. (2018) squash the Q function approximately by the square root before learning. The relevant transformation function T is defined by
T(Q) (ign( (V1@)+1-1) +
(28)
and its inverse is given by
(VT+ GET (11+
2
()) = sign(f)
(29)
neT
In our experiments we set ET = 0.01 as Pohlen et al. (2018) and the loss functions are
max fa (st+11 ))) (0: 8) LHuber (fo(s).a)) T (f YT
a'
(30)
EMSBE( ( Huber fo(ss, T fz (
(max fo fo
where So is the neural network, and T (fo a:)) represents the learned normalized function (s at), and A is the reward that is modified together with the normalization of the Q function, which is discussed in Sec. E.3
When we plot the figures, for consistency, we always report the mean squared errors as the loss functions, which are given by
DDN (0: 0) (Qo(sr) - max (ax((((et11,
(31)
(MSBE(0) (Q0()), - Tt- max TaaxxQu(ee (
or,
DON (so()c: -T ( mmax Ja(00+1,
(32)
(MSBE (0) = (fo()c; -T (++ (max Sol8041,
When we use double Q-learning (Van Hasselt al. 2016) in our experiments, all max, Qg(s++1,a)) a') and max fa (St+1, terms in the above equations are actually replaced by Q3 (St+1, arg max, Qo(s++1, a')) and fa (St41, arg max, fo (0 a')). This modification do not change the non-increasing property of LeDØN, which can be confirmed easily.
Other details We find that the exploration can often be insufficient when the game difficult, and follow Van Hasselt et al. (2016) and use a slightly more complicated schedule for the parameter in the e-greedy policy, slowly annealing from 0.1 to 0.01. We have a total computation budget of 5 x 107 steps for each agent, and the j-th step of the agent, for j 50000, set 1 since the initial policy is random; for 50000 > j 2 106, c exponentially annealed to 0.1 following
e c= c//T, with 5 = 108/ (I..))))); for 10 >j> 2 x 10?, is linearly decreased from 0.1 to 0.01; for j and facilitates exploration to mitigate the effects of local optima. We use this e schedule in all of our experiments.
107 we set 0.01. This strategy allows to stay above 0.01 for fairly long time
21

---

Published as a conference paper at ICLR 2022
We set the learning rate to be 6.25 x 10-5 following Hessel et al. (001 unless otherwise specified. We use gradient clipping in the gradient descent iterations, using the maximal f2 norm of 10 in Sec. 5.1 and 5.2, and 5 in Sec. 5.3. The e, hyperparameter for the Adam optimizer follows Hessel et al. (2018) and is set to be 1.5 x 10-1 in Sec. 5.2, but in Sec. 5.1 is set to be 1.5 x 10 for DQN, and 5 x 10-5 for C-DQN and 5 x 10-6 for RG, becaue we observe that the sizes of the gradients are different for DQN, C-DQN and RG. Ea is set to be 10-6 in Sec. 5,3 and E.3 The weight parameters in the neural networks are initialized following He et al. (2015). and the bias parameters are initialized to be zero.
E.2 PRIORITIZED SAMPLING
In our experiments we have slightly modified the original prioritized sampling scheme proposed by Schaul et al. (2015). In the original proposal, in gradient descent optimization, a transition data di (5t, Ge; Te, St41) E is sampled with priority pi, which is set to be
p; = (16,) t,p)
(33)
where Cp is a small positive number, a is a sampling hyperparameter, and |ö,| is the evaluated Bellman error when d, was sampled last time in gradient descent, which is
Q0(ss; ae) rt - 7 max Q0(5++1,a')
(34)
for DQN and
|ōл(c))] = Q0(s), as) - rr - max Q0(s)+1, | max (10(DOW)) (
(35)
a'
(36)
as we have chosen for RG and C-DQN, respectively. The probability for d; to be sampled is P. Pt To correct the bias that results from prioritized sampling, an importance sampling weight
Ej Pj
W; is multiplied to the loss computed on d;, which is given by
Wi= [E N
1 8
(37)
Pi
where N is the total number of data and ,3 is an importance sampling hyperparameter. The bias caused by prioritized sampling is fully corrected when /3 is set to be 1.
Schaul et al. 2015) propose using w; := W/s instead of wy that the importance sampling
max, wj weight only reduces the size of the gradient. However, we find that this strategy would make the learning highly dependent on the hyperparameter ep in Eq. (33), because given data with vanish- ingly small [ō%]. its corresponding priority is p; RS <p. and therefore the term max, Wj becomes
max; wj 2 (- (=x="=00)* 8 x Ep E-a.. As a result, the gradient in learning is scaled by the term max; Wy which is controlled by a, |8 and 6p. and max, wy changes throughout training and typi- cally increases when the average of J6; becomes large. For given e, hyperparameter in the Adam optimizer, the overall decrease of the gradient caused by max, Wy is equivalent to an increase of Eu. which effectively anneals the size of the update steps of the gradient descent. This makes Ep an important learning hyperparameter, as also noted by Fujimoto et al. (020)) although this hyperpa- rameter has been ignored in most of the relevant works including the original proposal. The results on Space Invaders for different values of ép are plotted in Fig. 14 which use the experimental set- tings in Sec. 5.1. It can be seen that the performance is strongly ly dependent on ép- This issue may partially explain the difficulties one usually encounters when trying to reproduce published results.
Lower bounded prioritization To remove this subtlety, we use the original importance sampling weight w; instead of W.. As |o is heavily task-dependent, to remove the dependence of p. on 6p for all the tasks, we make use of the average p == E, to bound p; from below instead of simply using Ep so as to prevents p4 from vanishing. Specifically, we set P. to be
1 P = max { (168) + 6)) 2,
(38)
22

---

Published as a conference paper at ICLR 2022
3000
DQN 5 =10
10
5 =
reward
2000
6 10
loss
10
DON 10"
1000
10"1
10
10
10
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
frames
x108
frames
x10
Training performance and loss for DQN on Space Invaders, with different hyperparam- eters Cp and following the prioritization scheme in /Schaul al. (2015). The loss is calculated by multiplying W; and EDON for each sampled data.
Figure 14:
where we Ep to be vanishingly small number 10-10, and E is a prioritization hyperparam- eter that controls the lower bound relative to the average. In our experiments we set En - 10. This scheme makes sure that regardless of the size of [6,]. a data is always sampled with probability 1 that is at least E and wi is bounded by 2Ø from above provided that the total priority E, Py does not change too quickly. We adopt this prioritization scheme in all of our experiments except for the experiments in Fig. abooe. Compared to Fig. [4] it can be seen that our DQN loss and C-DQN loss on Space Invaders in Fig. do not change much during training.
Details of setting When a new data is put into the replay memory, it is assigned priority that is equal to the maximum of all priorities in the memory that have been calculated using Eq. (38). and at the beginning of learning when gradient descent has not started, we assign the collected data priority equal to 100. We also additionally bound wy from above by 2čp. so that does not become too large even if the total priority E, Pj fluctuates. The hyperparameter /3 is linearly increased from 0.4 to during the x 10" steps of the agent, following Schaul et al. (005), and is 0.9 in Sec. 5,3 and E.3 and 0.6 otherwise. We did not try other values of a.
In an attempt to improve efficiency, whenever we use 66|| to update the priority of a transition
(st, de, Tt, St+1), we also use its half 16,1 to compute 2 update the priority of the preceding transition ($;-1, 1, Pr. 82). This accelerates learning by facilitating the propagation of information. We adopt this strategy in all of our experiments except in Sec. 5.2 and in Fig. 14 in order to make sure that the results are not due to this additional strategy.
6. cp)), and use it lower bound to
2
E.3 EVALUATION OF THE DISCOUNT FACTOR AND NORMALIZATION THE LEARNED Q FUNCTION
Evaluation of the discount factor As discussed in Sec. B.5 some tasks require a large discount factor 7, while for many other tasks, large y slows down the learning significantly and make the optimization difficult. Therefore, we wish to find a method to automatically determine a suitable y for given task. As an attempt, we propose heuristic algorithm to approximately estimate the frequency of the reward signal in an episode, based on which we can determine 7. The algorithm is described in the following.
Given an episode & in the form of an ordered sequence of rewards & = (r: T-- for which sT, a terminal state we wish have an estimate of the average number steps needed to observe the next non-negligible reward when one starts from i = 0 and moves to i Tī. Suppose that all rewards }ri} are either 0 or constant (1) of 0; then, one may simply count the average number of steps before encountering the next reward y(()) when one moves from i = 0 to Tg. However, such a simple strategy does not correctly respect the different kinds of distributions of rewards time, such as equispaced rewards and clustered rewards, and this strategy is symmetric with regard to the time reversal ++ Th, which not satisfactory Therefore, we use a weighted average instead. To
We consider re to be the reward that is obtained when moving from state 8, to 8t+1-
This is because if one almost encounters no reward at the beginning but encounters many rewards at the end of an episode, the time horizon for planning should be large; however, if one encounters many rewards the heginning but almost encounters reward the end, the time horizon is necessarily large. Therefore,
23

---

Published as a conference paper at ICLR 2022
this end we define the return
T--1 Σ TE:
(Ex) =
(39)
which is the sum of the rewards that are to be obtained starting from time step i, and we compute the average number of steps to see the next reward weighted by this return as
Σ.- Th- (
((E+)
4: minft | 12 i, L -
(40)
Ex=0 (Ex)
where I is the number of time steps to encounter the next reward starting from the time step i. This strategy does not respect the time reversal symmetry it involves R2 and as the sum is taken over the time steps {0, ... - J. it can distinguish between clustered rewards and equispaced rewards, and it also properly takes the distance between consecutive clusters of rewards into account.
The next problem is how we should deal rewards that have various different magnitudes. As we can deal with the case of the rewards being either 0 or a constant, we may decompose trajectory containing different magnitudes of rewards into few sub- sub-trajectories, each of which contains re- wards that are either 0 or a constant, so that we can deal with each of these sub-trajectories using Eq. (40). and finally use a weighted average of I over those uub-trajectories as our result. With a set of episodes ]. we treat each of the episodes separately, and again, use a weighted average over the episodes as our estimate. The algorithm is given by Alg. [ The weights in line 3 in Alg. [ return can be ruled out, and that an
ensure that when computing the final result, episodes with episode with a large return does not contribute too much compared with the episodes with smaller returns. We have intentionally used the inverse in line 10 in Alg. and used the root mean square in line 12 in order to put more weight on episodes that have frequent observations of rewards. Taking the absolute values of rewards in line 2 is customary, and in fact, one can also separate the negative and positive parts of rewards and treat them separately. Note that the output f should be divided by factor of 2 to correctly represent the frequency of rewards. We also notice that the above ap- proach can actually be generalized to the case of continuous variables of reward and time, for which integration can be used instead of decomposition and summation.
To obtain the discount factor 7, we set the time horizon to be 7. with a Lime-horizon hyperparameter Cy. and then we set y 1 L. To make y close to 0.9998 for the difficult games discussed in Sec. 5.3, we have set غ, = 15. However, later we noticed that the agent actually learns more efficiently with smaller y, and é, may be set to range from 5 to 15. In Sec. 5.3, E 15 is used, but in the following experiments we use č, = 10.
c..
We make of the complete episodes in the initial 50000 transitions collected at the beginning of training to evaluate ", and here we also regard the loss of a life in the game as the end of an episode. We clip the obtained 7 so that it lies between 0.99 and 0.9998, and ? is set be 0.9998 if no reward is observed.
Normalization of the Q function In addition to using the transformation function T(-) to squash the Q function as described in Eq. (28) and (30). we normalize the Q function by the scale of the reward since the tasks in Atari 2600 have vastly different magnitudes of rewards. For an episode & the Q function, or the value function, as the discounted return in the episode is given by
T--1 Q
T6
(41)
1=1
and we compute its mean j by taking the average of Qia over all states in given sample episodes. The standard deviation of Qik. however, has a dependence on č, If we simply normalize Qae by its standard deviation, the magnitude of the reward signal after normalization becomes dependent on the hyperparameter ट,, which we wish to avoid. To obtain normalization that is independent of C.. we assume that rewards are i.i.d. variables with mean μ, and standard deviation o,.. Focusing on
the discount factor should not be evaluated by a method that respects the time reversal. Note that the Fourier transform also respects the time reversal and thus does not suffice for our purpose.
24

---

Published as a conference paper at ICLR 2022
Algorithm 1 Estimation of the expected frequency of observing next reward signal
Input: sample episodes {
Output: estimate of the inverse of the number of time steps f
1: for & E {Ex} do
2: & = (ri) i-
1--1 + (1r:1)7=0-
Taking the absolute value reward > For computing a weighted average over different episodes
3:
wk - v Ro(Ex)
4:
j+0 0
while rewards & = Th- are not all zero do
5:
6:
j-1 j 1+1
E Ex +DICOMPOSESTQQENCCCCE)
7:
8:
end while
9: Compute l + Σ, Rote) ) Ey )
> Weighting the results by the contribution the rewards
10: fkr
+
Th 11: end for
12: Compute + V
Ee we Sh Ex' war
We use RMS have more emphasis on episodes with larger fx
13: return
14:
15: procedure DECOMPOSESEQUENCCEE)
r' < min( min &
0,
if; =0
17:
+' (1()) M
rr:
otherwise
18: (-
19: return 8
20: end procedure
the Q function at the initial states, i.e. Qu:k. we obtain the relation
1 - 7 pry
E [Qxxk]
(42)
1 ?
and therefore we estimate μr by Hrr Also, we have
Ne EE Qu:k -
with the number of sample episodes Ne-
Var (Qask - 1
1- 1- Tn (r))
2.2 - 1- O
1-
2
(43)
and therefore o, can be estimated by the variance of {QROA 1- T- pvr)
After obtaining the standard deviation of rewards a,, we need to compute scale to normalize the learned Q function. To avoid E, dependence of a, we use a, to roughly predict the standard deviation of Q if to = is used as the discount factor, and we use the obtained standard deviation the normalization factor o. For simplicity we ignore the variance of Tp and obtain
o = or
1
Σ
20
27
(44)
N
1
2
Finally, the function we let the agent learn is Q Q-u
The normalized function Q also obeys the Bellman equation as well, but with slightly modified reward. It can be easily shown that
rt (1 7)p
Q" 44)
+ 7 max (8(+1,)) if 8141 is non-terminal, σ
(45)
and
Q' (st, (1)
Pt ---
8141 is terminal.
(46)
25

---

Published as a conference paper at ICLR 2022
Sking 0.9997)
Tennis (.
Bowling ( 0.9096)
20
-10000
150
reward
-20000
C-DON
100
Human
Double DQN
-20
50
0.0
0.5
1.0 frames
1.5
2.0
0.0
0.5
3.0
0.0
0.5
1.0
1.5
2.0
x10
x10
Spacelnvaders (7.20.0000)
Hero (y=2
MsPacman (tye 0.9048)
30000
6000
2000
4000
1000
10000
2000
Yph
0.5
3.5
2.0
0.0
1.0 x10
0.5
1.0
2.0
x10
x10*
Figure 15: Training performance for C-DQN on several games in Atari 2600 compared with the human performance (Badia et al. 2020) and the double DQN (Hessel et al. 2018), using the same experimental setting as in Sec. 5.3, except for using é, = 10.
Therefore, the effect of normalization amounts to modifying the reward r. â == --((-))) and then assigning an additional terminal reward - This is easy to implement and we use this normalization in our experiments in 5.3) Similarly to the evaluation of 7, we use the episodes in the initial 50000 transitions to compute and o; however, here we do not regard the loss of a life as the end of an episode, so that the lengths of the episodes do not become too short. We also do not take episodes that have zero return into account.
a
Results on other Atari games To demonstrate the generality of the above strategy, we report our results several games in Atari 2600, using learning rate of 4 x 10-5 and é, 10. The results are shown in Fig. 15] We find that for some games, especially Hero, the learning sometimes gets trapped in a local optimum and learning may stagnate, which deserves further investigation. We did not do a fine grid search on the learning rate and we simply selected from 6 x 10-5, 4 x 10-5 and 2 x 10-5, and we chose x 10-3, because it produces reasonable results for most of the tasks. We notice that it is difficult to find a learning rate that works well for all the tasks, as the tasks have drastically different levels of stochasticity and are associated with different time horizons.
We also notice that there are several cases where our strategy of the normalization and the evaluation of y does not give satisfactory results. This is mainly because we have assumed that the time scales of obtaining rewards are similar for the random policy and for learned policy. A typical counterexample is the game Breakout, where the random policy almost obtains no reward in an episode but a learned policy frequently obtains rewards. Therefore, our strategy above is still not general enough to deal with all kinds of scenarios, and it cannot replace the bandit algorithm in Badia et al. (2020) which is used to select y, and therefore a better strategy is still desired.
F EXPERIMENTAL DETAILS ON CLIFF WALKING
In the cliff walking experiments, we store all state-action pairs into a table, excluding the states of goal positions and cliff positions, and excluding the actions that go into the walls. We plot the data on a log scale of iteration steps by explicitly evaluating the loss over all state-action pairs in Sec. 3.1, and evaluating the reward of the greedy policy in Sec. 3.2. Because we do evaluations at equal intervals on log scale the x-axis, fewer evaluations are made when the number of iteration steps is larger, and as a consequence, the scatter plots in the right of Fig. I do not have equally many data points along the curves. The learning rate a is always 0.5, and e in the e-greedy policy is always fixed. Specifically for the one-way way cliff walking task in Fig. 3, when two actions aj and a2 have the same Q function value, i.c. Q(s,, a1) = Q(s,, a2), the greedy policy randomly chooses aj or a at state St, and when max Q88+11, a') Q(8++1, a1) Q(st+1, a2), we modify the learning rule
26

---

Published as a conference paper at ICLR 2022
of RG for transition (st, ae, Pt: st+1) be
AQ(s,, a.) (rx + max ((+++, ((ss..) AQ(#++1;11) = AQ(5++1, 02) -"700(s at),
(47)
so that the greedy policy at 81+1 is not changed after learning from the transition.
27


Reviews:
[{"review_id": "u1V7R6yUc6", "reviewer": "Reviewer_SCA5", "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": "The primary way in which the authors approach the problem of convergence of DQN and related algorithms is replace the use of a DQN-style target network with a minimization of the mean squared Bellman error (MSBE), the foundation of the residual gradient-type algorithms introduced in 1995. This type of algorithms however did not traditionally perform better than other approaches, especially in the context of deep RL. \n\nThe authors are proposing an approach where the loss of their new algorithm C-DQN is the expectation of the maximum between the MSBE loss and a DQN loss which is derived from interpreting DQN as a form of fitted iteration. This definition enforces that both the DQN and the MSBE loss are decreasing during learning. \n\nWhile this guarantee is interesting, the experimental results do not show a clear motivation for the use of this approach. The experiments in which the authors succeed to show an improvement are hand engineered to show off the benefits of the approach - for instance the authors compare against DQN on space invaders where half of the data is randomly discarded, or when the replay buffer is using a random replacement strategy.", "summary_of_the_paper": "The paper argues that the DQN and its algorithm and its variants do not guarantee convergence and that they can diverge in realistic settings. \n\nThe authors develop a new technique that guarantees convergence of DQN. The authors show that in the case of very large discount factors (such as 0.9998) this algorithm outperforms baseline algorithms on certain Atari games. ", "summary_of_the_review": "The paper introduces an interesting perspective on guaranteed convergence for DQN. However, this is not the first algorithm that is doing so, and the experimental results show improvement only in specific selected, somewhat unusual circumstances.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M8Nj1iLMC6h", "reviewer": "Reviewer_x6bM", "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": "Overall, I feel this paper is well-organized and well-written. I can understand the message that the authors want to deliver. The experiments are well-designed and clean. The main limitation from my point of view is that there seems to be not too much new stuff. \n\nThe only change w.r.t to DQN is Line 12 which modifies the loss to be the maximum of DQN loss and MSBE loss. All the other components remain the same and all the drawbacks are inherited (sample-inefficiency and exploration). A lot of efforts are made on some corner cases that DQN and MSBE fail. Since there is no theory for C-DQN (I mean convergence is not the ultimate goal since it may converge to a bad local solution. For online RL, you should study regret. For policy optimization, you should study sample-complexity), I am wondering if there exist other corner cases that C-DQN could also suffer. \n\nWhen the paper mentioned efficiency or inefficiency, I think it is worth pointing out it is sample-efficiency or computational efficiency. For the problem pointed out in Section 3, how it relates to the problem of exploration? Because from the description, the data quality seems to play an important role. I admit the exploration for deep RL is hard, but at least for tabular cases, there are sample and computationally efficient algorithms, say https://arxiv.org/abs/1807.03765 Is Q-learning Provably Efficient?. The community may need some principle ways to understand the inefficiency. Current Section 3.2 seems to be not very in principle. \n\nThe limitation of MSBE has been studied for a long time in RL community. There are multiple important improvements on this but the authors didn't discuss in detail (although the authors cited them in one sentence). That means this paper is not properly positioned in literature. The widely known issue is the double-sampling issue (empirical MSBE is biased) and several works have been proposed to remedy this, \"A Kernel Loss for Solving the Bellman\nEquation\". But in this paper, the authors still discussed and compared the original version of RG algorithm. Since the discussion in Section 3.1 is quite specific, it's hard for me to know if a similar limitation holds for recently proposed algorithms. \n\n\"Although convergent gradient-based methods have also been proposed (Sutton et al., 2009; Bhatnagar et al., 2009; Feng et al., 2019; Ghiassian et al., 2020), they cannot be used with neural networks easily, and they often have worse performance than TD methods and DQN.\" If you want to make such arguments, please provide detailed references and explain the reason.\n \n\"In this work, we only consider the deterministic case and drop the notation Est+1 [·] where appropriate.\" I am wondering if the whole paper is limited to deterministic transition. If so, I think this should be highlighted in the abstract. In theory, there is a huge difference between deterministic case and stochastic transition. \n\nMinor: 1. \"If the task is difficult\" is vague. What do you mean by a difficult task? 2. In Figure 4, what the loss is for? \n", "summary_of_the_paper": "This paper studies several issues of DQN (basically FQI, a version of fixed-point iteration) and empirical Bellman error minimization (has a clear loss function). Several issues of MSBE are pointed out. The authors propose a new approach by replacing the DQN loss by the maximum of DQN loss and MSBE loss. Several experiments on Atari games support the argument. ", "summary_of_the_review": "The noverlty and significance of the proposed algorithm is limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6Ya0SBfo_bg", "reviewer": "Reviewer_bKTr", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "Strengths\\\nThe topic is very relevant, with potentially very strong impact on the field of Q-function based RL.\n\nThe paper is excellently written.\n\nThe method presented is extremely simple and can be incorporated into a wide variety (probably even most) Q-function based RL procedures without much effort.\n\nWeaknesses\\\nIn my opinion, the choice of benchmarks is not well suited for examining limitations of the method. I suspect that in benchmarks that are strongly stochastic in the sense that from a state-action pair, successor states with strongly different values of the value function can be reached, the Bellman residual loss function dominates and therefore no advantage is gained over optimization with respect to the Bellman residual loss function and thus the solutions do not solve the RL problem.\nIt would, in my opinion, add considerable value to the already good paper if the behavior of the method were additionally examined on one or more benchmarks that have the property that from a state-action pair, successor states with strongly different values of the value function can be reached.\nI realize that this cannot be easily incorporated into the limited number of pages, and the current excellent clarity of presentation should not suffer. Possibly this investigation could go into the appendix. Or this investigation could be considered as Future-Work.\n\nFurther comments\\\nI would appreciate it if in addition to current works that represent the field well, the pioneering works would also be referenced in each case. So instead of (Mnih et al., 2015; Hessel et al., 2018) rather (Riedmiller 2005, Mnih et al., 2015; Hessel et al., 2018).\n\nRiedmiller 2005, Neural Fitted Q Iteration - First Experiences with a Data Efficient Neural Reinforcement Learning Method\n\nAnd instead of (Munos & Szepesvári, 2008), rather (Ernst et al. 2005, Munos & Szepesvári, 2008).\n\nErnst et al. 2005, Tree-Based Batch Mode Reinforcement Learning \n\nA simple benchmark where the property that successor states with widely varying values of the value function can be reached from a single state-action pair is pronounced is the wet chicken benchmark (e.g., Hans & Udluft 2011). There is a one-dimensional variant and a two-dimensional variant that is somewhat more difficult. Perhaps an investigation with this, or a similar benchmark, would eliminate the concerns that in this case the Bellman residual is always dominant and CDQN performs worse than DQN ... or confirm it.\n\nHans & Udluft 2011, Ensemble Usage for More Reliable Policy Identification in Reinforcement Learning\n\nI am not sure what is meant by the term \"overgeneralization\". If this means something other than the following definition: \\\n*The American Psychological Association defines overgeneralization as, “a cognitive distortion in which an individual views a single event as an invariable rule, so that, for example, failure at accomplishing one task will predict an endless pattern of defeat in all tasks.”*\nthen this should be explained and/or supported by a reference.\n\nIn \"we construct a loss does not\" probably a \"that\" is missing.\n\nIn Table 1 in the Appendix is written \"DQN (ours)\".\n\nPlease check the bibliography for accidental lower case letters, like „bellman“, „q-“, „td“\n", "summary_of_the_paper": "The paper addresses the problem of unstable learning that arises in NFQ type RL methods. \nIt is assumed that the problem can be overcome by a provably convergent NFQ-like method.\nSuch a provably convergent method is presented and tested on a selection of benchmarks and compared to DQN.\n", "summary_of_the_review": "The paper is excellently written. The method presented could be groundbreaking. However, it is not explored whether the proposed method is generally applicable (see \"Main Review\" for details).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: It is important to have good stable and trustworthy algorithms.  Though I am unconvinved that the C-DQN algorithm proposed here is the final word (and I suppose this is not controversial, and the authors might agree), the ideas presented here are sufficiently interesting to be disseminated and discussed more widely.  All reviewers recommended accepting the paper, and I'll follow their lead.

That said, the paper can still be improved, and the authors are encouarged to carefully consider the feedback provided by the reviewers.  In particular, it is good to be clear about which parts are principled, and which parts are somewhat heuristic or arbitrary, and could therefore presumably be improved in future work.  In fact, doing so clearly could make the paper _more_ rather than less impactful.

In any case, it seems good to include this paper at the conference, to highlight the questions and partial answers given here, and to inspire more discussion.
Decision: Accept (Poster)