Year: 2019

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.

text: 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.

heading: 1 INTRODUCTION
text: 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 = √ xTx to denote the `2 norm of a vector x, and use ‖x‖∞ = max i |xi| to denote the infinity norm. When x, y are both vectors, x/y, xy, x2, √ 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 bxc ∈ Z as the largest integer such that bxc ≤ x < bxc+ 1.

heading: 1.1 RELATED WORK
text: 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.
Theoretical analysis of AltQ: Since proposed in Watkins & Dayan (1992), Q-learning has aroused great interest in theoretic analysis. 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 et al. (2019); Chen et al. (2019b); Du et al. (2019), to name a few. More recently, convergence of AltQ 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.
Convergence analysis of Adam: Adam was proposed in Kingma & Ba (2014) and has achieved a great success in training deep neural networks. Kingma & Ba (2014) and Reddi et 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 to converge to a stationary point. To the best of our knowledge, our study is the first convergence analysis of the Adam-type of algorithms for Q-learning.

heading: 2 PRELIMINARIES
text: We consider a Markov decision process with a considerably large or continuous state space S ⊂ RM and action space A ⊂ RN with a non-negative bounded reward function R : S ×A → [0, Rmax]. 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π(s0) = EP [ ∞∑ t=0 γtR(st, π(st)) ] ,
subject to st+1 ∼ P (·|st, at). (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
Q?(s, a) := R(s, a) + γEPJ?(s′), (2)
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.

heading: 2.1 ALTQ ALGORITHM
text: 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
TQ̂(s, a; θt) = R(s, a) + γ max a′∈U(s′)
Q̂(s′, a′; θt); (3)
θt+1 = θt − αt ( Q̂t(s, a; θt)− TQ̂(s, a; θt) ) ∂ ∂θt Q̂t(s, a; θt), (4)
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.

heading: 2.2 DQN ALGORITHM
text: 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.
TQ̂(s, a; θ0t ) = R(s, a) + γ max a′∈U(s′) Q̂(s′, a′; θ0t ), (5)
θYt = Optimizer(θ 0 t , T Q̂(s, a; θ 0 t )), (6)
where Optimizer can be SGD or Adam for example, and Equation (6) is thus a supervised learning process with TQ̂(s, a; θ0t )) as the ”supervisor”. At the t-th outer loop, DQN performs the so-called target update as θ0t+1 = (1− τ)θ0t + τθYt . (7) 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.

heading: 3 ACCELERATED ALTERNATING Q-LEARNING ALGORITHMS
text: 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 (AltQAdam) 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 (mt) and squared historical gradients (vt). 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 mr, vr, i.e., mr = 0, vr = 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.

heading: 4 EMPIRICAL PERFORMANCE
text: 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) := Q̂t(s, a; θt)− TQ̂(s, a; θt)
Algorithm 1 AltQ-Adam 1: Input: η, θ1, β1, β2, , γ,m0 = 0, v0 = 0. 2: for t = 1, 2, . . . ,K do 3: TQ̂(s, a; θt) = R(s, a) + γmaxa′ Q̂(s′, a′; θt)
4: gt = ( Q̂t(s, a; θt)− TQ̂(s, a; θt) ) ∂ ∂θt Q̂t(s, a; θt) 5: mt = (1− β1)mt−1 + β1gt 6: vt = (1− β2)vt−1 + β2g2t 7: θt+1 = θt − η mt√vt+ 8: end for 9: Output: θK
Algorithm 2 AltQ-AdamR 1: Input: η, θ1, β1, β2, , γ,m0 = 0, v0 = 0, r. 2: for t = 1, 2, . . . ,K do 3: if mod(t, r) = 0 then 4: mt = 0, vt = 0 5: end if 6: TQ̂(s, a; θt) = R(s, a) + γmaxa′ Q̂(s′, a′; θt)
7: gt = ( Q̂t(s, a; θt)− TQ̂(s, a; θt) ) ∂ ∂θt Q̂t(s, a; θt) 8: mt = (1− β1)mt−1 + β1gt 9: vt = (1− β2)vt−1 + β2g2t
10: θt+1 = θt − η mt√vt+ 11: end for 12: Output: θK
in Equation (4) as L̃(θt) = τ̃2L(θ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.

heading: 4.1 LINEAR QUADRATIC REGULATOR
text: 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?xt. The performance of the learning algorithm is then evaluated at each step of iterate t with the Euclidean norm ‖Kt −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 ‖Kt −K?‖2.
Figure 2: Atari game experiment with performance normalized and averaged over 23 games.

heading: 4.2 ATARI GAMES
text: 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 (AltQAdamR) 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.

heading: 5 CONVERGENCE ANALYSIS
text: 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
Q̂(s, a; θ) = Φ(s, a)T θ, (8)
where θ ∈ Rd, and Φ : S ×A → Rd is a vector function of size d, and the elements of Φ represent the nonlinear kernel (feature) functions.

heading: 5.1 MODIFICATION OF ALGORITHMS
text: 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 v̂t,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 ΠD,V̂ 1/4t (θ ′) = min θ∈D
∥∥∥V̂ 1/4t (θ′ − θ)∥∥∥. Correspondingly, we introduce AltQ-AMSGradR which applies the same update rule as Algorithm 3, but resets mt, v̂t with a period of r, i.e., mt = 0, v̂t = 0,∀t = kr, k = 1, 2, · · · .
Algorithm 3 AltQ-AMSGrad 1: Input: α, λ, θ1, β1, β2,m0 = 0, v̂0 = 0. 2: for t = 1, 2, . . . , T do 3: αt =
α√ t , β1t = β1λt 4: gt = ( φT (st, at)θt − r(st, at)−max
a′ φT (st+1, a ′)θt
) φ(st, at)
5: mt = (1− β1t)mt−1 + β1tgt 6: vt = (1− β2)v̂t−1 + β2g2t 7: v̂t = max(v̂t−1, vt), V̂t = diag(v̂1, . . . , v̂d)
8: θt+1 = ΠD,V̂ 1/4t
( θt − αtV̂ − 12 t mt ) 9: end for
10: Output: 1T ∑T t=1 θt

heading: 5.2 MAIN RESULTS
text: 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. gt = ḡt + ξt with Eξt = 0 where ḡt = E[gt], and ‖gt‖ < G∞,∀t. Thus ‖gt‖∞ < G∞ and ‖gt‖2 < G2∞. Assumption 2. (Chen et al., 2019b, Lemma 6.7) The equation ḡ(θ) = 0 has a unique solution θ?, which implies that there exists a c > 0, such that for any θ ∈ Rd we have
(θ − θ?)T ḡ(θ) ≥ c ‖θ − θ?‖2 . (9) Assumption 3. The domainD ⊂ Rd of approximation parameters is a ball originating at θ = 0 with bounded diameter containing θ?. That is, there existsD∞, 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.
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:
E ‖θout − θ?‖ ≤ B1 T
+ B2 √ T T + B3 √ 1 + log T T d∑ i=1 E ‖g1:T,i‖ , (10)
where B1 = G∞D
2 ∞
2α2c(1−β1) + β1G∞D
2 ∞
2αc(1−β1)(1−λ)2 + ‖θ1 − θ ?‖2 , B2 = dG∞D
2 ∞
2αc(1−β1) , and B3 = α(1+β1)
2c(1−β1)2(1−δ) √ 1−β2 .
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, AltQ-AMSGrad achieves a convergence rate of O ( 1√ T ) when ∑d i=1 ‖g1:T,i‖ << √ T which is justified in Duchi 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 in Reddi et al. (2018) pointed out by Tran et al. (2019).
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:
E ‖θout − θ?‖ ≤ B1 T
+ B2 √ 1 + log T
T
d∑ i=1 E ‖g1:T,i‖+ B3 T √T + bT/rc∑ k=1 √ kr − 1  + 1
T bT/rc∑ k=0 ( G∞D 2 ∞ α √ kr + 2 + 4c(1− β1)E ‖θkr − θ?‖2 ) ,
(11)
where B1 = β1D
2 ∞G∞
2αc(1−β1)(1−λ)2 , B2 = α(1+β1) 2c(1−β1)2(1−δ) √ 1−β2 , and B3 = 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 ‖g1:T,i‖ << √ T . In practice as demonstrated by the experiments in Section 4, AltQ-AMSGradR typically performs well, not necessarily under the theoretical conditions.

heading: 6 CONCLUSION
text: 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.

heading: A FURTHER DETAILS AND RESULTS ON EXPERIMENTS
text: 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 ( xTt Qxt + u T t Rut + 2x T t Nut ) ,
subject to xt+1 = Axt +But,
where ut = π(xt).
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):
P = ATPA− (ATPB +N)(R+BTPB)−1(BTPA+NT ) +Q, (12)
with the cost-to-go P being positive definite. The optimal policy satisfies u?t = −K?xt with
K? = (R+BTPB)−1(NT +BTPA). (13)
For experiments, we parameterize a quadratic Q-function with a matrix parameter H in the form of
Q(x, u;H) = [ x u ]T [ Hxx Hxu Hux Huu ] [ x u ] . (14)
The corresponding linear policy satisfies u = −Kx, and K = H−1uuHux. The performance of the learning algorithm is then evaluated at each step of iterate i with the Euclidean norm ‖Ki −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.

heading: B PROOF OF THEOREM 1
text: Different from the regret bound for AMSGrad obtained in Reddi et al. (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 {gt,mt, v̂t} for t = 1, 2, . . . be sequences generated by Algorithm 3 and ḡt = E[gt]. Under Assumption 1, ‖ḡt‖ ≤ G∞, ‖mt‖ ≤ G∞, ‖v̂t‖ ≤ G2∞. Lemma 2. (Reddi et al., 2018, Lemma 2) Let {mt, V̂t} for t = 1, 2, . . . be sequences generated by Algorithm 3. Given αt, β1t, β2 as specified in Theorem 1, we have
T∑ t=1 αt ∥∥∥V̂ − 12t mt∥∥∥2 ≤ α(1− β1)(1− δ)√1− β2 d∑ i=1 ‖g1:T,i‖ √√√√ T∑ t=1 1 t
≤ α √ 1 + log T
(1− β1)(1− δ) √ 1− β2 d∑ i=1 ‖g1:T,i‖ .
(15)
Lemma 3. Let αt = α√t and β1t = β1λ t for t = 1, 2, . . . . Then
T∑ t=1 β1t αt ≤ β1 α(1− λ)2 . (16)
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−1t α = β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/4t
( θt − αtV̂ − 12 t mt ) = min
θ∈D ∥∥∥V̂ 1/4t (θt − αtV̂ − 12t mt − θ)∥∥∥ . Clearly ΠD,V̂ 1/4t (θ
?) = θ? due to Assumption 3. We start from the update of θt when t ≥ 2.∥∥∥V̂ 1/4t (θt+1 − θ?)∥∥∥2 = ∥∥∥ΠD,V̂ 1/4t V̂ 1/4t (θt − θ? − αtV̂ − 12t mt)∥∥∥2
≤ ∥∥∥V̂ 1/4t (θt − θ? − αtV̂ − 12t mt)∥∥∥2
= ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + ∥∥∥αtV̂ −1/4t mt∥∥∥2 − 2αt(θt − θ?)Tmt
= ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + ∥∥∥αtV̂ −1/4t mt∥∥∥2 − 2αt(θt − θ?)T (β1tmt−1 + (1− β1t)gt)
(i) ≤ ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + ∥∥∥αtV̂ −1/4t mt∥∥∥2 + αtβ1t( 1αt ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + αt ∥∥∥V̂ −1/4t mt−1∥∥∥2) − 2αt(1− β1t)(θt − θ?)T gt
(ii) ≤ ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + ∥∥∥αtV̂ −1/4t mt∥∥∥2 + β1t ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tβ1t ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2 − 2αt(1− β1t)(θt − θ?)T gt,
where (i) follows from the Cauchy-Schwarz inequality, and (ii) holds because v̂t+1,i ≥ v̂t,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 Ft be the filtration of all the sampling up to time t, we have
E [ (θt − θ?)T gt ] = E [ E [ (θt − θ?)T gt ] |Ft−1 ] = E [ (θt − θ?)T ḡt ] . (18)
Thus we have E ∥∥∥V̂ 1/4t (θt+1 − θ?)∥∥∥2 ≤ E
∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tE∥∥∥V̂ −1/4t mt∥∥∥2 + β1tE∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tβ1tE∥∥∥V̂ −1/4t−1 mt−1∥∥∥2 − 2αt(1− β1t)E [ (θt − θ?)T gt
] (i) = E
∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tE∥∥∥V̂ −1/4t mt∥∥∥2 + β1tE∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tβ1tE ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2 − 2αt(1− β1t)E [ (θt − θ?)T ḡt
] (ii) ≤ E
∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tE ∥∥∥V̂ −1/4t mt∥∥∥2 + β1tE∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tβ1tE ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2 − 2αtc(1− β1t)E ‖θt − θ?‖2
(iii) ≤ E ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tE∥∥∥V̂ −1/4t mt∥∥∥2 + β1tE ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tβ1E ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2 − 2αtc(1− β1)E ‖θt − θ?‖2
(iv) ≤ E ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2 + α2tE∥∥∥V̂ −1/4t mt∥∥∥2 +G∞D2∞β1t + α2tβ1E ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2 − 2αtc(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/4t (θt − θ?)∥∥∥2 ≤∥∥∥V̂ 1/4t ∥∥∥2 2 ‖θt − θ?‖2 ≤ G∞D2∞ 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/4t (θt − θ?)∥∥∥2−E∥∥∥V̂ 1/4t (θt+1 − θ?)∥∥∥2)+ T∑ t=2 β1tG∞D 2 ∞ αt
+ T∑ t=2 αtE ∥∥∥V̂ −1/4t mt∥∥∥2 + T∑ t=2 αtβ1E ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2
(i) ≤ T∑ t=2 1 αt ( E ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2−E∥∥∥V̂ 1/4t (θt+1 − θ?)∥∥∥2)+ T∑ t=2 β1tG∞D 2 ∞ αt
+ T∑ t=2 αtE ∥∥∥V̂ −1/4t mt∥∥∥2 + T∑ t=2 αt−1β1E ∥∥∥V̂ −1/4t−1 mt−1∥∥∥2
≤ T∑ t=2 1 αt ( E ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2−E∥∥∥V̂ 1/4t (θt+1 − θ?)∥∥∥2)+ T∑ t=2 β1tG∞D 2 ∞ αt
+ (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥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/4t (θt − θ?)∥∥∥2 − ∥∥∥V̂ 1/4t (θt+1 − θ?)∥∥∥2)+ T∑ t=2 β1tG∞D 2 ∞ αt
+ (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥2
= E ∥∥∥V̂ 1/42 (θ2 − θ?)∥∥∥2
α2 + T∑ t=3 E
 ∥∥∥V̂ 1/4t (θt − θ?)∥∥∥2
αt − ∥∥∥V̂ 1/4t−1 (θt − θ?)∥∥∥2 αt−1  − E ∥∥∥V̂ 1/4T (θT+1 − θ?)∥∥∥2
αT + T∑ t=2 β1tG∞D 2 ∞ αt + (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥2
= E ∥∥∥V̂ 1/42 (θ2 − θ?)∥∥∥2
α2 + T∑ t=3 E
(∑d i=1 v̂ 1/2 t,i (θt,i − θ?i )2 αt − ∑d i=1 v̂ 1/2 t−1,i(θt,i − θ?i )2 αt−1 )
− E ∥∥∥V̂ 1/4T (θT+1 − θ?)∥∥∥2
αT + T∑ t=2 β1tG∞D 2 ∞ αt + (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥2 .
= E ∥∥∥V̂ 1/42 (θ2 − θ?)∥∥∥2
α2 + T∑ t=3 d∑ i=1 E(θt,i − θ?i )2 ( v̂ 1/2 t,i αt − v̂ 1/2 t−1,i αt−1 )
− E ∥∥∥V̂ 1/4T (θT+1 − θ?)∥∥∥2
αT + T∑ t=2 β1tG∞D 2 ∞ αt + (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥2 .
So far we just rearrange the terms in the series sum. Next, we are ready to obtain the upper bound.
2c(1− β1) T∑ t=2 E ‖θt − θ?‖2
(i) ≤
E ∥∥∥V̂ 1/42 (θ2 − θ?)∥∥∥2
α2 +D2∞ T∑ t=3 d∑ i=1 E
( v̂ 1/2 t,i
αt − v̂ 1/2 t−1,i αt−1
)
− E ∥∥∥V̂ 1/4T (θT+1 − θ?)∥∥∥2
αT + T∑ t=2 β1tG∞D 2 ∞ αt + (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥2
≤ E ∥∥∥V̂ 1/42 (θ2 − θ?)∥∥∥2
α2 +D2∞ d∑ i=1 E v̂ 1/2 T,i αT + T∑ t=2 β1tG∞D 2 ∞ αt + (1 + β1) T∑ t=1 αtE ∥∥∥V̂ −1/4t mt∥∥∥2
(ii) ≤ G∞D 2 ∞ α2 + dG∞D
2 ∞ √ T
α + β1G∞D
2 ∞
α(1− λ)2 +
α(1 + β1) √ 1 + log T
(1− β1)(1− δ) √ 1− β2 d∑ i=1 E ‖g1:T,i‖ ,
(19)
where (i) follows from Assumption 3 and because v̂ 1/2 t,i
αt > v̂ 1/2 t−1,i αt−1 , and (ii) follows from Lemmas 1 - 3.
Finally, applying the Jensen’s inequality yields
E ‖θout − θ?‖2 ≤ 1
T T∑ t=1 E ‖θt − θ?‖2 . (20)
We conclude our proof by further applying the bound in Equation (19) to Equation (20).

heading: C PROOF OF THEOREM 2
text: 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., mkr = v̂kr = 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 ‖gkr+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 ‖gkr+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) bT/rc∑ k=1 kr−1∑ t=(k−1)r E ‖θt − θ?‖2 + T∑ t=bT/rcr E ‖θt − θ?‖2 − E ‖θ0 − θ?‖2  ≤ bT/rc∑ k=0 ( G∞D 2 ∞ α √ kr + 2 + 4c(1− β1)E ‖θkr − θ?‖2 ) + bT/rc∑ k=1 dG∞D 2 ∞ α √ kr − 1
+ dG∞D
2 ∞ √ T
α +
α(1 + β1)
(1− β1)(1− δ) √ 1− β2 bT/rc∑ k=1 d∑ i=1 E ∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t
+ α(1 + β1)
(1− β1)(1− δ) √ 1− β2 d∑ i=1 E ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t
+G∞D 2 ∞ bT/rc∑ k=1 kr−1∑ t=(k−1)r+2 β1t αt +G∞D 2 ∞ T∑ t=bT/rcr+2 β1t αt
≤ bT/rc∑ k=0 ( G∞D 2 ∞ α √ kr + 2 + 4c(1− β1)E ‖θkr − θ?‖2 ) + bT/rc∑ k=1 dG∞D 2 ∞ α √ kr − 1
+ dG∞D
2 ∞ √ T
α +
α(1 + β1)
(1− β1)(1− δ) √ 1− β2 bT/rc∑ k=1 d∑ i=1 E ∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t
+ α(1 + β1)
(1− β1)(1− δ) √ 1− β2 d∑ i=1 E ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t +G∞D 2 ∞ T∑ t=1 β1t αt .
We can bound the term G∞D2∞ ∑T t=1 β1t αt
by Lemma 3. Next, we bound another key term in the above inequality. We first observe that ∀k ≥ 2,∀i ∈ [d],
∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t (i) ≤ ∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t + |gkr,i| √ 1 kr
(ii) ≤ ∥∥g(k−1)r+1:kr,i∥∥ √√√√ kr∑ t=(k−1)r+1 1 t ,
(21)
where (i) holds due to |gt,i| √ 1 t > 0 and (ii) follows from the Cauchy-Schwarz inequality. Then we have
bT/rc∑ k=1 d∑ i=1 ∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t + d∑ i=1 ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t
(i) ≤ bT/rc∑ k=1 d∑ i=1 |gkr,i| √ 1 kr + bT/rc∑ k=1 d∑ i=1 ∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t
+ d∑ i=1 ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t
= bT/rc∑ k=1 d∑ i=1 ∥∥g(k−1)r+1:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r+1 1 t + |gkr,i| √ 1 kr  +
d∑ i=1 ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t
(ii) ≤ bT/rc∑ k=1 d∑ i=1 ∥∥g(k−1)r+1:kr,i∥∥ √√√√ kr∑ t=(k−1)r+1 1 t + d∑ i=1 ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t
= d∑ i=1 bT/rc∑ k=1 ∥∥g(k−1)r+1:kr,i∥∥ √√√√ kr∑ t=(k−1)r+1 1 t + ∥∥gbT/rcr+1:T,i∥∥ √√√√ T∑ t=bT/rcr+1 1 t  (iii) ≤
d∑ i=1 ‖g1:T,i‖ √√√√ T∑ t=1 1 t ,
where (i) follows from |gkr,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) T∑ t=1 E ‖θt − θ?‖2
≤ bT/rc∑ k=0 ( G∞D 2 ∞ α √ kr + 2 + 4c(1− β1)E ‖θkr − θ?‖2 ) + bT/rc∑ k=1 dG∞D 2 ∞ α √ kr − 1
+ dG∞D
2 ∞ √ T
α +
α(1 + β1)
(1− β1)(1− δ) √ 1− β2 bT/rc∑ k=1 d∑ i=1 E ∥∥g(k−1)r:kr−1,i∥∥ √√√√ kr−1∑ t=(k−1)r 1 t
+ α(1 + β1)
(1− β1)(1− δ) √ 1− β2 d∑ i=1 E ∥∥gbT/rcr:T,i∥∥ √√√√ T∑ t=bT/rcr 1 t +G∞D 2 ∞ T∑ t=1 β1t αt
≤ bT/rc∑ k=0 ( G∞D 2 ∞ α √ kr + 2 + 4c(1− β1)E ‖θkr − θ?‖2 ) + bT/rc∑ k=1 dG∞D 2 ∞ α √ kr − 1
+ dG∞D
2 ∞ √ T
α +
α(1 + β1)
(1− β1)(1− δ) √ 1− β2 d∑ i=1 E ‖g1:T,i‖ √√√√ T∑ t=1 1 t +G∞D 2 ∞ T∑ t=1 β1t αt
(i) ≤ bT/rc∑ k=0 ( G∞D 2 ∞ α √ kr + 2 + 4c(1− β1)E ‖θkr − θ?‖2 ) + bT/rc∑ 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 ‖g1:T,i‖+ β1G∞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 bT/rc∑ k=0 ( G∞D 2 ∞ 2cα(1− β1) √ kr + 2 + 2E ‖θkr − θ?‖2 ) + 1 T bT/rc∑ 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 ‖g1:T,i‖+ β1G∞D 2 ∞ 2cα(1− β1)(1− λ)2 ,
which concludes the proof.

Review summaries:
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.

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