CAN ALTQ LEARN FASTER: EXPERIMENTS AND THEORY
Authors: Bowen Weng
Huaqing Xiong
Yingbin Liang
Wei Zhang
Venue:  (2020)
Keywords: Reinforcement Learning
Q-Learning
Adam
Restart
Convergence Analysis

Abstract: Differently from the popular Deep Q-Network (DQN) learning, Alternating Q-learning (AltQ) does not fully fit a target Q-function at each iteration, and is generally known to be unstable and inefficient. Limited applications of AltQ mostly rely on substantially altering the algorithm architecture in order to improve its performance. Although Adam appears to be a natural solution, its performance in AltQ has rarely been studied before. In this paper, we first provide a solid exploration on how well AltQ performs with Adam. We then take a further step to improve the implementation by adopting the technique of parameter restart. More specifically, the proposed algorithms are tested on a batch of Atari 2600 games and exhibit superior performance than the DQN learning method. The convergence rate of the slightly modified version of the proposed algorithms is characterized under the linear function approximation. To the best of our knowledge, this is the first theoretical study on the Adam-type algorithms in Q-learning. 

Under review as a conference paper at ICLR 2020
CAN ALTQ LEARN FASTER: EXPERIMENTS AND THEORY
Anonymous authors Paper under double-blind review
ABSTRACT
Differently from the popular Deep Q-Network (DQN) learning, Alternating Q- learning (Alt)) does not fully a target Q-function at each iteration, and is generally known to be unstable and inefficient. Limited applications of AltQ mostly rely on substantially altering the algorithm architecture in order to improve its performance. Although Adam appears to be a natural solution, its performance in AltQ has rarely been studied before. In this paper, we first provide a solid exploration on how well AltQ performs with Adam. We then take further step improve the implementation by adopting the technique of parameter restart. More specifically, the proposed algorithms are tested on batch of Atari 2600 games and exhibit superior performance than the DQN learning method. The convergence rate of the slightly modified version of the proposed algorithms is characterized under the linear function approximation. To the best of our knowledge, this is the first theoretical study on the Adam-type algorithms in Q-learning.
INTRODUCTION
Q-learning (Watkins & Dayan, 1992) is one of the most important model-free reinforcement learning (RL) problems, which has received considerable research attention in recent years (Bertsekas & Tsitsiklis, 1996; Even-Dar & Mansour, 2003; Hasselt, 2010; Lu et al., 2018 8; Achiam et al., 2019). When the state-action space is large or continuous, parametric approximation of the Q-function is often necessary. One remarkable success of parametric Q-learning in practice is its combination with deep learning, known as the Deep Q-Network (DQN) learning (Mnih et al., 2013; 2015). has been applied to various applications in computer games (Bhatti et al., 2016), traffic control (Arel et al., 2010), recommendation systems (Zheng et al., 2018; Zhao et al., 2018), chemistry research (Zhou et al., 2017), etc. Its on-policy continuous variant (Silver et al., 2014) has also led to great achievements in robotics locomotion (Lillicrap et al., 2016).
The DQN algorithm is performed in nested-loop manner, where the outer loop follows one-step update of the Q-function (via the empirical Bellman operator for Q-learning). and the inner loop takes supervised learning process to fit the updated (i.e., target) Q-function with neural network. In practice, the inner loop takes a sufficiently large number of iterations under certain optimizer (e.g. stochastic gradient descent (SGD) or Adam) fit the neural network well to the target Q-function.
In contrast, a conventional Q-learning algorithm runs only one SGD step in each inner loop, in which case the overall Q-learning algorithm updates the Q-function and fits the target Q-function alternatively in each iteration. We refer to such a Q-learning algorithm with alternating updates as Alternating Q-learning (Ali)). Although significantll simpler the update rule, AltQ well known to be unstable and have weak performance (Mnih et al., 2016). This is in part due to the fact that the inner loop does not fit the target Q-function sufficiently well. To fix this issue, Mnih et al. (2016) proposed a new exploration strategy and asynchronous sampling schemes over parallel computing units (rather than the simple replay sampling in DQN) in order for the AltQ algorithm to achieve comparable or better performance than DQN. As another alternative, Knight & Lerner (2018) proposed a more involved natural gradient propagation for Alt to improve the performance. All these schemes require more sophisticated designs or hardware support, which may place AltQ less advantagcous compared to the popular DQN, even with their better performances. This motivates us to ask the following first question.

---

Under review as a conference paper at ICLR 2020
Q1: Can design simple and easy variant of the AltQ algorithm, which uses as simple setup as DQN and does not introduce extra computational burden and heuristics, but still achieves better and more stable performance than DQN?
In this paper, we provide an affirmative answer by introducing novel lightweight designs to AItQ based on Adam. Although Adam appears to be a natural tool, its performance in AltQ has rarely been studied yet. Thus, we first provide solid exploration on how well AltQ performs with Adam (Kingma & Ba, 2014), where the algorithm is referred to as AltQ-Adam. We then take a further step to improve the implementation of AlmQ- by adopting the technique of parameter restart (i.e., restart the initial setting of Adam parameters every a few iterations), and refer to the new algorithm as AliQ-AdamR, This is the first time that restart applied for improving the performance of RL algorithms although restart has been used for conventional optimization before.
In a batch of 23 Atari 2600 games, our experiments show that both AlrQ-Adam and AlIQ-AdamR outperform the baseline performance of DQN by 50% on average. Furthermore, AliQ-AdamR effectively reduces the performance variance and achieves much more stable learning process. In our experiments for the linear quadratic regulator (LQR) problems, AltQ-AdamR converges even faster than the moodll-assed value iteration (VI) solution. This is a rather surprising result given that the model-based VI has been treated as the performance upper bound for the Q-learning (including DQN) algorithms with target update (Lewis& & Vrabie, 2009; Yang et al., 2019).
Regarding the theoretical analysis of AllQ algorithms, their convergence guarantee has been ex- tensively studied (Melo et al., 2008; Chen et al., 2019h). More references are given in Section 1.1. However, all the existing studies foeus the AltQ algorithms that take simple SGD step. Such theory is not applicable to the proposed AltQ-Adam and AltQ-AdamR that implement the Adam-type update. Thus, the second intriguing question we address here is described as follows.
Q2: Can we provide the convergence guarantee for AliQ-Adam and AliQ-AdamR or their slightly modified variants (if these two algorithms do not always converge by nature)?
It is well known in optimization that Adam does not always converge, and instead, a slightly modified variant AMSGrad proposed in Reddi et al. (2018) has been widely accepted as an alternative to justify the performance of Adam-type algorithms. Thus, our theoretical analysis here also focuses on such slightly modified variants AliQ-AMSGrad and AIIQ-AMSGradR of the proposed algorithms. We show that under the linear function approximation (which is the structure that the current tools for analysis of Q-learning can handle), both AltQ-AMSGrad and AltQ-AMSGradR converge to the global optimal solution under standard assumptions for Q- learning. To the best of our knowledge, this is the first non-ase asmmayyymttiic convergence guarantee Q-learning that incorporates Adam-type update and momentum restart. Furthermore, slight adaptation of our proof provides the convergence rate for the AMSGrad for conventional strongly convex optimization which has not been studied before and can be of independent interest.
Notations We use |z||| := ||||| = VI to denote the f2 norm of vector and use || max | to denote the infinity norm. When T, y are both vectors, x/ y,, ay, a², vir are all calculated in the element-wise manner, which will be used in the update of Adam and AMSGrad. We denote | +1.
[n] = 1,2,.... n, and | E Z as the largest integer such that |x] < x
1.1 RELATED WORK
Empirical performance of AltQ: AltQ algorithms that strictly follow the alternating updates are rarely used in practice, particularly in comparison with the well-accepted DQN learning and its improved variants of dueling network structure (Wang et al., 2016), double Q-learning (Hasselt, 2010) and variance exploration and sampling schemes (Schaul et al., 2015). Mnih et al. (2016) proposed the asynchronous one-step Q-learning that conceptually close to AltQ with competitive performance against DQN. However, the algorithm still relies on a slowly moving target network like DQN, and the multi-thread learning also complicates the computational setup. Lu et al. (2018) studied the problem of value overestimation and proposed the non-delusional Q-learning algorithm that employed the so-called pre-conditioned Q-networks, which is also computationally complex. Knight & Lerner (2018) proposed natural gradient propagation for AltQ to improve the performance, where the gradient implementation is complex. In this paper, we propose two simple and computationally efficient schemes to improve the performance of AltQ.
2

---

Under review as a conference paper at ICLR 2020
Since proposed in Watkins & Dayan (1992), Q-learning has aroused great interest in theoretic amalysis. The line of theoretic research of AltQ that are most relevant to our study lies in the Q-learning with function approximation. A large number of works study Q-learning with linear function approximation such as Bertsekas & Tsitsiklis (1996); Devraj & Meyn (2017); Zou al. (2019); Chen et al. (2019b); Du et al. (2019), to name few. More recently, convergence of AliQ with neural network parameterization was given in Cai et al. (2019), which exploits the linear structure of neural networks in the overparamterized regime for analysis. It is worth noting that all the existing analysis of AltQ with function approximation considers the simple SGD update, whereas our analysis in this paper focuses on the more involved Adam-type updates.
Theoretical analysis of AltQ:
Convergence analysis of Adam: Adam was proposed in Kingma & Ba (2014) and has achieved great success in training deep neural networks. Kingma & Ba (2014) and Reddi al. (2018) provided regret bounds under the online convex optimization framework for Adam and AMSGrad, respectively. However, Tran et al. (2019) pointed out errors in the proofs of the previous two papers and corrected them. Recently, convergence analysis of Adam and AMSGrad in nonconvex optimization was provided in Zou et al. (2018); Zhou et al. (2018); Chen et al. (2019a); Phuong & Phong (2019), in which the Adam-type algorithms were guaranteed converge to stationary point. To the best of our knowledge, our study is the first convergence analysis the Adam-type of algorithms for Q-learning.
PRELIMINARIES
We consider Markov decision process with considerably large or continuous state space S C RM and action space A C RN with non-negative bounded reward function It : 8 x A - [0, Rmax]. We define (+) C A as the admissible set of actions at state 8, and S - A as a feasible stationary policy. We seek to solve a discrete-time sequential decision problem with y E (0,1) as follows:
maximize (s0) = EE
Σ
7 (((s,
subject to Sc-1 P(-)s
Let (s) == (s)(s) be the optimal value function when applying the optimal policy x². The corresponding optimal Q-function can be defined as
Q" R(s,a) + (BpJJ')
where 8'~ ~ P(-ss, a) and we use the same notation hereafter when no confusion arises. In other words, (s a.) is the reward of agent who starts from state and takes action at the first step and then follows the optimal policy x thereafter.
2.1 ALTQ ALGORITHM
This paper focuses the Alternating Q-learning (AliQ) algorithm that uses parametric function (s,, a; f) to approximate the Q-function with a parameter of finite and relatively small dimension. The update rule of AltQ-learning is given by
TQ(s, a; 0,) R(s, a) + max Q ,',,,';0); d'EU(S')
(3)
0411 0, ar - (Q.(s, -)
θ TQ(s, a;
(r(s,a;00))
(4)
00,
where ae is the step size time f. It is immediate from the equations that AltQ performs the update by taking one step temporal target update and one step parameter learning in an alternating fashion.
2.2 DQN ALGORITHM
As DQN is also included in this work for performance comparison. We recall the update of DQN in the following as reference. Differently from AltQ, DQN updates the parameters in a nested loop. Within the (-th inner loop, DQN first obtains the target Q-function as in Equation (5), and then uses
3

---

Under review as a conference paper at ICLR 2020
neural network to fit the target Q-function by running Y steps of certain optimization algorithm as Equation (6). The update rule of DQN is given as follows.
T TQ(s, a; 02) R(s. a) + max Q d'; 00), d'EU(*))
(5)
0.- = Optimizer(ff;, TÔ(s, az (;)))),
where Optimizer can be SGD or Adam for example, and Equation (6) is thus a supervised learning process with TQ(s, a; p!)) as the "supervisor". At the t-th outer loop. DQN performs the so-called target update as
1-+1= -1 (1- r)6 + +
In practice, when one of the momentum-based optimizers is adopted for Equation (6), such as Adam, it is only initialized once at the beginning of the first inner loop. The historical gradient terms then accumulate throughout multiple inner loops with different targets. While this stabilizes the DQN training empirically, it is still lack of theoretical understanding on how the optimizer affects the training with various moving targets. As we will discuss in detail in Section 5, the analysis of AItQ with Adam can potentially shed light on such ambiguity and inspire future work for this matter.
Note that AllQ and DQN mainly differ at how the Q-function evolves after each step of sampling. fair comparison between the algorithms should be made without introducing dramatic difference on gradient propagation (Knight & Lerner, 2018). policy structure, exploration and sampling strate- gies (Mnih et al., 2016). In practice. the vanilla Alt is often slow in convergence and unstable with high variance. To improve the performance, propose to incorporate Adam and restart schemes, which are easy to implement and yield improved performance than DQN.
3 ACCELERATED ALTERNATING Q-LEARNING ALGORIHTMM
In this section, we first describe how to incorporate Adam to the AllQ algorithm, and then introduce a novel implementation scheme to improve the performance of AllQ with Adam.
AltQ with Adam-type update We propose a new AllQ algorithm with Adam-type update (AliQ- Adam) as described Algorithm Its update is similar to the well-known Adam (Kingma & Ba, 2014). The iterations evolve by updating the exponentially decaying average of historical gradients (m²) and squared historical gradients (w²). The syper--prrmmttrs 31, .32 are used to exponentially decrease the rate of the moving averages. The difference between Algorithm 1 and the standard Adam in supervised learning is that in AltQ, there is no fixed target to "supervise" the learning process. The target is always moving along with iteration t, leading to more noisy gradient estimations. The proposed algorithm sheds new light on the possibility of using Adam to deal with such unique challenge brought by RL.
AltQ-Adam with momentum restart We also introduce the restart technique to AltQ-Adam and propose AltQ-Adamb the historical gradient direction. When part of the historical information is incorrect, the estimation error tends to accumulate. The restart technique restart the momentum-basee restart iteration r, we reset m,, Uy. i.c., m. 0, U,- = O, which yields 0,41 0,. It is intuitive implementation technique to adjust the trajectory from time to time, and can usually help mitigate the aforementioned problem while keeping fast convergence property. For the implementation. we execute the restart periodically with period r. It turns out that the restart technique can significantly improve the numerical performance, which can be seen in Section
Algorithm 2. Traditional momentum-basee algorithms largely depend on
be employed to deal with this issue. One way to methods is to initialize the momentum at some restart iteration. That is,
4 EMPIRICAL PERFORMANCE
We empirically evaluate the proposed algorithms in this section. The linear quadratic regulator (L.QR) is a direct numerical demonstration of the convergence analysis under linear function approximation which will be discussed in the next section. Atari 2600 game (Bellemare et al., 2013; Brockman et al., 2016), a classic benchmark for DQN evaluations, is also used to show the effectiveness of the proposed algorithms for complicated tasks. In practice, we also make small adjustment to the proposed algorithms. That is, re-scale the loss term of L(O.)= = (8, 0.) TQ(s, a;
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Alam
1: Input: 07,01, 31, B2, C,y, = 0, = O.
2: for t= 1,2,.....
do
3:
(Q(8, a; 0t) = R(s,a) a) +y Q(s',
4:
gr Q1(ss,a; a;), -TQ(s, a;b,), 30, ac(s,
5:
me (1 1-) 3100
6:
Ut (1 12 + 329
7: 0++1 0 -1 Vucte
8: end for
9: Output: 0K
Algorithm 2 AllQ-AAamm
1: Input: 17, 01,01,81 BL, B2, 7, mo 0, 0,
2: for t == 1, 1.2....; K do
3: if r) =0 then
4:
m. = 0. U1 =0
5:
end if
6:
TQ(s, az 0z) = R(s,00 a) + max a';','';0,
7:
9t = Qu(5, a; 0.) TQ(s, a; 81) 00, Q((s,
8:
my
81 -1)ma-11 31
9:
UF = (1 U-1 + 329
10:
Oc+1 = 0+ Verte
me
11: end for
Output: 0K
in Equation (4) as L(,)) (0,, with some scaling factor i (0, 1]. which is beneficial for stabilizing the learning process.
We find that in both experiments, AltQ-AdamR outperforms both AltQ-Adam and DQN in terms of convergence speed and variance reduction. Compared with DQN in the empirical experiments of Atari games, under the same hyper-parameter settings, AltQ-Adam and AltQ-AdamR improve the performance of DQN by 50% on average.
4.1 LINEAR QUADRATIC REGULATOR
We numerically validate the proposed algorithms through an infinite-horiue discrete-time time LQR problem whose background can be found in Appendix A. A typical model-based solution (with known dynamics), known as the discrete-ting algebraic Riccati equation (DARE), is adopted to derive the optimal policy nt - K"*;, The performance of the learning algorithm is then evaluated at each step of iterate & with the Euclidean norm |KK, K* ||. The performance result for each method is averaged over 10 trials with different random seeds. All algorithms share the same of random seeds and are initialized with the same 0g. The hyper-parameters of the learning settings are also consistent and further details are shown in Table Note that for all the implementations, we also adopt the double Q Q-update (Hasselt, 2010) to help prevent over-estimations of the Q-value. The performance results are seen in Figure Here we highlight main observations from the LQR experiments.
AltQ-AdamR outperforms DARE In ideal cases where data sampling perfectly emulates the system dynamics and the target is accurately learned in each inner loop, DARE for LQR would become equivalent the DQN-like update the neural network is replaced with a parameterzied linear function. In practice, such ideal conditions are difficult to satisfy, and hence the actual Q-learning with target update usually far slower (in terms of number of steps of target updates) than DARE. Note that AltQ-AdamR performs significantly well and even converges faster than DARE, and thus implies it faster than the most well- perfforing Q-learning with target update,
AltQ-AdamR outperforms AltQ-Adam Overall, under the same batch sampling scheme and restart period, AltQ-AdamR achieves a faster convergence and smaller variance than AlrQ-Adam.
5

---

Under review as a conference paper at ICLR 2020
AltQ
AltQ-AdamR DARE
2009
DQN
AltQ-Adam
375%
AltQ-Adaam AltQ-Adamm
Normalized Return
225%
LOSS
800%
50%
25%
0.0
40000
80000
120000
100000
Steps
Steps
Figure 1: LQR experiments with performance Figure 2: Atari game experiment with perfor-
evaluated in terms of policy loss |K; K+ mance normalized and averaged over 23 games.
Table I: flyper-parametert for LQR experiments
Step size 0.0001
Adam $1
Adam 82 0.999
Restart period
Stop criterion
?
0.01
0.9
100
K
K 1 I 10
4.2 ATART GAMES
We apply the proposed AllQ algorithms to more challenging tasks of deep convolutional neural network playing group of Atari 2600 games. The particular DQN we train compare against adopts the dueling network structure (Wang et al., 2016), double Q-learning setup (Van Hasselt et al., 2016), e-greedy exploration and experience replay (Mnih al., 2013). Adam also adopted, without momentum restart, as the optimizer for the inner-loop supervised learning process. AltQ-Adam and AlrQ-AdamR are implemented using the identical setup of network construction, exploration and sampling strategies.
We test all the three algorithms with batch of 23 Atari games. The choice of 10 million steps of iteration is a common setup for benchmark experiments with Atari games. Although this does not guarantee the best performance in comparison with more time-consuming training with 50 million steps or more, it is sufficient to illustrate different performances among the selected methods. The software infrastructure based on the baseline implementation of OpenAl. Selections of the hyper- parameters are listed in Table 2. We summarize the results in Figure 2. The overall performance is illustrated by first normalizing the return of each method with respect to the results obtained from DQN, and then averaging the performance of all 23 games to obtain the mean return and standard deviation. Considering we use a smaller buffer size than common practice, DQN is not consistently showing improved return over all tested games. Therefore. the self-normalizer average return of DQN in Figure is not strictly increasing from 0 to 100%.
Overall. both Adam and AliQ- achieve significant improvement in comparison with the DQN results. While AltQ-Adam is suffering from a higher variance, periodic restart (AliQ- AdamR) resolves the issue efficiently with on-par performance average and far smaller variance. Specifically, in terms of the maximum average return, Al(Q-Adam and AlrQ-AdamR perform no worse then DQN 17 and 20 games respectively out of the 23 games being evaluated.
CONVERGENCE ANALYSIS
In this section, we characterize the convergence guarantee for the proposed AltQ-learning algorithms. Furthermore, like most the related papers, we focus on convergence analysis under the linear approximation class. Understanding the analytical behavior in the linear case is an important stepping stone to understand general cases such as deep neural network. A linear approximation of the Q-function ((s, a; 0) can be written as
Q(s, 0) = ((s, a)=
where 0 E Rd and & S x A + Rd is a vector function of size d, and the elements of represent the nonlinear kernel (feature) functions.

---

Under review as a conference paper at ICLR 2020
Table Flyper-parameters for Atari games experiments DQN, AliQ-Adam and AliQ-AdamR
Step size
Scale factor 7
Adam 31
Adam 08
Restart period r
Buffer size
0.0001
0.0001
0.9
0.999
10a
106
7
Batch size
Total training steps K
Target update frequency (DQN only)
0.99
32
10?
10a
5.1 MODIFICATION OF ALGORITHMS
Although Adam has obtained great success as an optimizer in deep learning, it is well known that Adam by nature is non-convergent even for simple convex loss functions (Reddi al., 2018). Instead, slightly modified version called AMSGrad (Reddi et al., 2018) 8) is widely used to study the convergence property of the Adam-type algorithms. Compared with the update rule of Adam, AMSGrad makes the sequence Gt.5 increasing along the time step / for each entry E [d]. Here, we apply the update rule AMSGrad to the AltQ algorithm and refer to such an algorithm as AltQ-AMSSrad Algorithm
3 describes AltQ-AMSS AMrr-Ad in detail, where 11, v. (0') ) min DED
V/1/4 (0'- -0'-)) 0) Correspondingly,
we introduce Alto-AMSrraRR which applies the same update rule as Algorithm but resets m,, 0, with period of i.e., m, 0, 02 0, vl kr, k 1...
Algorithm 3 AltQ-AMSGrad
1: Input: 0, X, f1, 82, mo = O, 00 = O.
2: for i 1,2.... .... do
3: at Vi Si = 31
4:
9t 0 (81,0;)0, r();, max (8441, (1))
5:
m = (1- B1 m, 1 -3r
6:
Ut (1 (32 + G29
7:
0, max 1 vt), V. diag(Ur...... 04)
8:
0.+11 11 piy/
(O V. ? mm
9: end for
Output: 1 -T B₂
5.2 MAIN RESULTS
Our theoretical analysis here focuses on the slight variants, AltQ-AMSGrad and AltQ-AMSGradR. Before stating the theorems, first introduce some technical assumptions for analysis.
Assumption 1. At each iteration t, the noisy gradient is unbiased and uniformly bounded, i.e. 9t 9: + & with EE 0 where ge Blgr]. and l[gell Go Vt. Thus l|gelloo Go and 1 < G22
Assumption 2. (Chen al., 2019b, Lemma 6.7) The equation g(0) 0 has unique solution 6*, which implies that there exists a c > 0, such that for any E Red we have
(9 TT (0) c 1'1
Assumption 3. The domain C R.d of approximation parameters is ball originating at with bounded diameter containing 0* That is, there exists D such that |00m 0,11 < Doo, vo... O, D, and E D.
Assumption 1 is standard in the theoretical analysis of Adam-type algorithms (Chen et al., 2019a; Zhou et al., 2018). Under linear function approximation and given Assumption 3 and bounded r(-). Assumption 1 is almost equivalent to the assumption of bounded Φ(-) which is commonly taken in related RL work (Tsitsiklis & Van Roy, 1997; Bhandari et al., 2018). Assumption 2 has been proved key technical lemma in Chen et al. (2019b) under certain assumptions. Such an assumption appears to be the weakest the existing studies of the theoretic guarantee for Q-learning with function approximation.
7

---

Under review as a conference paper at ICLR 2020
We next provide the convergence results of AltQ-AMSGrad and AIQ--AMSradR under linear function approximation in the following two theorems.
Theorem 1. (Convergence of AltQ-AMSGrad Suppose
V/E' $1c = 31 and 5 = 3/1/32 with A E (0. for 1,2,... Algorithm 3. Given Assumptions I 3, the output of AlrQ-AMSGral
satisfies:
B1 T
B2TT T
Bav + log T
E oot 10 S
+
Σ
E 11r,,
(10)
T
==1
where B
2azc(1-8:)
Gx D2
+
2ac
8,Gx
D2
+ 110 - -0-102 B2
2ac(1-B.)'
dG D
and B3
=
(11+81)
2c(1
In Theorem 1, B1, B2, B3 in the bound in Equation (10) are constants and independent of time. Therefore, under the choice of the stepsize and hyper-parameters in Algorithm 3. AlIQ-AMSSra
achieves convergence rate of O when Ei= |1g.r << VT which is justified in Duchi et al. (2011).
Remark 1. Our proof of convergence here has two major differences from for AMSGrad in Reddi et al. (2018): (a) The two algorithms are quite different. AlrQ-AMSGrad is a Q-learning algorithm alternatively finding the best policy, whereas AMSGrad is an optimizer for conventional optimization and does not have alternating nature. (b) Our analysis is on the convergence rate whereas Reddi et al. (2018) provides regret bound. In fact, slight modification of our proof also provides the convergence rate of AMSGrad conventional strongly convex optimization, which can be of independent interest. Moreover, our proof avoids the theoretical error the proof in Reddi el al. (2018) pointed out by Tran et al. (2019).
In the following theorem, we provide the convergence result for AIQ-AMSGradR. Theorem 2. (Convergence of AlrQ-AMSGnadR) Under the same condition of Theorem the output of Alt--AMSGradR satisfies:
B1 T
BaV1 log T
d 11g.T +
B3
r//
E 10ot - 0-1
+
VT+
Σ
v kr
T
(11)
T/+]
D2
v kr + 4c(1 - LE 1|0kr 0¹11)
a
k=0
where Bi
8 D. Goz 2ac(I-Bi(1--x-
B2
P1-0-11) and B3 2ac(1 -3.)
a(l+B:
dG D2
Theorem 2 indicates that for AltQ- AMMGradRR to enjoy a convergence rate of O the restart
period needs to be sufficiently large and Dim |IghT << VT. practice as demonstrated by the experiments in Section 4, AlrQ-AMSGradi typically performs well, not necessarily under the theoretical conditions.
CONCLUSION
We propose two types of the accelerated AliQ algorithms, and demonstrate their superior performance over the state-of- oftt--of-hhearne games.
the-art art through a linear quadratic regulator problem and a batch of 23 Atari 2600
Notably, Adam is not the only scheme in the practice for general optimization. Heavy ball (Ghadimi al., 2015) and Nesterov (Nesterov, 2013) are also popular momentum- methods. When adopting such methods in AltQ-learning for RL problems, however, we tend to observe a less stable learning process than AltQ-Adam. This is partially caused by the fact that they optimize over shorter historical horizon of updates than Adam. Furthermore, the restart scheme provides somewhat remarkable performance in our study. It is thus of considerable future interest to further investigate the potential of such scheme. One possible direction is to develop with changing period determined by an appropriately defined signal of restart. This will potentially relieve the effort in syper-paramest tuning of finding a good fixed period.
adaptive restart mechanism
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence deep Q-learning. arXiv preprint arXiv:1903, 08894, 2019.
Itamar Arel. Cong Liu, T Urbanik, and A.G. Kohls. Reinforcement learning based multi aulti-agentt system for network traffic signal control. IET Intelligent Transport Systems, 4(2): 1331228--3,-00 2010.
Mare 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.
Dimitri P. Bertsekas and John N Tsitsiklis. Neuro-Dyaamic Programming, volume 5. Athena Scientific, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. arXiv preprint 1.Kiv:1800.0245000 2018.
Shehroze Bhatti, Alban Desmaison, Ondrej Miksik. Nantas Nardelli, N. Siddharth, and Philip H.S. Torr. Playing doom with slam-augmented deep reinforcement learning. arXiv preprint 161iv: 1612.00380, 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1606.00600.1555550000 2016.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural lemporal-difference learning converges global optima. arXiv preprint a90iv: 10025 2019.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019a.
Zaiwei Chen, Sheng Zhang, Thinh Doan, Siva Theja Maguluri, and John-Pau Paul Clarke. Finite-time analysis of Q-learning with linear function approximation. arXiv preprint arXiv: arXiv:1905. 1425, 2019b.
Adithya M Devraj and Sean Meyn. Fastest convergence for Q-learning. arXiv preprint arXhv:1707.03770, 2017.
Simon S Du, Yuping Luo, Ruosong Wang. and Hanrui Zhang. Provably efficient Q-learning with func- tion approximation via distribution shift error checking oracle. arXiv preprint vrXiv:1906. 06321, 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, Jul 2011.
Eyal Even-Dar and Yishay Mansour. Learning rates for Q-learning. Journal of Machine Learning Research, 5:1-25, Dec 2003.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In Proceeding of IEEE European Control Conference (ECC), pp. 310-315, 2015.
Hado Hasselt. Double Q-learning. In Advances in Neural Information Processing Systems, pp- 2613-2621, 2010.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint 1rXiv:1412.6988. 2014.
Ethan Knight and Osher Lerner. Natural gradient deep Q-learning. arXiv preprint arXiv:1803.0748.. 2018.
F. L. Lewis and D. Vrabie. Reinforcement learning and adaptive dynamic programming for feedback control. IEEE Circuits and Systems Magazine, 9(3)322-50 Third 2009. doi: 10.110///AAS2000 933854.

---

Under review as a conference paper at ICLR 2020
Frank L Lewis and Kyriakos G Vamvoudakis. Reinforcement learning for partially observable dy- namic processes: Adaptive dynamic programming using measured output data. IEEE Transactions Systems, Man, and Cybernetics, Part B (Cybernetics), 41(1):14-255 2011.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Tyler Lu, Dale Schuurmans, and Craig Boutilier. Non-delusional Q-learning and value-iteration. In Proceedings of the T'hirty-second Conference on Neural Information Processing Systems (NeurIPS- 18), pp. 9971-9981 Montreal, QC, 2018.
Borislav Mavrin, Hengshuai Yao, and Linglong Kong. Deep reinforcement learning with decorrelation. arXiv preprint arXiv:1903.07700 2019.
Francisco S. Melo, Sean P. Meyn, and M. Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th International Conference on Machine Learning, ICML '08. pp. 664-671, 1, New York, NY, USA, 2008. ACM. ISBN 978-1-60555-205-5
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:/312.5600 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra. Shane Legg. and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of The 33rd International Conference Machine Learning, volume 48, pp. 1928-1937. PMLR, 20-22 Jun 2016.
Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013.
Tran Thi Phuong and Le Tricu Phong. On the convergence proof of AMSGrad and new version. arXiv preprint 1904:0390 2019.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05952. 2015.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In ICML, 2014.
Phuong Thi Tran al. On the convergence proof of AMSGrad and a new version. IEEE Access, 7: 11706-61716 2019.
John N. Tsitsiklis and Benjamin Van Roy. Analysis of temporal -ifffeeeee learning with function approximation. In M. C. Mozer, M. Jordan, and T. Petsche (eds.), Advances in Neural Information Processing Systems 9, pp. 1075-1081. MIT Press, 1997.
Kyriakos Vamvoudakis. Q-learning for continuous time linear systems: model-free infinite horizon optimal control approach. Systems & Control Letters, 100:14-20, 2017.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
10

---

Under review as a conference paper at ICLR 2020
Draguna Vrabie, O. Pastravanu, Murad Abu-Khalaf, and Frank L. Lewis. Adaptive optimal control for continuous-timg time linear systems based on policy iteration. Automatica, 45(2):477-444 2009.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML'16 16, pp. 1995-2003. JMLR. 2016.
Christopher J.C.H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):279 21099999922222 1992.
Zhuora Yang, Yuchen Xic, and Zhaoran Wang. A theoretical analysis of deep Q-learning. arXiv preprint 1rXiv:1901.01133. 2019.
Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep reinforce- ment learning for page-wise recommendations. In Proceedings of the 12th ACM Conference on Recommender Systems, pp. 95-103, 2018.
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. DRN: A deep reinforcement learning framework for news recommendation, In Proceedings of the 2018 World Wide Web Conference on World Wide Web, pp. 167-176, 2018.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint 1rXiv:1808.056777 2018.
Zhenpeng Zhou, Xiaocheng Li, and Richard N Zare. Optimizing chemical reactions with deep reinforcement learning. ACS Central Science, 3(12);13371144, 2017.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for conver- gences Adam and RMSProp. arXiv preprint arXiv: 1811.0011000 181.00938,,,, 2018.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA and Q-lcarning with linear function approximation. arXiv preprint arXiv: 1902.0224,, 2019.

---

Under review as a conference paper at ICLR 2020
Supplementary Materials
A
FURTHER DETAILS AND RESULTS ON EXPERIMENTS
We discuss more details on the experiment setup and provide further results that are not included in Section 4.
A.1 LINEAR QUADRATIC REGULATOR
The linear quadratic regulator (LQR) problem is of great interest for control community where Lewis al. applies PQL to both discrete-time problems (Lewis & Vrabie, 2009; Lewis & Vamvoudakis, 2011) 1) and continuous-ting time problems (Vamvoudakis,, 2017; Vrabie et al., 2009).
We empirically validate the proposed algorithms through an infinite-horizon discrete-time LQR problem defined as
minimize
J - It Qui + ut Ru, + 2x Nu:)
subject to
ft-1 Ax + Bui
where u, = (1ze).
A typical modell-baeed solution (with known A and B) considers the problem backwards in time and iterates dynamic equation known as the time algebraic Riccati equation (DARE):
P = A PA - (A" + ( PD PA+ N²) + Q,
(12)
with the cost-to-go P being positive definite. The optimal policy satisfies ut = - xt with
K (R BBB + PA).
(13)
For experiments, we parameterize quadratic Q-function with matrix parameter H in the form of
Haz
H
Qxx, u; H)
(14)
Hus
Hus
u
The corresponding linear policy satisfies Kw. and K = H.rHHus The performance of the learning algorithm is then evaluated at each step of iterate i with the Euclidean norm || K K*1 1l2--
A.2
ATARI GAMES
We list detailed experiments of the 23 Atari games evaluated with the proposed algorithms in Figure 3. All experiments executed with the same set of random seeds. Each task takes about 20-hour of wall-clock time on GPU instance. All three methods being evaluated share similar training time. AliQ-Adam and AliQ-AdamR can be further accelerated practice with a more weeoory-efficiee implementation considering the target network is not required. We keep our implementation of proposed algorithms consistent with the DQN we are comparing against. Other techniques that are not included in this experiment are also compatible with AltQ-Adam and AltQ-AdamR, such like asynchronous exploration (Mnih et al., 2013) and training with decorrelated loss (Mavrin et al., 2019).
Overall, AlrQ-Adam significantly increases the performance by over 100% in some of the tasks including Asterix, BeamRider, Enduro, Gopher, etc. However, it also illustrates certain instability with complete failure Amidar and Assault. This is mostly caused by the sampling where are using a relevantly small buffer size with 10% of the common configured size Atari games with experience replay. Notice that those failures tend to appear when the e-greedy exploration has evolved to a certain level where the immediate policy is effectively contributing to the accumulated experience. This potentially amplifies the biased exploration that essentially leads to the observed phenomenon.
Interstingly, AltQ- AdamR that incorporates the restart scheme resolves the problem of high variance of average return brought by AliQ-Adam and provides a more consistent performance across the task
12

---

Under review as a conference paper at ICLR 2020
domain. This implies that momentum restart effectively corrects the accumulated error and stabilizes the training process.
Abm
Lmitor
Anouue
2.
12
MM
DON
Acamm
Andwers sl
06
lewwiigg
traryCltbbe
175
indum
125
100
36
020
264
PabingDartt
0.
-20
-00
00
Copher
Jammenbond
150
675
Pual
Obee
100000
-10
-30
-20
-24
-30
-20
Spacefrorders
30
Figure 3: Experiment results of 23 Atari games with DQN, AltQ-Adam and AlIQ-AdamR
13

---

Under review as a conference paper at ICLR 2020
Task
DQN
AltQ-Adam
AltQ-AdamR
Alien
1529
1125
1587
Amidar
269
313
551
Assault
1925
260
2097
Asteroids
1147
1394
1069
Asterix
11794
22413
17064
BeamRider
5728
10210
6458
Bowling
60
45
30
CrazyClimber
116422
102731
121770
Enduro
866
1671
1291
DemonAttack
5729
10485
9273
DoubleDunk
-14
-12
-15
Fish
29.01
4
19
Gopher
6066
16863
9508
Gravitar
316
551
518
Jamesbond
663
899
756
Pitfall
-76
-20
-7
Pong
20.68
20.79
20.74
Qbert
13453
12487
14352
Robotank
56
34
42
Seaquest
3652
6121
6624
Spaceinvaders
923
1528
1036
Tennis
-17
-5
Tutankham
159
194
191
Table 3: Best empirical return of 23 Atari games with DQN, AltQ-Adam and AltQ-AdamR
B PROOF OF THEOREM
Different from the regret bound for AMSGrad obtained in Reddi al. (2018), our analysis is on the convergence rate. In fact, slight modification of our proof also provides the convergence rate for AMSGrad for conventional strongly convex optimization, which can be of independent interest. Moreover, proof avoids the theoretical error in the proof in Reddi et al. (2018) pointed out by (Tran et al., 2019). Before proving the theorems, we first provide some useful lemmas.
Lemma 1. (Zhou al., 2018, Lemma A. Let (gt, m,, 01) for 1,2, ... be sequences generated | < Goo, || S G
by Algorithm 3 and 0r = B.g.). Under Assumption 1, 11 S Goe,
Lemma 2. (Reddi al., 2018, Lemma 2) Let {m,, V.) for t 1,2,... be sequences generated by Algorithm 3. Given (k, 3ic, B2 as specified in Theorem we have
1 Σ
a2
me
S - (1-81)(1 - 8) I B2
1grr.
t
(15)
avi + TogT
11
(1 31)(1 - 8) 32
Lemma 3. Let Vi and 31 = 31 for = 1,2, Then
T
31 <
B1 a(1
(16)
ai
X)2'
Proof. The proof is based on taking the standard sum of geometric sequences.
T
B1
T
3
31
1
Σ
T
1-
-TX²)
-x²)
< a(1
B
(17)
X
x)2
1=1
t=1
14

---

Under review as a conference paper at ICLR 2020
With the lemmas above, we ready to prove Theorem 1. Observe that
01+1 D. (o: a.V, m.)
1/4 (B.-auV, V. m. f)|
min BED
Clearly 11 p/pp Or due to Assumption 3. We start from the update of 0g when 2 2.
(0L1 01)l
|T 1/1/11 (0:-0- vet,z1nn mm:))
|o:// (0: -0 -avee mc) 11
(0, - 03 || + Ore V. 1/4 me
20, (0; )
(0: - 83) +
ar V2 1/1
2a (0: - (B + (1 B1e)ge)
(0: - 83) + as V1 1/4
m
me
2 +
1/114(00 (0. - 03)l + as 11 1/4 me-1 12)
1/4
-2 - (0, 0²)"'H gt
vi (0, - 03) 11 + | V,
1/4
Vi + a (0, 03)1² -0)1
1/4
m |
mix
+ Biz
-2ar(1 (0, 0-)""a.
where (i) follows from the Cauchy- Ssuchy-Schrve Schwarz inequality, and (ii) holds because f441.5 2 62.s, Vt, vi. Next, we take the expectation over all samples used up to time step t on both sides, which still preserves the inequality. Since we consider i.i.d. sampling case, by letting F, be the filtration of all the sampling up to time I, we have
= E [(e, - -=0 (O.- - T g.) = E E (0. - - 9i] [F-1]
(18)
Thus have
b /4 (0e+1 -8t //
E
E
12 (0: - 0-)1 112 + aZ 1/ 1/4
1/mm///m m+
1 + BnB 1/. 1100-0% o/)l - + af
vi-1/ m
2a, BB EL/1 [00 0²) 9.]
E
V/:1//(0/ (0/ - 0*) 1| + aB 1/2
1/4 m+
2
+ BrB
B (0. 0/)l + a V m
-2a((1 B1.) [(0 8T) (
m
E (0. 0r) 2 E
V.
1/4 m+
2
+ BirB
1/11100 (0. 0// + B1
| m
2
- -2, - B,,)
10 - 1²
(1)
< E 1/1/4(0 0*) 2 + a
1.- 1/4 me
+ B 1/114(0, 00)1² -0.0))) + 0
V
1/-1/4 m
1
20yc(1 E 100 11
(
E (0,1 0*) I||
+ af
V.- 1/4 mel 2 Goo B1 a3 E
/4 m,
2
-2a,c(1 - E1)E [|0, - 8-11" 112
where (i) follows from Equation (18), (ii) follows due to Assumption 2 and 1 B1 > 0. (1i)
follows from 31e < B1 < and E 000 - 1-2 > 0, and (iv) follows from || [ V/11/(0 (0: - 0*) <
1///4/2 || 2 00 - 0-112 s G D& by Lemma I and Assumption We note that (iii) is the key step to
15

---

Under review as a conference paper at ICLR 2020
avoid the error in the proof in Reddi et al. (2018), where can directly bound BIe, which is impossible in Reddi et al. (2018). By rearranging the terms in the above inequality and taking the summation over time steps, have
T
2c(1 - -1)
Σ
E 110
0-12
1=2
T
1
E
- -0t))= -00)|²-E -18
-By)|=
(0+41
(0++1 (0+11-000) - =0)1())
+ Σ
G0 Da
04
t=2
t=
1/-1/4
1/4 me/ || + Σ
3 E V/ 1 m
1 mm=1a 1|
1/2
a,E
T
E
1//1/411 (Bc
- -80) /²
-E
V/ 1/1 (81+1 - 0 0))(²)
+
T Gr
D
at
at
1=2
t=2
T
ag
11
me
1/4 me
| +
Σ
a 11 1/:1//mm m ||
1
1=2
t=2
T
1
E
8/11;1//400 (0,
-0+)|²
-IE Vi 1/4 (0++1 (0 -0>11²
(0.41-
+ +
31 Do
at
022
t=2
t=2
(1 + 31)
aB
11
1/4 m
2
where (i) follows from a₂ < a--1- With further adjustment of the first term in the right hand side of the last inequality, we then bound the sum as
T
20(1 - 31)
Σ
E 100 - 11
2=
1
E
1//1/100 - -0)11= 11111
Σ
T
3o
D3
1=2 a1
a
(1 + B1) Σ
arE 1/- 17-1/44 1/4my/ m+
+
12 /4 (02 -0r]"
1
1/114 (0. 0²)
1////00 0r)
E
T
+
E
a2
04
a1-1
t=3
E
(0r+1 (1 (4))
T
B1 Goc D2
a.E V, 1/4 me ||
+ (1 + B1)
Σ
ar
1 /4 (02 0r)|
E
T
1/2
(0e, 01)²
Σ
1/2 0,2,, (Bc. - 67)²
Liz1 ii=
Li=1
+
E
a2
04-1
1=3
1/4 (OT+1 0*)
12
E
T
Go D2
+
(1+ 81)
T Σ
a
V
1/4 me
||
OT
04
t=2
1=1
E
1/4 (02
-0+)"
T Σ
1/2
1/2
E(O,,5 - 8:72
11-1,1
a2
a1-1
t=3 im
E
42/4 (0r+1
8*)
1
T
BuG D2
T Σ
+ (1 + B1)
a
17-1/4
mp
OT
2=
1=1
16

---

Under review as a conference paper at ICLR 2020
So far we just rearrange the terms in the series sum. Next, are ready to obtain the upper bound.
2c(1
(1) E 110
Σ
1²12
t=2
E
122 1/14 (02
0*) 2
1/2
1//2
D
E
1,2
1-11
a2
at-1
22/4 (0T+1 8*)
2
E
Do
(1+ B1)
Σ a,E
V.
1/4
m4
OTT
at
5
E
1/4 (02
8*)
2
DD=
T
1/2
Do
D2
+ +1+ B1)
Σ arB
[1
1/4
mr
02
QT
0t
(
Do +
dG D2 VT
G D
a(1 + 31)v T+ + log T
d
a(1
X)a
B1)(1 - -8vvI 32
(19)
1/2 Fi
1/2 "iii and (ii) follows from Lemmas 1 3.
where (i) follows from Assumption and because
Finally, applying the Jensen's 's inequality yields
E Iuouu 8-11 < T 1=1
Σ
E 11110-00 1-
(20)
We conclude our proof by further applying the bound in Equation (19) to Equation (20).
17

---

Under review as a conference paper at ICLR 2020
C PROOF OF THEOREM 2
To prove the convergence for AIIQ-AMSGradR, the major technical development beyond the proof of Theorem 1 lies in dealing with the parameter restart. More specifically, the moment approximation terms are reset every 7 steps, i.e., Myr = ükr = for k = 1, ...., which implies 0kr+1 = 0%r 1.2.... ..... For technical convenience, to Equation (19), in time window that does not contain a restart (i.e. kr S S s (k + 1)r 1) we have
for k 1,2,
define On 0,. Using the arguments similar
2c(1 31)
Σ t=kr
E10
1'12
( Goc D2
+
dG vs
+
a(1 + 31)
Σ
d
1
Σ
8
1 t
a
(1 B1)(1 - 8)v1 - B2 1=1
1r++1
+ Goo D2
Σ
B1
+ 2c(1 11 31)) ( 11100++11 - 1-1 + E. 10r - 0-(1²)
04
t=
Goo D3
vkr +2
De VS
a(1 + 31)
Σ
E 11
a
a
(1 - 31) - 5) B2 i=1
k=r++1
B1 4c(1 1 -B1)E 10xr 1-12
+ Goo D
Qg
tmkr+2
where (i) follows from Equation (19) and (ii) follows from 0kr+1 = Oer due to the definition of restart. Then we take the summation over the total time steps and obtain
T
2c(1- - 31) Σ
E 11, 1-1
1=1
[T/r]
kr-1
=2c(1 B1)
B100 -- +
110 0-11²
E3 11000 - 1
k=1 t= (k-1)3 1}r
[T/rlr
T/rl
Go D2
[T/r
dG D2
Ver +2 + 4c(1 B1) 0-112)
kr -
a
a
k=0
[T/rl d
dG 00 D2 VT
a(1 + 31)
EE
9(k - 1)r- 1,kr 1.1
Σ
(1 31)(1 - 8)v11 - B2
(=(k-1) 1)
a(1 + 31)
d
T
+ (1 (1- 31)(1 - V)v1 11 B2 1=1
E Blg
[=[T/r]++1
[T/rl kr-
Bie
BIt
Goo 2
Σ
Do
at
IIT/r/++2 a4
k=
T/rl
[T/r] dG D2
Go
D2
xc
v kr +2 + 4c(1 - E 10 - 0/112
+
vkr -1
a
k=0
dG.g D2 T
a(1+ 31)
[T/rl d
kr
E3 fl 1)
(1- 31)(1 -1 8) -- B2
b
=
t= -1
a(1 + 31)
d
T
T
31
Σ [=(T/r]r+1
+ Goo D2
(1-
82 1=1
t
1=1
18

---

Under review as a conference paper at ICLR 2020
We can bound the term Go Do Σ fi by Lemma 3. Next, bound another key term in the above inequality. We first observe that wk: 2 2, Vi E [d].
at
kr
kr
g 1)-B-1)++tdr--1 1,5
Σ
| - 1)
Σ
+
Okr.ily
IV
1
t
t
kr
1)++1
13++1
(21)
kr
1
E.
1= 1j++1
where (i) holds due to 19r.ll 1 > 0 and (ii) follows from the inequality. Then have
[T/rl
d
Ar-1 1
d
T
9(k 1)+ 1,kr
Σ
9 /
Σ
k=1
f=1
(=(k-1)r++ 1)r+1
t= [T/r. r+1
[T/r]
[T/r]
hr-1 Σ
1
1krr
+
l9ck-
kr
1=1
1=1
k=
1= 1)++1
d
|9
|
Σ (=(T/rir+1
IT/rJ
Ar
Σ
+ Ighn
kr
(= 1)++1
||9 |
t= T/r
kr
1)(
Σ
k=
(= 1r++1
t= [=[T/r]n+t 1+11
d
kr
T
g 11
Σ
+ ||11T//J++1oT
t
(k
[=(T/r]++1
T Σ
|
where (i) follows from |g due to the Cauchy-Schwarz inequality. Then have
Vk 2 Vi E [d]. (ii) follows from Equation (21) and (iii) holds
Kr
19

---

Under review as a conference paper at ICLR 2020
T
20(1 - 31)
Σ 1=1
E 110, - 0¹1²
[T/r]
[T/rl
Dz
dG D2
Vkr + 2 4c(1 BI) 10k 04113)
Σ
Vkr-I
α2
k=0
dGx D2 VT
VT
a(1 + 31)
[2/r]
kr 1
+
IE
a
(1- 31) 8)
v 32
k=
1= 1)r
a(1 + B1)
d
T Σ
T B11
+
E |9TT//J07T111
+ GZ D2
(1 -1) 80 V $2
-
[=(T//]r
a2
T/rl
[T/r]
Dx
dG D2
kr + + 4c(1 B1) 10 -0113)
+
vrr-1
K=0
1=1
dG D2 VT
a(1+81) 31)
d
T
T
31
+
+ (1- 31)(1 8) VI 132
E 119.TT1 Σ
+
D2
a
t
00
at
1=1
[//r]
[Tir]
D2
dG dG
D2 Dc
kr + 2 + 4c(1 - BI)DE 10 -012)
+
kr
k=0
k=1
dG D& T
a(1 + 31) /d(1 + log 7)
B1 a(1 X)2
Σ
a
(1 31)(1 - 8)v B3
where (i) follows from Lemma 2 and Lemma 3.
Finally, applying the Jensen's inequality and the above bound, we obtain
E 0 outt
1
1
E 10:
11
T 1=1
[T/r]
[T/rl
$
1
D2
V kr + + 2E 2E|| 1|0p - 0-112)
+ T
kKT Vkr-1 1
T
2ca(1 B.)
200 (1 -1 B11)
k=0
dG D2 VT
a(1 31)+ 3:) ((1 + +log 7)
d
BiGxoD3
E
20a - B1)
20(1 (o(1-3))331 - 8)v1 B2
200e(1 - :3:)(1 A)2
which concludes the proof.
20


Reviews:
[{"review_id": "S1xkUljkqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper describes a method to improve the AltQ algorithm (which is typically unstable and inefficient) by using a combination of an Adam optimizer and regularly restarting the internal parameters of the Adam optimizer. The approach is evaluated on both a synthetic problem and on Atari games.\n\nThe core of the approach (simply replacing the optimizer with Adam) is relatively simple and the restarts seem mostly to improve variance rather than return over the vanilla Adam approach. It's hard to see what additional value the convergence analysis provides over the AMSGrad convergence analysis. Especially when the convergence rate appears to be the same for AltQ-AMSGrad and AltQ-AMSGradR for large r. Overall, it seems the approach of using Adam for the optimizer in AltQ seems to be too trivial an improvement and the difference between the Adam with restarts and Adam without restarts also seems to be relatively insignificant when looking at normalized return on Atari. They also both have increasing variance near the end of training in figure 2, much larger than that of DQN. Another downside of this work is that the convergence analysis is done on AMSGrad instead of Adam which the experimental results are based on, why were experiments not done with AltQ-AMSGrad?\n\nOther comments:\nIn section 4.1: \"to help preventing\" -> \"to help prevent\"\nBottom of page 5: \"most well-performed\" -> \"most well-performing\"\nAbove eq 8: \"step stone\" -> \"stepping stone\"\n\n================================================================================================\nUpdate after rebuttal:\n\nThanks for the response. I will stand by my score. I still find it odd that no experiments are done with AltQ-AMSGrad since the convergence analysis was done for this algorithm. After all, the results of AltQ-Adam might be very different to AltQ-AMSGrad, which puts into question how relevant that convergence analysis is to the experimental results.\n\nFinally, I agree with the other reviewers that AltQ is a misleading name for this algorithm and recommend the paper use a standard name for the algorithm.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJxEMKiEYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is well-written and it provides a convergence result for traditional Q-learning, with linear function approximation, when using an Adam-like update (AMSGrad). It does the same for a variation of this algorithm where the momentum-like term is reset every now and then. This second result is not that exciting as it ends up concluding that the “best way” to converge with such an approach is by resetting the momentum-like term rarely. That being said, it is still interesting to have such theoretical result. On the empirical side, this paper evaluates the traditional Q-learning algorithm with non-linear function approximation (through a neural network), using Adam (and AdamR) while not using a target network, in both an LQR problem and a subset of the Atari games. The empirical results are not necessarily that convincing and there are important details missing. I’m willing to increase my score if my concerns w.r.t. the empirical validation are addressed since this paper presents a potentially interesting theoretical result with Adam, which is so prominent in the literature nowadays.\n\nWith respect to the empirical analysis, it is not clear to me why only 23 Atari games were used. The traditional answer often revolves around limited computational resources, but for this set of experiments it is particularly concerning. *How were these 23 games chosen?* The reason I ask is that DQN, without a target network, does work in approximately half of the Atari games. In the other games DQN presents instability and it doesn’t succeed. I wonder if the proposed approach would actually be stable throughout the whole set of Atari games. Moreover, it is not clear to me *why such a small buffer size was used*. As acknowledged in the paper: “Considering we use a smaller buffer size than common practice, DQN is not consistently showing improved return over all tested games”. It seems to me that DQN was evaluated in a suboptimal parameter setting, so it is not clear to me how relevant the claims that the evaluated algorithm outperforms DQN are.\n\nThe results itself, which are summarized in Figure 2 and in the Appendix, in Figure 3, are not that convincing (I would also like to see a table with the raw numbers at the end, as it is often done). In Figure 2, as acknowledged in the paper, “AltQ-Adam” has a huge variance at the end (raising concerns about its stability, as I previously mentioned). “AltQ-AdamR” does seem to be more stable but the confidence intervals (or standard deviation?) overlap (red and blue). Is there a significant difference? Looking at Figure 3 in the Appendix, the individual learning curves are not that convincing as well. In 12 out of 23 games DQN outperforms the other methods or there is pretty much no difference in performance between them (i.e., Alien, Assault, Asteroids, Bowling, CrazyClimber, FishingDerby, JamesBond, Pitfall, Pong, QBert, Robotank, Tutankham). In 11 out of 23 games there’s a clear advantage of AltQ-Adam or AltQ-AdamR (i.e., Amidar, Asterix, BeamRider, Enduro, DemonAttack(?), DoubleDunk, Gopher, Gravitar, Seaquest, SpaceInvaders, Tennis). Consequently, although AltQ seems better than DQN, the difference is not that big. Importantly, some crucial details are missing (at least I couldn’t find them). *How many seeds were used in each game?* One seed is way too little since the performance difference in Tennis could be explained by “luck” in the random action selection process. Which Atari version was used? The deterministic one or the stochastic one (Machado et al., 2018)? \n\nWith respect to presentation, I don’t understand why Q-learning is being called AltQ. AltQ, with linear function approximation, is exactly what Q-learning does. *Introducing a new name for an old algorithm is very distracting* and it actually might reduce the impact of the paper, since more people can relate to Q-learning than to AltQ, which sounds as a newly introduced algorithm. Some details are not clear in Algorithms 1 and 2. *Is there a minibatch? That’s not represented in these algorithms, it it? Would it be fair to say that AltQ is _online_ Q-learning? I don’t think so since it uses a minibatch uniformly sampled from the experience replay buffer. It would be beneficial to have a paragraph explicitly discussing what are the differences between AltQ and DQN. Is it only dropping the target network?* Finally, there are some typos (e.g., “Nestrov”) and the references could be improved. Specifically, I’d recommend the authors to not use citations as nouns (e.g., “which is justified in (Duchi et al., 2011).”) and to cite Bellemare et al. (2013) instead of (or with) Brockman et al. (2016) when referring to the Atari games.\n\n\nReferences:\n\nMarc G. Bellemare, Yavar Naddaf, Joel Veness, Michael Bowling: The Arcade Learning Environment: An Evaluation Platform for General Agents. J. Artif. Intell. Res. 47: 253-279 (2013)\n\nMarlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew J. Hausknecht, Michael Bowling: Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents. J. Artif. Intell. Res. 61: 523-562 (2018)\n\n\n--- \n\n>>> Update after rebuttal: I stand by my score after the rebuttal. \n\nThis paper has several presentation issues that need to be addressed before publication. The theoretical result does make it an interesting contribution, but the empirical section weakens the paper quite a lot. The paper is trying to show that the proposed approach is more stable but the smaller replay buffer size is not satisfying, since it is a setting which no one uses. Moreover, it is not possible to claim that a method presents lower variance when all one has are to 2 seeds to back up those claims. I don't think \"limited computational capability and cost\" is a good justification in that case.\n\nFinally, the term AltQ is distracting and misleading. The authors didn't demonstrate any intention of changing this name, but if they decide to submit this paper to a next conference, with stronger empirical evidence to back up the paper claims, I recommend them to drop the AltQ learning name as well.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "H1x4aHQlcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper claims to propose a method to train q-based agents that use “alternating” Q-learning. However, the alternating approach given in the paper appears to be the normal Bellman update implemented in most versions of DQN. Furthermore, the citation given for AltQ (Mnih et al. 2016) makes no mention of the term “Alternating Q learning”.\n\nThe novelty here would be that the authors propose incorporating an Adam-like optimizer and periodically resetting the ADAM parameters. I would not consider using Adam to be sufficiently novel for publication in this venue, and the results from using parameter resetting are not so spectacular or convincing that they qualify, either. Since no ablations are given, I suspect some of the improvement could have come from just using Adam.\n\nFinally, the convergence proofs given seem to hold only in the tabular case--not in the case when the Q function is an approximation. Generally, proofs only show that Q-learning converges in the tabular case. If these proofs held in the function approximation case, this would be a surprising breakthrough.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers attempted to provide a fair assessment of this work, albeit with varying qualifications.  Nevertheless, the depth and significance of the technical contribution was unanimously questioned, and the experimental evaluation was not considered to be convincing by any of the assessors.  The criticisms are sufficient to ask the authors to further strengthen this work before it can be considered for a top conference.
Decision: Reject