Year: 2021

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 in 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.

heading: 1 INTRODUCTION
text: With the development of deep learning, reinforcement learning (RL) that utilizes deep neural networks 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ösel 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 et al., 2015; Hessel et al., 2018; Riedmiller, 2005), which hold records on many difficult RL tasks (Badia et al., 2020). However, unlike supervised learning, Q-learning, or more generally temporal difference (TD) learning, does not guarantee convergence when function approximations such as neural networks are used, and as a 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 to construct the learning objective, a.k.a. bootstrapping, and as it generalizes, its predictions over different data interfere with each other, which can make its learning objective unstable in the course of training and potentially lead to instability and divergence.
This non-convergence 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 Hasselt 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 require linearity or involve computationally heavy operations, and they often show worse empirical performance compared with TD methods.
In this work, we show that the above-mentioned gradient-based methods actually have inherent problems in learning dynamics which hamper efficient learning, and we propose a convergent DQN (C-DQN) algorithm by modifying the loss of DQN. Because an 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 Sec. 2 we present the background. In Sec. 3 we discuss the inefficiency issues in the previous gradient-based methods and demonstrate using
toy problems. In Sec. 4 we propose C-DQN and show its convergence. In Sec. 5 we show the results of C-DQN on the Atari 2600 benchmark (Bellemare et al., 2013) and in Sec. 6 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 to obtain successful results on the standard Atari 2600 benchmark using deep neural networks, showing its efficacy in dealing with realistic and complicated problems.

heading: 2 BACKGROUND
text: Reinforcement learning involves a Markov decision process (MDP), where the state st of an environment at time step tmakes a transition to the next state st+1 conditioned on the action of the agent at at time t, producing a reward rt depending on the states. The process can terminate at terminal states sT , and the transition of states can be either probabilistic or deterministic. The goal is to find a policy π(s) to determine the actions at+i ∼ π(st+i) in order to maximizes the return ∑T−t i=0 rt+i,
i.e., the sum of future rewards. In practice, a discounted return ∑T−t i=0 γ
irt+i is often used instead, with the discount factor γ < 1 and γ ≈ 1, so that the expression is convergent for T →∞ and that rewards far into the future can be ignored, giving an effective time horizon 11−γ . 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 a state-action pair (st, at):
Vπ(st) = Eat,{(st+i,at+i)}T−ti=1 [ T−t∑ i=0 γirt+i ] , Qπ(st, at) = E{(st+i,at+i)}T−ti=1 [ T−t∑ i=0 γirt+i ] , (1)
with at+i ∼ π(st+i) in the evaluation of the expectation. When the Q function is maximized by a policy, we say that the policy is optimal and denote the Q function and the policy by Q∗ and π∗, respectively. The optimality implies that Q∗ satisfies the Bellman equation (Sutton & Barto, 2018)
Q∗(st, at) = rt + γEst+1 [ max a′ Q∗(st+1, a ′) ] . (2)
The policy π∗ is greedy with respect to Q∗, i.e. π∗(s) = arg maxa′ Q ∗(s, a′). Q-learning uses this recursive relation to learn Q∗. In this work we only consider the deterministic case and drop the notation Est+1 [·] 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 a table, and iterate over the values using
∆Q(st, at) = α ( rt + γmax
a′ Q(st+1, a
′)−Q(st, at) ) , (3)
where α is the learning rate. This is called Q-table learning and it guarantees convergence to Q∗. If the space of (s, a) is large and Q-table learning is impossible, a function approximation is used instead, representing the Q function as Qθ with learnable parameter θ. The learning rule is
∆θ = α∇θQθ(st, at) ( rt + γmax
a′ Qθ(st+1, a
′)−Qθ(st, at) ) , (4)
which can be interpreted as modifying the value of Qθ(st, at) following the gradient so that Qθ(st, at) approaches the target value rt + γmaxa′ Qθ(st+1, a′). However, this iteration may not converge, because the term maxa′ Qθ(st+1, a′) is also θ-dependent and may change together with Qθ(st, at). Specifically, an exponential divergence occurs if γ∇θQθ(st, at) · ∇θ maxa′ Qθ(st+1, a′) > ||∇θQθ(st, at)||2 is always satisfied and the value of maxa′ Qθ(st+1, a′) is not constrained by other means.1 This can be a serious issue for realistic tasks, because the adjacent states st and st+1 often have similar representations and∇θQθ(st, ·) is close to∇θQθ(st+1, ·). The DQN algorithm uses a deep neural network with parameters θ as Qθ (Mnih et al., 2015), and to stabilize learning, it introduces a target network with parameters θ̃, and replace the term maxa′ Qθ(st+1, a ′) by maxa′ Qθ̃(st+1, a ′), so that the target value rt + γmaxa′ Qθ̃(st+1, a ′) does
1This can be shown by checking the Bellman error δt := rt + γmaxa′ Qθ(st+1, a′) − Qθ(st, at), for which we have ∆δt = αδt ( γ∇θQθ(st, at) ·maxa′ Qθ(st+1, a′)− ||∇θQθ(st, at)||2 ) up to the first order of ∆θ following Eq. (4). As ∆δt is proportional to δt with the same sign, it can increase exponentially.
not change simultaneously with Qθ. The target network θ̃ is then updated by copying from θ for every few thousand iterations of θ. This technique reduces fluctuations in the target value and dramatically 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; Lillicrap et al., 2015). Nevertheless, the introduction of the target network θ̃ is not well-principled, and it does not really preclude the possibility of divergence. As a 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 to diagnose or remove, and usually one cannot use a discount factor γ that is very close to 1. In an attempt to solve this problem, Durugkar & Stone (2017) considered only updating θ in a direction that is perpendicular to ∇θ maxa′ Qθ(st+1, a′); however, this strategy is not satisfactory in general and can lead to poor performance, as shown in Pohlen et al. (2018).
One way of approaching this problem is to consider the mean squared Bellman error (MSBE), which is originally proposed by Baird (1995) and called the residual gradient (RG) algorithm. The Bellman error, or Bellman residual, TD error, is given by δt(θ) := rt + γmaxa′ Qθ(st+1, a′) − Qθ(st, at). Given a dataset S of state-action data, δt is a function of θ, and we can minimize the MSBE loss
LMSBE(θ) := E [ |δ(θ)|2 ] = 1 |S| ∑
(st,at,rt,st+1)∈S
∣∣∣Qθ(st, at)− rt − γmax a′ Qθ(st+1, a ′) ∣∣∣2 , (5)
and in practice the loss is minimized via gradient descent. If LMSBE becomes zero, we have δt ≡ 0 and the Bellman equation is satisfied, implying Qθ = Q∗. Given a 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 et al. (2009); Dai et al. (2018); Feng et al. (2019); Ghiassian et al. (2020); Touati et al. (2018), and they are often referred to as gradientTD 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.

heading: 3 INEFFICIENCY OF MINIMIZING THE MSBE

heading: 3.1 ILL-CONDITIONNESS OF THE LOSS
text: In the following we show that minimizing LMSBE does not lead to efficient learning in general by considering the case of tabular problems, for which all the gradient-TD methods mentioned above reduce to deterministic RG learning. For a tabular problem, the Q function values for different stateaction pairs are independent variables. Suppose we have a trajectory of experience {(st, at, rt)}N−1t=0 obtained by following the greedy policy with respect to Q, i.e. at = arg maxa′ Q(st, a
′), and sN is a terminal state. Taking γ = 1, the MSBE loss is given by
LMSBE = 1
N [ N−2∑ t=0 (Q(st, at)− rt −Q(st+1, at+1))2 + (Q(sN−1, aN−1)− rN−1)2 ] . (6)
Despite the simple quadratic form, the Hessian matrix of LMSBE with variables {Q(st, at)}N−1t=0 is ill-conditioned, and therefore does not allow efficient gradient descent optimization. The condition number κ of a Hessian matrix is defined by κ := |λmax||λmin| , where λmax and λmin are the largest and smallest eigenvalues. We have numerically found that κ of the Hessian of LMSBE in Eq. (6) grows as O(N2). To find an analytic expression, we add an additional term Q(s0, a0)2 to LMSBE, so that the Hessian matrix becomes  4 −2 −2 4 . . .
. . . . . . −2 −2 4  N×N . (7)
The eigenvectors of this Hessian matrix that have the form of standing waves are given by (sin kπN+1 , sin 2kπ N+1 , ... sin Nkπ N+1 )
T for k ∈ {1, 2, ...N}, and the corresponding eigenvalues are given by 4− 4 cos kπN+1 . Therefore, we have κ = 1+cos πN+1 1−cos πN+1 ∼ O(N2). See appendix for the details.
With γ < 1, if the states form a cycle, i.e., if sN−1 makes a transition to s0, the loss becomes LMSBE = 1 N [ ∑N−2 t=0 (Qt − rt − γQt+1) 2 + (QN−1 − rN−1 − γQ0)2], where Q(st, at) is denoted by Qt. Then, the Hessian matrix is cyclic and the eigenvectors have the form of periodic waves: (sin 2kπN , sin 4kπ N , ... sin 2Nkπ N ) T and (cos 2kπN , cos 4kπ N , ... cos 2Nkπ N )
T for k ∈ {1, 2, ...N2 }, with corresponding eigenvalues given by 2(1 + γ2) − 4γ cos 2kπN . At the limit of N → ∞, we have κ = (1+γ) 2 (1−γ)2 . Using γ ≈ 1, we have κ ∼ O ( 1 (1−γ)2 ) . By interpreting 11−γ as the effective time horizon, or the effective size of the problem, we see that κ is quadratic in the size of the problem, which is the same as its dependence on N in the case of γ = 1 above. In practice, κ is usually 104 ∼ 105, and we therefore conclude that the loss is ill-conditioned. The ill-conditionedness has two important implications. First, as gradient descent converges at a rate of O(κ),2 the required learning time is quadratic in the problem size, i.e. O(N2), for the RG algorithm. In contrast, Q-learning only requires O(N) steps as it straightforwardly propagates reward information from si+1 to si 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 a small distance between the learned Q and the optimal Q∗, which may explain why LMSBE is not a useful indicator of performance (Geist et al., 2017).
Cliff walking By way of illustration, we consider a tabular task, the cliff walking problem in Sutton & Barto (2018), as illustrated in Fig. 1. The agent starts at the lower left corner in the grid and can move into nearby blocks. If it enters a white block, it receives a reward −1; if it enters a grey block which is the cliff, it receives a reward −100 and the process terminates; if it enters the goal, it terminates with a zero reward. To learn this task, we initialize Q for all stateaction pairs to be zero, and we randomly sample a state-action pair as (st, at) and find the next state st+1 to update Q via Eq. (3), which is the Q-table learning, or to minimize the associated loss (Qθ(st, at)− rt − γmaxa′ Qθ(st+1, a′))2 following the gradient, which is RG learning. As shown
2Although in the deterministic case momentum can be used to accelerate gradient descent to a convergence rate of O( √ κ), it cannot straightforwardly be applied to stochastic gradient descent since it requires a large momentum factor ( √ κ−1√ κ+1
)2 (Polyak, 1964) which results in unacceptably large noise. 3|Q−Q∗|2 is defined by ∑ (s,a) |Q(s, a)−Q ∗(s, a)|2, where the sum is taken over all state-action pairs.
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 γ = 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. 1. Notice that the agent learns by random sampling from the state-action space, and doubling the system size reduces the sampling efficiency by a 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 above.

heading: 3.2 TENDENCY OF MAINTAINING THE AVERAGE PREDICTION
text: 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 Qt ≡ Q(st, at) and Qt+1 ≡ maxa′ Q(st+1, a′), and given that they initially satisfy Qt = γQt+1, with an observed transition from st to st+1 with a non-zero reward rt, repeatedly applying the Q-table learning rule in Eq. (3) leads to ∆Qt = rt and ∆Qt+1 = 0, and thus ∆ (Qt +Qt+1) = rt. On the other hand, in the case of RG, minimizing LMSBE using the gradient results in the following learning rule
∆Q(st, at) = α ( rt + γmax
a′ Q(st+1, a
′)−Q(st, at) ) , ∆ max
a′ Q(st+1, a ′) = −γ∆Q(st, at), (8)
and therefore whenever Qt is modified, Qt+1 changes simultaneously, and we have
∆ (Qt +Qt+1) = (1− γ)rt. (9)
Due to the condition γ ≈ 1, ∆ (Qt +Qt+1) can be very small, which is different from both Qlearning and human intuition, because the sum of the predicted Q, i.e. ∑ tQt, almost does not change. This occurs because there is an additional degree of freedom when one modifies Qt and Qt+1 to satisfy the Bellman equation: Q-learning tries to keep Qt+1 fixed, while RG follows the gradient and keeps Qt + 1γQt+1 fixed, except for the case where st+1 is terminal and thus Qt+1 is a constant. This has important implications on the learning behaviour of RG as discussed below.
If the average of Q(s, a) is initialized above that of Q∗(s, a) and the transitions among the states can form loops, the learning time of RG additionally scales as O( 11−γ ) 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 γ, while RG scales roughly as O( 11−γ ) and does not learn for γ = 1. This is because the policy arg maxa′ 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. (9) controls the learning dynamics of the sum of all Q values, i.e. ∑ (s,a)Q(s, a), with the learning target being ∑ (s,a)Q
∗(s, a), and the learning time scales asO( 11−γ ). For γ = 1, ∆ ∑ (s,a)Q(s,a) is always zero and ∑ (s,a)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 improving its performance. A typical example is shown in Fig. 3, where Q is initialized to be zero and the agent learns from its observed state transitions in an online manner following the -greedy policy.4 We see that while Q-table learning can solve the problem easily without the help of a non-zero , RG cannot find the optimal policy with = 0, and it learns slowly and relies on non-zero values. This is because when RG finds rewards, Q(s, a) for some states increase while the other Q(s, a) values decrease and may become negative, and if the negative values become smaller than the reward associated with the termination, i.e. −1, it will choose termination as its best action. Therefore, it relies on the exploration strategy to correct its behaviour at those states with lowQ(s, a) values and to find the optimal policy. Generally, when an unexpected positive reward rt is found in learning, according to the learning rule in Eq. (8), with an increase of rt in Q(st, at), maxa′ Q(st+1, a′) decreases simultaneously by rt, and the action at st+1, i.e. arg maxa′ Q(st+1, a ′), is perturbed, which may
4 -greedy means that for probability a random action is used; otherwise arg maxa′ Q(s, a ′) is used.
make the agent choose a worse action that leads to rt less reward, and therefore the performance may not improve on the whole. In such cases, the performance of RG crucially relies on the exploration strategy so that the appropriate action at st+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 analysis is based on the tabular case, we believe that the situation is not generally better when function approximations are involved. With the above issues in mind, it can 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 a Qlearning-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 et 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 ill-conditionedness may be resolved by a second-order optimizer or the Retrace loss (Munos et al., 2016; Badia et al., 2020), the issue in Sec. 3.2 may not be resolved, because it will likely converge to the same solution as the one found by gradient descent and thus have the same learning behaviour.

heading: 4 CONVERGENT DQN ALGORITHM

heading: 4.1 INTERPRETING DQN AS FITTED VALUE ITERATION
text: As we find that Q-learning and the related conventional TD methods and DQN have learning dynamics that is preferable to RG, we wish to minimally modify DQN so that it can maintain its learning dynamics while being convergent. To proceed, we first cast DQN into the form of fitted value iteration (FVI) (Ernst et al., 2005; Munos & Szepesvári, 2008). With initial parameters θ̃0 of the target network, the DQN loss for a transition (st, at, rt, st+1) and network parameters θ is defined as
`DQN(θ; θ̃i) := ( Qθ(st, at)− rt − γmax
a′ Qθ̃i(st+1, a
′) )2 , (10)
and DQN learns by iterating over the target network LDQN(θ; θ̃i) := E [ lDQN(θ; θ̃i) ] , θ̃i+1 = arg min
θ LDQN(θ; θ̃i), (11)
and θ̃i is used as the parameter of the trained network for a sufficiently large i. In practice, the minimum in Eq. (11) is found approximately by stochastic gradient descent, but for simplicity, here we consider the case where the minimum is exact. When DQN diverges, the loss is supposed to diverge with iterations, which means we have minθ LDQN(θ; θ̃i+1) > minθ LDQN(θ; θ̃i) for some i.

heading: 4.2 CONSTRUCTING A NON-INCREASING SERIES
text: Theorem 1. The minimum of LDQN(θ; θ̃i) with target network θ̃i is upper bounded by LMSBE(θ̃i).
This relation can be derived immediately from LDQN(θ̃i; θ̃i) = LMSBE(θ̃i) and minθ LDQN(θ; θ̃i) ≤ LDQN(θ̃i; θ̃i), giving minθ LDQN(θ; θ̃i) ≤ LMSBE(θ̃i).
When DQN diverges, minθ LDQN(θ; θ̃i) diverges with increasing i, and therefore LMSBE(θ̃i) must also diverge. Therefore at each iteration, while the minimizer θ̃i+1 minimizes the i-th DQN loss LDQN(θ; θ̃i), it can increase the upper bound of the (i+1)-th DQN loss, i.e. LMSBE(θ̃i+1). We want both LDQN and LMSBE to decrease in learning and we define the convergent DQN (C-DQN) loss as
LCDQN(θ; θ̃i) := E [ max { `DQN(θ; θ̃i), `MSBE(θ) }] , (12)
where `MSBE(θ) := (Qθ(st, at)− rt − γmaxa′ Qθ(st+1, a′))2 and LMSBE = E [`MSBE]. Theorem 2. The C-DQN loss satisfies minθ LCDQN(θ; θ̃i+1) ≤ minθ LCDQN(θ; θ̃i), given θ̃i+1 = arg minθ LCDQN(θ; θ̃i).
We have
min θ LCDQN(θ; θ̃i+1) ≤ LCDQN(θ̃i+1; θ̃i+1) = LMSBE(θ̃i+1), (13) LMSBE(θ̃i+1) ≤ E [ max { `DQN(θ̃i+1; θ̃i), `MSBE(θ̃i+1) }] = LCDQN(θ̃i+1; θ̃i) ≤ min
θ LCDQN(θ; θ̃i).
(14)
Therefore, we obtain the desired non-increasing condition minθ LCDQN(θ; θ̃i+1) ≤ minθ LCDQN(θ; θ̃i), which means that the iteration θ̃ ← arg minθ LCDQN(θ; θ̃) is convergent, in the sense that the loss is bounded from below and non-increasing.
C-DQN as defined above is convergent for a given fixed dataset. Although the analysis starts from the assumption that θ̃i exactly minimizes the loss, in fact, it is not necessary. In practice, at the moment when the target network θ̃ is updated by θ, the loss immediately becomes equal to LMSBE(θ) which is bounded from above by the loss LCDQN(θ; θ̃) before the target network update. Therefore, as long as 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 LDQN, 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-learning, distributional DQN and soft Q-learning (Van Hasselt et al., 2016; Bellemare et al., 2017; Haarnoja et al., 2017), by modifying the losses `DQN and `MSBE 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.

heading: 5 EXPERIMENTS

heading: 5.1 COMPARISON OF C-DQN, DQN AND RG
text: We focus on the Atari 2600 benchmark as in Mnih et al. (2015), and use the dueling network architecture and prioritized sampling, with double Q-learning where applicable (Wang et al., 2016; 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. 4. We see that both C-DQN and DQN can learn the tasks, while RG almost does not learn, despite that RG has a 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 a few other games are given in the appendix.

heading: 5.2 LEARNING FROM INCOMPLETE TRAJECTORIES OF EXPERIENCE
text: To give an example in which DQN is prone to diverge, we consider learning from incomplete trajectories of experience, i.e. given a transition (st, at, st+1) in the dataset, the subsequent transition (st+1, at+1, st+2) may be absent from the dataset. This makes DQN prone to diverge because while DQN learns Qθ(st, at) based on maxa′ Qθ(st+1, a′), there is a possibility that maxa′ Qθ(st+1, a′) has to be inferred and cannot be directly learned from any data. To create such a setting, we randomly 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 a 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 learning is only slightly reduced. This confirms that C-DQN is 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-first-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 is 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, we show that when the size of the replay memory is reduced by a factor of 10, C-DQN can benefit 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 less off-policy when it is 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.

heading: 5.3 DIFFICULT GAMES IN ATARI 2600
text: 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 γ. However, we find that a large γ does not always result in better performance in practice, because a 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 γ is larger than 0.9999, the order of magnitude of (1 − γ)Qθ gets close to the intrinsic noise caused by the finite learning rate and learning can stagnate. Therefore, we require γ to satisfy 0.99 ≤ γ ≤ 0.9998, and use a simple heuristic algorithm to evaluate how frequent reward signals appear so as to determine γ for each task, which is discussed in detail in the appendix. We also take this opportunity to evaluate the mean µ 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 state-of-the-art test performance on Skiing despite the simplicity of the algorithm.

heading: 6 CONCLUSION AND FUTURE PERSPECTIVES
text: We have discussed the inefficiency issues regarding RG and gradient-TD 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 γ 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 as in Lillicrap et al. (2015).
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.

heading: A CONVERGENCE OF C-DQN IN STOCHASTIC SETTINGS
text: When the transition of states is stochastic, it is well-known that the minimum of LMSBE does not exactly correspond to the solution of the Bellman equation, because we have
LMSBE(θ) = Est+1 [( Qθ(st, at)− rt − γmax
a′ Qθ(st+1, a
′) )2]
= ( Qθ(st, at)− rt − γEst+1 [ max a′ Qθ(st+1, a ′) ])2 + γ2Varst+1(max a′ Qθ(st+1, a ′)),
(15)
where Var(·) represents the variance, and it can be seen that only the first term on the last line corresponds to 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 LMSBE and the solution of the Bellman equation are stationary points for C-DQN. To show this, we first assume that the minimum of LDQN and that of LMSBE are unique and different. If parameters θ and θ̃i satisfy θ = θ̃i = arg minLDQN(·; θ̃i), i.e., if they are at the converging point of DQN, then we consider an infinitesimal change δθ of θ following the gradient of LMSBE in an attempt to reduce LMSBE. Because we have LMSBE(θ) = LDQN(θ; θ) = LDQN(θ; θ̃i), as θ + δθ moves away from the minimum LDQN(θ; θ̃i), we have
LDQN(θ + δθ; θ̃i) > LDQN(θ; θ̃i) = LMSBE(θ) > LMSBE(θ + δθ), (16)
and therefore for θ + δθ, LDQN is larger than LMSBE, and C-DQN will choose to optimize LDQN instead of LMSBE and the parameter will return to the minimum θ, which is the converging point of DQN. On the other hand, given θ = θ̃i = arg minLMSBE(·), if we change θ by an infinitesimal amount δθ in an attempt to reduce LDQN(θ; θ̃i), we similarly have
LMSBE(θ + δθ) > LMSBE(θ) = LDQN(θ; θ̃i) > LDQN(θ + δθ; θ̃i), (17)
and therefore, for the same reason C-DQN will choose to optimize LMSBE and the parameter will return to θ. 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. It 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 a severe problem as demonstrated by the successful application of C-DQN to the Atari 2600 benchmark (see Sec. 5), because the tasks include a 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 a stochastic toy problem, which is known as the wet-chicken benchmark (Tresp, 1994; Hans & Udluft, 2009; 2011). In the problem, a canoeist paddles on a river starting at position x = 0, and there is a waterfall at position x = l = 20, and the goal of the canoeist is to get as close as possible to 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, 0, or +1 in his/her position x, and there is random turbulence z ∼ Uniform(−2.5,+2.5), a uniformly distributed random number, that also contributes to the change in x and stochastically perturbs x at each step. The reward is equal to the position x, and x is reset back to 0 if he/she reaches the waterfall at x = 20. The task does not involve the end of an episode, and the performance 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 a 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. 8. In the left panel of Fig. 8, 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 DQN. This shows that when the task is highly stochastic, although C-DQN
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 Q functions. The distance |Q1 − Q2| between two Q functions Q1 and Q2 is estimated as√∑ (x,a)(Q1(x, a)−Q2(x, a))2, where the summation on the position x is taken over the discrete set {0, 1, 2, ...19}. In the right panel of Fig. 8, we show the estimated distances among the learned Q functions of DQN, C-DQN and RG. We see that the distance between QDQN and QCDQN increases rapidly in the beginning and then slowly decreases, implying that DQN learns quickly at the beginning, and C-DQN catches up later and reduces its distance to DQN. Notably, we find that the value |QCDQN −QDQN|+ |QCDQN −QRG| − |QDQN −QRG| always converges to zero, indicating that the solution found by C-DQN, i.e. QCDQN, lies exactly on the line from QDQN 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 4 hidden layers, each of 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 a factor of 10 and 100 at the 1000th and the 1500th epochs. The discount factor γ 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.

heading: B ADDITIONAL EXPERIMENTAL RESULTS
text: In this section we present some additional results on Atari 2600 games. Results for several other games are presented in Sec. B.1. In Sec. B.2 we show that C-DQN allows for more flexible update periods of the target network. In Sec. B.3 we report the test performance of C-DQN on the difficult Atari 2600 games shown in Sec. 5.3, and in Sec. B.4 we discuss the results of C-DQN on the game Skiing.
B.1 EXPERIMENTAL RESULTS ON OTHER GAMES
In addition to the results in Sec. 5.1, we present results on 6 other Atari 2600 games comparing C-DQN and DQN, which are shown in Fig. 9.
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 as Fishing Derby and Time Pilot, C-DQN may perform less well compared with DQN, probably because the term LMSBE in LCDQN does not properly account for stochastic transitions.
B.2 MORE FLEXIBLE UPDATE PERIODS FOR THE TARGET NETWORK
As C-DQN has a better convergence property, it allows for shorter update periods of the target network. Specifically, convergence of C-DQN is obtained as long as 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 LCDQN(θ; θ̃i) or LDQN(θ; θ̃i) with the target network θ̃i, and then using θ as the next target network θ̃i+1, where Nθ̃ represents the update period of the target network. In previous works on DQN, Nθ̃ is set to be 2000 or 2500 (Hessel et al., 2018; Mnih et al., 2015), and DQN may experience instability for a too small Nθ̃. However, we empirically find that for many tasks in Atari 2600, Nθ̃ can be reduced to 200 or even 20 without instability for C-DQN. Therefore, we find that C-DQN requires less fine tuning on the hyperparameter Nθ̃ compared with DQN. The experimental results on Space Invaders and Hero are shown in Fig. 10, using the experimental settings in Sec. 5.1. We see that C-DQN has a generally higher performance compared to DQN when Nθ̃ becomes small, and the performance of DQN is sometimes unstable and is sensitive to the value of Nθ̃.
B.3 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 at the
end of training, we use the best-performing agent during training to evaluate the test performance. Specifically, we save a checkpoint of the parameter θ of the agent every 104 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 best-performing one among the three agents, and then, we evaluate the test performance of the validated best agent by another 400 episodes, using a different random seed. The policy during evaluation is the -greedy policy with = 0.01„ with noop starts5 (Mnih et al., 2015). The average of the test performances of the 3 runs in our experiments are shown in 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 on Atari 2600 as in Mnih et al. (2015) and Hessel et al. (2018), our C-DQN and the Rainbow DQN in Hessel et al. (2018) allow for a fair comparison because they use the same amount of computational budget and a similar neural network architecture.6 In Table 1, we see that in these four difficult Atari 2600 games Rainbow DQN fails to 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 not 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 is exceptional, which is discussed in the next section.
B.4 THE ATARI GAME Skiing
In Table 1, one exceptional result is that C-DQN achieves a performance higher than Agent57 on the game Skiing, actually, using an amount of computation that is less than 0.1% of that of Agent57.
5No-op starts mean that at the start of each episode the no-operation action is executed randomly for 1 to 30 frames.
6In fact, a fair comparison with Rainbow DQN can be made except for the case of Skiing, because reward clipping adopted by Rainbow DQN does not permit the learning of Skiing. Nevertheless, this does not affect our conclusion.
We find that this performance is higher than any other known result so far and thus achieves the state-of-the-art (SOTA) for this specific game. To elucidate the underlying reason, we describe this game first.
A screenshot of the game Skiing is shown in Fig. 11. This game is similar to a 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 a 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. 11, and whenever the player fails to pass a gate, a 5-second penalty is added to 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 Mnih 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 γ should be at least around 1 − 1500 to make learning effective. However, the learning may still stagnate if γ is not larger, because when γ is small, the agent prefers taking a 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 a larger γ necessary. Therefore, we have chosen to tune our hyperparameter setting so that γ ≈ 1− 15000 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. 12. 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 γ is in favour of this game, while Agent57 uses a more general bandit algorithm to adaptively determine γ.

heading: C RELATED WORKS
text: In this section, we present some related works for further references. The slow convergence of RG compared with TD methods has been shown in Schoknecht & 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 β-mixing, i.e. it converges to a stable distribution exponentially fast. However, this assumption is often impractical, which may have underlain the discrepancy between the theoretical results of RG and the experimental effectiveness. There is an improved version of RG proposed in Zhang et al. (2020), and RG
7The single highest performance we observed was around−3350, and the optimal performance in this game is reported to be −3272 in Badia et al. (2020).
has been applied to robotics in Johannink et al. (2019). Concerning DQN, there have been many attempts to stabilize the learning, to remove the target network, and to use a larger γ. Pohlen et al. (2018) introduces a temporal consistency loss to reduce the difference between Qθ and Qθ̃ on st+1, and the authors showed that the resulting algorithm can learn with γ = 0.999. A 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 DQN variants can sometimes operate without a target network when properly tuned. Achiam 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 is computationally heavy as it uses second-order information, and therefore it cannot be used efficiently with large neural 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.

heading: D CALCULATION DETAILS OF THE CONDITION NUMBER
text: In this section we provide the calculation details of Sec. 3.1. Given the loss function
L = 1
N [ N−2∑ t=0 (Qt − rt −Qt+1)2 + (QN−1 − rN−1)2 ] , (18)
where Q(st, at) is denoted by Qt, we add an additional term (Q0)2 to it, and the loss function becomes
L = 1
N [Q20 + N−2∑ t=0 (Qt − rt −Qt+1)2 + (QN−1 − rN−1)2]
= 1
N [Q20 + N−2∑ t=0 ( Q2t − 2rtQt + 2rtQt+1 − 2QtQt+1 + r2t +Q2t+1 ) + ( Q2N−1 − 2rN−1QN−1 + 2r2N−1 ) ].
(19)
To calculate the condition number of the Hessian matrix, we ignore the prefactor 1N and only evaluate the second-order derivatives. From Eq. (19), it is straightforward to obtain
∂2L ∂Q2t = 4, t ∈ {0, 1, ...N − 1}
∂2L
∂Qt∂Qt+1 = −2, t ∈ {0, 1, ...N − 2}
(20)
and therefore the Hessian matrix is 4 −2 −2 4 . . .
. . . . . . −2 −2 4  N×N . (21)
The eigenvectors of this matrix can be explicitly obtained due to the special structure of the matrix, which are given by (sin kπN+1 , sin 2kπ N+1 , ... sin Nkπ N+1 )
T for k ∈ {1, 2, ...N}, and the corresponding eigenvalues are given by 4 − 4 cos kπN+1 . To show this, we first simplify the Hessian matrix by removing its constant diagonal 4, which only contributes to a constant 4 in the eigenvalues, and then we multiply the eigenvectors by the eigenvalues(
sin kπ
N + 1 , sin
2kπ
N + 1 , ... sin
Nkπ
N + 1
)T · (−4 cos kπ
N + 1 ) = (22)
−2 (
(sin 0 · kπ N + 1 + sin 2kπ N + 1 ), (sin kπ N + 1 + sin 3kπ N + 1 ), ...(sin (N − 1)kπ N + 1 + sin (N + 1)kπ N + 1 ) )T (23)
due to sin nkπN+1 cos kπ N+1 = 1 2 ( sin (n−1)kπN+1 + sin (n+1)kπ N+1 ) . As we also have sin 0·kπN+1 =
sin (N+1)kπN+1 ) = 0, the product of the vector and the eigenvalue is exactly equal to the product of the vector and the Hessian matrix. As the vectors (sin kπN+1 , sin 2kπ N+1 , ... sin Nkπ N+1 )
T are linearly independent for k ∈ {1, 2, ...N}, they are all the eigenvectors of the Hessian matrix, and therefore the eigenvalues are 4−4 cos kπN+1 . The condition number is then κ = 4−4 cos NπN+1 4−4 cos πN+1 . Using the Taylor series expansion, the denominator in the expression of κ is 4− 4 cos πN+1 = 2π2 (N+1)2 +O( 1 N4 ), and therefore for large N , κ ≈ 4−4 cosπ4−4 cos πN+1 ∼ O(N 2).
When the state sN−1 makes a transition to s0, with the discount factor γ, the loss is given by
L = 1
N [ N−2∑ t=0 (Qt − rt − γQt+1)2 + (QN−1 − rN−1 − γQ0)2 ] . (24)
Using the same calculation, the non-zero second-order derivatives are given by
∂2L ∂Q2t = 2 + 2γ2, t ∈ {0, 1, ...N − 1} ∂2L
∂Qt∂Qt+1 = −2γ, t ∈ {0, 1, ...N − 1}, QN = Q0,
(25)
and the Hessian matrix is cyclic. Assuming that N is even, the eigenvectors are given by (sin 2kπN , sin 4kπ N , ... sin 2Nkπ N ) T and (cos 2kπN , cos 4kπ N , ... cos 2Nkπ N )
T for k ∈ {1, 2, ...N2 }, with eigenvalues given by 2(1 + γ2) − 4γ cos 2kπN . The result can be similarly confirmed by noticing the relation sin 2nkπN · (−4γ cos 2kπ N ) = −2γ(sin 2(n−1)kπ N + sin 2(n+1)kπ N ) and the periodicity sin 2(N+1)kπN = sin 2kπ N , and similarly cos 2nkπ N · (−4γ cos 2kπ N ) = −2γ(cos 2(n−1)kπ N + cos 2(n+1)kπN ) and cos 2(N+1)kπ N = cos 2kπ N , which proves that they are indeed the eigenvectors and eigenvalues. At the limit of N →∞, we have κ = 2(1+γ 2)−4γ cosπ
2(1+γ2)−4γ cos 2πN ≈ 2(1+γ 2)+4γ 2(1+γ2)−4γ = (1+γ)2 (1−γ)2 . Using γ ≈ 1, we obtain κ ∼ O (
1 (1−γ)2
) .

heading: E EXPERIMENTAL DETAILS ON ATARI 2600
text: E.1 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 84×84 images, we downscale exactly by a factor of 2, which results in 80×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 st, and decides an action at and executes the action repeatedly for 4 frames in the game and accumulates the rewards during the 4 frames as rt. 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 to collect some initial data before starting the gradient descent. The replay memory stores 1 million transition data, using the first-in-first-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 80×105 images are connected to the output. Following to Hessel et al. (2018), 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 β1, β2 hyperparameters, and we make the agent regard the loss of one life in the game as the end of an episode. The discount factor γ 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 LCDQN upon updating the target network Although we use gradient descent to minimize LCDQN, when we update the target network by copying from θ to θ̃, `DQN(θ; θ̃i) is exactly equal to `MSBE(θ) and the gradient of LCDQN is undefined. In this case, we find that one may simply use the gradient computed from `DQN without any problem, and one may rely on the later gradient descent iterations to reduce the loss LCDQN. In our experiments, we further bypass this issue by using the parameters θ at the previous gradient descent step instead of the current step to update θ̃, 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 `DQN and `MSBE. In Sec. 5.2 we use one half of the mean squared error, and the loss functions are given by
`DQN(θ; θ̃) = 1
2
( Qθ(st, at)− rt − γmax
a′ Qθ̃(st+1, a
′) )2 ,
`MSBE(θ) = 1
2
( Qθ(st, at)− rt − γmax
a′ Qθ(st+1, a
′) )2 .
(26)
In Sec. 5.1 we use the Huber loss, and the loss functions are given by
`DQN(θ; θ̃) = `Huber ( Qθ(st, at), rt + γmax
a′ Qθ̃(st+1, a
′) ) ,
`MSBE(θ) = `Huber ( Qθ(st, at), rt + γmax
a′ Qθ(st+1, a
′) ) ,
`Huber(x, y) =
{ 1 2 (x− y) 2 , if |x− y| < 1,
|x− y| − 12 , if |x− y| ≥ 1.
(27)
In Sec. 5.3, we let the agents learn a normalized Q function Q̂ ≡ Q−µσ , and we use the strategy in Pohlen et al. (2018) to squash the Q function approximately by the square root before learning. The relevant transformation function T is defined by
T (Q̂) := sign(Q̂) (√ |Q̂|+ 1− 1 ) + T Q̂, (28)
and its inverse is given by
T −1(f) = sign(f) (√1 + 4 T (|f |+ 1 + T )− 1 2 T )2 − 1  . (29) In our experiments we set T = 0.01 as in Pohlen et al. (2018), and the loss functions are
`DQN(θ; θ̃) = `Huber ( fθ(st, at), T ( r̂t + γT −1 ( max a′ fθ̃(st+1, a ′) ))) ,
`MSBE(θ) = `Huber ( fθ(st, at), T ( r̂t + γT −1 ( max a′ fθ(st+1, a ′) ))) , (30)
where fθ is the neural network, and T −1(fθ(st, at)) represents the learned normalized Q function Q̂θ(st, at), and r̂t 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
`DQN(θ; θ̃) = ( Qθ(st, at)− rt − γmax
a′ Qθ̃(st+1, a
′) )2 ,
`MSBE(θ) = ( Qθ(st, at)− rt − γmax
a′ Qθ(st+1, a
′) )2 ,
(31)
or,
`DQN(θ; θ̃) = ( fθ(st, at)− T ( r̂t + γT −1 ( max a′ fθ̃(st+1, a ′) )))2 ,
`MSBE(θ) = ( fθ(st, at)− T ( r̂t + γT −1 ( max a′ fθ(st+1, a ′) )))2 .
(32)
When we use double Q-learning (Van Hasselt et al., 2016) in our experiments, all maxa′ Qθ̃(st+1, a ′) and maxa′ fθ̃(st+1, a ′) terms in the above equations are actually replaced by Qθ̃ (st+1, arg maxa′ Qθ(st+1, a ′)) and fθ̃ (st+1, arg maxa′ fθ(st+1, a
′)). This modification do not change the non-increasing property of LCDQN, which can be confirmed easily.
Other details We find that the exploration can often be insufficient when the game is difficult, and we follow Van Hasselt et al. (2016) and use a slightly more complicated schedule for the parameter in the -greedy policy, slowly annealing from 0.1 to 0.01. We have a total computation budget of 5 × 107 steps for each agent, and at the j-th step of the agent, for j ≤ 50000, we set = 1 since the initial policy is random; for 50000 > j ≥ 106, is exponentially annealed to 0.1 following = ej/τ , with τ = 106/ ln(0.1); for 106 > j ≥ 4 × 107, is linearly decreased from 0.1 to 0.01; for j > 4 × 107 we set = 0.01. This strategy allows to stay above 0.01 for a fairly long time and facilitates exploration to mitigate the effects of local optima. We use this schedule in all of our experiments.
We set the learning rate to be 6.25× 10−5 following Hessel et al. (2018) unless otherwise specified. We use gradient clipping in the gradient descent iterations, using the maximal `2 norm of 10 in Sec. 5.1 and 5.2, and 5 in Sec. 5.3. The a hyperparameter for the Adam optimizer follows Hessel et al. (2018) and is set to be 1.5 × 10−4 in Sec. 5.2, but in Sec. 5.1 it is set to be 1.5 × 10−4 for DQN, and 5 × 10−5 for C-DQN and 5 × 10−6 for RG, becaue we observe that the sizes of the gradients are different for DQN, C-DQN and RG. a 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 = (st, at, rt, st+1) ∈ S is sampled with priority pi, which is set to be
pi = (|δi|+ p)α , (33)
where p is a small positive number, α is a sampling hyperparameter, and |δi| is the evaluated Bellman error when di was sampled last time in gradient descent, which is
|δi(DQN)| = ∣∣∣Qθ(st, at)− rt − γmax
a′ Qθ̃(st+1, a
′) ∣∣∣ (34)
for DQN and
|δi(RG)| = ∣∣∣Qθ(st, at)− rt − γmax
a′ Qθ(st+1, a
′) ∣∣∣ , (35)
|δi(C-DQN)| = max { |δi(DQN)|, |δi(RG)| } , (36)
as we have chosen for RG and C-DQN, respectively. The probability for di to be sampled is Pi = pi∑ j pj . To correct the bias that results from prioritized sampling, an importance sampling weight wi is multiplied to the loss computed on di, which is given by
wi =
(∑ j pj
N · 1 pi
)β , (37)
where N is the total number of data and β is an importance sampling hyperparameter. The bias caused by prioritized sampling is fully corrected when β is set to be 1.
Schaul et al. (2015) propose using w̃i := wi
maxj wj instead of wi, so that the importance sampling
weight only reduces the size of the gradient. However, we find that this strategy would make the learning highly dependent on the hyperparameter p in Eq. (33), because given a data with vanishingly small |δi|, its corresponding priority is pi ≈ αp , and therefore the term maxj wj becomes
maxj wj ≈ (∑ j pj N · −α p )β ∝ −αβp . As a result, the gradient in learning is scaled by the term maxj wj which is controlled by α, β and p, and maxj wj changes throughout training and typically increases when the average of |δi| becomes large. For a given a hyperparameter in the Adam optimizer, the overall decrease of the gradient caused by maxj wj is equivalent to an increase of a, which effectively anneals the size of the update steps of the gradient descent. This makes p an important learning hyperparameter, as also noted by Fujimoto et al. (2020), although this hyperparameter 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. 13, which use the experimental settings in Sec. 5.1. It can be seen that the performance is strongly 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 wi instead of w̃i. As |δi| is heavily task-dependent, to remove the dependence of pi on p for all the tasks, we make use of the average p̄ := ∑ j pj
N to bound pi from below instead of simply using p so as to prevents pi from vanishing. Specifically, we set pi to be
pi = max { (|δi|+ p)α , p̄
c̃p
} , (38)
where we set p to be a vanishingly small number 10−10, and c̃p > 1 is a prioritization hyperparameter that controls the lower bound relative to the average. In our experiments we set c̃p = 10. This scheme makes sure that regardless of the size of |δi|, a data is always sampled with a probability that is at least 1c̃pN , and wi is bounded by c̃ β p from above provided that the total priority ∑ j pj does not change too quickly. We adopt this prioritization scheme in all of our experiments except for the experiments in Fig. 13 above. Compared to Fig. 13, it can be seen that our DQN loss and C-DQN loss on Space Invaders in Fig. 4 do not change as much during training.
Details of setting When a new data is put into the replay memory, it is assigned a priority that is equal to the maximum of all priorities pi 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 a priority equal to 100. We also additionally bound wi from above by 2c̃p, so that wi does not become too large even if the total priority ∑ j pj fluctuates. The hyperparameter β is linearly increased from 0.4 to 1 during the 5× 107 steps of the agent, following Schaul et al. (2015), and α is 0.9 in Sec. 5.3 and E.3 and is 0.6 otherwise. We did not try other values of α.
In an attempt to improve efficiency, whenever we use |δi| to update the priority pi of a transition (st, at, rt, st+1), we also use its half |δi| 2 to compute ( |δi| 2 + p)
α, and use it as a lower bound to update the priority of the preceding transition (st−1, at−1, rt−1, st). This strategy accelerates learning by facilitating the propagation of information, and it is especially justified for β = 1, as the prioritization does not change the expected gradient. We use this strategy in all of our experiments
except in Sec. 5.2, in order to make sure that the divergence observed in Sec. 5.2 is not due to this additional strategy.
E.3 EVALUATION OF THE DISCOUNT FACTOR AND NORMALIZATION OF THE LEARNED Q FUNCTION
Evaluation of the discount factor As discussed in Sec. B.4, some tasks require a large discount factor γ, while for many other tasks, a large γ slows down the learning significantly and make the optimization difficult. Therefore, we wish to find a method to automatically determine a suitable γ for a given task. As an attempt, we propose a heuristic algorithm to approximately estimate the frequency of the reward signal in an episode, based on which we can determine γ. The algorithm is described in the following.
Given an episode Ek in the form of an ordered sequence of rewards Ek = (ri)Tk−1i=0 , for which sTk is a terminal state,8 we wish to have an estimate of the average number of steps needed to observe the next non-negligible reward when one starts from i = 0 and moves to i = Tk. Suppose that all rewards {ri} are either 0 or a constant r(1) 6= 0; then, one may simply count the average number of steps before encountering the next reward r(1) when one moves from i = 0 to Tk. However, such a simple strategy does not correctly respect the different kinds of distributions of rewards in time, such as equispaced rewards and clustered rewards, and this strategy is symmetric with regard to the time reversal 0 ↔ Tk, which is not satisfactory.9 Therefore, we use a weighted average instead. To this end we define the return
Ri(Ek) := Tk−1∑ t=i rt, (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
l̂(Ek) = ∑Tk−1 i=0 Ri(Ek) li∑Tk−1 i′=0 Ri′(Ek) , li := min{t | t ≥ i, rt = r(1)} − i+ 1 (40)
where li 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 as it involves Ri, and as the sum is taken over the time steps {0, 1, ...Tk−1}, 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 a trajectory containing different magnitudes of rewards into a few sub-trajectories, each of which contains rewards 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 l̂ over those sub-trajectories as our result. With a set of episodes {Ek}, 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. 1. The weights in line 3 in Alg. 1 ensure that when computing the final result, episodes with a zero return can be ruled out, and that an 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. 1 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 a factor of 2 to correctly represent the frequency of rewards. We also notice that the above approach 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.
8We consider rt to be the reward that is obtained when moving from state st to st+1. 9This 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 at the beginning but almost encounters no reward at the end, the time horizon is not necessarily large. Therefore, 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.
Algorithm 1 Estimation of the expected frequency of observing a next reward signal Input: sample episodes {Ek} Output: an estimate of the inverse of the number of time steps f
1: for Ek ∈ {Ek} do 2: Ek = (ri)Tk−1i=0 ← (|ri|) Tk−1 i=0 . Taking the absolute value of reward
3: wk ← √ R0(Ek) . For computing a weighted average over different episodes 4: j ← 0 5: while rewards Ek = (ri)Tk−1i=0 are not all zero do 6: j ← j + 1 7: E(j)k , Ek ←DECOMPOSESEQUENCE(Ek) 8: end while 9: Compute lk ← ∑ j R0(E (j) k ) l̂(E (j) k )∑
j′ R0(E (j′) k )
. Weighting the results by the contribution of the rewards
10: fk ← 1lk 11: end for 12: Compute f ← √∑ k wk f 2 k∑
k′ wk′ . We use RMS to have more emphasis on episodes with larger fk
13: return f 14: 15: procedure DECOMPOSESEQUENCE(E) 16: r′ ← min{ri}T−1i=0 = min E
17: E ′ ← (r′′i ) T−1 i=0 , r ′′ i := { 0, if ri = 0 r′, otherwise 18: E ← (ri − r′′i ) T−1 i=0 19: return E ′, E 20: end procedure
To obtain the discount factor γ, we set the time horizon to be c̃γf , with a time-horizon hyperparameter c̃γ , and then we set γ = 1 − fc̃γ . To make γ close to 0.9998 for the difficult games discussed in Sec. 5.3, we have set c̃γ = 15. However, later we noticed that the agent actually learns more efficiently with a smaller γ, and c̃γ may be set to range from 5 to 15. In Sec. 5.3, c̃γ = 15 is used, but in the following experiments we use c̃γ = 10.
We make use 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 γ so that it lies between 0.99 and 0.9998, and γ is set to 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 Ek, the Q function, or the value function, as the discounted return in the episode is given by
Qi;k = Tk−1∑ t=i γt−irt, (41)
and we compute its mean µ by taking the average of Qi;k over all states in given sample episodes. The standard deviation of Qi;k, however, has a dependence on c̃γ . If we simply normalize Qi;k by its standard deviation, the magnitude of the reward signal after normalization becomes dependent on the hyperparameter c̃γ , which we wish to avoid. To obtain a normalization that is independent of c̃γ , we assume that rewards are i.i.d. variables with mean µr and standard deviation σr. Focusing on the Q function at the initial states, i.e. Q0;k, we obtain the relation
E [Q0;k] = 1− γTk 1− γ µr, (42)
and therefore we estimate µr by µr = 1NE
∑
kQ0;k 1−γ 1−γTk , with the number of sample episodes NE . Also, we have
Var ( Q0;k −
1− γTk 1− γ µr
) =
1− γ2Tk 1− γ2 σ2r , (43)
and therefore σr can be estimated by the variance of {( Q0;k − 1−γ Tk
1−γ µr
) · √
1−γ2 1−γ2Tk } k .
After obtaining the standard deviation of rewards σr, we need to compute a scale σ to normalize the learned Q function. To avoid c̃γ dependence of σ, we use σr to roughly predict the standard deviation of Q0;k if γ0 ≡ 1 − f2 is used as the discount factor, and we use the obtained standard deviation as the normalization factor σ. For simplicity we ignore the variance of Tk and obtain
σ = σr · 1
NE ∑ k √ 1− γ2Tk0 1− γ20 . (44)
Finally, the function we let the agent learn is Q̂ ≡ Q−µσ .
The normalized function Q̂ also obeys the Bellman equation as well, but with a slightly modified reward. It can be easily shown that
Q̂∗(st, at) = rt − (1− γ)µ
σ + γmax a′ Q̂∗(st+1, a ′) if st+1 is non-terminal, (45)
and Q̂∗(st, at) =
rt − µ σ if st+1 is terminal. (46)
Therefore, the effect of normalization amounts to modifying the reward rt to r̂t := rt−(1−γ)µ
σ , and then assigning an additional terminal reward −γµσ . This is easy to implement and we use this normalization in our experiments in Sec.5.3. Similarly to the evaluation of γ, we use the episodes in the initial 50000 transitions to compute µ and σ; 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 a zero return into account.
Results on other Atari games To demonstrate the generality of the above strategy, we report our results on several games in Atari 2600, using a learning rate of 4 × 10−5 and c̃γ = 10. The results are shown in Fig. 14. 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 × 10−5, 4 × 10−5 and 2× 10−5, and we chose 4× 10−5, 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 γ 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 a 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 γ, and therefore a better strategy is still desired.

heading: F EXPERIMENTAL DETAILS ON CLIFF WALKING
text: 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 a log scale of 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. 1 do not have equally many data points along the curves. The learning rate α is always 0.5, and in the -greedy policy is always fixed. Specifically for the one-way cliff walking task in Fig. 3, when two actions a1 and a2 have the same Q function value, i.e. Q(st, a1) = Q(st, a2), the greedy policy randomly chooses a1 or a2 at state st, and when maxa′ Q(st+1, a′) = Q(st+1, a1) = Q(st+1, a2), we modify the learning rule of RG for transition (st, at, rt, st+1) to be
∆Q(st, at) = α ( rt + γmax
a′ Q(st+1, a
′)−Q(st, at) ) ,
∆Q(st+1, a1) = ∆Q(st+1, a2) = − γ
2 ∆Q(st, at),
(47)
so that the greedy policy at st+1 is not changed after learning from the transition.

Review summaries:
The paper argues that the DQN and its algorithm and its variants do not guarantee convergence and that they can diverge in realistic settings.   The 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. 

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. 

The paper addresses the problem of unstable learning that arises in NFQ type RL methods.  It is assumed that the problem can be overcome by a provably convergent NFQ-like method. Such a provably convergent method is presented and tested on a selection of benchmarks and compared to DQN.