Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
Authors: Shaocong Ma
Ziyi Chen
Yi Zhou
Shaofeng Zou
Venue: ICLR 2021 Poster (2021)
Keywords: Optimization
Reinforcement Learning
Machine Learning

Abstract: Greedy-GQ is a value-based reinforcement learning (RL) algorithm for optimal control. Recently, the finite-time analysis of Greedy-GQ has been developed under linear function approximation and Markovian sampling, and the algorithm is shown to achieve an $\epsilon$-stationary point with a sample complexity in the order of $\mathcal{O}(\epsilon^{-3})$. Such a high sample complexity is due to the large variance induced by the Markovian samples. In this paper, we propose a variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm for off-policy optimal control. In particular, the algorithm applies the SVRG-based variance reduction scheme to reduce the stochastic variance of the two time-scale updates. We study the finite-time convergence of VR-Greedy-GQ under linear function approximation and Markovian sampling and show that the algorithm achieves a much smaller bias and variance error than the original Greedy-GQ. In particular, we prove that VR-Greedy-GQ achieves an improved sample complexity that is in the order of $\mathcal{O}(\epsilon^{-2})$. We further compare the performance of VR-Greedy-GQ with that of Greedy-GQ in various RL experiments to corroborate our theoretical findings.

Published as a conference paper at ICLR 2021
GREEDY-GQ WITH VARIANCE REDUCTION: FINITE- TIME ANALYSIS AND IMPROVED COMPLEXITY
Shaocong Ma, Ziyi Chen & Yi Zhou
Shaofeng Zou Department of EE University at Buffalo Buffalo, NY 14260 szou3 fa edu
Department of ECE
University of Utah Salt Lake City, UT 84112 {s ma,
(a.ma, 01276972, zhou caaauueeuthheeee
ABSTRACT
Greedy-GQ value-based reinforcement learning (RL) algorithm for optimal control. Recently, the finite-time analysis of Greedy-GQ has been developed un- der linear function approximation and Markovian sampling, and the algorithm is shown to achieve an e-stationary point with sample complexity in the order of O(e-²). Such a high sample complexity is due to the large variance induced by the Markovian samples. In this paper, we propose variance-reduced Greedy- GQ (VR- Greedy--G)) algorithm for off-policy optimal control. In particular, the algo- rithm applies the SVRG-based variance reduction scheme reduce the stochas- tic variance of the two time-scale updates. We study the finite-time convergence of EE-Greedy-GGO under linear function approximation and Markovian sampling and show that the algorithm achieves a much smaller bias and variance error than the original Greedy- GQQ In particular, we prove that VR-Greedy-CG achieves an improved sample complexity that is in the order of O(c-3). 3). We further compare the performance of VR-Greedy-GEr with that of Greedy-GQ various RL exper- iments to corroborate our theoretical findings.
INTRODUCTION
In reinforcement learning (RL), an agent interacts with a stochastic environment following a certain policy and receives some reward, and it aims to learn optimal policy that yields the maximum cumulated reward Sutton & Barto (2018). In particular, many RL algorithms have been developed to learn the optimal control policy, and they have been widely applied to various practical applications such as finance, robotics, computer games and recommendation systems Mnih et al. (2015; 2016); Silver et al. (2016); Kober et al. (2013).
Conventional RL algorithms such as Q-learning Watkins & Dayan (1992) and SARSA Rummery & Niranjan (1994) have been well studied and their convergence guaranteed in the tabular setting. However, it is known that these algorithms may diverge in the popular off-policy setting under lin- car function approximation Baird (1995); Gordon (1996). To address this issue, the two time-scale Greedy-GQ algorithm was developed in Maei et al. (2010) for learning the optimal policy. This algorithm extends the efficient gradient temporal difference (GTD) algorithms for policy evaluation Sutton et al. (2009b) to policy optimization. In particular, the asymptotic convergence of Greedy- GQ to stationary point has been established Maei et al. (2010). More recently, Wang & Zou (2020) studied the finite-time convergence of Greedy-Ge under linear function approximation and Markovian sampling, and it is shown that the algorithm achieves an e-stationary point of the objec- tive function with sample complexity in the order of O Such an undesirable high sample complexity is caused by the large variance induced by the Markovian samples queried from the dynamic environment. Therefore, want ask the following question.
Ql: Can develop variance reduction scheme for the two time-scale Greedy-GQ algorithm?

---

Published as a conference paper at ICLR 2021
In fact, in the existing literature, many recent work proposed to apply the variance reduction tech- niques developed in the stochastic optimization literature to reduce the variance of various TD learn- ing algorithms for policy evaluation, e.g., Du et al. (2017); Peng et al. (2019); Korda & La (2015); Xu et al. (2020). Some other work applied variance reduction techniques to Q-learning algorithms, e.g.. Wainwright (2019); Jia et al. (2020). Hence, it is much desired to develop variance-reduced Greedy-GQ algorithm for optimal control. In particular, as many of the existing variance-reduced RL algorithms have been shown achieve an improved sample complexity under variance reduc- tion, it is natural to ask the following fundamental question.
Q2: Can cariance-reduced Greedy-GQ achieve an improved sample complexity under Markovian sampling?
In this paper, we provide affirmative answers to these fundamental questions. Specifically, we develop two time-scale variance reduction scheme for the Greedy-GQ algorithm by leveraging the SVRG scheme Johnson Zhang (2013). Moreover, under linear function approximation and Markovian sampling, we prove that the proposed variance-reduced Greedy-GQ algorithm achieves an e-stationary point with an improved sample complexity O(E We summarize our technical contributions follows.
1.1 OUR CONTRIBUTIONS
We develop variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm for optimal control in inforcement learning. Specifically, the algorithm leverages the SVRG variance reduction scheme Johnson & Zhang (2013) to construct variance-reduced stochastic updates for updating the parame- ters in both time-scales.
We study the finite-time convergence of VR-Greedy-GQ under linear function approximation and Markovian sampling in the off-policy setting. Specifically, we show that VR-Greedy-GQ achieves an e-stationary point of the objective function J (i.e., [(](2) S e) with a sample complexity in the order of O(e 3). Such a complexity result improves that of the original Greedy-GG by significant factor of () Wang & Zou (2020). In particular, our analysis shows that the bias error caused by the Markovian sampling and the variance error of the stochastic updates are in the order of (MM-)) O0 (no.M-)) respectively, where d)o is the learning rate and M corresponds to the batch size of the SVRG reference batch update. This shows that the proposed variance reduction scheme can significantly reduce the bias and variance errors of the original Greedy-GQ update (by factor of M) and lead to improved overall sample complexity.
The analysis logic of VR-Greedy-GQ partly follows that of the conventional SVRG, but requires substantial new technical developments. Specifically, we must address the following challenges. First, VR-Greedy-GGQ involves two time-scale variance-reduced updates that are correlated with each other. Such an extension of the SVRG scheme the two time-scale updates is novel and re- quires new technical developments. Specifically, we need to develop tight variance bounds for the two time-scale updates under Markovian sampling. Second, unlike the convex objective functions of the conventional GTD type of algorithms, the objective function of VR-Greedy-GQ is generally non-convex due to the non-stationary target policy. Hence, we need develop new techniques to characterize the per-iteration optimization progress towards stationary point under nonconvexity. In particular, to analyze the two time-scale variance reduction updates of the algorithm, we intro- duce a 'fine-tuned' Lyapunov function of the form 1t!" = [(!!")) + cello!")) ((mm)12, where the parameter o is fine-tuned to cancel other additional quadratic terms ||0[m) T(m) I|2 that are implic- itly involved in the tracking етror terms. The design of this special Lyapunov function is critical to establish the formal convergence of the algorithm. With these technical developments, we are able to establish an improved finite-time time convergence rate and sample complexity for VR-Greedy-CGe
1.2 RELATED WORK
Q-learning and SARSA with function approximation. The asymptotic convergence of Q-learning and SARSA under linear function approximation were established in Melo et al. (2008); Perkins & Precup (2003). and their finie--imme analysis were developed in Zou et al. (2019); Chen et al. (2019). However, these algorithms may diverge in off oollpy training Baird (1995). Also, recent works focused on the Markovian setting. Various analysis techniques have been developed to analyze
2

---

Published as a conference paper at ICLR 2021
the finite-time convergence of ID/Q-learning under Markovian samples. Specifically, Wang et al. (2020) developed a multi-step Lyapunov amalysis for addressing the biasedness of the stochastic approximation in Q-learning. Srikant & Ying (2019) developed a drift analysis to the linear stochas- tic approximation problem. Besides the linear function approximation, the finite-time analysis of Q-learning under neural network function approximation is developed in Xu & Gu (2019).
GTD algorithms. The GTD2 and TDC algorithms were developed for off-policy TD learning. Their asymptotic convergence was proved in Sutton al. (2009a;b); Yu (2017), and their finite-time analysis were developed recently in Dalal et al. (2018); Wang et al. (2017); Liu et al. (2015); Gupta al. (2019); Xu et al. (2019). The Greedy-GQ algorithm is an extension of these algorithms to optimal control and involves nonlinear updates.
RL with variance reduction: Variance reduction techniques have been applied to various RL al- gorithms. In TD learning, Du et al. (2017) reformulate the MSPBE problem as a convex-concave saddle-point optimization problem and applied SVRG Johnson & Zhang (2013) and SAGA Defazio et al. (2014) primal-dual batch gradient algorithm. In Korda & La (2015), the rrrianc-rreduced TD algorithm was introduced for solving the MSPBE problem, and later Xu et al. (2020) provided correct non-asympiotic analysis for this algorithm over Markovian samples. Recently, some other works applied the SVRG SARAH Nguyen et al. (2017) and SPIDER Fang et al. (2018) variance reduction techniques develop variance-reduced Q-learning algorithms, e.g., Wainwright (2019); Jia et al. (2020). In these works, TD or TDC algorithms are in the form of linear stochastic approx- imation, and Q-learning has only single time-scale update. As comparison, our VR-Greedy-GQ takes nonlinear two time-scale updates to optimization a nonconvex MSPBE.
2 PRELIMINARIES: POLICY OPTIMIZATION AND GREEDY-GQ
In this section, we review some preliminaries of reinforcement learning and recap the Greedy-GQ algorithm under linear function approximation.
2.1 POLICY OPTIMIZATION REINFORCEMENT LEARNING
In reinforcement learning, an agent takes actions to interact with the environment via Markov Decision Process (MDP). Specifically, an MDP specified by the tuple (S,A, P.r, where S and A respectively correspond to the state and action spaces that include finite elements, r AxxxS + [0, +o0) denotes reward function and 7 E (0, 1) the associated reward discount factor.
At any time f, assume that the agent is in the state E S and takes certain action E A following a stationary policy n, i.c., Gr ~ π (-(s)). Then, at the subsequent time + 1, the current state of the agent transfers to new state St+1 according to the transition kernel (- ). At the same time, the agent receives a reward r = r(s,, at, $t-1) from the environment for this action-state transition. To evaluate the quality of given policy
often use the action-state value function Q" S x A + R that accumulates the discounted rewards as follows:
Q (s, = =EssP())s.a) [r(s, s') + >VV"(s')]
where (*))s is the state value function defined (*()) = E o =s] In partieu- lar, define the Bellman operator T such that T (T(((s,) a) (r(s, a.) +7Q(s' aa)) for any Q(s, a), where ~ x--ls). Then, Q= a) is a fixed point 7" i.c.
T" as),s,), Vs,a.
learn the optimal policy म² that maximizes the expected total 2 2're s] for any initial state E S, and this is equivalent to learn the optimal value function Q" Q"(ss,) a) = sup, Q (s, a). Vs, a. particular, Q" is a fixed point of the Bellman operator T that is defined TQ(s, a) P(ss) s') m Q(s', b)].
The goal of policy optimization reward B
2.2 GREEDY-GQ WITH LINEAR FUNCTION APPROXIMATION
The Greedy-Gr algorithm is inspired by the fixed point characterization in eq. (I), and in the tabular setting it aims minimize the Bellman emror l Q"I Here, || [|2... is induced by
3

---

Published as a conference paper at ICLR 2021
the state-action stationary distribution Ms,a (induced by the behavior policy TT), and is defined as || = (((,,)))
In practice, the state and action spaces may include a large number of elements that makes tabular approach infeasible. To address this issue, function approximation technique is widely applied. In this paper, we consider approximating the state-action value function Q(s, a) by a linear function. Specifically, consider set of basis functions {Ø(() : A + R. i= 1,2, d}. each of which maps a given state-action pair to certain value. Define Φs.a (s) (( (s, a)] as the feature vector for (s, a). Then, under linear function approximation. the value function Q(s a) is approximated by Qn(s, a) & 6,,00, where 0 E Rd denotes the parameter of the linear approxi- mation. Consequently, Greedy-GQ aims to find the optimal 0" that minimizes the following mean squared projected Bellman error (MSPBE).
(MSPBE): J(O) |17 Q0 Qol
where Hs,a is the stationary distribution induced by the behavior policy ve. Il a projection operator that maps an action-value function Q to the space Q spanned by the feature vectors, i.e., IIQ arg min | - ell.... Moreover, the policy ma is parameterized by In this paper, we consider the class of Lipschitz and smooth policies (see Assumption 4.2).
Next, we introduce the Greedy-Gi algorithm. Define Vo((0)
=Eved To (' 0.
o (0) a,s,a, 5') (0) 2T.00 and denote (0) VV. VV. Then, the gradient of
the objective function (0) in eq. (2) is expressed
( = 166, s (0) + El (0) s, (0),
where (0) Tf S. - -E o/ (,) To address the double-sampling issue when esti- (0) (0). Sutton et al. (2009a) applies weight doubling trick and constructs the following two time-scale update rule for the Greedy-GQ algorithm: for every t 0, 1, 2, sample (st, ae, Tt, St+1) using the behavior policy and do
mating the product of expectations involved in Bl (0) s
cc+1 = 02 - 77 1 + 7(u, @.)))+1
(Greedy-GO)
Wh+1 = Wt n (0t (0))
(3)
100 P(OT -P 0.+1).
where no. The O are the learning rates and we denote 6.+1 (0) = Se, 00. (0), 2 as. Se+1 (0.) S.. (0x) for simplicity. To elaborate, the first two steps correspond to the two time- scale updates for updating the value function Qo, whereas the last step is policy improvement operation that exploits the updated value function to improve the target policy, e.g., greedy, e-greedy, softmax and mellowmax Asadi Littman (2017).
The above Greedy-GQ algorithm uses a single Markovian sample to perform the two time-scale updates in each iteration. Such a stochastic Markovian sampling significantly slows down the overall convergence. This motivates us to develop variance reduction schemes for the two time-scale Greedy- the next section.
often induces a large variance that
GREEDY-GQ WITH VARIANCE REDUCTION
In this section, we propose a variance-reduced Greedy-GQ VV--Gredy-GQQ) algorithm under Markovian sampling by leveraging the SVRG variance reduction scheme Johnson & Zhang (2013). To simplify notations, we define the stochastic updates regarding sample xt = (8t, a, Tt, 8(+1) used in the Greedy-GQ follows:
Gz, = 86 + 7ww To)
Hz, (0, w) = (0T w (0))
Next, consider a single MDP trajectory { obtained by the behavior policy Tp. In partic- ular, divide the entire trajectory into multiple batches of samples (Bm)22 that B,n
4

---

Published as a conference paper at ICLR 2021
{m/m- - 11M .... 2m1-1 and our proposed VR-Greedy- uses one batch of samples in every epoch. To elaborate, in the m-th epoch, we first initialize this epoch with pair reference points m!m) 0(m), wamm) a(m), where @lm), a3(m) are set to be the output points 0f ((m-1) (m-1) of Mr the previous epoch, respectively. Then, we compute a pair reference batch updates using the reference points and the batch of samples as follows
md--1
mM-1 -1
(mm)
Σ
H(m)
Σ k= 11M
Hag (0(m)) (m()))
(4)
M
M
k= (m-1))M
In the t-th iteration of the m-th epoch, we first query random sample zgr from the batch Bm uniformly with replacement (i.e., sample et from {(m 1). mM }} uniformly). Then, we use this sample to compute the stochastic updates Gzep, Hag. at both of the points (o(m) (o(m) (m)), (0(m), ()))). After that, we use these stochastic updates and the reference batch updates to construct the variance-reduced updates in Algorithm I via the SVRG scheme, where for simplicity we denote the stochastic updates Gzegu Hegp respectively as G. G( _H(T" In particular, project the two time-scale updates onto the Euclidean ball with radius R to stabilize the algo- rithm updates, and we assume that R is large enough to include at least one stationary point of J. Lastly, we further update the policy via the policy improvement operation P.
(m)
Algorithm 1: Mariance-Reduced Greedy-
Input: learning rates 7o. Mus batch size M. Initialize: ((1) = 0, (1)) = wo. Taa + P(o TO()).
for m 1, .. do
pgm) ((m)) wb (m) (m). Compute (mm), (m) according eq. (4).
for = 0.1..... .M- do
Query a sample from B., with replacement.
p(m)) = IT [m:) - no (G (m) (0(m)) (((")) - G. (@im) (mmm) + {(m)))
w (m))
I wi (m) (H, (m) (0(m)) ,w0 (m) - H!!e (m)) (p(m)) (m))) ) + Hm(m
Policy improvement: Tz(m) f P(o )lm))
end
Set ((m++1
(m))) (m(+1) wmmm
end
Output: parameter & chosen among (0(")).... Jr.. uniformly at random.
The above VR-Greedy-GQ algorithm has several advantages and uniqueness. First, takes incre- mental updates that use single Markovian sample per-iteration. This makes the algorithm sample efficient. Second, VR-Greedy-GQ applies variance reduction to both of the time-scale updates. As we show later in the analysis, such a two time-scale variance reduction scheme significantly reduces the variance error of both of the stochastic updates.
We want to further clarify the incrementalism and online property of VR-Greedy-GQ. Our VR- Greedy-GQ is based on the online-SVRG and can be viewed as incremental algorithm with regard to the batches of samples used in the outer-loops, i.e., in every outer-loop the algorithm samples new batch of samples and use them to perform variance reduction in the corresponding inner-loops. Therefore, VR- TR-Greedy-GQ can be viewed as an online batch-ineree incremental algorithm. In general, there is a trade-off between incrementalism and variance reduction for SVRG-type algorithms: larger batch size in the outer-loops enhances the effect of variance reduction, while smaller batch size makes the algorithm more incremental.
ANALYSIS OF VR-GREEDY-GQ
In this section, we analyze the finit--imme convergence rate of TR-Greedy-GQ. We adopt the follow- ing standard technical assumptions from Wang & Zou (2020); Xu et al. (2020).
5

---

Published as a conference paper at ICLR 2021
Assumption 4.1 (Feature boundedness). The feature vectors uniformly bounded, i.e, 11 1 1 for all (s, a) E x A. Assumption 4.2 (Poliey smoothness). The mapping + Th -L-ipscchitz and k2-smooth.
We note that the above class of smooth policies covers a variety of practical policies, including softmax and mellowmax policies Asadi & Littman (2017); Wang & Zou (2020).
Assumption 4.3 (Problem solvability). The matrix C = El s,al is non-singular.
Assumption 4.4 (Geometric uniform ergodicity). There exists A > 0 and p E (0, 1) such that
sup .ES
= x) s Ap',
for any O, where drv is the notal-variation distance.
Based the above assumptions, obtain the following finite-time convergence rate result.
Theorem 4.5 (Finite-time convergence). Let Assumptions 4.1- 4.4 hold and consider the VR- Greedy-GQ algorithm. Choose learning rates nes Qu and the batch size M that satisfy the conditions specified in eqs. (15) to (19). Then, after T epochs, the oulput of the algorithm satisfies
E|| |
5 1
1 (1 7oTM TTTT
+
nh
(nw
73
1
The
T
M
where 5.S are random indexes that are sampled from {O...., M 1} and {1, (1..... T} uniformly at random, respectively.
Theorem 4.5 shows that VR-Greedy-GQ asymptotically converges to a neighborhood of stationary point sublinear rate. particular, the size of the neighborhood is in the order of O(M n/m_ + ) which can be driven arbitrarily close to zero by choosing large batch size and sufficiently small learning rates that satisfy the two time-scale condition Too /0/%/ - O. Moreover, the convergence error terms implicitly include bias error O 3z caused by the Markovian sampling and variance error O ne caused by the stochastic updates, both of which are substantially reduced by the large batch size M. This shows that the SVRG scheme can effectively reduce the bias and variance error the two time-scale stochastic updates.
By further optimizing the choice of hyper-parameter we obtain the following characterization of sample complexity of VR-Greedy-GQ.
Corollary 4.6 (Sample complexity). Under the same conditions as those of Theorem 4.5, choose learning rates so that ne = O hr), ), = O 2/3, and set T,M ())- Then, the required sample complexity for achieving ((A ||( < c is in the order of T (c-
Such complexity result is orderwise lower than the complexity 33) of the original Greedy-GQ Wang & Zou (2020). Therefore, this demonstrates the advantage of applying variance reduction to the two time-scale updates of VR-Greedy-GO. We also that for online stochastic non-convex optimization, the sample complexity of the SVRG algorithm is in the order of O(e ((() Li & Li (2018), which is slightly better than our result. This is reasonable as the SVRG in stochastic opti- mization is unbiased due the i.i.d. sampling. In comparison, VR-Greedy-GQ works a single MDP trajectory that induces Markovian noise, and the two- voo-immeccale updates of the algorithm also introduces additional tracking error.
SKETCH OF THE TECHNICAL PROOF
In this section, we provide an outline of the technical proof the main Theorem 4.5 and highlight the main technical contributions. The details of the proof can be found in the appendix.
We note that our proof logic partly follows the that of the conventional SVRG, i.e., exploiting the objective function smoothness and introducing Lyapunov function. However, our analysis requires substantial new developments to address the challenges of off-policy control, two time-scale updates of VR- TR-Greedy-GQ and correlation of Markovian samples.

---

Published as a conference paper at ICLR 2021
The key step of the proof is to develop proper Lyapunov function that drives the parameter to stationary point along the iterations. In addition, we also need to develop tight bounds for the bias error, variance error and tracking error. We elaborate the key steps of the proof below.
Step 1: We first define the following Lyapunov function with certain C2. > to be determined later.
R4 = == + ce cell0]") 0lm))p
(5)
To explain the motivation, note that unlike the analysis of aariance-reduced TD learning Xu et al. (2020) where the term [|0|!) - (ím))|2 can be decomposed into [10(m) 1- + ||0(m) - 2 to get the desired upper bound, here we do not have 0* due to the non-convexity of (0). Hence, we need properly merge this term into the Lyapunov function Ho By leveraging the smoothness of
J(O) and the algorithm update rule, we obtain the following bound for the Lyapunov function R." (see eq. (10) in the appendix for the details).
E R 1 S B[J(O[ ( + (E(10( m(m) 122] B[Il B[I[ 1|12 1-
+ O (F wt (o(m)) ||²] + B[||w] (m) - - (0, (0! ||
(6)
In particular, the error term X7 is due to the noise of Markovian sampling and the variance of the stochastic updates, and the last two terms correspond to tracking errors.
Step 2: To telescope the Lyapunov function over t based on eq. (6), may want to define [(B[ + (E[lle!m)
((m))pp)) R." by choosing a proper et of R.T. However, note that eq. (6) involves the last two tracking error terms, which also implicitly depend on Eljo(T) - 7 j|a as we show later in the Step 3. Therefore, we need to carefully define the ct of R. so that after applying the tracking error bounds developed the Step 3, the right hand side of eq. (6) can yield
an R," without involving the term Elle!")) @(m)) I|?. It turns out that we need to define oe via the recursion specified in eq. (11) in the appendix. We rigorously show that the sequence {Co]e is uni- formly bounded by a small constant ē = g. Then, plugging these bounds into eq. (6) and summing over one epoch, we obtain the following bound (see eq. (13) in the appendix for the details).
M-1
no
J
)1 S E[RE"] B[RT O (B wn w²(0(m))))3)
M
M- Ello!!m) - @11))191).
+ o ne Σ
E |بm (mm)
- - (0(m)) )12 nec nuo +
Ne T
Step We derive bounds for the tracking error terms -M Bl[w (()) w (o! )12 and (m)
w² (((m))) 2 in the above bound in Lemma D.7 and Lemma D.8.
Step 4: Lastly, by substituting the tracking error bounds obtained in Step 3 into the bound obtained
in Step 2, the resulting bound does not involve the term ΣM'1 "llo(")) - Øom) 1|2. Then, summing this bound over the epochs m .,.,, T, we obtain the desired finite-time convergence rate result.
EXPERIMENTS
In this section, we conduct two reinforcement learning experiments, namely, Garnet problem Archibald al. (1995) and Frozen Lake game Brockman et al. (2016), to test the performance of VR-Greedy-GQQ in the off-po setting, and compare it with Greedy- Beeedy-GQ in the Markovian setting.
6.1 GARNET PROBLEM
For the Garnet problem, we refer to Appendix F for the details of the problem setup. In Figure (left), we plot the minimum gradient norm v.s. the number of pseudo stochastic gradient com- putations for both algorithms using 40 Garnet MDP trajectories, and each trajectory contains 10k samples. The upper and lower envelopes of the curves correspond to the 95% and 5% percentiles of the 40 curves, respectively. It can be seen that VR-Greedy-GQ outperforms Greedy-GQ and achieves a significantly smaller asymptotic gradient norm.
7

---

Published as a conference paper at ICLR 2021
Convergence Error VR-Greedy-GG under Different Batch Sizes
Greedy-GG
Greedy-GQ
0.035
VR Greecyy GQ: M-3000
1.75
VR. Gready GQ: M-3000
0.030
1.50
Convergence Error
0.6
1.25
0.020
1.00
0.4
0.015
Edimated
0.010
0.2
0.005
0.000
4 of gradient compurations
2500
5000
7500
10000
0.00
100
of Iterations
200
300
400
0.0
1
1000
Batch Size
2000
3000
Figure Comparison Greedy-Ge and VR- VR-Greedy- GQ in solving the Garnet problem.
In Figure (middle), we track the estimated variance of the stochastic update for both algorithms along the iterations. Specifically, we query 500 Monte Carlo samples iteration to estimate the
pseudo gradient variance EE| E||G(()) ((()) W. ())) (e(r))) )|? It can be seen from the figure that the stochastic updates of VR- TR-GGreey--Ge induce much smaller variance than Greedy-GQ This demonstrates the effectiveness of the two time-scale variance reduction scheme of IR-Greedy-GQ.
(0(m²)
We further study the asymptotic convergence error of VR-Greedy- under different batch sizes M. We use the default learning rate setting that is mentioned previously and run 100k iterations for one Gareet trajectories. We use the mean of the convergence error of the last 10k iterations as estimate of the asymptotic convergence error (the training curves are already saturated and flattened), Figure 1 (right) shows the asymptotic convergence error of "R-Greedy-GGr GQQ under different batch sizes M. can be seen that VR- ER-Greedy-Go achieves a smaller asymptotic convergence error with a larger batch size, which matches our theoretical result.
20.0
Greedy-CO
GQ VR Greedy 60: M-3000
0.3650
17.5
VB-Crmedy--iit Mi-3000
15.0
Maimum Roased
Maximum Rowwrrd
0,3000
0,360
0.353
0.3322
Greedy N-1000
0.250
0.3775
computations
3K
9k computatons
12x
Beration
gradle
Figure 2: Comparison of MSPBE and reward obtained by Greedy-GQ, VR-Greedy-GQ and PG.
In Figure 2 (Left), we plot the MSPBE J0) v.s. number of gradient computations for both Greedy- GQ and VR-Greedy-GQ. where one can see that VR-Greedy-GQ achieves a much smaller MSPBE than Greedy-GQ. In Figure (Middle), pendix F for details) v.s. number of gradient computations for Greedy-GQ, VR-Greedy-GO and actor-critic, where for actor-critic we set learning rate пe 0.02 for the actor update and n 0.01 for the critic update. One can see that VR- TR-Greedy-Go achieves higher reward than the other two algorithms, demonstrating the high quality of its learned policy. addition, we also plot the es- timated expected maximum reward policy gradient in Figure 2 (Right). For the policy gradient, we apply the standard off-policy policy gradient algorithm. For each update, we sample 30 independent trajectories with fixed length 60 to estimate the expected discounted return. The learning rate of policy gradient is set as 7j0- We note that each iteration of policy gradient consumes 1800 samples and hence it is very sample inefficient. Hence we set the r-axis to be number of iterations for a clear presentation (otherwise it becomes flat curve). One can see that VR-Greedy-GG achieves much higher expected reward than both Greedy-GQ and policy gradient.
plot the estimated expected maximum reward (see Ap-
number of iterations for Greedy-GQ, VR-Greedy-GQQ and
6.2 FROZEN LAKE GAME
We further test these algorithms in solving the more complex frozen lake game. we refer to Ap- pendix F for the details of the problem setup. Figure shows the comparison between VR-Greedy-
8

---

Published as a conference paper at ICLR 2021
GQ and Greedy-Go and make consistent observations with those made in the Garnet periment. Specifically, Figure 3 (left) shows that VR-Greedy-GQ achieves a much more stationary policy than Greedy-GQ. Figure 3 (middle) shows that the stochastic updates of VR-Greedy-Gö induce a much smaller variance than those of Greedy-GQ. Moreover, Figure (right) verifies our theoretical result that VR-Greedy achieves smaller asymptotic convergence error with larger batch size.
1e5
Convergence Error of VR-Greedy-GQ under Different Balch Sizes
Vi-Greedy-CQ M- 3000
Greedy
Estimated Gradient Vertence
3.5
VR GG: M-3000
Greedy-GO
1.0
3.0
min "UOPN
50
2.5
0.8-
40
0.6
30-
1.5
0.4
20
1.0
0.2
0.5
20R
4dkk
60k
Bok
100k
0.0
0.0
1
200
400
800
of gradient computations
Batch Size
Figure 3: Comparison of Greedy-GQ and VR-Greedy-GG in solving the Frozen Lake problem.
We further plot the MSPBE u.s. number of gradient computations for both Greedy-GO and VR- Greedy-GQ in Figure 4 (Left), where one can see that VR-Greedy-GQ outperforms Greedy-GQ. In Figure 2 (Middle), we plot the estimated expected maximum reward v.s. number of gradient computations for Greedy-GQ. VR-Greedy-GQ and actor-critic, where for actor-critic we learning rate 7e 0.2 for the actor update and T 0.1 for the critic update. It can be seen that VR- Greedy-GQ achieves higher reward than the other two algorithms. In Figure 2 (Right), we plot the estimated expected maximum reward v.s. number of iterations for Greedy-GQ, VR-Greedy "R-Greedy-Go and policy gradient. For policy gradient, we use the same parameter settings as before. One can see that VR- IR-Greedy-GQ achieves much higher expected reward than both Greedy-GQ and policy gradient.
Actor-Crit
10
Greedy-GG
Policy Greclent
Greedy-GQ
VitCrreey--3ii Ni30000
Greedy GO
Greedy GO: No-0000
VR-Sreeddy-Ga G0i Mo-3000
Maximum nowarrd
Vist Veatuum Renuere
0.006
2.004
2-
0,002
0.002
20k
grad compu computttion
40%
30k
100+
6,000
grocient computations
100k
200k
300k
0.000
103k
Iteratioos
200k
300c
Figure 4: Comparison of MSPBE and reward obtained by Greedy-GQ, VR-Greedy-GQ and PG.
7 CONCLUSION
In this paper, we develop a variance-reduced two time-scale Greedy-GO algorithm for optimal con- trol by leveraging the SVRG variance reduction scheme. Under linear function approximation and Markovian sampling, we establish the sublinear finite-time convergence rate of the algorithm to stationary point and prove an improved sample complexity bound over that of the original Greedy- GQ. The RI. experiments well demonstrated the effectiveness of the proposed two time-scale vari- ance reduction scheme. Our algorithm design may inspire new developments of variance reduction for two time-scale scale RL algorithms. In the future, will explore Greedy-GO with other nonconvex variance reduction schemes to possibly further improve the sample complexity.
ACKNOWLEDGEMENT
The work of S. Zou was supported by the National Science Foundation under Grant CCF-2007783.

---

Published as a conference paper at ICLR 2021
REFERENCES
TW Archibald, KIM McKinnon, and LC Thomas. On the generation of Markov decision processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
Kavosh Asadi and Michael Littman. alternative softmax operator for reinforcement learning- In Proceedings the 34th International Conference Machine Coaninng-Volume 70, pp. 243- 252. JMLR. org, 2017.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym, 2016.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke Perfor- mance of Q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint arXiv:1905.1 1425, 2019.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. Proceedings of Machine Learning Research, 75:1-35, 2018.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 1646-1654, 2014.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. Proc. International Conference on Machine Learning (ICML), pp. 1049-1058, 2017.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 689-699, 2018.
Geoffrey Gordon. Chattering in SARSA (A)-a CMU learning lab internal report. Citeseer, 1996.
Harsh Gupta, R Srikant, and Lei Ying. Finite-timg performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. In Proc. Advances in Neural Information Processing Systems (NeurIPS). pp. 4706-4715, 2019.
Haonan Jia, Xiao Zhang, Jun Xu, Wei Zeng, Hao Jiang, Xiaohui Yan, and Ji-Rong Wen. Variance reduction for deep g-laarning using stochastic recursive gradient. arXiv:2007.12817, 07 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in roboties: A survey. The International Journal of Robotics Research, 32(11):1238-1274 2013.
Nathaniel Korda and Prashanth La. On td (0) with function approximation: and a centered variant with exponential convergence. International Conference on Machine Learning, pp. 626-634, 2015.
Concentration bounds
Zhize Li and Jian Li. simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in neural information processing systems, pp. 555445574, 2018.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), pp. 504-513. Citeseer, 2015.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton. Toward off oof-pc learning control with function approximation. In Proc. International Conference on Machine Learning (ICMI), 2010.
10

---

Published as a conference paper at ICLR 2021
Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. Proc. International Conference on Machine Learning (ICML), pp- 664-671. ACM, 2008.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, Graves, M. Ried- miller, A. K. Fidjeland, and G. Ostrovski. Human-level control through deep reinforcement learn- ing. Nature, 518:529-5333 2015.
V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proc. International Conference Machine Learning (ICML), pp.
2016.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Searning-Volume 70, pp. 2613-2621. JMLR. org, 2017.
Zilun Peng, Ahmed Touati, Pascal Vincent, and Doina Precup. SVRG for policy evaluation with fewer gradient evaluations. arXiv:1906.055: 2019.
Theodore J Perkins and Doina Precup. A convergent form of approximate policy iteration. In Proc. Advances in Neural Information Processing Systems (NeurlPS), pp. 1627-1634, 2003.
G. A. Rummery and M. Niranjan. Online Q-learning using connectionist systems. Technical Report, Cambridge University Engineering Department, September 1994.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, and Marc Lanetot. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):884, 2016.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andıd learning. In Conference on Learming Theory, pp. 2803-2830. PMLR, 2019.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction, Second Edition.
The MIT Press, Cambridge, Massachusetts, 2018
Richard Sutton, Hamid Maci, and Csaba Szepesvári. A convergent ((n) -iiffree-differenee algorithm for off-policy learning with linear function approximation. In Advances in neural in- formation processing systems, pp. 1609-1616, 2009a.
Richard S Sutton. Hamid Reza Maci, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-different learn- ing with linear function approximation. In Proc. International Conference on Machine Learning (ICML), pp. 1000, 2009b.
Martin Wainwright. Variance-reduced q-learning is minimax optimal. UrXiv:1906.04697. 06 2019.
Gang Wang, Bingcong Li, and Georgios B. Giannakis. A multistep Iyapunov approach for finite- time analysis of biased stochastic approximation. arXiv: (tt:::999..42222 2020.
Yue Wang and Shaofeng Zou. Finite-samee samile analysis of greedy-gg with linear function approxima- tion under markovian noise. In Proc. Machine Learning Research, volume 124, pp. 11-20, Aug 2020.
Yue Wang, Wei Chen, Yuting Liu, Zhi-Ming Ma, and Tie- Yan Liu. Finite sample analysis of the gtd policy evaluation algorithms in markov setting. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 5504-5513, 2017.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite time analysis of two time-scale actor critic methods. arXiv preprint arXiv:2005.01350) 2020.
Pan Xu and Quanquan Gu. A finite-time time analysis q-learning with neural network function ap- proximation. arXiv preprint 19Xiv:1912.045/ 2019.

---

Published as a conference paper at ICLR 2021
Tengyu Xu, Shaofeng Zou, and Yingbin Liang. Two time-scale off-policy TD learning: Non- asymptotic analysis over Markovian samples. In Proc. Advances in Neural Information Pro- cessing Systems (NeurIPS), pp. 10633-10643, 2019.
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. In Proc. International Conference on Learning Representations (ICLR), 2020.
Huizhen Yu. On convergence of some gradient-based temporal-diiferences algorithms for off-policy learning. arXiv preprint arXi::1712.096652 2017.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. samile-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems, pp. 8665-8675, 2019.
12

---

Published as a conference paper at ICLR 2021
Appendix
Table of Contents
A Filtration and List of Constants
13
Proof Theorem 4.5
Proof Corollary 4.6
20
D Technical Lemmas
20
E Other Supporting Lemmas
27
F Details of Experiments
29
A FILTRATION AND LIST OF CONSTANTS
Filtration We follow the definition of filtration in VRTD (Appendix D, Xu et al. (2020)). Recall that Bm denotes the of Markovian samples used in the m-th epoch, and we also abuse the notation here by letting x ((m) be the sample picked in the t-th iteration of the m-th epoch. Then, we define the filtration for Markovian samples as follows
Fi.o (Bo ( it (0))),, F1,1 oFFi, (2)))))) FI,M 1 (2) F2.0 a (B1 U FL, Uo(0 ())) F2,1 oFF2, Ja(a) ))... F2,M o @ 1 Ua (a
FM,D (B U Fm- U (m(m))))), Fm,1 a(Fm, Ua(s (m))
F Fm,M = o U (ar
(m)
Moreover, define Es,m the conditional expectation with respect to the o-field Ft,m-
List of Constants
We summarize all the constants that are used in the proof follows.
G Tmax + (1 7) Rk) 1)R.
= (2 + R Tmax.
Ci = (1+ 2A - (G CT.)².
C2 H² + A 1-
C3 Xa (1 + A
aR
C de (R(2 + 7) + Fmax) 2 P.)))
B PROOF OF THEOREM 4.5
We first define the following Lyapunov function
R ())())) ca coll0!"m) -mim)
13

---

Published as a conference paper at ICLR 2021
where os > is to be determined later. Our strategy is to characterize the per-iteration progress of R In particular, we use Lemma E.9 to bound the first term of Rt"" and use Lemma E.10 to bound the second term of R,". Note that Lemma E.9 implies that
](O(=)) - J(O(m)) no (V)(( ). (m))
VJ(O!"))) no (.](E
)12 +
2 1/0 l9: 1|2
L
), (m)) - (J(((("))) ))- Then, we obtain that Let c(m) = (V((() ),9
j( ((O(())) m nol ((( L m6ll m 2
Substituting eq. (7) and eq. (30) into the definition of R241 we obtain that
R == ((0(m)) + c++1 1011100100 11 (1
S _(( - - - nol ((( + 2 vá nillo!
n/ 11 (m)) ||2 + ||0!!T) - 01 - 2n
(m)) (m)
+ cc+1
| (m)) ||ا + Be 3el1o(m)) - (6mm) [r]]
+ 110
3
)(B(T)) + cc+1 (1o & + 1)](o(m) - -
+ (- no + a++1 110 3
[V(((mm)) 112 + ( nă + c++1 c141n))l99! m1
I.
Et (m) 2c,+ 1 mo (m)
Next, we bound the two inner product terms (()) and ((m)
Bounding the term c(mm)
< (n) = (VJ(O( (m) of (m) ()((()))) ))
Recall the variance-reduced stochastic update
Di (m) = G! (m)) (o(mm) , (m)) ((,)) (glm), wd()) + ((m)
Then, the term ((m)) can be decomposed as
(m) (. (m)
). ()(((m)))
= (VJ(O! ), a. (o! w (0((m)))
( 1.)--van v)((((m)))
+ (VJ(O!")), (o) wes (m)) (mm) (ofm) w (((mmm) mm) )))
+ (VJ(O("))) c(m)) (0lm) (m/))) + ((m))
In the last equality, the first inner product term is the bias caused by Markovian samples, and by Lemma D.3 we have that
B(JJ(O!()) (m)) ) G. (m) (o. _ (0(m)) {)(o(m)))
(V ((m) (p! (m!))) n (a(m))) {)(O(m)))
= LE m|? E (m) (m! w (o(m))) - v.((!
" Ci M
The second inner product term is the bias caused by tracking error, and we further obtain that
(VJ() mi (0!m) (m)) cm (o( w (o!"))))
>) + L Lilwo(m) w (0!!
14

---

Published as a conference paper at ICLR 2021
The third inner product term is unbiased. Combining all of these bounds, we finally obtain that
(
(m)
C1
+ \V
+ Iillut - w =((p!")))1
(8)
M
2
Bounding the term &e
(m) (g(m) (.( ) glm)).
Similar to the previous proof for bounding ((m)) we can decompose (())) as
mm (0!m)) g(m) 9i (m)] (J((!(m)))
(B!T)) g(m), G((m) (0lm)) _ (o(m)) -
V-((f(m)))
(0(m) m(m), G. (m) (o(m)) , (m)) [. (0fm)) w (0(m))))
(0(m) - gmm) G (()) (ōim) (())) + (()))
In the last equality, the first inner product term is the bias caused by Markovian samples. We obtain that
E(OO!m) - T(m)) G.m))
(o(
,w((o!")) [)(
2 101(0(m)) 11
2 [ (olm) w (o( -
1
Rl10(m)) (m)
112 mmm))1
1 C₁
<
2 M
The second inner product term is the bias caused by tracking error. We obtain that
(o!")) gim) (o!T)) (m)) G( (o!T)) w (o!m))
(m
1 (1 g(m)) Ia |umm) w (0(m))
<>
The third inner product term is unbiased. Combining all of these bounds, we finally obtain that
1 C1 + ||@!T) - (mm) 12 +
L1 ||w (m) w- (o("m)))))
EEC
(9)
2 M
2
Next, we continue to bound the Lyapunov function. Recall we have shown that
R m(((( + c++1 (1 + 1)](0(m) m
L nu + cc+111)) 119. (m)
+ (- no + c++1
[[]] +
B
St [ (m) 2c++ So (m)
(m))
Taking expectation both sides of the above inequality and applying eq. (8). eq. (9), and Lemma D. we obtain that
E 1
S B [[(((m)) + ce+1
(n + 1)](o((m) (m)) [1m
+ ( 110 + Cc+1
n
B V [( (m))
3.
+ 1
L
+ c+ m²)
,7, Bl|co ((m) w/ (0!T)))1 9L 9L,E)) (((m)))1
+ 91 (m)
Tmm)
12
1 M
106 + 933 VJ (0 (m) |1
Ci
1
|| ||
ر ( - (0) |12]
+ no M
+
2
+ 2c 1/0
10
mmmmm)
nlm) 1| يي (lm( w w²((! (m!
(10)
2 M
15

---

Published as a conference paper at ICLR 2021
We note that the tracking error term [!w]]m] - w (0(()m)) )|( has dependence |10(m)) - -mm) 1|a. Here we use a trick to merge this dependence to the coefficient ct-1- Specifically, we add and subtract the same term in the above bound and obtain that
B[ - E
J ((((T) + [cce (1103) + + 2no) + 1166
L Σn
ce+1 cc+1rr)) 110!! -06m)11
+
2 no + c++1
1
110 B1
+ 9(
2 110 + cc+188)
2
E 112
Tu
Ci
+ no + 20141770 9
2 Ml
c-176)
M
L
9T,1
(
110
+
cc+1
n/ (1 (
wn (11
+
6L1
L
2 110
c(+17)) + 10oi + c c 2
Bllus (m) - -w" (B(
6L7
2 Tm
L
+ Ct+1 1++1 + no.1 + no c
12L3 +( +/x= +211) 9L9
"10 m/m
E (l(m)m)))
@(m)) ||2
AC
σ77 ( bT
L
+ c+177)) + n1oi + no LoL1111
12L3TT + :/o + 212
913
E (0)mmm)) 0mm)
A
Then, we define RV m(O(m)) + c:110!m)) - 012 with e, being specified via the following recursion.
L
C c + 1 + 2nd) + +161 2 t1 c(+14))
+ |6L 5 nm + Gc+1 + noL1 + no L 1
4 Ac
9 + 222) 9L n 12 + +(e
(11)
no
Based on this definition, the previous inequality reduces to
B B[R
E[RTTT) + [ - 210 + c++1
1
n1
+
9 L
2
11
+ cc+
B
L
C1
+ 110 + 202+1100 1100 + 9
+ mn))
M
+ 9L,
z + c1+1 (())( - w/ (0(m)))1
+ 677
+
+ n7an + no Li L111c11 +
Bllw (mm) - w- (o!
2
177
_
L
2
11117) + n7li + neLic411
4 12L3 ( 9
(xx + 223) 9L
me
- @(m) 1|2
1i0
2
Ao
m/
(12)
Assume that e S for some universal constant 0 (we will formally prove later). Then, we sum the above inequality over one epoch and obtain that
M-1
1
9( G + +T)))
{
2 T/
2=7
< E R
E Rm! + 110 + 2 + 9( L
th
+ aाे)
Ci + 1L1 (- + ME) w-w'((0n (0(m)))
2
M-1
119
2 Ti + )ाの + 110n nolie ē
E
(m)
w (0(
1=0
M-1
GL1 ( 2 nho
L 2 + )n + 1101 1
4
12L5
n
+
(>/0- 9 + 213) 2L3
Σ El (m) mlm) 12.
Ao
The
(13)
16

---

Published as a conference paper at ICLR 2021
By Lemma D.7, we have that
E Bl (m)) w" ((6, (0(
4 1
M {(
[xx00 + +223) 9L9
9
n
+ 18L
B1| (m) w- ))(
A
Nw
n 36 M-1
+
4
+ 213)
1h n
9C1 +
4
Tle
12C2 + Axc
9
+ 22
Σ
E [
AC
AC
A
nh Ac
M-1 1
+
4
12L +
9
+ +222
9L2
1
Bll0(m) - 02
AC
AC
8 Ae
+ (C3 CC).
For simplicity, we define D == 6 20) + L1 + L1d. Substituting the above bound into the previous inequality and simplifying, we obtain that
M-1
1
110
9 L 2
11 + +
Σ
B (( (r)) )12
To
1
< ERG
- ER + 110 + 2010 + 99 2 n + 
Ci + 111 (
(
L nh + G
MEI - -(im))1
+ Dna
4 1
+M
+
[ A
+ +223)
+ +18L7
|B(((mm) ~ (01m)))
Àc -/w
4 A
9 A
2133)
1g n
2
9C, +
4 xe
12C₂ + -// + +2113) T
9
n1 36 M-1
E
BI + 8 (Cs
[Ca+ + Ca)
Ao
2
Ao
1=
One can see that the above bound is independent of 2 we desire. After simplification, the above inequality further implies that
@lm) 12? and this is what
[ 110
2
10 - Be
9
I 5 + oTd) - DD - +2L3)
9
36
M-1
Σ
do
< E R E. R
+ 110 + 281 + +9( (9 + aाt)
L
Ci +
8
(C3 + C4) + Drio
4 ( To
+
+2L3)
90 + Xo nw 12C3]
dc
Toc
ne
+ 11
7 110
L
+ + M + D7
4 1
+ M
(
-o= + +223)
9
9
T n
18L3 []
Bl
w w (ātm))y)
dc
(14)
Choose optimal learning rates: Here, we provide the omitted proof of our earlier claim made after eq. (12). that is, the upper bound of {ce} is a small constant. We first present the following fundamental simple lemma, and the proof is omitted.
Lemma B.1. Let {csJe=......M be a finite sequence with eas and satisfies the following relation for certain a > 1:
c S a C411 + b.
Then, {ci)==0.....M M is deceasing sequence and
M
Cp S ab
8
17

---

Published as a conference paper at ICLR 2021
Next, we derive the upper bound é of cr. Set B 1 for all t. Then we have that
S CT41 + +1+ 2na) + 176 7 + c++11)
+ 6L1
I. n0 c2+11)) + no L n1
4
121
+( +,x + +222)
9
91.
10 m
xc
where
1 (3+ 16T,))
and
15 b
4
21L) ne
L1 Lng + LiTT
12L + ( àc
+
2
Note that here we require
12t,3 + +(x² Ac
9
+ 21 21.
91.
vo
1
(15)
Ac
1
and
max
(aws no} S 1.
(16)
Moreover, let
1
(3 + 1611) 5
(17)
M
Based on the above conditions, obtain that
co <
15
L1
Lnp +
4L1
12L +
+ +
9
7 7L 9L2
223
4 1661
(1 (3 16L1)1o) -
2
dc
3 167
15 L +
4L1
12L +
+,xo
9
+ 2L3
11 9L3 1
4+ 1671
(e-1). 1).
2
Ac
3 1641
Lastly, we choose
15 [15 L, Lmp
4h1 12L. ( 9 Ae
+222)
9L2
100
4 + 1641
+ 16L; (c (c- - 8' (18)
Ac
m2
Therefore co < 1. Since faeh is decreasing, we obtain that ē 1 Now, substituting 3g = 1 and 2 into the coefficient of the term ΣM- E| ( in eq. (14), the coefficient reduces to the following, and we choose an appropriate (11. such that the coefficient is greater than 1
3 T 9 2 + cTb)
9 Ac
36 1
D(
+ +2L
n1
(19)
dC T
Deriving the final bound: Exploiting the above conditions on the learning rates, eq. (14) further implies that
M
E {((mm) )
4
< <EJ (2) B[J [ (0(m+)))
+ 11
231 + 9
( n/ ant)
L
Ci +
8 (Cs -Cs
C4) + Duo
4 9
2T
t n
9C1 +
x 12C2)
Xo n
dc
de
Ao
+
116 L
2 n + = M + Dne
4
+ M
9 ( do
+2L2) 9L
222
18L3 11
E Bl w (01m)))1
de Tlw
72
(20)
18

---

Published as a conference paper at ICLR 2021
On the other hand, by Lemma D.8 we have that
Bl( w" w0(mm))) S (1 )m - w (0(0)))1
4
(Cs C.) 1/- Ca)
4 1f
2 (2L3G
6 69)
9
Ac
Xc
Ac
Substituting the above bound into eq. (20) and summing over m, we obtain that
M-1
B ||2
110
TM
[[(()())]
TM
1 M
{
n0 + 2ôno + +9( _ T0 काه) ci
(Cs+ C.) + Dne
-
4 9
( (-00 + 222)
ni n
99C
4
n 1202]
de
Ao Ac
Ac
1
9h
1188 + mn M
TM
2
+ Dns
4
1
+ M
9 AC
+ 223))L
118 n
+ 18L3 Tw
El w 00(10)
1
No
T
1 1 (1 {))TT))
+
1
911
L
2 1100
+
+ Dne
+ M 1o +
91
1 + 18L3n ]1]
M
Ae
G2) 1
v
(Cs + Ca) M Ac
+
H n + Ac
(2
+ Ac
Ac
Rearranging the above inequality, we obtain the following final bound, where &. C are random in- dexes that are sampled from (0...., M 1} and (1,...; T} uniformly random, respectively.
E J 112
4E 4E
naTM
+ 4
4
{
[ + 28 + 9(
5 no + and)
I
C1+ +
8
(Oss + CD) +
9
+ 213)
T The
9C1
+
xo Now 12Cg)
4
M
Ac
Ac Ao
1
9h, ( + a0
1 - M(( 2222 91, v/
+ 1812 nM 11
+
TM
Ae Mw
Ac
1
w" (11
1- {d
+
9h, 1-m ) + D
L
4
1
+
[
9
22
9
1/
+ 18T
|]
do
M
m
1
4
2 (213
9
v
(Cs + Ca)
H2m
+
02)
Ae
M
Ac
Ac
do
n
Next, we simplify the above inequality into an asymptotic form. Note that the first term is in the order
of O 7 7. ). The second term order O 11) The third term is of order O T. + + (nw no )),
and the last term the product of term of order O The + Wo and another term of order +n ). Combining these asymptotic
O ná +,w), which leads to the overall order O(( m
orders together, we obtain the following asymptotic convergence rate result.
|| o( T
+
+
m
2 +
1 M
+ (nw +
7
T
19

---

Published as a conference paper at ICLR 2021
C PROOF OF COROLLARY 4.6
Regarding the convergence rate result of Theorem 4.5, we choose the optimized learning rates such that 1/0 O1l 2/2), and we obtain that
B B J (((()))1 O
1 NoTM + ( +
M
T
Then, we set 77 this learning rate setting, the learning rate conditions in eq, (15), eq. (16), eq. (18), eq. (19) are all satisfied for a sufficiently large constant-level M. Then, the overall convergence rate further becomes
+ such that eq. (17) satisfied, and moreover The O M7r3)
) Under
- M )
E
(21)
By choosing M O(e-t), we conclude that the sample complexity for achieving |] I e is in the order of T'M = O)
D TECHNICAL LEMMAS
In this section, we present all the technical lemmas that are used in the proof of the main theorem. Bounding El[gt
(m) 1|2 and E|]A(T))3
Lemma D.1. Under the same assumptions those of Theorem 4.5, the square norm of the one-step
update of m())) Algorithm 1 is bounded as
1|2 S 6L? - w -0, (o(m)) 112 + 9L (0(mm)) + 913 112
9
M 9C1 J( 2ll
1
where the constant C₁ is specified in Lemma D.3.
Proof. For convenience, define
T. (m) G( (o!m) we (m)) c. (plm) ((m))
(m)
(m)
and
(m(m) (m) = (m)) ((m)((!!m)) (o!!), " ((((m)))) G (m)) (@(m) w- (((mm)))
Then, obtain that
llg. (m) 1 |GG (m) (o(m)) ,w, (mm)) cf (m(m) ( (دm) + (m ||
(m + (()) - (m() (T(m) ~ (m(m))) + (i() (@im)) - (ō(m)))
-(lm) + (12
3( (m) sm 3| (mm) - (@(m) ~ (oLm))))
+ +3 (m)) + ( w (01
< 6L |W| (m)) w² -0(!!" (0!m)) || + 9 (m)(m)) w (12
3| (((m) G(m) w
where (m)) (āim) w (dlm)) is obtained by substituting the arguments Tim) w (0lm) into the def- inition in eq. (4). Moreover, we have that
(m)) (((m)) w (0im)
= ([ + 7(m) (p)m), w (ā(m))) (o( + ( )12
S {(1ls((mm) -mn (()) + 311 (m| (m! ,w- (o!! vo(o!m)>>i
+ 3 +3
20

---

Published as a conference paper at ICLR 2021
which further implies that
Bl( (m) (mm) (fim), w/ (0(m))))1
- 3 (m)] 1 + 3E| (()) (0(m) mm) w (0( - (.((omm)>) + 3/I (
2 <333 0im) || + M 30, + 35 {
Combining all the above bounds, finally obtain that
E Ellg: (mm) 1| S 6L3 (m)) w (o!m)))1 )|2 + 9L, (m)) w((m))))
+ +933 - (1m)) - M
900 + 9B V ( )12
Lemma D.2. Under the same assumptions as those of Theorem 4.5, we have that
[145ml 1 1p S 6L3]l w (o(m)))) + 9L3)( - w (0(mm)))1 + 6L3]10(m) - -00m) 6C2
M
Proof. For convenience, define
y((m) = (m)) (m((m)) (()) mm(m) (mlm) ()(m)),
and
V (m) = Hmm)) ( (!!!!) w ()((m))))
mm (7(m)) w (m(m)))
Then, we obtain that
|| 112
||/1/m)) (o(m)) w (m)) m1() (0(m) (m)) + [i(mm) 12
||%g(m) + (m)) - (m) (mm)) w (0(m)) (m) (0(m)) ~ (0(m))) - (m + mm
S 3lly((m) 2 (m)
2m 1/2 + 3 11 (m)) H (m) (m(m) ~ (1
+ 3| (m) + (m) ( - (0 ) )| 2
6T (m) wn (0! )m) y1 9 - w (12
(m)
+ 3| 2 (m) + (m) ( mm)) ~ (0 m)
Moreover, note that
12 (m) + (m)) (@lm) w (Q(m)) 12 < 21|22 (m) + 2/ 21) (@7mm) , (0(m))))
< 21 ()) T(m) 12 +
20²
M
Combining the above bounds, we finally obtain that
| 12 s 6 - w (0((m)) 122 + 917 w/ 112
6C²
+ +613)1((²) @im)
M
Bounding pseudo-gradient variance: Lemma D.3. Under the same ussumptions as those of Theorem 4.5, we have that
E| [1])(m) (6(m)) _ (efmr)) - v.(o("))) )1 - C
M
21

---

Published as a conference paper at ICLR 2021
Proof. Note that the variance can be expanded as
E
Gim) (o(m)
w= ()(
)1(
M
(m) (m)) w (B!_m))) - y|
M
(G)) (0) m w (0(")))) v-((o!m)) ) .
(
(ofml)) - v-((fmm))]]
+
i
M-1
(G + Cv,)² + (Ap
M2
$=0
1
(1 2A
M
Then, we define the constant C = (1 ( + Coz)². (C.))
Lemma D.4. Under the same assumptions those of Theorem 4.5, we have that
C2
E H (m) (m)(m))) w" (0 |>1 V
M
Proof. Note that this second moment term can be expanded
1 M
(l(H()) ~ (1|=
=
E
H (m)) (@lm) ~ (0(m))))
M
k=0
(H (m) (@(m) w ()lm))) (mm (0im) w (0(mm) )))
+ M
2²
1
+
H²
A
M
M
itj
< H² + P
1
M
Lastly, we define the constant C2 = (2 + A
Bounding Markovian Noise: Lemma D.5. Let the same assumptions as those of Theorem 4.5 hold and define
(m)
(m) - -w" (0(_"))) (1() (o( ( - C) (w) - (0(()) (o(m)))) )))-
-
St
Then, it holds that
El5, mm))
S 1 Soollu _0(
(o("))))) C3
8
M
where C3
88t
Ae (1 + )
Proof. By definition of (m)) we obtain that
Blu((m) - w (o(m)), ) (m)) ( (T C) (uf - -o((m()))
(m)
-B(ul (m)) - w ((((m)) Em,.- (0f (o(()) -C) (w) (mm) w -w'(0(()) (((m))))
2 1 Ac Elluu! (m) - w- (0! mm!
1 4R²
M-1
)1² +
EEI
Σ
4
2
M
T=Ul
22

---

Published as a conference paper at ICLR 2021
For the last term, note that
M -1
(m))
(0) (
E
1=0
M 1
= E
10 (m) (0) (m))
C112 + E
Σ
(o
(m)
(m)))) - C, (om - -c)
1=0
< 4M 4
Apli-sl
4M + 4M AA
Combining the above bounds, we finally obtain that
Blw (m) w (0(m)), (of
(1m) (o(m)(((m)))
(ofm))= (2( (m)) w (o(m))))
Ac Blww (m) - (0(
8R
PA
1
(1
A
p
M
We define Cg := &ل2 xc (1+ + (.
Lemma D.6. Let the same assumptions as those of Theorem 4.5 hold and define
(m) := :w (w( wn (B!"))), ((o(mm) Tw= ((((())) ((m) (e! ) )
Then, we obtain that
Ex S 1
(m)
Shcllus
(o! - )12 1|2 C4
8
M
Proof. Similar to the proof of Lemma D.6, we have that
ElW, (m)) w (o!m))), (m Tw (o!"i)) o( (] mm)))))
1 Ac B Bllwe
(m))
(0(
$
2
M 1-
1
Σ ([(ofm)) ( ((((mm))) ((m) (mm ( 112
+ 2
El
M2
For the last term, we can bound it as
M 1
Σ
((olm)) (om))TT((!! (o!m)) - (p())] {[]["))))) 1|2
<(R(2 7) + ) + (R(2 7) + Tmmxx )2 PA M.
1 p
Combining all the above bounds, we finally obtain that
B(ue(m) (m) - w- (B(")), [m) T " wn((()) Ac
((17)(((mm)) (((m))
8 Ellw! (m) w (0 )|1 + Àc
2
(1122 + 7) + ) )2(12211111 + 1- M
PA 1
We then define C₁ = 2 (R(2 7) + Tmax) (2(1 + )
Bounding Tracking Error:
23

---

Published as a conference paper at ICLR 2021
Lemma D.7. Under the same assumptions as those of Theorem 4.5, the tracking error can be bounded as
E Bllwe
(m) w" (8!
1=
4
1
M [1 [1
9
+ +2L3) 9L2
+ 18L
BB| (m) w w((
AC
7w
A
36 M-
+
4
+ +22g))
nh n
9C1 +
4
Tw
12C²
9 +
Ao
+ 21.3)
nhw xc Σ
no
(J(( )|2
λ
A
x
+
4
12L +
+ +22
9L2
1
M-1
E| Ello(mm) - 02
AC
AC
0=
8 CC..
+
(C3
Ae
Proof. Recall the one-step update at W
(m))
(m) In (w( (iahhmm))
Wri1
Then, we obtain the following upper bound of the tracking error [ (m) w (0(F))12
|w/p wn (e(m))? 122 S (m) w ((((m)) hh ((n)
+ + (o!!!) w (0(
(m) w (0!!mm)) )11 (wl (m) w (0((!))) (m)) {m))
2(w (1m) - w" (o!m), ) w, (8( - w (B(
+ 2 1/, (m)) 1|2 2|| (o(m)) - w (o!T
Substituting the bound of Lemma D.2 into the above bound, we obtain that
| w (B!T))11
< 1k// (m)) - wn (0((m)
() )12 2m (w) (m)) - w (8!m))) (((m)) mmm)))
+ Acnsllag (mm) w=((p (0b!")))
+ Ae + 213)
- (L? (m1) - w (0!!m))) + - m0(
nl
m12 +
1
99C 9E VJ (.((!m))))) )|(
M
2m 663 (m)) - (0 mm) || + 9 w (0اm))) - p2 M
602²
Taking expectation on both sides of the above inequality and simplifying, we obtain that
E Bllumm (m) - wn (0(m)) 12
1 1 Acn + A
9
+ 21
6L?
+ 12L3m3
Ellug - w= (0!=))) )|2
+
( Ac
+ +2L3)
me
+ 18
Blaam) - w (0(m)))
n
+
9
+ 213)
the
9C1
+ The
12C²s
+
( Nc
9
The + 213)
9E1 v J (0! (m)) م1²
AC
T/o
M
M
The
+ 12 + +1xc
+ 2L
vá n
mm -mmm 12
x
Ex,
(m)
21 (m)
(22)
24

---

Published as a conference paper at ICLR 2021
where
St (m) = (w( - w- (0(mm))) (cf (c) (ut - ()(
and
Am)) (w) w (B) (m
) T w (B(m))) - ol (0f of
Applying Lemma D.5, and Lemma D.6 to (22). we obtain that
Bl|wi+1 (m)) - w/ (o(f))) < (1 - 2 dcn +
1
+ 211
6L7
1 +
12
Ellus - w- (ofm)))) )1²
2
1/w
+
[ A
+ +2L3)
+ 1
2
E| - w" (0(m)))
Nl
9
9C1
12C₂
9 + +2L3)
_ee (o
+
+ 2L3)
+ n
+ ( do
Ao
T
M
M
+ 12 +
9
+ 21
91
- p2
Ac
n
1
+ 2n + Ca) M Telescoping the above incquality over one epoch, we obtain that
(23)
M-1
( (AAnU - 9 (5o +21.3)
Tha 12L
Σ
Bllu?" (m) - w- m0
T
s Bllw((n) -w*(0(m)) )12
+ MI(
9 +2(3)
91.
10 + 18 Bl - -11
de
n/
M-1
+ ( 9
+21z)
no
-90 + n 12C2 + ( Ae
+ +213)
Σ
[(!")(
Ac
n7
nw
M-1
+ [12L312 + ( Ac
+ 2L
9
18
Σ
Ello!m) - 0mm) 122
1=
+ (C3 + Ct).
Choosing an appropriate (rze, mw) such that
2 don
1
(~=== +
9
2223)62
nh
12L3n 2 1
7 AACTW
(24)
n/
and we finally obtain that
M
Σ El Bllw
(m)) wa(0""0'" (0!")))12
5
9 + M((
+ +222)) 91
nh n
+ 11822
Bl] - ((
Ac=
n 36 M-1
+
4
+ +2L3)
9C1 +
4
T 12C₂ + ( 9
(~o + 223)
Σ E (
Ao
Ae
13
Ac
nh Ac
M-1
+ do
4
|2L6 + +(- 9
+ 213) 2
n
Σ
E El (m) - 02m))1
dc
1=0
8
+
(Ca CC).
25

---

Published as a conference paper at ICLR 2021
Lemma D.8. Under the same assumptions as those of Theorem 4.5, the tracking ervor can be bounded as
Bl( - w (1)m))) - (1
' )m
- 2B(0)))1
2
+ A
4
(Cs + Ci)
1 + 4
+ G2L
2 d
+
9 Ac
G T
M
dc
Proof. Recall the ste- update at w
(m) II (w] (w("m)
(mm)
W
Then, obtain the following upper bound of the tracking error ((w( w" wa'0"" (1P
)12
| (m) w (0 (o(+))r
)1
< (u(mm) - w (0!m))) - m (m)) w (0(m)) w (0(7)))
S |lm - w (0, (0!m)))? - 2ww (m) w (((( (o( mm))) _
2( (m) w" w0(0!m)) (0(m)), ) (0((m))) - w (0(+)))
21 112 + +2|l=* (0!m)) w² (0(
Then above inequality can be further bounded as |w/H]] - w (0(+)))1 < (la(m)) - w w0((! (1 - 2n /w) (m) - w (0(())) 1. mm))
Aomwllw? (mm) w"' "'((((")))" )12
nh G²
+ +21
T
+ +n
Taking conditional expectation on both sides of the above inequality, we obtain that
Em (hnooll/mmi w (B(_m)
< Em, Emmollui
allai (m) w² (0!-)))² )11² 21 Bw. (m) - w (o.m)), ), H. (
2np (u (m)) - w" w'((!mm) (0!m))) - H. (mlm), + (m(m)
+ Aemollal (m) - w (0.m))) 112 gnd G²
+ + - G2 n/
&Rmallui (m) w" (0, (0! 1|2 2n (w, (10) w² wn'('''00 (o(m)), Hmm (0!")) .u. (())))
+ Ilc (m) - w" w0!!" )12
+1H22 22130² 9 Ac
n
G2)
(25)
nle
To further bound the inequality above, we first consider the following explicit form of the pseudo- gradient term:
H( (m) (8, [(o! Tw 5fm) (f)] ml
(m) (()))()(())) (mf I (w - --(w()()) + mm) To (o((m)) 56. (0))
= =(o! (m)) (a!me) (m)) - C) (w- w (0)) + C(w - --(()))
+ [(0 (mm) T w0) gmm) (0) mm
(26)
By Assumption 4.3, we have
-m. (w) (ww - w" (o!!!)) ),((m! w/ (0) < -2ndlll( w (o!!))))1.
(27)
26

---

Published as a conference paper at ICLR 2021
Substituting eq. (27) and eq. (26) into eq. (25) yields that
|l|wW/1 w" (6 11 - (1 Ac Bl ( (m))
w²
(0((
2n "xx, Bxg,
B4, (m)
G²) n
+ +2H2 n + (2L3 + Ao
(28)
where
(m) = (m) w""(0" (O((()))) (0,
( - C) (wg - (0(m)))))
St
and
(m) = (wi (m) w w0( (0! ((o Tw" (0) (0!-))) اm (0(m))) "m!)
Applying Lemma D.5, and Lemma D.6 the above inequality, obtain that
E| Bl (m)) wn (0(T))1 S (1 do |llws (T) w (1!
2m 2 Ci) 1
M
9
03 m
2H2 m + G2Tg
Ac
n
Telescoping the above inequality over one epoch, we obtain that
Bllw w((((r (((((=))) )1 = (1 - > ) Ellwo - w" (0) )1
1
2
1 1 (1 )))on))
+ 2n (Ca + C2) M
ANOT
1 - (1 ))
1 1
(1 )
+ 22 m/u
+ (2L3G² +
G2)
2don
Ac
2
By definition, (m)) = war and (m)) ((m)) and the initial parameter for the current inner loop chosen the reference parameter, w6t) ((m) and pfm) =((m), Then we have
(mm)
(m)
Bl(a(m)) w" ((((mm))) s (1
2 (cn)) M MEl w" (01
1 1 (1 - {
+ 2n (Cs C2)
M
2dom
+ 2
1- (1 11(1-3Acm))) (2L3G² +
_
v
1- (1
{)om))
Ac
T/
Then, we unroll the inequality above and yield that
Bl(a(m) - - (0(m))) 1| < (1-
(m.m)mMBll - w (((00))11
4
(Ca Ct) 1 4 112m
2 22L30
2
9
G2)
Ag M do
Ac
Ae
E
OTHER SUPPORTING LEMMAS
Constant Bounds:
Lemma E.I. Within the (0: ||o|| < RJ, there exists a constant C such that
sup VJ((]] & CvJ-
(29)
d
Proof. By Lemma E.9, (J(()) is smooth. Hence, by the compactness of {0 ||ll| conclude that [V]( bounded by certain constant Ce.-
< R). we
27

---

Published as a conference paper at ICLR 2021
Lemma E.2. Let G == max + (1 + R + + 1)R be constant unrelated to and t.
Then ||G|m] || & for all m and
Proof. By its definition, obtain that
|[ (m)) || = |I( 5141 (0:) + Twm +
$ |I( 8e+1 (0:) + (w) de (
S mmax (1 + + 1)
Lemma E.3. Let H = (2 + 7)R + Tmax be a constant unrelated to and t. Then 1| (m)) for all and
S H
Proof. The result follows from the definition:
( = 11[07 we
I (2 + y)R + Tmax-
Lipschitz Continuity:
Lemma E.4. The mapping + ( is -I-Iisschitz w for all O.
Proof. See Lemma 3 of Wang & Zou (2020).
Lemma E.S. The mapping 0 + G (0, w (0)) is Le-Lipschitz in
Proof. See Lemma 3 of Wang Zou (2020).
Lemma E.6. The mapping w" (-) is Lapsschchitz
Proof. See (56) of Wang & Zou (2020).
Lemma E.7. The mapping w + H(mh (0, w) is I Lipsscchhitz
Proof. It follows that
(0, Hmm) [m)) (0, w2)l = ||(55m] (m) (0) [ T wi wi)
(m)) -68/m) (0) [o]mm]]] T
w2 (p(
< | || well
| well-
Hence, LA = 1.
Lemma E.8. The mapping H (0, Lipsschhiitz
Proof. By definition, have
H H (02, we (B1)) H ~ (Bz)))
= [( (0:) (m) w/ (0 01 (m) (6(m)(0) ( m!))
< 110mm (01)
||"" (0z) w0(O,)]
5 (GT/A/ki ++ +1+ La) |0, 02ll-
Hence, Ls = (T|AiAy) R +1+1+44 Lg
Bounding Lyapunov function:
28

---

Published as a conference paper at ICLR 2021
Lemma E.9 (L-smoothness of J). For any 01 and 82. it holds that
(J(01) - J(2)) (VJ(02), 02)1 - L
2 2 0211
Proof. See Lemma 2 of Wang & Zou (2020).
Lemma E.10. It holds that
| - -0(m)
112 n llg (mm)
1| + [10(,m) - -0mm) 2:155
+ 3
J (m)) )12 + 301 - mmm)) 112]
(30)
where </ = (0) mm) ((((m))) mmm) A(m)).
Proof. Note that
[10(m) 1+1
{(m))p
=110(7) a(m²) 1|2 [|0[mm] - ((m))1 + 2(0(m) g(m) ,0(m) mlmm))
n l1 (m) 1|a + ||0!!m] 0(m)) 1|2 2n (g) (m)) _00mm) /(m²)
19.1 (m) 1|2 [|!!!)) - 11 2no0 (3) (m))
{(((!)))
m)) ) ml - F(m))
21o (V J( ()) ) ). 0(m))
n l6. (m) 12
[m( 11 2n (gt (mm) V ((( ).0mm) -lmmly
1
VJ )| + Bel10(m)) 01m))1)
B
F DETAILS OF EXPERIMENTS
Garnet problem: The Gareet problem Archibald et al. (1995) is specified as G(ns, n.A, b, d). where ns and 1 denote the cardinality of the state and action spaces, respectively, b referred to as the branching factor-the number of states that have strictly positive probability to be visited after an action taken, and d denotes the dimension of the features. In our experiment, we set ns 5, n1A = 3, 6 2, 4 and generate the features 4 E Rnsxd via the uniform distribution on [0, 1]. We then normalize its rows to have unit norm. Then, we randomly generate a state-action transition kernel P E gn xas via the uniform distribution on [0, 1] (with proper normalization). We set the behavior policy the uniform policy, i.e., nr (a)s)) " for any and a. The discount factor is set to be to evaluate the performance of all the algorithms. We set the default learning rates as тe 0.02 and nw 0.01 for both VR-Greedy-GQ and Greedy-GQ algorithm. For VR-Greedy-GQ. set the default batch size as M = 3000.
0.95. As the transition kernel and the features are known, we compute || J[)
We generate Gaussian feature matrix with dimension 8 to linearly approximate the value function and we aim to evaluate a target policy based on a behavior policy. The target policy [0, 1] with proper normalization and the behavior policy
Frozen Lake:
is generated via the uniform distribution is the uniform policy. We set the learning rates as T/ = 0.2 and The = 0.1 for both algorithms and set the batch size as M 3000 for the VR- We run 200k iterations for each of the 10 trajectories.
Estimated maximum Reward: In the experiments, we compute the maximum reward as follows: When the policy parameter 0, is updated to O,+1, we estimate the corresponding reward by sam- pling Markov decision process (81,01,4 82, 022 .......,,8 8N, aN, 8N+1) using we. Then estimate the expected reward using
f
T (3,, 0g 8141).
N
i=1
29

---

Published as a conference paper at ICLR 2021
Under the ergodicity assumption, this average reward will tend to the expected reward with respected the stationary distribution induced by те (Wu et al. (2020)). Then the maximum reward is defined as the maximum estimated expected reward along the training trajectory; that is,
Maximum Reward = max fz.
In the experiments, we set N 100 when estimating the expected reward.
30


Reviews:
[{"review_id": "wMvHI-j-8Rf", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 submission deals with the classical value-based Greedy-GQ algorithm for off-policy optimal control, and develops a two-timescale variance reduction scheme to reduce the stochastic variance of Greedy-GQ thus improving its sample complexity. \n\nSpecifically, a variance reduced (VR)-Greedy-GQ variant that applies the SVRG-type variance reduction technique to the two-timescale updates of Greedy-GQ. Assuming linear function approximation and Markovian data samples, it is shown that the VR-Greedy-GQ achieves a sample complexity of O(\\epsilon^{-2}), which is order-wise lower than the sample complexity O(\\epsilon^{-3}) of the original Greedy-GQ. Convincing experiments are also provided to demonstrate the effectiveness of the proposed variance reduction algorithm.\n\nOverall evaluation: This paper is reasonably well written and presents interesting technical results. The Greedy-GQ algorithm is an important and efficient value-based approach for off-policy control. \n\nDetailed comments: In the existing study, variance reduction techniques have been successfully applied to value-based TD learning algorithms for policy evaluation (e.g., VRTD, VRTDC), but they have not been explored by value-based algorithms for control, especially in the off-policy setting with Markovian samples. This paper fills this important gap. Below please find several related technical comments.\n\ni) The main contribution is to show that VR-Greedy-GQ achieves an improved sample complexity over that of Greedy-GQ. In particular, the authors showed that (as commented in the contribution section), VR-Greedy-GQ induces a small bias error caused by the Markovian sampling and a small variance error of the stochastic updates, both errors are inverse proportional to M — the batch size of the SVRG reference batch update. Hence, a larger M should gives smaller error terms, and this is also suggested by the bounds in Theorem 4.5. However, it is not clear why Corollary 4.6 chooses the special M=\\epsilon^{-1} to achieve the desired sample complexity, can the author clarify the trade-off in choosing these hyper-parameters?\n\nii) A key technique in the finite-time analysis is the introduction of the fine-tuned Lyapunov function R_t^m. In particular, the coefficient c_t is specially chosen so that the quadratic term on theta can be totally absorbed into the Lyapunov function for telescoping. Although this technical development is very interesting, how is it different from the traditional analysis of nonconvex SVRG? For example, see the paper Stochastic Variance Reduction for Nonconvex Optimization by Sashank J. Reddi et.al. \n\niii) More recent results on finite-time analysis of TD/Q-learning algorithms dealing with Markovian samples should be discussed, as well as how the current analysis differentiates/improves from existing e.g., drift analysis in [Srikant et al, COLT'2019] and multistep Lyapunov analysis in [Wang et al, AISTATS'2020] in terms of accommodating the bias and correlations introduced by the Markovian data samples. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "upBcPc5cgn", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "\n\nGreedy-GQ is an RL algorithm for a control problem that extends on GTD, which is a prediction algorithm. While Greedy-GQ asymptotically converges to a stationary point, it does so with high sample complexity. The authors reduce the variance of Greedy-GQ by incorporating SVRG variance reduction scheme to both the time-scale update of the algorithm. The main contribution of the paper is in showing that the variance reduced Greedy-GQ algorithm achieves a sample complexity that is an order of magnitude less than the vanilla Greedy-GQ. \n\nMajor concerns:\n\n1.\tMy major concern is that the paper uses SVRG for variance reduction, which is not the state-of-the-art method. Since the two seminal methods (SVRG and SAGA) have been proposed, there have been substantial achievements during the past few years along this direction, such as SARAH, SPIDER, and STORM. It is very important they author identify with enough analysis that those three competing methods as mentioned above reach the same time and space complexity (aka, w.r.t the mini-batch size). The reviewer strongly suggests the author to do so.\n2.\tAssumption 4 (geometric ergodicity) seems too restrictive. The author should give some more detailed justification to justify if it is widely applicable or not.\n3.\tFor the experiments, it would have been nice to include the plots based on the objective function and not just its norms.\n4.\tWordings of the experiments in 6.2 is a bit confusing to me. After the target policy is generated via the uniform distribution, is it getting improved as the off-policy control algorithm should, or is it only evaluated against the behavior policy?\n5.\tin section 1.2 the paper concluded Q-learning and SARSA with function approximation as related work. However, the proposed algorithm doesn’t seem to be related to it.\n6.  I noticed that there is a recently published NeurIPS paper (Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis), which further reduces the merit of the paper on the perspective of adapting SVR techniques to nonstandard stochastic optimization algorithms such as TDC/Greedy-GQ. \n\n\nMinor concerns:\n1.\tPage 6, Corollary 4.6: Shouldn’t one of the \\eta_\\theta be \\eta_\\omega?\n2.\tin section 1.1 paragraph 2 line 7, it is better to use “order of O(M^-1) and O(\\eta_\\theta M^-1) respectively” instead of “…O(M^-1), O(\\eta_\\theta M^-1),…”\n3.\tin section 5 equation (6), it is better to use “… 1/M)” instead of “…M^-1” to keep consistency. \n4.\tIn section 5 step 3, it is better to say lemma D.7 and D.9 is in the Appenix.\n5.\tThe paper mentioned “SPIDER (a.k.a SARAH)”. These two algorithms are very similar, but they are not identical, as pointed out by several papers. For example, referring to the last few paragraphs of pp.3 of the paper “Finite-Sum Smooth Optimization with SARAH” (https://arxiv.org/pdf/1901.07648.pdf).\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rarLr55URG-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT: After reading the other reviews, responses, and thinking more about the issues raised and resolved, I'm increasing my score to an 8.\n\n---\n\n### Summary:\nThe paper introduces a variance-reduced version of the Greedy-GQ algorithm for off-policy control, based on SVRG. The paper then analyzes the finite-time convergence rate of the proposed method (VR-Greedy-GQ) under the assumption of Markovian noise and finds an improvement on the order of 1/epsilon to achieve an epsilon-stationary point. The theoretical findings are supported by some experiments.\n\n### Pros:\n- Proposed improvement to existing method\n- Theoretical support for proposed improvement\n- Markovian noise assumption\n- Some new techniques in the theoretical analysis\n- Well written\n\n### Cons:\n- SVRG setup involving inner and outer loop conflicts with the original motivation for Greedy-GQ (online and incremental latent learning)\n\n#### Clarity/Quality:\nThe paper is well written and not too difficult to follow despite the complicated topics. Sections 4 (Finite-time analysis of VR-Greedy-GQ) and 5 (sketch of the technical proof) were especially well-written and helpful, and the experiments seemed reasonable.\n\n#### Originality:\nThe paper seems fairly incremental in terms of the proposed method, applying an existing method for variance reduction to an existing algorithm. However, some of the technical tools used in the analysis of the resulting VR-Greedy-GQ algorithm are original to the best of my knowledge.\n\n### Decision:\nDespite some concerns listed below, I recommend accepting the paper for publication.\n\nWhy use SVRG to reduce variance? The nested loop structure seems at odds with the single Markovian path of experience, and conflicts with the original motivation for Greedy-GQ (\"Online, incremental, with memory and per-time-step computation costs that are linear in the number of features\" ). If we're giving up online and incremental algorithms, why not use an LSTD-based method like LSPI (Lagoudakis & Parr, 2003) instead?\n\nWhy require smooth policies when the original Greedy-GQ paper doesn’t? Is it just for convenience? Would the analysis still apply for a non-smooth policy like the greedy policy?\n\n### Suggestions for improvement:\n- In the related work section, it could be helpful to explicitly write how the related work is different from the current work.\n\n### Miscellaneous comments:\n- Spelling error in third paragraph of section 1.1: “new tecnical developments”\n- In section 2.2 the paper states that “[Greedy-GQ] aims to minimize the Bellman error”, but my understanding is that Greedy-GQ was designed explicitly for the function approximation setting where minimizing MSBE and MSPBE are different. It would be better to write “and in the tabular setting it aims to minimize the Bellman error”.\n- Corollary 4.2 sets $\\eta_\\theta$ twice. Is the second $\\eta_\\theta$ supposed to be $\\eta_\\omega$?\n\n### References:\n- Wang, Y., & Zou, S. (2020). Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise. arXiv preprint arXiv:2005.10175.\n- Maei, H. R., Szepesvári, C., Bhatnagar, S., & Sutton, R. S. (2010, January). Toward off-policy learning control with function approximation. In ICML.\n- Lagoudakis, M. G., & Parr, R. (2003). Least-squares policy iteration. Journal of machine learning research, 4(Dec), 1107-1149.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ae8p5fddUKI", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper combines a widely used variance reduction technique SVRG with the greedy-GQ. It provides a finite-time analysis of the proposed algorithm  in the off-policy and Markovian sampling setting (convergence to the stationary point) and improves the sample complexity from the order $\\epsilon^{-3}$ to $\\epsilon^{-2}$ comparing with the vanilla greedy GQ. Interestingly, the analysis shows that the biase error caused by the Markovian sampling and the variance error of the stochastic gradient are reduced by the $M$, where M is the batch size of the batch gradient in SVRG. At last, it verifies the theoretical claim by two toy examples.\n\npros:\n1. It combines the variance reduction trick in optimization community with the two time scale analysis in RL.\n2. The analysis is on the off-policy control setting, which in general is much harder than the off-policy evaluation setting.\n3. The objective function of MSPBE in control setting is non-convex, which increases the difficulty of the proof.\n\n\ncons:\n1. The main contribution of this paper is its theoretical analysis. However the techniques in the proof have already existed in many literatures. It seems that the author just combines them together. For instance, there are many literatures on the convergence analysis of the SVRG in the non-convex setting.  The author claims that the 'fine-tuned' Lyapunov function is novel. However such tools in the non-convex SVRG are widely used. It may be true that we need to chose the c_t carefully to cancel some error term but  the main framework of the proof is the same.\n\n2. I am not sure whether the variance reduction technique is useful in practice. There are some evidences that SVRG does not work well in the training of deep learning problem.  Would faster convergence to the stationary points lead to the better performance (e.g. higher reward )? I do not see anything related to that in the experiment. \n\n3. The author just tests their algorithm on two toy examples. I hope to see more complicated experiments. Maybe the author can try the neural network in the function approximation beyond the linear function approximation.  I know the analysis is just on the linear case, but this experiment would demonstrate the potential applicability of the algorithm.\n\n\n################after rebuttal\n\nAfter reading the responds from the author, I keep my score at 5.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QSk-MNK8ZG7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a variance reduced Greedy-GQ algorithm and proves that it enjoys a lower convergence rate compared with vanilla Greedy-GQ. The paper is well written and clearly presented. The sample complexity of the proposed algorithm is lower than Greedy-GD by a factor of 1/eps, which could be a great improvement when the target precision eps is small. \n\nIn the related work part, the nonasymptotic convergence of Q-learning with function approximation has also been extended to neural network function approximation (A finite-time analysis of q-learning with neural network function approximation. In ICML 2020).\n\nIn the algorithm, what specific policy improvement is used? Does the choice affect the proof of the convergence?\n\nOne drawback of the result in Theorem 4.5 is that the convergence is only guaranteed for the minimal gradient norm over the whole trajectory. However, in Algorithm 1, the output is defined as the last iterate. In other words, the convergence rate in Theorem 4.5 is not for the proposed algorithm. In this sense, the convergence results may not be as useful as other algorithms that can guarantee the convergence of the last iterate of the average iterate.\n\nIn terms of the experiments, it would be nice if the cumulative reward versus running time can be shown, which demonstrates the performance in a clearer way. It would also be interesting to see whether the proposed variance reduced Greedy-GQ method can match the performance of off-policy policy gradient (or actor-critic) methods and variance reduced policy gradient methods in controlling problems.\n\n#########Edits after the rebuttal#########\n\nI have read the response and other reviewers' review/discussion. I will keep a score as 6.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Overview** This paper provides a way to combine SVRG and greedy-GQ to improve the algorithm performance. In particular, the finite iteration complexity is improved from $\epsilon^{-3}$ to $\epsilon^{-2}$.

**Pros** The paper is well-written. Reviewers believe this is a solid theoretical work on advancing value-based algorithms for off-policy optimal control. It has sufficient theoretical advancement and experiments demonstrations of the methods. 

**Cons** Some reviewers are concerned that SVRG is not SOTA. SVRG is not used in practice. The techniques appear to be similar to some existing works. 

**Recommendation** The meta-reviewer believes that the paper has solid theoretical contributions. SVRG is a component in the new algorithm to improve the complexity. It does not need to be "useful" or "SOTA". The paper is also well-written. Hence the recommendation is accept.
Decision: Accept (Poster)