Title: CAN ALTQ LEARN FASTER: EXPERIMENTS AND THEORY

Abstract: Differently from the popular Deep Q-Network (DQN) learning, Alternating Qlearning (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.

1. 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; 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) . It 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 a nested-loop manner, where the outer loop follows an one-step update of the Q-function (via the empirical Bellman operator for Q-learning), and the inner loop takes a supervised learning process to fit the updated (i.e., target) Q-function with a 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) to 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 (AltQ). Although significantly simpler in the update rule, AltQ is 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 AltQ to improve the performance. All these schemes require more sophisticated designs or hardware support, which may place AltQ less advantageous compared to the popular DQN, even with their better performances. This motivates us to ask the following first question.

• Q1: Can we design a 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 AltQ based on Adam. Although Adam appears to be a natural tool, its performance in AltQ has rarely been studied yet. Thus, we first provide a 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 AltQ-Adam 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 AltQ-AdamR. This is the first time that restart is 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 AltQ-Adam and AltQ-AdamR outperform the baseline performance of DQN by 50% on average. Furthermore, AltQ-AdamR effectively reduces the performance variance and achieves a much more stable learning process.

In our experiments for the linear quadratic regulator (LQR) problems, AltQ-AdamR converges even faster than the model-based 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 AltQ algorithms, their convergence guarantee has been extensively studied (Melo et al., 2008; Chen et al., 2019b) . More references are given in Section 1.1. However, all the existing studies focus on the AltQ algorithms that take a 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 AltQ-Adam and AltQ-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 AltQ-AMSGrad and AltQ-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 Qlearning. To the best of our knowledge, this is the first non-asymptotic convergence guarantee on Q-learning that incorporates Adam-type update and momentum restart. Furthermore, a 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 x := x 2 = √ x T x to denote the 2 norm of a vector x, and use x ∞ = max i |x i | to denote the infinity norm. When x, y are both vectors, x/y, xy, x 2 , √ x are all calculated in the element-wise manner, which will be used in the update of Adam and AMSGrad. We denote

[n] = 1, 2, . . . , n, and x ∈ Z as the largest integer such that x ≤ x < x + 1.

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 is 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 a 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. PRELIMINARIES:

We consider a Markov decision process with a considerably large or continuous state space S ⊂ R M and action space A ⊂ R N with a non-negative bounded reward function R :

S × A → [0, R max ].

We define U (s) ⊂ A as the admissible set of actions at state s, and π : S → A as a feasible stationary policy. We seek to solve a discrete-time sequential decision problem with γ ∈ (0, 1) as follows:

maximize π J π (s 0 ) = E P ∞ t=0 γ t R(s t , π(s t )) ,

subject to s t+1 ∼ P (•|s t , a t ).

(1) Let J (s) := J π (s) be the optimal value function when applying the optimal policy π . The corresponding optimal Q-function can be defined as

EQUATION

where s ∼ P (•|s, a) and we use the same notation hereafter when no confusion arises. In other words, Q (s, a) is the reward of an agent who starts from state s and takes action a at the first step and then follows the optimal policy π thereafter.

2.1. ALTQ ALGORITHM:

This paper focuses on the Alternating Q-learning (AltQ) algorithm that uses a parametric function Q(s, a; θ) to approximate the Q-function with a parameter θ of finite and relatively small dimension.

The update rule of AltQ-learning is given by

EQUATION

EQUATION

where α t is the step size at time t. 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 t-th inner loop, DQN first obtains the target Q-function as in Equation ( 5), and then uses a neural network to fit the target Q-function by running Y steps of a certain optimization algorithm as Equation ( 6). The update rule of DQN is given as follows.

EQUATION

EQUATION

where Optimizer can be SGD or Adam for example, and Equation ( 6) is thus a supervised learning process with T Q(s, a; θ 0 t )) as the "supervisor". At the t-th outer loop, DQN performs the so-called target update as

EQUATION

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 AltQ with Adam can potentially shed light on such ambiguity and inspire future work for this matter.

Note that AltQ and DQN mainly differ at how the Q-function evolves after each step of sampling.

A fair comparison between the algorithms should be made without introducing dramatic difference on gradient propagation (Knight & Lerner, 2018) , policy structure, exploration and sampling strategies (Mnih et al., 2016) . In practice, the vanilla AltQ is often slow in convergence and unstable with high variance. To improve the performance, we propose to incorporate Adam and restart schemes, which are easy to implement and yield improved performance than DQN.

3. ACCELERATED ALTERNATING Q-LEARNING ALGORITHMS:

In this section, we first describe how to incorporate Adam to the AltQ algorithm, and then introduce a novel implementation scheme to improve the performance of AltQ with Adam.

AltQ with Adam-type update We propose a new AltQ algorithm with Adam-type update (AltQ-Adam) as described in Algorithm 1. 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 t ) and squared historical gradients (v t ). The hyper-parameters β 1 , β 2 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-AdamR as Algorithm 2. Traditional momentum-based algorithms largely depend on the historical gradient direction. When part of the historical information is incorrect, the estimation error tends to accumulate. The restart technique can be employed to deal with this issue. One way to restart the momentum-based methods is to initialize the momentum at some restart iteration. That is, at restart iteration r, we reset m r , v r , i.e., m r = 0, v r = 0, which yields θ r+1 = θ r . It is an 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 a period r. It turns out that the restart technique can significantly improve the numerical performance, which can be seen in Section 4.

4. EMPIRICAL PERFORMANCE:

We empirically evaluate the proposed algorithms in this section. The linear quadratic regulator (LQR) 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 a small adjustment to the proposed algorithms. That is, we re-scale the loss term of L(θ t ) := Qt (s, a; θ t ) -T Q(s, a; θ t )

Algorithm 1 AltQ-Adam 1: Input: η, θ 1 , β 1 , β 2 , , γ, m 0 = 0, v 0 = 0. 2: for t = 1, 2, . . . , K do 3: T Q(s, a; θ t ) = R(s, a) + γ max a Q(s , a ; θ t ) 4: g t = Qt (s, a; θ t ) -T Q(s, a; θ t ) ∂ ∂θt Qt (s, a; θ t ) 5: m t = (1 -β 1 )m t-1 + β 1 g t 6: v t = (1 -β 2 )v t-1 + β 2 g 2 t 7: θ t+1 = θ t -η mt √ vt+ 8: end for 9: Output: θ K Algorithm 2 AltQ-AdamR 1: Input: η, θ 1 , β 1 , β 2 , , γ, m 0 = 0, v 0 = 0, r. 2: for t = 1, 2, . . . , K do 3:

if mod(t, r) = 0 then 4:

m t = 0, v t = 0 5: end if 6: T Q(s, a; θ t ) = R(s, a) + γ max a Q(s , a ; θ t ) 7: g t = Qt (s, a; θ t ) -T Q(s, a; θ t ) ∂ ∂θt Qt (s, a; θ t ) 8: m t = (1 -β 1 )m t-1 + β 1 g t 9: v t = (1 -β 2 )v t-1 + β 2 g 2 t 10: θ t+1 = θ t -η mt √ vt+

11: end for 12: Output: θ K in Equation (4) as L(θ t ) = τ 2 L(θ t ) with some scaling factor τ ∈ (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-horizon discrete-time LQR problem whose background can be found in Appendix A.1. A typical model-based solution (with known dynamics), known as the discrete-time algebraic Riccati equation (DARE), is adopted to derive the optimal policy u t = -K x t . The performance of the learning algorithm is then evaluated at each step of iterate t with the Euclidean norm K t -K . The performance result for each method is averaged over 10 trials with different random seeds. All algorithms share the same set of random seeds and are initialized with the same θ 0 . The hyper-parameters of the learning settings are also consistent and further details are shown in Table 1 . Note that for all the implementations, we also adopt the double Q-update (Hasselt, 2010) to help prevent over-estimations of the Q-value. The performance results are seen in Figure 1 . 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 to the DQN-like update if 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 is 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 is faster than the most well-performing 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 AltQ-Adam.

Figure 1 : LQR experiments with performance evaluated in terms of policy loss K t -K 2 .

Figure 2 : Atari game experiment with performance normalized and averaged over 23 games. 

K i -K 2 ≤ 10 -4 1 4.2 ATARI GAMES

We apply the proposed AltQ algorithms to more challenging tasks of deep convolutional neural network playing a group of Atari 2600 games. The particular DQN we train to compare against adopts the dueling network structure (Wang et al., 2016) , double Q-learning setup (Van Hasselt et al., 2016) , -greedy exploration and experience replay (Mnih et al., 2013) . Adam is also adopted, without momentum restart, as the optimizer for the inner-loop supervised learning process. AltQ-Adam and AltQ-AdamR are implemented using the identical setup of network construction, exploration and sampling strategies.

We test all the three algorithms with a 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 is based on the baseline implementation of OpenAI. Selections of the hyperparameters 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-normalized average return of DQN in Figure 2 is not strictly increasing from 0 to 100%.

Overall, both AltQ-Adam and AltQ-AdamR achieve significant improvement in comparison with the DQN results. While AltQ-Adam is suffering from a higher variance, periodic restart (AltQ-AdamR) resolves the issue efficiently with an on-par performance on average and far smaller variance. Specifically, in terms of the maximum average return, AltQ-Adam and AltQ-AdamR perform no worse then DQN on 17 and 20 games respectively out of the 23 games being evaluated.

5. CONVERGENCE ANALYSIS:

In this section, we characterize the convergence guarantee for the proposed AltQ-learning algorithms. Furthermore, like most of 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 Q(s, a; θ) can be written as

EQUATION

where θ ∈ R d , and Φ : S × A → R d is a vector function of size d, and the elements of Φ represent the nonlinear kernel (feature) functions. 

Π D, V 1/4 t (θ ) = min θ∈D V 1/4 t (θ -θ) . Correspondingly,

we introduce AltQ-AMSGradR which applies the same update rule as Algorithm 3, but resets m t , vt with a period of r, i.e., m t = 0, vt = 0, ∀t = kr, k = 1, 2, • • • .

Algorithm 3 AltQ-AMSGrad 1: Input: α, λ, θ 1 , β 1 , β 2 , m 0 = 0, v0 = 0. 2: for t = 1, 2, . . . , T do 3: α t = α √ t , β 1t = β 1 λ t 4: g t = φ T (s t , a t )θ t -r(s t , a t ) -max a φ T (s t+1 , a )θ t φ(s t , a t ) 5: m t = (1 -β 1t )m t-1 + β 1t g t 6: v t = (1 -β 2 )v t-1 + β 2 g 2 t 7: vt = max(v t-1 , v t ), Vt = diag(v 1 , . . . , vd ) 8: θ t+1 = Π D, V 1/4 t θ t -α t V -1 2 t m t

9: end for 10: Output: 1 T T t=1 θ t

5.2. MAIN RESULTS:

Our theoretical analysis here focuses on the slight variants, AltQ-AMSGrad and AltQ-AMSGradR. Before stating the theorems, we first introduce some technical assumptions for our analysis. Assumption 1. At each iteration t, the noisy gradient is unbiased and uniformly bounded, i.e. g t = ḡt + ξ t with Eξ t = 0 where ḡt = E[g t ], and g t < G ∞ , ∀t. Thus g t ∞ < G ∞ and g t 2 < G 2 ∞ . Assumption 2. (Chen et al., 2019b, Lemma 6.7) The equation ḡ(θ) = 0 has a unique solution θ , which implies that there exists a c > 0, such that for any θ ∈ R d we have

EQUATION

)

Assumption 3. The domain D ⊂ R d of approximation parameters is a ball originating at θ = 0 with bounded diameter containing θ . That is, there exists D ∞ , such that θ m -θ n < D ∞ , ∀θ m , θ n ∈ D, and θ ∈ 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 as a key technical lemma in Chen et al. (2019b) under certain assumptions. Such an assumption appears to be the weakest in the existing studies of the theoretic guarantee for Q-learning with function approximation.

Under review as a conference paper at ICLR 2020

We next provide the convergence results of AltQ-AMSGrad and AltQ-AMSGradR under linear function approximation in the following two theorems. Theorem 1. (Convergence of AltQ-AMSGrad) Suppose α t = α √ t , β 1t = β 1 λ t and δ = β 1 /β 2 with δ, λ ∈ (0, 1) for t = 1, 2, . . . in Algorithm 3. Given Assumptions 1 ∼ 3, the output of AltQ-AMSGrad satisfies:

EQUATION

where

B 1 = G∞D 2 ∞ 2α2c(1-β1) + β1G∞D 2 ∞ 2αc(1-β1)(1-λ) 2 + θ 1 -θ 2 , B 2 = dG∞D 2 ∞ 2αc(1-β1) , and B 3 = α(1+β1) 2c(1-β1) 2 (1-δ) √ 1-β2 .

In Theorem 1, B 1 , B 2 , B 3 in the bound in Equation ( 10 In the following theorem, we provide the convergence result for AltQ-AMSGradR. Theorem 2. (Convergence of AltQ-AMSGradR) Under the same condition of Theorem 1, the output of AltQ-AMSGradR satisfies:

EQUATION

)

where

B 1 = β1D 2 ∞ G∞ 2αc(1-β1)(1-λ) 2 , B 2 = α(1+β1) 2c(1-β1) 2 (1-δ) √ 1-β2 , and B 3 = dG∞D 2 ∞ 2αc(1-β1) .

Theorem 2 indicates that for AltQ-AMSGradR to enjoy a convergence rate of O 1 √ T the restart period r needs to be sufficiently large and

d i=1 g 1:T,i << √ T .

In practice as demonstrated by the experiments in Section 4, AltQ-AMSGradR typically performs well, not necessarily under the theoretical conditions.

6. CONCLUSION:

We propose two types of the accelerated AltQ algorithms, and demonstrate their superior performance over the state-of-the-art through a linear quadratic regulator problem and a batch of 23 Atari 2600 games.

Notably, Adam is not the only scheme in the practice for general optimization. Heavy ball (Ghadimi et al., 2015) and Nesterov (Nesterov, 2013) are also popular momentum-based 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 a 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 a scheme. One possible direction is to develop an adaptive restart mechanism with changing period determined by an appropriately defined signal of restart. This will potentially relieve the effort in hyper-parameter tuning of finding a good fixed period.

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 et al. applies PQL to both discrete-time problems (Lewis & Vrabie, 2009; Lewis & Vamvoudakis, 2011) and continuous-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 = ∞ t=0 x T t Qx t + u T t Ru t + 2x T t N u t , subject to x t+1 = Ax t + Bu t ,

where u t = π(x t ).

A typical model-based solution (with known A and B) considers the problem backwards in time and iterates a dynamic equation known as the discrete-time algebraic Riccati equation (DARE):

EQUATION

with the cost-to-go P being positive definite. The optimal policy satisfies u t = -K x t with

EQUATION

)

For experiments, we parameterize a quadratic Q-function with a matrix parameter H in the form of

EQUATION

)

The corresponding linear policy satisfies u = -Kx, and K = H -1 uu H ux . The performance of the learning algorithm is then evaluated at each step of iterate i with the Euclidean norm K i -K 2 .

A.2 ATARI GAMES:

We list detailed experiments of the 23 Atari games evaluated with the proposed algorithms in Figure 3 . All experiments are executed with the same set of two random seeds. Each task takes about 20-hour of wall-clock time on a GPU instance. All three methods being evaluated share similar training time. AltQ-Adam and AltQ-AdamR can be further accelerated in practice with a more memory-efficient 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, AltQ-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 on Amidar and Assault. This is mostly caused by the sampling where we are using a relevantly small buffer size with 10% of the common configured size in Atari games with experience replay. Notice that those failures tend to appear when the -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 AltQ-Adam and provides a more consistent performance across the task domain. This implies that momentum restart effectively corrects the accumulated error and stabilizes the training process. 2018), our analysis is on the convergence rate. In fact, a slight modification of our proof also provides the convergence rate for AMSGrad for conventional strongly convex optimization, which can be of independent interest. Moreover, our 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 et al., 2018, Lemma A.1) Let {g t , m t , vt } for t = 1, 2, . . . be sequences generated by Algorithm 3 and ḡt et al., 2018 , Lemma 2) Let {m t , Vt } for t = 1, 2, . . . be sequences generated by Algorithm 3. Given α t , β 1t , β 2 as specified in Theorem 1, we have

= E[g t ]. Under Assumption 1, ḡt ≤ G ∞ , m t ≤ G ∞ , vt ≤ G 2 ∞ . Lemma 2. (Reddi

EQUATION

Lemma 3. Let α t = α √ t and β 1t = β 1 λ t for t = 1, 2, . . . . Then

EQUATION

)

Proof. The proof is based on taking the standard sum of geometric sequences.

T t=1

β 1t α t = T t=1 β 1t √ t α ≤ T t=1 β 1 λ t-1 t α = β 1 α 1 (1 -λ) T t=1 λ t-1 -T λ T ≤ β 1 α(1 -λ) 2 . (17)

With the lemmas above, we are ready to prove Theorem 1. Observe that

θ t+1 = Π D, V 1/4 t θ t -α t V -1 2 t m t = min θ∈D V 1/4 t θ t -α t V -1 2 t m t -θ .

Clearly Π D, V 1/4 t (θ ) = θ due to Assumption 3. We start from the update of θ t when t ≥ 2.

V 1/4 t (θ t+1 -θ ) 2 = Π D, V 1/4 t V 1/4 t θ t -θ -α t V -1 2 t m t 2 ≤ V 1/4 t θ t -θ -α t V -1 2 t m t 2 = V 1/4 t (θ t -θ ) 2 + α t V -1/4 t m t 2 -2α t (θ t -θ ) T m t = V 1/4 t (θ t -θ ) 2 + α t V -1/4 t m t 2 -2α t (θ t -θ ) T (β 1t m t-1 + (1 -β 1t )g t ) (i) ≤ V 1/4 t (θ t -θ ) 2 + α t V -1/4 t m t 2 + α t β 1t 1 α t V 1/4 t (θ t -θ ) 2 + α t V -1/4 t m t-1 2 -2α t (1 -β 1t )(θ t -θ ) T g t (ii) ≤ V 1/4 t (θ t -θ ) 2 + α t V -1/4 t m t 2 + β 1t V 1/4 t (θ t -θ ) 2 + α 2 t β 1t V -1/4 t-1 m t-1 2 -2α t (1 -β 1t )(θ t -θ ) T g t ,

where (i) follows from the Cauchy-Schwarz inequality, and (ii) holds because vt+1,i ≥ vt,i , ∀t, ∀i.

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 t be the filtration of all the sampling up to time t, we have

EQUATION

)

Thus we have

E V 1/4 t (θ t+1 -θ ) 2 ≤ E V 1/4 t (θ t -θ ) 2 + α 2 t E V -1/4 t m t 2 + β 1t E V 1/4 t (θ t -θ ) 2 + α 2 t β 1t E V -1/4 t-1 m t-1 2 -2α t (1 -β 1t )E (θ t -θ ) T g t (i) = E V 1/4 t (θ t -θ ) 2 + α 2 t E V -1/4 t m t 2 + β 1t E V 1/4 t (θ t -θ ) 2 + α 2 t β 1t E V -1/4 t-1 m t-1 2 -2α t (1 -β 1t )E (θ t -θ ) T ḡt (ii) ≤ E V 1/4 t (θ t -θ ) 2 + α 2 t E V -1/4 t m t 2 + β 1t E V 1/4 t (θ t -θ ) 2 + α 2 t β 1t E V -1/4 t-1 m t-1 2 -2α t c(1 -β 1t )E θ t -θ 2 (iii) ≤ E V 1/4 t (θ t -θ ) 2 + α 2 t E V -1/4 t m t 2 + β 1t E V 1/4 t (θ t -θ ) 2 + α 2 t β 1 E V -1/4 t-1 m t-1 2 -2α t c(1 -β 1 )E θ t -θ 2 (iv) ≤ E V 1/4 t (θ t -θ ) 2 + α 2 t E V -1/4 t m t 2 + G ∞ D 2 ∞ β 1t + α 2 t β 1 E V -1/4 t-1 m t-1 2 -2α t c(1 -β 1 )E θ t -θ 2 ,

where (i) follows from Equation ( 18), (ii) follows due to Assumption 2 and 1 -β 1t > 0, (iii) follows from β 1t < β 1 < 1 and E θ t -θ 2 > 0, and (iv) follows from

V 1/4 t (θ t -θ ) 2 ≤ V 1/4 t 2 2 θ t -θ 2 ≤ G ∞ D 2

∞ by Lemma 1 and Assumption 3. We note that (iii) is the key step to avoid the error in the proof in Reddi et al. (2018) , where we can directly bound 1 -β 1t , which is impossible in Reddi et al. (2018) . By rearranging the terms in the above inequality and taking the summation over time steps, we have

2c(1 -β 1 ) T t=2 E θ t -θ 2 ≤ T t=2 1 α t E V 1/4 t (θ t -θ ) 2 -E V 1/4 t (θ t+1 -θ ) 2 + T t=2 β 1t G ∞ D 2 ∞ α t + T t=2 α t E V -1/4 t m t 2 + T t=2 α t β 1 E V -1/4 t-1 m t-1 2 (i) ≤ T t=2 1 α t E V 1/4 t (θ t -θ ) 2 -E V 1/4 t (θ t+1 -θ ) 2 + T t=2 β 1t G ∞ D 2 ∞ α t + T t=2 α t E V -1/4 t m t 2 + T t=2 α t-1 β 1 E V -1/4 t-1 m t-1 2 ≤ T t=2 1 α t E V 1/4 t (θ t -θ ) 2 -E V 1/4 t (θ t+1 -θ ) 2 + T t=2 β 1t G ∞ D 2 ∞ α t + (1 + β 1 ) T t=1 α t E V -1/4 t m t 2 ,

where (i) follows from α t < α t-1 . With further adjustment of the first term in the right hand side of the last inequality, we can then bound the sum as

2c(1 -β 1 ) T t=2 E θ t -θ 2 ≤ T t=2 1 α t E V 1/4 t (θ t -θ ) 2 - V 1/4 t (θ t+1 -θ ) 2 + T t=2 β 1t G ∞ D 2 ∞ α t + (1 + β 1 ) T t=1 α t E V -1/4 t m t 2 = E V 1/4 2 (θ 2 -θ ) 2 α 2 + T t=3 E    V 1/4 t (θ t -θ ) 2 α t - V 1/4 t-1 (θ t -θ ) 2 α t-1    - E V 1/4 T (θ T +1 -θ ) 2 α T + T t=2 β 1t G ∞ D 2 ∞ α t + (1 + β 1 ) T t=1 α t E V -1/4 t m t 2 = E V 1/4 2 (θ 2 -θ ) 2 α 2 + T t=3 E d i=1 v1/2 t,i (θ t,i -θ i ) 2 α t - d i=1 v1/2 t-1,i (θ t,i -θ i ) 2 α t-1 - E V 1/4 T (θ T +1 -θ ) 2 α T + T t=2 β 1t G ∞ D 2 ∞ α t + (1 + β 1 ) T t=1 α t E V -1/4 t m t 2 . = E V 1/4 2 (θ 2 -θ ) 2 α 2 + T t=3 d i=1 E(θ t,i -θ i ) 2 v1/2 t,i α t - v1/2 t-1,i α t-1 - E V 1/4 T (θ T +1 -θ ) 2 α T + T t=2 β 1t G ∞ D 2 ∞ α t + (1 + β 1 ) T t=1 α t E V -1/4 t m t 2 .

So far we just rearrange the terms in the series sum. Next, we are ready to obtain the upper bound.

EQUATION

where (i) follows from Assumption 3 and because

v1/2 t,i αt > v1/2 t-1,i

αt-1 , and (ii) follows from Lemmas 1 -3. Finally, applying the Jensen's inequality yields

EQUATION

We conclude our proof by further applying the bound in Equation ( 19) to Equation (20).

C PROOF OF THEOREM 2:

To prove the convergence for AltQ-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 r steps, i.e., m kr = vkr = 0 for k = 1, 2, . . . , which implies θ kr+1 = θ kr for k = 1, 2, . . . . For technical convenience, we define θ 0 = θ 1 . Using the arguments similar to Equation ( 19), in a time window that does not contain a restart (i.e. kr ≤ S ≤ (k + 1)r -1) we have

2c(1 -β 1 ) S t=kr E θ t -θ 2 (i) ≤ G ∞ D 2 ∞ α kr+2 + dG ∞ D 2 ∞ √ S α + α(1 + β 1 ) (1 -β 1 )(1 -δ) √ 1 -β 2 d i=1 E g kr+1:S,i S t=kr+1 1 t + G ∞ D 2 ∞ S t=kr+2 β 1t α t + 2c(1 -β 1 ) E θ kr+1 -θ 2 + E θ kr -θ 2 (ii) = G ∞ D 2 ∞ √ kr + 2 α + dG ∞ D 2 ∞ √ S α + α(1 + β 1 ) (1 -β 1 )(1 -δ) √ 1 -β 2 d i=1 E g kr+1:S,i S t=kr+1 1 t + G ∞ D 2 ∞ S t=kr+2 β 1t α t + 4c(1 -β 1 )E θ kr -θ 2 ,

where (i) follows from Equation ( 19) and (ii) follows from θ kr+1 = θ kr due to the definition of restart. Then we take the summation over the total time steps and obtain 

2c(1 -β 1 ) T t=1 E θ t -θ 2 = 2c(1 -β 1 )   T /r k=1 kr-1 t=(k-1)r E θ t -θ 2 + T t= T /r r E θ t -θ 2 -E θ 0 -θ 2   ≤ T /r k=0 G ∞ D 2 ∞ α √ kr + 2 + 4c(1 -β 1 )E θ kr -θ 2 + T /r k=1 dG ∞ D 2 ∞ α √ kr -1 + dG ∞ D 2 ∞ √ T α + α(1 + β 1 ) (1 -β 1 )(1 -δ) √ 1 -β 2 T /

β 1t α t + G ∞ D 2 ∞ T t= T /r r+2 β 1t α t ≤ T /r k=0 G ∞ D 2 ∞ α √ kr + 2 + 4c(1 -β 1 )E θ kr -θ 2 + T /r k=1 dG ∞ D 2 ∞ α √ kr -1 + dG ∞ D 2 ∞ √ T α + α(1 + β 1 ) (1 -β 1 )(1 -δ) √ 1 -β 2 T /

1 t + G ∞ D 2 ∞ T t=1 β 1t α t ≤ T /r k=0 G ∞ D 2 ∞ α √ kr + 2 + 4c(1 -β 1 )E θ kr -θ 2 + T /r k=1 dG ∞ D 2 ∞ α √ kr -1 + dG ∞ D 2 ∞ √ T α + α(1 + β 1 ) (1 -β 1 )(1 -δ) √ 1 -β 2 d i=1 E g 1:T,i T t=1 1 t + G ∞ D 2 ∞ T t=1 β 1t α t (i) ≤ T /r k=0 G ∞ D 2 ∞ α √ kr + 2 + 4c(1 -β 1 )E θ kr -θ 2 + T /r k=1 dG ∞ D 2 ∞ α √ kr -1 + dG ∞ D 2 ∞ √ T α + α(1 + β 1 ) d(1 + log T ) (1 -β 1 )(1 -δ) √ 1 -β 2 d i=1 E g 1:T,i + β 1 G ∞ D 2 ∞ α(1 -λ) 2 ,

where (i) follows from Lemma 2 and Lemma 3.

Finally, applying the Jensen's inequality and the above bound, we obtain

E θ out -θ 2 ≤ 1 T T t=1 E θ t -θ 2 ≤ 1 T T /r k=0 G ∞ D 2 ∞ 2cα(1 -β 1 ) √ kr + 2 + 2E θ kr -θ 2 + 1 T T /r k=1 dG ∞ D 2 ∞ 2cα(1 -β 1 ) √ kr -1 + dG ∞ D 2 ∞ √ T 2cα(1 -β 1 ) + α(1 + β 1 ) d(1 + log T ) 2c(1 -β 1 ) 2 (1 -δ) √ 1 -β 2 d i=1 E g 1:T,i + β 1 G ∞ D 2 ∞ 2cα(1 -β 1 )(1 -λ) 2 ,

which concludes the proof.

:



Figures and Tables:

) are constants and independent of time. Therefore, under the choice of the stepsize and hyper-parameters in Algorithm 3, AltQ-AMSGrad achieves a convergence rate of O 1 justified inDuchi et al. (2011). Remark 1. Our proof of convergence here has two major differences from that for AMSGrad in Reddi et al. (2018): (a) The two algorithms are quite different. AltQ-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, a slight modification of our proof also provides the convergence rate of AMSGrad for conventional strongly convex optimization, which can be of independent interest. Moreover, our proof avoids the theoretical error in the proof inReddi et al. (2018) pointed out by Tran et al. (2019).

Figure 3: Experiment results of 23 Atari games with DQN, AltQ-Adam and AltQ-AdamR

g (k-1)r+1:kr-1,i kr-1 t=(k-1)r+11 t + α(1 + β 1 ) (1 -β 1 )(1 -δ) √ 1 -3. Next,we bound another key term in the above inequality. We first observe that ∀k ≥ 2, ∀i ∈ [d], ) holds due to |g t,i | 1 t > 0 and (ii) follows from the Cauchy-Schwarz inequality. Then we have ) follows from |g kr,i | 1 kr , ∀k ≥ 1, ∀i ∈ [d], (ii) follows from Equation (21) and (iii) holds due to the Cauchy-Schwarz inequality. Then we have 2c(1 -β 1 )

Hyper-parameters for LQR experimentsStep size τ Adam β 1 Adam β 2 Restart period r

Table content: <table><tr><td>Stop criterion</td><td>γ</td></tr></table>

Hyper-parameters for Atari games experiments of DQN, AltQ-Adam and AltQ-AdamRStep size Scale factor τ Adam β 1 Adam β 2 Restart period r 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 et al., 2018). Instead, a slightly modified version called AMSGrad(Reddi et al., 2018) is widely used to study the convergence property of the Adam-type algorithms. Compared with the update rule of Adam, AMSGrad makes the sequence vt,i increasing along the time step t for each entry i ∈[d]. Here, we apply the update rule of AMSGrad to the AltQ algorithm and refer to such an algorithm as AltQ-AMSGrad. Algorithm 3 describes AltQ-AMSGrad in detail, where

Table content: <table><tr><td>Buffer size</td></tr></table>

Best empirical return of 23 Atari games with DQN, AltQ-Adam and AltQ-AdamR B PROOF OF THEOREM 1 Different from the regret bound for AMSGrad obtained in Reddi et al. (

Table content: <table><tr><td>Task</td><td>DQN</td><td colspan="2">AltQ-Adam AltQ-AdamR</td></tr><tr><td>Alien</td><td>1529</td><td>1125</td><td>1587</td></tr><tr><td>Amidar</td><td>269</td><td>313</td><td>551</td></tr><tr><td>Assault</td><td>1925</td><td>260</td><td>2097</td></tr><tr><td>Asteroids</td><td>1147</td><td>1394</td><td>1069</td></tr><tr><td>Asterix</td><td>11794</td><td>22413</td><td>17064</td></tr><tr><td>BeamRider</td><td>5728</td><td>10210</td><td>6458</td></tr><tr><td>Bowling</td><td>60</td><td>45</td><td>30</td></tr><tr><td colspan="2">CrazyClimber 116422</td><td>102731</td><td>121770</td></tr><tr><td>Enduro</td><td>866</td><td>1671</td><td>1291</td></tr><tr><td>DemonAttack</td><td>5729</td><td>10485</td><td>9273</td></tr><tr><td>DoubleDunk</td><td>-14</td><td>-12</td><td>-15</td></tr><tr><td>FishingDerby</td><td>29.01</td><td>-4</td><td>19</td></tr><tr><td>Gopher</td><td>6066</td><td>16863</td><td>9508</td></tr><tr><td>Gravitar</td><td>316</td><td>551</td><td>518</td></tr><tr><td>Jamesbond</td><td>663</td><td>899</td><td>756</td></tr><tr><td>Pitfall</td><td>-76</td><td>-20</td><td>-7</td></tr><tr><td>Pong</td><td>20.68</td><td>20.79</td><td>20.74</td></tr><tr><td>Qbert</td><td>13453</td><td>12487</td><td>14352</td></tr><tr><td>Robotank</td><td>56</td><td>34</td><td>42</td></tr><tr><td>Seaquest</td><td>3652</td><td>6121</td><td>6624</td></tr><tr><td>Spaceinvaders</td><td>923</td><td>1528</td><td>1036</td></tr><tr><td>Tennis</td><td>-17</td><td>20</td><td>-5</td></tr><tr><td>Tutankham</td><td>159</td><td>194</td><td>191</td></tr></table>

Peer review (iclr2020):
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. With 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. The 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)? With 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. References: Marc 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) Marlos 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) --- >>> Update after rebuttal: I stand by my score after the rebuttal. This 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. Finally, 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.