Year: 2021

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 -stationary point with a sample complexity in the order of O( −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 O( −2). We further compare the performance of VR-Greedy-GQ with that of Greedy-GQ in various RL experiments to corroborate our theoretical findings.

heading: 1 INTRODUCTION
text: In reinforcement learning (RL), an agent interacts with a stochastic environment following a certain policy and receives some reward, and it aims to learn an optimal policy that yields the maximum accumulated 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 is guaranteed in the tabular setting. However, it is known that these algorithms may diverge in the popular off-policy setting under linear 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 GreedyGQ to a stationary point has been established in Maei et al. (2010). More recently, Wang & Zou (2020) studied the finite-time convergence of Greedy-GQ under linear function approximation and Markovian sampling, and it is shown that the algorithm achieves an -stationary point of the objective function with a sample complexity in the order of O( −3). Such an undesirable high sample complexity is caused by the large variance induced by the Markovian samples queried from the dynamic environment. Therefore, we want to ask the following question.
• Q1: Can we develop a variance reduction scheme for the two time-scale Greedy-GQ algorithm?
In fact, in the existing literature, many recent work proposed to apply the variance reduction techniques developed in the stochastic optimization literature to reduce the variance of various TD learning 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 a variance-reduced Greedy-GQ algorithm for optimal control. In particular, as many of the existing variance-reduced RL algorithms have been shown to achieve an improved sample complexity under variance reduction, it is natural to ask the following fundamental question.
• Q2: Can variance-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 a 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 -stationary point with an improved sample complexity O( −2). We summarize our technical contributions as follows.

heading: 1.1 OUR CONTRIBUTIONS
text: We develop a variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm for optimal control in reinforcement learning. Specifically, the algorithm leverages the SVRG variance reduction scheme Johnson & Zhang (2013) to construct variance-reduced stochastic updates for updating the parameters 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 -stationary point of the objective function J (i.e., ‖∇J(θ)‖2 ≤ ) with a sample complexity in the order of O( −2). Such a complexity result improves that of the original Greedy-GQ by a significant factor of O( −1) 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 ofO(M−1),O(ηθM−1), respectively, where ηθ 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 a factor of M ) and lead to an 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-GQ involves two time-scale variance-reduced updates that are correlated with each other. Such an extension of the SVRG scheme to the two time-scale updates is novel and requires 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 to develop new techniques to characterize the per-iteration optimization progress towards a stationary point under nonconvexity. In particular, to analyze the two time-scale variance reduction updates of the algorithm, we introduce a ‘fine-tuned’ Lyapunov function of the form Rmt = J(θ (m) t ) + ct‖θ (m) t − θ̃(m)‖2, where the parameter ct is fine-tuned to cancel other additional quadratic terms ‖θ(m)t − θ̃(m)‖2 that are implicitly involved in the tracking error 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 convergence rate and sample complexity for VR-Greedy-GQ.

heading: 1.2 RELATED WORK
text: 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 finite-time analysis were developed in Zou et al. (2019); Chen et al. (2019). However, these algorithms may diverge in off-policy training Baird (1995). Also, recent works focused on the Markovian setting. Various analysis techniques have been developed to analyze
the finite-time convergence of TD/Q-learning under Markovian samples. Specifically, Wang et al. (2020) developed a multi-step Lyapunov analysis for addressing the biasedness of the stochastic approximation in Q-learning. Srikant & Ying (2019) developed a drift analysis to the linear stochastic 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 et 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 et 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 algorithms. 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) to primal-dual batch gradient algorithm. In Korda & La (2015), the variance-reduced TD algorithm was introduced for solving the MSPBE problem, and later Xu et al. (2020) provided a correct non-asymptotic 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 to 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 approximation, and Q-learning has only a single time-scale update. As a comparison, our VR-Greedy-GQ takes nonlinear two time-scale updates to optimization a nonconvex MSPBE.

heading: 2 PRELIMINARIES: POLICY OPTIMIZATION AND GREEDY-GQ
text: In this section, we review some preliminaries of reinforcement learning and recap the Greedy-GQ algorithm under linear function approximation.

heading: 2.1 POLICY OPTIMIZATION IN REINFORCEMENT LEARNING
text: In reinforcement learning, an agent takes actions to interact with the environment via a Markov Decision Process (MDP). Specifically, an MDP is 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 : S×A×S → [0,+∞) denotes a reward function and γ ∈ (0, 1) is the associated reward discount factor. At any time t, assume that the agent is in the state st ∈ S and takes a certain action at ∈ A following a stationary policy π, i.e., at ∼ π(·|st). Then, at the subsequent time t + 1, the current state of the agent transfers to a new state st+1 according to the transition kernel P(·|st, at). At the same time, the agent receives a reward rt = r(st, at, st+1) from the environment for this action-state transition. To evaluate the quality of a given policy π, we often use the action-state value function Qπ : S ×A → R that accumulates the discounted rewards as follows:
Qπ(s, a) = Es′∼P(·|s,a) [r(s, a, s′) + γV π(s′)] , where V π(s) is the state value function defined as V π(s) = E [∑∞
t=0 γ trt|s0 = s
] . In particu-
lar, define the Bellman operator Tπ such that TπQ(s, a) = Es′,a′ [r(s, a, s′) + γQ(s′, a′)] for any Q(s, a), where a′ ∼ π(·|s′). Then, Qπ(s, a) is a fixed point of Tπ , i.e.,
TπQπ(s, a) = Qπ(s, a), ∀s, a. (1) The goal of policy optimization is to learn the optimal policy π∗ that maximizes the expected total reward E[ ∑∞ t=0 γ
trt|s0 = s] for any initial state s ∈ S, and this is equivalent to learn the optimal value function Q∗(s, a) = supπ Q
π(s, a),∀s, a. In particular, Q∗ is a fixed point of the Bellman operator T that is defined as TQ(s, a) = Es′∼P(·|s,a)[r(s, a, s′) + γmaxb∈AQ(s′, b)].

heading: 2.2 GREEDY-GQ WITH LINEAR FUNCTION APPROXIMATION
text: The Greedy-GQ algorithm is inspired by the fixed point characterization in eq. (1), and in the tabular setting it aims to minimize the Bellman error ‖TπQπ − Qπ‖2µs,a . Here, ‖ · ‖ 2 µs,a is induced by
the state-action stationary distribution µs,a (induced by the behavior policy πb), and is defined as ‖Q‖2µs,a = E(s,a)∼µs,a [Q(s, a) 2].
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 a set of basis functions {φ(i) : S × A → R, i = 1, 2, . . . , d}, each of which maps a given state-action pair to a certain value. Define φs,a = [φ(1)(s, a); ...;φ(d)(s, a)] as the feature vector for (s, a). Then, under linear function approximation, the value function Q(s, a) is approximated by Qθ(s, a) = φ>s,aθ, where θ ∈ Rd denotes the parameter of the linear approximation. Consequently, Greedy-GQ aims to find the optimal θ∗ that minimizes the following mean squared projected Bellman error (MSPBE).
(MSPBE): J(θ) := 1
2 ‖ΠTπθQθ −Qθ‖2µs,a , (2)
where µs,a is the stationary distribution induced by the behavior policy πb, Π is a projection operator that maps an action-value function Q to the space Q spanned by the feature vectors, i.e., ΠQ = arg minU∈Q ‖U−Q‖µs,a . Moreover, the policy πθ is parameterized by θ. In this paper, we consider the class of Lipschitz and smooth policies (see Assumption 4.2).
Next, we introduce the Greedy-GQ algorithm. Define V s′(θ) = ∑ a′∈A πθ(a
′|s′)φ>s′,a′θ, δs,a,s′(θ) = r(s, a, s
′) + γV s′(θ) − φ>s,aθ and denote φ̂s(θ) = ∇V s(θ). Then, the gradient of the objective function J(θ) in eq. (2) is expressed as
∇J(θ) = −E[δs,a,s′(θ)φs,a] + γE[φ̂s′(θ)φ>s,a]ω∗(θ),
where ω∗(θ) = E[φs,aφ>s,a]−1E[δs,a,s′(θ)φs,a]. To address the double-sampling issue when estimating the product of expectations involved in E[φ̂s′(θ)φ>s,a]ω∗(θ), Sutton et al. (2009a) applies a 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, at, rt, st+1) using the behavior policy πb and do
(Greedy-GQ):  θt+1 = θt − ηθ ( − δt+1(θt)φt + γ(ω>t φt)φ̂t+1(θt) ) , ωt+1 = ωt − ηω ( φ>t ωt − δt+1(θt) ) φt,
πθt+1 = P(φ>θt+1).
(3)
where ηθ, ηω > 0 are the learning rates and we denote δt+1(θ) := δst,at,st+1(θ), φt := φst,at , φ̂t+1(θt) := φ̂st+1(θt) for simplicity. To elaborate, the first two steps correspond to the two timescale updates for updating the value function Qθ, whereas the last step is a policy improvement operation that exploits the updated value function to improve the target policy, e.g., greedy, -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 often induces a large variance that significantly slows down the overall convergence. This motivates us to develop variance reduction schemes for the two time-scale Greedy-GQ in the next section.

heading: 3 GREEDY-GQ WITH VARIANCE REDUCTION
text: In this section, we propose a variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm under Markovian sampling by leveraging the SVRG variance reduction scheme Johnson & Zhang (2013). To simplify notations, we define the stochastic updates regarding a sample xt = (st, at, rt, st+1) used in the Greedy-GQ as follows:
Gxt(θ, ω) := −δt+1(θ)φt + γ(ω>φt)φ̂t+1(θ), Hxt(θ, ω) := ( φ>t ω − δt+1(θ) ) φt.
Next, consider a single MDP trajectory {xt}t≥0 obtained by the behavior policy πb. In particular, we divide the entire trajectory into multiple batches of samples {Bm}m≥1 so that Bm =
{x(m−1)M , ..., xmM−1}, and our proposed VR-Greedy-GQ uses one batch of samples in every epoch. To elaborate, in the m-th epoch, we first initialize this epoch with a pair of reference points θ
(m) 0 = θ̃ (m), ω (m) 0 = ω̃ (m), where θ̃(m), ω̃(m) are set to be the output points θ(m−1)M , ω (m−1) M of the previous epoch, respectively. Then, we compute a pair of reference batch updates using the reference points and the batch of samples as follows
G̃(m) = 1
M mM−1∑ k=(m−1)M Gxk(θ̃ (m), ω̃(m)), H̃(m) = 1 M mM−1∑ k=(m−1)M Hxk(θ̃ (m), ω̃(m)). (4)
In the t-th iteration of the m-th epoch, we first query a random sample xξmt from the batch Bm uniformly with replacement (i.e., sample ξmt from {(m − 1)M, ...,mM − 1} uniformly). Then, we use this sample to compute the stochastic updates Gxξmt , Hxξmt at both of the points (θ (m) t , ω (m) t ), (θ̃
(m), ω̃(m)). After that, we use these stochastic updates and the reference batch updates to construct the variance-reduced updates in Algorithm 1 via the SVRG scheme, where for simplicity we denote the stochastic updates Gxξmt , Hxξmt respectively as G (m) t , H (m) t . In particular, we project the two time-scale updates onto the Euclidean ball with radius R to stabilize the algorithm 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 .
Algorithm 1: Variance-Reduced Greedy-GQ Input: learning rates ηθ, ηω , batch size M . Initialize: θ̃(1) = θ0, ω̃(1) = ω0, πθ̃(1) ← P(φ
>θ̃(1)). for m = 1, 2, . . . do θ
(m) 0 = θ̃ (m), ω(m)0 = ω̃ (m). Compute G̃(m), H̃(m) according to eq. (4).
for t = 0, 1, . . . ,M − 1 do Query a sample from Bm with replacement. θ
(m) t+1 = ΠR
[ θ
(m) t − ηθ
( G
(m) t (θ (m) t , ω (m) t )−G (m) t (θ̃
(m), ω̃(m)) + G̃(m) )] .
ω (m) t+1 = ΠR
[ ω
(m) t − ηω
( H
(m) t (θ (m) t , ω (m) t )−H (m) t (θ̃
(m), ω̃(m)) + H̃(m) )] .
Policy improvement: π θ (m) t+1 ← P(φ>θ(m)t+1).
end Set θ̃(m+1) = θ(m)M , ω̃ (m+1) = ω (m) M .
end Output: parameter θ chosen among {θ(m)t }t,m uniformly at random.
The above VR-Greedy-GQ algorithm has several advantages and uniqueness. First, it takes incremental updates that use a single Markovian sample per-iteration. This makes the algorithm sample efficient. Second, VR-Greedy-GQ applies variance reduction to both of the two 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 VRGreedy-GQ is based on the online-SVRG and can be viewed as an incremental algorithm with regard to the batches of samples used in the outer-loops, i.e., in every outer-loop the algorithm samples a new batch of samples and use them to perform variance reduction in the corresponding inner-loops. Therefore, VR-Greedy-GQ can be viewed as an online batch-incremental algorithm. In general, there is a trade-off between incrementalism and variance reduction for SVRG-type algorithms: a larger batch size in the outer-loops enhances the effect of variance reduction, while a smaller batch size makes the algorithm more incremental.

heading: 4 FINITE-TIME ANALYSIS OF VR-GREEDY-GQ
text: In this section, we analyze the finite-time convergence rate of VR-Greedy-GQ. We adopt the following standard technical assumptions from Wang & Zou (2020); Xu et al. (2020).
Assumption 4.1 (Feature boundedness). The feature vectors are uniformly bounded, i.e., ‖φs,a‖ ≤ 1 for all (s, a) ∈ S ×A. Assumption 4.2 (Policy smoothness). The mapping θ 7→ πθ is k1-Lipschitz 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 := E[φs,aφ>s,a] is non-singular. Assumption 4.4 (Geometric uniform ergodicity). There exists Λ > 0 and ρ ∈ (0, 1) such that
sup s∈S
dTV ( P(st|s0 = s), µ ) ≤ Λρt,
for any t > 0, where dTV is the total-variation distance.
Based on the above assumptions, we obtain the following finite-time convergence rate result.
Theorem 4.5 (Finite-time convergence). Let Assumptions 4.1– 4.4 hold and consider the VRGreedy-GQ algorithm. Choose learning rates ηθ, ηω and the batch sizeM that satisfy the conditions specified in eqs. (15) to (19). Then, after T epochs, the output of the algorithm satisfies
E‖∇J(θ(ζ)ξ )‖ 2 ≤ O ( 1 ηθTM + 1 T ( ηω + η2θ η2ω ) + ( ηω + η2θ η2ω )2 + 1 M ) ,
where ξ, ζ are random indexes that are sampled from {0, ...,M − 1} and {1, ..., T} uniformly at random, respectively.
Theorem 4.5 shows that VR-Greedy-GQ asymptotically converges to a neighborhood of a stationary point at a sublinear rate. In particular, the size of the neighborhood is in the order of O(M−1 + η4θη −4 ω + η 2 ω), which can be driven arbitrarily close to zero by choosing a large batch size and sufficiently small learning rates that satisfy the two time-scale condition ηθ/ηω → 0. Moreover, the convergence error terms implicitly include a bias error O( 1M ) caused by the Markovian sampling and a variance errorO( ηθM ) 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 of the two time-scale stochastic updates.
By further optimizing the choice of hyper-parameters, 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 ηθ = O( 1M ), ηω = O(η 2/3 θ ), and set T ,M = O( −1)). Then, the required sample complexity for achieving E‖∇J(θ(ζ)ξ )‖2 ≤ is in the order of TM = O( −2).
Such a complexity result is orderwise lower than the complexityO( −3) 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-GQ. We also note that for online stochastic non-convex optimization, the sample complexity of the SVRG algorithm is in the order of O( −5/3) Li & Li (2018), which is slightly better than our result. This is reasonable as the SVRG in stochastic optimization is unbiased due to the i.i.d. sampling. In comparison, VR-Greedy-GQ works on a single MDP trajectory that induces Markovian noise, and the two-timescale updates of the algorithm also introduces additional tracking error.

heading: 5 SKETCH OF THE TECHNICAL PROOF
text: In this section, we provide an outline of the technical proof of 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 a Lyapunov function. However, our analysis requires substantial new developments to address the challenges of off-policy control, two time-scale updates of VR-Greedy-GQ and correlation of Markovian samples.
The key step of the proof is to develop a proper Lyapunov function that drives the parameter to a 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 ct > 0 to be determined later.
Rmt := J(θ (m) t ) + ct‖θ (m) t − θ̃(m)‖2. (5)
To explain the motivation, note that unlike the analysis of variance-reduced TD learning Xu et al. (2020) where the term ‖θ(m)t − θ̃(m)‖2 can be decomposed into ‖θ (m) t − θ∗‖2 + ‖θ̃(m) − θ∗‖2 to get the desired upper bound, here we do not have θ∗ due to the non-convexity of J(θ). Hence, we need to properly merge this term into the Lyapunov function Rmt . By leveraging the smoothness of J(θ) and the algorithm update rule, we obtain the following bound for the Lyapunov function Rmt (see eq. (10) in the appendix for the details).
E[Rmt+1] ≤ E[J(θ (m) t )] +O ( E[‖θ(m)t − θ̃(m)‖2] + E[‖∇J(θ (m) t )]‖2 +M−1 ) +O ( E[‖ω̃(m) − ω∗(θ̃(m))‖2] + E[‖ω(m)t − ω∗(θ (m) t )‖2] ) . (6)
In particular, the error term 1M 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), one may want to define J(θ
(m) t )] + O ( E[‖θ(m)t − θ̃(m)‖2] ) = Rmt by choosing a proper ct of R m t . However, note that eq. (6) involves the last two tracking error terms, which also implicitly depend on E‖θ(m)t − θ̃(m)‖2 as we show later in the Step 3. Therefore, we need to carefully define the ct of Rmt so that after applying the tracking error bounds developed in the Step 3, the right hand side of eq. (6) can yield an Rmt without involving the term E‖θ (m) t − θ̃(m)‖2. It turns out that we need to define ct via the recursion specified in eq. (11) in the appendix. We rigorously show that the sequence {ct}t is uniformly bounded by a small constant ĉ = 18 . 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∑ t=0 E[‖∇J(θ(m)t )‖2] ≤ E[Rm0 ]− E[RmM ] +O ( ηθ + η 2 θME[‖ω̃(m) − ω∗(θ̃(m))‖2] ) +O ( ηθ
M−1∑ t=0 E‖ω(m)t − ω∗(θ (m) t )‖2 − ηθ ĉ ( ηω + η2θ η2ω )M−1∑ t=0 E[‖θ(m)t − θ̃(m)‖2] ) .
Step 3: We derive bounds for the tracking error terms ∑M−1 t=0 E‖ω (m) t −ω∗(θ (m) t )‖2 and E‖ω̃(m)− ω∗(θ̃(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 t=0 E‖θ (m) t − θ̃(m)‖2. Then, summing this bound over the epochs m = 1, ..., T , we obtain the desired finite-time convergence rate result.

heading: 6 EXPERIMENTS
text: In this section, we conduct two reinforcement learning experiments, namely, Garnet problem Archibald et al. (1995) and Frozen Lake game Brockman et al. (2016), to test the performance of VR-Greedy-GQ in the off-policy setting, and compare it with Greedy-GQ in the Markovian setting.

heading: 6.1 GARNET PROBLEM
text: For the Garnet problem, we refer to Appendix F for the details of the problem setup. In Figure 1 (left), we plot the minimum gradient norm v.s. the number of pseudo stochastic gradient computations 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.
In Figure 1 (middle), we track the estimated variance of the stochastic update for both algorithms along the iterations. Specifically, we query 500 Monte Carlo samples per iteration to estimate the pseudo gradient variance E‖G(m)t (θ (m) t , ω (m) t ) − ∇J(θ (m) t )‖2. It can be seen from the figure that the stochastic updates of VR-Greedy-GQ induce a much smaller variance than Greedy-GQ. This demonstrates the effectiveness of the two time-scale variance reduction scheme of VR-Greedy-GQ.
We further study the asymptotic convergence error of VR-Greedy-GQ under different batch sizesM . We use the default learning rate setting that is mentioned previously and run 100k iterations for one Garnet trajectories. We use the mean of the convergence error of the last 10k iterations as an estimate of the asymptotic convergence error (the training curves are already saturated and flattened). Figure 1 (right) shows the asymptotic convergence error of VR-Greedy-GQ under different batch sizes M . It can be seen that VR-Greedy-GQ achieves a smaller asymptotic convergence error with a larger batch size, which matches our theoretical result.
In Figure 2 (Left), we plot the MSPBE J(θ) v.s. number of gradient computations for both GreedyGQ and VR-Greedy-GQ, where one can see that VR-Greedy-GQ achieves a much smaller MSPBE than Greedy-GQ. In Figure 2 (Middle), we plot the estimated expected maximum reward (see Appendix F for details) v.s. number of gradient computations for Greedy-GQ, VR-Greedy-GQ and actor-critic, where for actor-critic we set learning rate ηθ = 0.02 for the actor update and ηω = 0.01 for the critic update. One can see that VR-Greedy-GQ achieves a higher reward than the other two algorithms, demonstrating the high quality of its learned policy. In addition, we also plot the estimated expected maximum reward v.s. number of iterations for Greedy-GQ, VR-Greedy-GQ and 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 a fixed length 60 to estimate the expected discounted return. The learning rate of policy gradient is set as ηθ. We note that each iteration of policy gradient consumes 1800 samples and hence it is very sample inefficient. Hence we set the x-axis to be number of iterations for a clear presentation (otherwise it becomes a flat curve). One can see that VR-Greedy-GQ achieves a much higher expected reward than both Greedy-GQ and policy gradient.

heading: 6.2 FROZEN LAKE GAME
text: We further test these algorithms in solving the more complex frozen lake game. we refer to Appendix F for the details of the problem setup. Figure 3 shows the comparison between VR-Greedy-
GQ and Greedy-GQ, and one can make consistent observations with those made in the Garnet experiment. 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-GQ induce a much smaller variance than those of Greedy-GQ. Moreover, Figure 3 (right) verifies our theoretical result that VR-Greedy achieves a smaller asymptotic convergence error with a larger batch size.
We further plot the MSPBE v.s. number of gradient computations for both Greedy-GQ and VRGreedy-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 set learning rate ηθ = 0.2 for the actor update and ηω = 0.1 for the critic update. It can be seen that VRGreedy-GQ achieves a 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-GQ and policy gradient. For policy gradient, we use the same parameter settings as before. One can see that VR-Greedy-GQ achieves a much higher expected reward than both Greedy-GQ and policy gradient.

heading: 7 CONCLUSION
text: In this paper, we develop a variance-reduced two time-scale Greedy-GQ algorithm for optimal control 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 a stationary point and prove an improved sample complexity bound over that of the original GreedyGQ. The RL experiments well demonstrated the effectiveness of the proposed two time-scale variance reduction scheme. Our algorithm design may inspire new developments of variance reduction for two time-scale RL algorithms. In the future, we will explore Greedy-GQ with other nonconvex variance reduction schemes to possibly further improve the sample complexity.

heading: ACKNOWLEDGEMENT
text: The work of S. Zou was supported by the National Science Foundation under Grant CCF-2007783.

heading: A FILTRATION AND LIST OF CONSTANTS
text: Filtration We follow the definition of filtration in VRTD (Appendix D, Xu et al. (2020)). Recall thatBm denotes the set of Markovian samples used in them-th epoch, and we also abuse the notation here by letting x(m)t be the sample picked in the t-th iteration of the m-th epoch. Then, we define the filtration for Markovian samples as follows
F1,0 = σ(B0 ∪ σ(θ̃(0), w̃(0))), F1,1 = σ(F1,0 ∪ σ(x(1)0 )), . . . , F1,M = σ(F1,M−1 ∪ σ(x (1) M−1)) F2,0 = σ ( B1 ∪ F1,M ∪ σ(θ̃(1), w̃(1)) ) , F2,1 = σ(F2,0 ∪ σ(x(2)0 )), . . . , F2,M = σ(F2,M−1 ∪ σ(x (2) M−1))
...
Fm,0 = σ ( Bm−1 ∪ Fm−1,M ∪ σ(θ̃(m−1), w̃(m−1)) ) , Fm,1 = σ(Fm,0 ∪ σ(x(m)0 )), . . . ,
Fm,M = σ(Fm,M−1 ∪ σ(x(m)M−1)).
Moreover, we define Et,m as the conditional expectation with respect to the σ-field Ft,m.
List of Constants We summarize all the constants that are used in the proof as follows.
• G = rmax + (1 + γ)R+ γ(|A|Rk1 + 1)R. • H = (2 + γ)R+ rmax. • C1 = (1 + 2Λ ρ1−ρ )(G+ C∇J) 2.
• C2 = H2(1 + Λ ρ1−ρ ).
• C3 = 8R 2 λC (1 + ρΛ1−ρ ).
• C4 = 2λC (R(2 + γ) + rmax) 2(1 + ρΛ1−ρ ).

heading: B PROOF OF THEOREM 4.5
text: We first define the following Lyapunov function
Rmt := J(θ (m) t ) + ct‖θ (m) t − θ̃(m)‖2,
where ct > 0 is to be determined later. Our strategy is to characterize the per-iteration progress of Rmt . In particular, we use Lemma E.9 to bound the first term of R m t and use Lemma E.10 to bound the second term of Rmt . Note that Lemma E.9 implies that
J(θ (m) t+1) ≤ J(θ (m) t )− ηθ〈∇J(θ (m) t ), g (m) t −∇J(θ (m) t )〉 − ηθ‖∇J(θ (m) t )‖2 +
L 2 η2θ‖g (m) t ‖2.
Let ξ(m)t := 〈∇J(θ (m) t ), g (m) t −∇J(θ (m) t )〉. Then, we obtain that
J(θ (m) t+1) ≤ J(θ (m) t )− ηθξ (m) t − ηθ‖∇J(θ (m) t )‖2 +
L 2 η2θ‖g (m) t ‖2. (7)
Substituting eq. (7) and eq. (30) into the definition of Rmt+1, we obtain that
Rmt+1 := J(θ (m) t+1) + ct+1‖θ (m) t+1 − θ̃(m)‖2
≤ J(θ(m)t )− ηθξ (m) t − ηθ‖∇J(θ (m) t )‖2 +
L 2 η2θ‖g (m) t ‖2
+ ct+1 [ η2θ‖g (m) t ‖2 + ‖θ (m) t − θ̃(m)‖2 − 2ηθζ (m) t
+ ηθ [ 1 βt ‖∇J(θ(m)t )‖2 + βt‖θ (m) t − θ̃(m)‖2 ]] = J(θ
(m) t ) + ct+1(ηθβt + 1)‖θ (m) t − θ̃(m)‖2
+ ( − ηθ + ct+1
ηθ βt
) ‖∇J(θ(m)t )‖2 + (L 2 η2θ + ct+1η 2 θ ) ‖g(m)t ‖2
− ηθξ(m)t − 2ct+1ηθζ (m) t .
Next, we bound the two inner product terms ξ(m)t and ζ (m) t .
Bounding the term ξ(m)t :
ξ (m) t := 〈∇J(θ (m) t ), g (m) t −∇J(θ (m) t )〉.
Recall the variance-reduced stochastic update
g (m) t = G (m) t (θ (m) t , ω (m) t )−G (m) t (θ̃ (m), ω̃(m)) + G̃(m).
Then, the term ξ(m)t can be decomposed as
ξ (m) t = 〈∇J(θ (m) t ), g (m) t −∇J(θ (m) t )〉
= 〈∇J(θ(m)t ), G (m) t (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉
+ 〈∇J(θ(m)t ), G (m) t (θ (m) t , ω (m) t )−G (m) t (θ (m) t , ω ∗(θ (m) t ))〉
+ 〈∇J(θ(m)t ),−G (m) t (θ̃ (m), ω̃(m)) + G̃(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
E〈∇J(θ(m)t ), G (m) t (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉
=E〈∇J(θ(m)t ), G(m)(θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉
= 1
4 E‖∇J(θ(m)t )‖2 + E‖G(m)(θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉‖2
≤1 4 E‖∇J(θ(m)t )‖2 + C1 M .
The second inner product term is the bias caused by tracking error, and we further obtain that
〈∇J(θ(m)t ), G (m) t (θ (m) t , ω (m) t )−G (m) t (θ (m) t , ω ∗(θ (m) t ))〉
≤1 4 ‖∇J(θ(m)t )‖2 + L1‖ω (m) t − ω∗(θ (m) t )‖2.
The third inner product term is unbiased. Combining all of these bounds, we finally obtain that
|Eξ(m)t | ≤ C1 M + 1 2 ‖∇J(θ(m)t )‖2 + L1‖ω (m) t − ω∗(θ (m) t )‖2. (8)
Bounding the term ζ(m)t :
ζ (m) t := 〈g (m) t −∇J(θ (m) t ), θ (m) t − θ̃(m)〉.
Similar to the previous proof for bounding ξ(m)t , we can decompose ζ (m) t as
ζ (m) t = 〈θ (m) t − θ̃(m), g (m) t −∇J(θ (m) t )〉
= 〈θ(m)t − θ̃(m), G (m) t (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉
+ 〈θ(m)t − θ̃(m), G (m) t (θ (m) t , ω (m) t )−G (m) t (θ (m) t , ω ∗(θ (m) t ))〉
+ 〈θ(m)t − θ̃(m),−G (m) t (θ̃ (m), ω̃(m)) + G̃(m)〉
In the last equality, the first inner product term is the bias caused by Markovian samples. We obtain that
E〈θ(m)t − θ̃(m), G (m) t (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉
≤1 2 E‖θ(m)t − θ̃(m)‖2 + 1 2 E‖G(m)t (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉‖2
≤1 2 E‖θ(m)t − θ̃(m)‖2 + 1 2 C1 M .
The second inner product term is the bias caused by tracking error. We obtain that
〈θ(m)t − θ̃(m), G (m) t (θ (m) t , ω (m) t )−G (m) t (θ (m) t , ω ∗(θ (m) t ))〉
≤1 2 ‖θ(m)t − θ̃(m)‖2 + L1 2 ‖ω(m)t − ω∗(θ (m) t )‖2.
The third inner product term is unbiased. Combining all of these bounds, we finally obtain that
|Eζ(m)t | ≤ 1
2 C1 M + ‖θ(m)t − θ̃(m)‖2 + L1 2 ‖ω(m)t − ω∗(θ (m) t )‖2. (9)
Next, we continue to bound the Lyapunov function. Recall we have shown that
Rmt+1 ≤ J(θ (m) t ) + ct+1(ηθβt + 1)‖θ (m) t − θ̃(m)‖2
+ ( − ηθ + ct+1
ηθ βt
) ‖∇J(θ(m)t )‖2 + (L 2 η2θ + ct+1η 2 θ ) ‖g(m)t ‖2
− ηθξ(m)t − 2ct+1ηθζ (m) t .
Taking expectation on both sides of the above inequality and applying eq. (8), eq. (9), and Lemma D.1, we obtain that
E[Rmt+1] ≤ E [ J(θ (m) t ) + ct+1(ηθβt + 1)‖θ (m) t − θ̃(m)‖2 ] + ( − ηθ + ct+1
ηθ βt
) E‖∇J(θ(m)t )‖2
+ (L
2 η2θ + ct+1η 2 θ
)[ 6L1E‖ω(m)t − ω∗(θ (m) t )‖2 + 9L1E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 9L2E‖θ(m)t − θ̃(m)‖2 + 1
M · 9C1 + 9E‖∇J(θ(m)t )‖2 ] + ηθ [C1 M + 1 2 ‖∇J(θ(m)t )‖2 + L1‖ω (m) t − ω∗(θ (m) t )‖2
] + 2ct+1ηθ [1 2 C1 M + ‖θ(m)t − θ̃(m)‖2 + L1 2 ‖ω(m)t − ω∗(θ (m) t )‖2 ] . (10)
We note that the tracking error term ‖ω(m)t −ω∗(θ (m) t )‖2 has dependence on ‖θ (m) t − θ̃(m)‖2. 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
E[Rmt+1] ≤ E [ J(θ (m) t ) + [ ct+1(ηθβt + 1 + 2ηθ) + 9L1 (L 2 η2θ + ct+1η 2 θ )] ‖θ(m)t − θ̃(m)‖2 ] + [ − 1
2 ηθ + ct+1 ηθ βt
+ 9 (L
2 η2θ + ct+1η 2 θ
)] E‖∇J(θ(m)t )‖2
+ [ ηθ + 2ct+1ηθ + 9 (L 2 η2θ + ct+1η 2 θ )]C1 M
+ 9L1 (L
2 η2θ + ct+1η 2 θ
) E‖ω̃(m) − ω∗(θ̃(m))‖2
+ [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] E‖ω(m)t − ω∗(θ (m) t )‖2
− [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] · 4 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ] E‖θ(m)t − θ̃(m)‖2
+ [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] · 4 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ] E‖θ(m)t − θ̃(m)‖2.
Then, we define Rmt := J(θ (m) t ) + ct‖θ (m) t − θ̃(m)‖2 with ct being specified via the following recursion.
ct = ct+1(ηθβt + 1 + 2ηθ) + 9L1 (L
2 η2θ + ct+1η 2 θ ) + [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] · 4 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ] . (11)
Based on this definition, the previous inequality reduces to E[Rmt+1] ≤ E[Rmt ] + [ − 1
2 ηθ + ct+1 ηθ βt
+ 9 (L
2 η2θ + ct+1η 2 θ
)] E‖∇J(θ(m)t )‖2
+ [ ηθ + 2ct+1ηθ + 9 (L 2 η2θ + ct+1η 2 θ )]C1 M
+ 9L1 (L
2 η2θ + ct+1η 2 θ
) E‖ω̃(m) − ω∗(θ̃(m))‖2
+ [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] E‖ω(m)t − ω∗(θ (m) t )‖2
− [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] · 4 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ] E‖θ(m)t − θ̃(m)‖2.
(12)
Assume that ct ≤ ĉ for some universal constant ĉ > 0 (we will formally prove it later). Then, we sum the above inequality over one epoch and obtain that [1 2 ηθ − ĉ ηθ βt − 9 (L 2 η2θ + ĉη 2 θ )]M−1∑ t=0 E‖∇J(θ(m)t )‖2
≤ E[Rm0 ]− E[RmM ] + [ ηθ + 2ĉηθ + 9 (L 2 η2θ + ĉη 2 θ )] C1 + 9L1 (L 2 η2θ + ĉη 2 θ ) ME‖ω̃(m) − ω∗(θ̃(m))‖2
+ [ 6L1 (L 2 η2θ + ĉη 2 θ ) + ηθL1 + ηθL1ĉ ]M−1∑ t=0 E‖ω(m)t − ω∗(θ (m) t )‖2
− [ 6L1 (L 2 η2θ + ĉη 2 θ ) + ηθL1 + ηθL1ĉ ] · 4 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]M−1∑ t=0 E‖θ(m)t − θ̃(m)‖2.
(13)
By Lemma D.7, we have that
M−1∑ t=0 E‖ω(m)t − ω∗(θ (m) t )‖2
≤ 4 λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 4
λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 + ( 9 λC + 2L23 ) η2θ η2ω 36 λC M−1∑ t=0 E‖∇J(θ(m)t )‖2
+ 4
λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]M−1∑ t=0 E‖θ(m)t − θ̃(m)‖2
+ 8
λC (C3 + C4).
For simplicity, we define D := 6L1 ( L 2 + ĉ ) + L1 + L1ĉ. Substituting the above bound into the previous inequality and simplifying, we obtain that [1 2 ηθ − ĉ ηθ βt − 9 (L 2 η2θ + ĉη 2 θ )]M−1∑ t=0 E‖∇J(θ(m)t )‖2
≤ ERm0 − ERmM + [ ηθ + 2ĉηθ + 9 (L 2 η2θ + ĉη 2 θ )] C1 + 9L1 (L 2 η2θ + ĉη 2 θ ) ME‖ω̃(m) − ω∗(θ̃(m))‖2
+Dηθ
[ 4
λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 4
λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 + ( 9 λC + 2L23 ) η2θ η2ω 36 λC M−1∑ t=0 E‖∇J(θ(m)t )‖2 + 8 λC (C3 + C4).
]
One can see that the above bound is independent of ∑M−1 t=0 E‖θ (m+1) t − θ̃(m)‖2, and this is what
we desire. After simplification, the above inequality further implies that
[1 2 ηθ − ĉ ηθ βt − 9 (L 2 η2θ + ĉη 2 θ ) −D ( 9 λC + 2L23 ) 36 λC η3θ η2ω ]M−1∑ t=0 E‖∇J(θ(m)t )‖2
≤E[Rm0 ]− E[RmM ] + [ ηθ + 2ĉηθ + 9 (L 2 η2θ + ĉη 2 θ )] C1 + 8 λC (C3 + C4)Dηθ +Dηθ [ 4 λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 ] + [ 9L1 (L 2 η2θ + ĉη 2 θ ) M +Dηθ [ 4
λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]]] E‖ω̃(m) − ω∗(θ̃(m))‖2.
(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 {ct} is a small constant. We first present the following fundamental simple lemma, and the proof is omitted.
Lemma B.1. Let {ci}i=0,...,M be a finite sequence with cM = 0 and satisfies the following relation for certain a > 1:
ct ≤ a · ct+1 + b.
Then, {ci}i=0,...,M is a deceasing sequence and
c0 ≤ ab · aM − 1 a− 1 .
Next, we derive the upper bound ĉ of ct. Set βt = 1 for all t. Then we have that
ct ≤ ct+1(ηθ + 1 + 2ηθ) + 9L1 (L
2 η2θ + ct+1η 2 θ ) + [ 6L1 (L 2 η2θ + ct+1η 2 θ ) + ηθL1 + ηθL1ct+1 ] · 4 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω
] := a · ct+1 + b
where a = 1 + (3 + 16L1)ηθ
and
b = 15
2 L1Lη
2 θ + L1ηθ ·
4
λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ] .
Note that here we require
4
λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ] ≤ 1 (15)
and
max{ηω, ηθ} ≤ 1. (16)
Moreover, let
(3 + 16L1)ηθ ≤ 1
M . (17)
Based on the above conditions, we obtain that c0 ≤ [15
2 L1Lηθ + 4L1 λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]] · 4 + 16L1 3 + 16L1 · [ (1 + (3 + 16L1)ηθ) M − 1 ]
≤ [15
2 L1Lηθ + 4L1 λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]] · 4 + 16L1 3 + 16L1 · (e− 1).
Lastly, we choose[15 2 L1Lηθ + 4L1 λC [ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]] · 4 + 16L1 3 + 16L1 · (e− 1) ≤ 1 8 . (18)
Therefore c0 ≤ 18 . Since {ct}t is decreasing, we obtain that ĉ = 1 8 . Now, substituting βt = 1 and ĉ = 18 into the coefficient of the term ∑M−1 t=0 E‖∇J(θ (m) t )‖2 in eq. (14), the coefficient reduces to the following, and we choose an appropriate (ηθ, ηω) such that the coefficient is greater than 14ηθ.
3 8 ηθ − 9 (L 2 η2θ + ĉη 2 θ ) −D ( 9 λC + 2L23 ) 36 λC η3θ η2ω ≥ 1 4 ηθ. (19)
Deriving the final bound: Exploiting the above conditions on the learning rates, eq. (14) further implies that
1 4 ηθ M−1∑ t=0 E‖∇J(θ(m)t )‖2
≤E[J(θ̃(m))]− E[J(θ̃(m+1))] + [ ηθ + 2ĉηθ + 9 (L 2 η2θ + ĉη 2 θ )] C1 + 8 λC (C3 + C4)Dηθ +Dηθ [ 4 λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 ] + [ 9L1 (L 2 η2θ + ĉη 2 θ ) M +Dηθ [ 4
λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]]] E‖ω̃(m) − ω∗(θ̃(m))‖2.
(20)
On the other hand, by Lemma D.8 we have that
E‖ω̃(m) − ω∗(θ̃(m))‖2 ≤ (1− 1 2 λCηω) mME‖ω̃(0) − ω∗(θ̃(0))‖2
+ 4
λC
( C3 + C4 ) 1 M + 4 λC H2ηω + 2 λC ( 2L23G 2 + 9 λC G2 ) η2θ η2ω .
Substituting the above bound into eq. (20) and summing over m, we obtain that
1 4 ηθ 1 TM T∑ m=1 M−1∑ t=0 E‖∇J(θ(m)t )‖2
≤ 1 TM E[J(θ̃(0))]
+ 1
M
{[ ηθ + 2ĉηθ + 9 (L 2 η2θ + ĉη 2 θ )] C1 + 8 λC (C3 + C4)Dηθ +Dηθ [ 4 λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 ]} + 1
TM
[ 9L1 (L 2 η2θ + ĉη 2 θ ) M
+Dηθ [ 4 λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]]]] · E‖ω̃(0) − ω∗(θ̃(0))‖2 · 1 1− (1− 12λCηω)M
+ 1
M
[ 9L1 (L 2 η2θ + ĉη 2 θ ) M +Dηθ [ 4 λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]]] · [ 4 λC ( C3 + C4 ) 1 M + 4 λC H2ηω + 2 λC ( 2L23G 2 + 9 λC G2 ) η2θ η2ω ]] .
Rearranging the above inequality, we obtain the following final bound, where ξ, ζ are random indexes that are sampled from {0, ...,M − 1} and {1, ..., T} uniformly at random, respectively.
E‖∇J(θ(ζ)ξ )‖ 2
≤ 1 ηθTM · 4E[J(θ̃(0))]
+ 4
M
{[ 1 + 2ĉ+ 9 (L 2 ηθ + ĉηθ )] C1 + 8 λC (C3 + C4)D +D [ 4 λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 ]} + 1
TM
[ 9L1 (L 2 ηθ + ĉηθ ) M +D [ 4
λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω
]]]]
· E‖ω̃(0) − ω∗(θ̃(0))‖2 · 1 1− (1− 12λCηω)M
+ [ 9L1 (L 2 ηθ + ĉηθ ) +D [ 4
λC [ 1 ηωM + [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω
]]]
· [ 4 λC ( C3 + C4 ) 1 M + 4 λC H2ηω + 2 λC ( 2L23G 2 + 9 λC G2 ) η2θ η2ω ]] .
Next, we simplify the above inequality into an asymptotic form. Note that the first term is in the order ofO( 1ηθTM ). The second term is of orderO( 1 M ). The third term is of orderO( 1 ηωTM + 1T (ηω+ η2θ η2ω )), and the last term is the product of a term of order O( η 2 θ
η2ω + ηω + 1 ηωM ) and another term of order
O( 1M + η2θ η2ω +ηω), which leads to the overall orderO(( η 2 θ η2ω +ηω) 2+ 1M ). Combining these asymptotic orders together, we obtain the following asymptotic convergence rate result.
E‖∇J(θ(ζ)ξ )‖ 2 = O ( 1 ηθTM + ( η2θ η2ω + ηω )2 + 1 M + 1 T ( ηω + η2θ η2ω )) .

heading: C PROOF OF COROLLARY 4.6
text: Regarding the convergence rate result of Theorem 4.5, we choose the optimized learning rates such that ηθ = O(η3/2ω ), and we obtain that
E‖∇J(θ(ζ)ξ )‖ 2 = O ( 1 ηθTM + η2ω + 1 M + ηω T ) .
Then, we set ηθ = O( 1M ) such that eq. (17) is satisfied, and moreover ηω = O( 1 M2/3 ). Under 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
E‖∇J(θ(ζ)ξ )‖ 2 = O ( 1 T + 1 M ) . (21)
By choosing T,M = O( −1), we conclude that the sample complexity for achieving E‖∇J(θ(ζ)ξ )‖2 ≤ is in the order of TM = O( −2).

heading: D TECHNICAL LEMMAS
text: In this section, we present all the technical lemmas that are used in the proof of the main theorem.
Bounding E‖g(m)t ‖2 and E‖h (m) t ‖2: Lemma D.1. Under the same assumptions as those of Theorem 4.5, the square norm of the one-step update of θ(m)t in Algorithm 1 is bounded as
E‖g(m)t ‖2 ≤ 6L21E‖ω (m) t − ω∗(θ (m) t )‖2 + 9L21E‖ω̃(m) − ω∗(θ̃(m))‖2 + 9L22E‖θ (m) t − θ̃(m)‖2
+ 1
M 9C1 + 9E‖∇J(θ(m)t )‖2
where the constant C1 is specified in Lemma D.3.
Proof. For convenience, define
T (m) t := G (m) t (θ (m) t , ω (m) t )−G (m) t (θ̃ (m), ω̃(m)),
and S
(m) t := G (m) t (θ (m) t , ω ∗(θ (m) t ))−G (m) t (θ̃ (m), ω∗(θ̃(m))).
Then, we obtain that
‖g(m)t ‖2 = ‖G (m) t (θ (m) t , ω (m) t )−G (m) t (θ̃ (m), ω̃(m)) + G̃(m)‖2
= ‖T (m)t + G̃(m) − G̃(m)(θ̃(m), ω∗(θ̃(m))) + G̃(m)(θ̃(m), ω∗(θ̃(m)))
−S (m)t + S (m) t ‖2
≤ 3‖T (m)t −S (m) t ‖2 + 3‖G̃(m) − G̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
+ 3‖S (m)t + G̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
≤ 6L21‖ω (m) t − ω∗(θ (m) t )‖2 + 9L21‖ω̃(m) − ω∗(θ̃(m))‖2
+ 3‖S (m)t + G̃(m)(θ̃(m), ω∗(θ̃(m)))‖2,
where G̃(m)(θ̃(m), ω∗(θ̃(m))) is obtained by substituting the arguments θ̃(m), ω∗(θ̃(m)) into the definition in eq. (4). Moreover, we have that
‖S (m)t + G̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
= ‖S (m)t + G̃(m)(θ̃(m), ω∗(θ̃(m)))−∇J(θ (m) t ) +∇J(θ (m) t )‖2
≤ 3‖S (m)t − Em,tS (m) t ‖2 + 3‖G̃(m)(θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )‖2
+ 3‖∇J(θ(m)t )‖2,
which further implies that
E‖S (m)t + G̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
≤ 3E‖S (m)t ‖2 + 3E‖G̃(m)(θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )‖2 + 3E‖∇J(θ (m) t )‖2
≤ 3L22E‖θ (m) t − θ̃(m)‖2 +
1
M · 3C1 + 3E‖∇J(θ(m)t )‖2.
Combining all the above bounds, we finally obtain that
E‖g(m)t ‖2 ≤ 6L21E‖ω (m) t − ω∗(θ (m) t )‖2 + 9L21E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 9L22E‖θ (m) t − θ̃(m)‖2 +
1
M · 9C1 + 9E‖∇J(θ(m)t )‖2.
Lemma D.2. Under the same assumptions as those of Theorem 4.5, we have that
‖h(m)t ‖2 ≤ 6L24‖ω (m) t − ω∗(θ (m) t )‖2 + 9L24‖ω̃(m) − ω∗(θ̃(m))‖2 + 6L25‖θ (m) t − θ̃(m)‖2 + 6C2 M .
Proof. For convenience, define
V (m) t := H (m) t (θ (m) t , ω (m) t )−H (m) t (θ̃ (m), ω̃(m)),
and U
(m) t := H (m) t (θ (m) t , ω ∗(θ (m) t ))−H (m) t (θ̃ (m), ω∗(θ̃(m))).
Then, we obtain that
‖h(m)t ‖2 = ‖H (m) t (θ (m) t , ω (m) t )−H (m) t (θ̃ (m), ω̃(m)) + H̃(m)‖2
= ‖V (m)t + H̃(m) − H̃(m)(θ̃(m), ω∗(θ̃(m))) + H̃(m)(θ̃(m), ω∗(θ̃(m)))−U (m) t + U (m) t ‖2
≤ 3‖V (m)t −U (m) t ‖2 + 3‖H̃(m) − H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
+ 3‖U (m)t + H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
≤ 6L24‖ω (m) t − ω∗(θ (m) t )‖2 + 9L24‖ω̃(m) − ω∗(θ̃(m))‖2
+ 3‖U (m)t + H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2.
Moreover, note that
‖U (m)t + H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2 ≤ 2‖U (m) t ‖2 + 2‖H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2
≤ 2L25‖θ (m) t − θ̃(m)‖2 + 2C2 M .
Combining the above bounds, we finally obtain that
‖h(m)t ‖2 ≤ 6L24‖ω (m) t − ω∗(θ (m) t )‖2 + 9L24‖ω̃(m) − ω∗(θ̃(m))‖2
+ 6L25‖θ (m) t − θ̃(m)‖2 + 6C2 M .
Bounding pseudo-gradient variance: Lemma D.3. Under the same assumptions as those of Theorem 4.5, we have that
E‖G̃(m)(θ(m)t , ω∗(θ (m) t ))−∇J(θ (m) t )‖2 ≤ C1 M .
Proof. Note that the variance can be expanded as
E‖G̃(m)(θ(m)t , ω∗(θ (m) t ))−∇J(θ (m) t )‖2
= 1 M2 E [M−1∑ s=0 ‖G(m)s (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )‖2
+ ∑ i 6=j 〈G(m)i (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t ), G (m) j (θ (m) t , ω ∗(θ (m) t ))−∇J(θ (m) t )〉 ] ≤ 1 M2 [M−1∑ s=0 (G+ C∇J) 2 + ∑ i 6=j Λρ|i−j|(G+ C∇J) 2 ]
≤ 1 M (1 + 2Λ ρ 1− ρ )(G+ C∇J) 2.
Then, we define the constant C1 := (1 + 2Λ ρ1−ρ )(G+ C∇J) 2.
Lemma D.4. Under the same assumptions as those of Theorem 4.5, we have that
E‖H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2 ≤ C2 M .
Proof. Note that this second moment term can be expanded as
E‖H̃(m)(θ̃(m), ω∗(θ̃(m)))‖2 = 1 M2 M−1∑ i=0 E‖H(m)i (θ̃ (m), ω∗(θ̃(m)))‖
+ 1
M2 ∑ i 6=j E〈H(m)i (θ̃ (m), ω∗(θ̃(m))), H (m) j (θ̃ (m), ω∗(θ̃(m)))〉
≤ H 2
M +
1
M2 H2Λ ∑ i 6=j ρ|i−j|
≤ H2(1 + Λ ρ 1− ρ ) 1 M .
Lastly, we define the constant C2 := H2(1 + Λ ρ1−ρ ).
Bounding Markovian Noise: Lemma D.5. Let the same assumptions as those of Theorem 4.5 hold and define
ς (m) t := 〈ω (m) t − ω∗(θ (m) t ),
( φ
(m) t (φ (m) t )
> − C )( ω
(m) t − ω∗(θ (m) t )
) 〉.
Then, it holds that
E[ς(m)t ] ≤ 1
8 λC‖ω(m)t − ω∗(θ (m) t )‖2 + C3 M ,
where C3 = 8R 2 λC (1 + ρΛ1−ρ ).
Proof. By definition of ς(m)t , we obtain that
E〈ω(m)t − ω∗(θ (m) t ),
( φ
(m) t (φ (m) t )
> − C )( ω
(m) t − ω∗(θ (m) t )
) 〉
=E〈ω(m)t − ω∗(θ (m) t ),Em,t−1
( φ
(m) t (φ (m) t )
> − C )( ω
(m) t − ω∗(θ (m) t )
) 〉
≤1 2 · λC 4 E‖ω(m)t − ω∗(θ (m) t )‖2 + 1 2 · 4R
2
λCM2 E‖ M−1∑ i=0 ( φ (m) i (φ (m) i ) > − C ) ‖2.
For the last term, note that
E‖ M−1∑ i=0 ( φ (m) i (φ (m) i ) > − C ) ‖2
= E M−1∑ i=0 ‖φ(m)i (φ (m) i ) > − C‖2 + E ∑ i 6=j 〈φ(m)i (φ (m) i ) > − C, φ(m)j (φ (m) j ) > − C〉
≤ 4M + 4 ∑ i 6=j Λρ|i−j|
≤ 4M + 4M ρΛ 1− ρ .
Combining the above bounds, we finally obtain that
E〈ω(m)t − ω∗(θ (m) t ),
( φ
(m) t (φ (m) t )
> − C )( ω
(m) t − ω∗(θ (m) t )
) 〉
≤λC 8 E‖ω(m)t − ω∗(θ (m) t )‖2 +
8R2
λC (1 +
ρΛ
1− ρ )
1
M .
We define C3 := 8R 2 λC (1 + ρΛ1−ρ ).
Lemma D.6. Let the same assumptions as those of Theorem 4.5 hold and define
κ(m)t := 〈ω (m) t − ω∗(θ (m) t ),
[ (φ
(m) t ) >ω∗(θ (m) t )− δ (m) t+1(θ (m) t )
] φ
(m) t 〉.
Then, we obtain that
Eκ(m)t ≤ 1
8 λC‖ω(m)t − ω∗(θ (m) t )‖2 + C4 M .
Proof. Similar to the proof of Lemma D.6, we have that
E〈ω(m)t − ω∗(θ (m) t ),
[ (φ
(m) t ) >ω∗(θ (m) t )− δ (m) t+1(θ (m) t )
] φ
(m) t 〉
≤1 2 · λC 4 E‖ω(m)t − ω∗(θ (m) t )‖2
+ 1 2 · 4 λCM2 E‖ M−1∑ i=0 ([ (φ (m) i ) >ω∗(θ (m) t )− δ (m) i+1 (θ (m) t ) ] φ (m) i ) ‖2.
For the last term, we can bound it as
E‖ M−1∑ i=0 ([ (φ (m) i ) >ω∗(θ (m) t )− δ (m) i+1 (θ (m) t ) ] φ (m) i ) ‖2
≤(R(2 + γ) + rmax)2M + (R(2 + γ) + rmax)2 ρΛ
1− ρ M.
Combining all the above bounds, we finally obtain that
E〈ω(m)t − ω∗(θ (m) t ),
[ (φ
(m) t ) >ω∗(θ (m) t )− δ (m) t+1(θ (m) t )
] φ
(m) t 〉
≤λC 8 E‖ω(m)t − ω∗(θ (m) t )‖2 + 2 λC (R(2 + γ) + rmax) 2(1 + ρΛ 1− ρ ) 1 M .
We then define C4 := 2λC (R(2 + γ) + rmax) 2(1 + ρΛ1−ρ ).
Bounding Tracking Error:
Lemma D.7. Under the same assumptions as those of Theorem 4.5, the tracking error can be bounded as
M−1∑ t=0 E‖ω(m)t − ω∗(θ (m) t )‖2
≤ 4 λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 4
λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 + ( 9 λC + 2L23 ) η2θ η2ω 36 λC M−1∑ t=0 E‖∇J(θ(m)t )‖2
+ 4
λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]M−1∑ t=0 E‖θ(m)t − θ̃(m)‖2
+ 8
λC (C3 + C4).
Proof. Recall the one-step update at ω(m)t+1 :
ω (m) t+1 = ΠR
( ω
(m) t − ηωh (m) t
) .
Then, we obtain the following upper bound of the tracking error ‖ω(m)t+1 − ω∗(θ (m) t+1)‖2,
‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤ ‖ω (m) t − ω∗(θ (m) t )− ηωh (m) t + ω ∗(θ (m) t )− ω∗(θ (m) t+1)‖2
≤ ‖ω(m)t − ω∗(θ (m) t )‖2 − 2ηω〈ω (m) t − ω∗(θ (m) t ), h (m) t 〉
+ 2〈ω(m)t − ω∗(θ (m) t ), ω ∗(θ (m) t )− ω∗(θ (m) t+1)〉
+ 2η2ω‖h (m) t ‖2 + 2‖ω∗(θ (m) t )− ω∗(θ (m) t+1)‖2.
Substituting the bound of Lemma D.2 into the above bound, we obtain that
‖ω(m)t+1 − ω∗(θ (m) t+1)‖2
≤ ‖ω(m)t − ω∗(θ (m) t )‖2 − 2ηω〈ω (m) t − ω∗(θ (m) t ), h (m) t 〉
+ λCηω‖ω(m)t − ω∗(θ (m) t )‖2
+ ( 9 λC + 2L23 ) η2θ ηω [ 6L21E‖ω (m) t − ω∗(θ (m) t )‖2 + 9L21E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 9L22E‖θ (m) t − θ̃(m)‖2 +
1
M · 9C1 + 9E‖∇J(θ(m)t )‖2 ] + 2η2ω [ 6L24E‖ω (m) t − ω∗(θ (m) t )‖2 + 9L24E‖ω̃(m) − ω∗(θ̃(m))‖2 + 6L25E‖θ (m) t − θ̃(m)‖2 +
6C2 M
] .
Taking expectation on both sides of the above inequality and simplifying, we obtain that
E‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤ ( 1− λCηω + ( 9 λC + 2L23 ) 6L21 η2θ ηω + 12L24η 2 ω ) E‖ω(m)t − ω∗(θ (m) t )‖2
+ [( 9 λC + 2L23 ) 9L21 η2θ ηω + 18L24η 2 ω ] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ ( 9 λC + 2L23 ) η2θ ηω · 9C1 M + η2ω · 12C2 M + ( 9 λC + 2L23 ) η2θ ηω 9E‖∇J(θ(m)t )‖2
+ [ 12L25η 2 ω + ( 9 λC + 2L23 ) 9L22 η2θ ηω ] E‖θ(m)t − θ̃(m)‖2
− 2ηωEκ(m)t − 2ηωEς (m) t , (22)
where ς (m) t := 〈ω (m) t − ω∗(θ (m) t ), ( φ (m) t (φ (m) t ) > − C )( ω (m) t − ω∗(θ (m) t ) ) 〉,
and κ(m)t := 〈ω (m) t − ω∗(θ (m) t ), [ (φ (m) t ) >ω∗(θ (m) t )− δ (m) t+1(θ (m) t ) ] φ (m) t 〉.
Applying Lemma D.5, and Lemma D.6 to (22), we obtain that
E‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤
( 1− 1
2 λCηω + ( 9 λC + 2L23 ) 6L21 η2θ ηω + 12L24η 2 ω ) E‖ω(m)t − ω∗(θ (m) t )‖2
+ [( 9 λC + 2L23 ) 9L21 η2θ ηω + 18L24η 2 ω ] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ ( 9 λC + 2L23 ) η2θ ηω · 9C1 M + η2ω · 12C2 M + ( 9 λC + 2L23 ) η2θ ηω 9E‖∇J(θ(m)t )‖2
+ [ 12L25η 2 ω + ( 9 λC + 2L23 ) 9L22 η2θ ηω ] E‖θ(m)t − θ̃(m)‖2
+ 2ηω(C3 + C4) 1
M . (23)
Telescoping the above inequality over one epoch, we obtain that(1 2 λCηω − ( 9 λC + 2L23 ) 6L21 η2θ ηω − 12L24η2ω )M−1∑ t=0 E‖ω(m)t − ω∗(θ (m) t )‖2
≤ E‖ω(m)M − ω ∗(θ (m) M )‖ 2 +M [( 9 λC + 2L23 ) 9L21 η2θ ηω + 18L24η 2 ω ] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ ( 9 λC + 2L23 ) η2θ ηω · 9C1 + η2ω · 12C2 + ( 9 λC + 2L23 ) η2θ ηω 9 M−1∑ t=0 E‖∇J(θ(m)t )‖2
+ [ 12L25η 2 ω + ( 9 λC + 2L23 ) 9L22 η2θ ηω ]M−1∑ t=0 E‖θ(m)t − θ̃(m)‖2
+ 2ηω(C3 + C4).
Choosing an appropriate (ηθ, ηω) such that
1 2 λCηω − ( 9 λC + 2L23 ) 6L21 η2θ ηω − 12L24η2ω ≥ 1 4 λCηω, (24)
and we finally obtain that
M−1∑ t=0 E‖ω(m)t − ω∗(θ (m) t )‖2
≤ 4 λC [ 1 ηω +M [( 9 λC + 2L23 ) 9L21 η2θ η2ω + 18L24ηω ]] E‖ω̃(m) − ω∗(θ̃(m))‖2
+ 4
λC ( 9 λC + 2L23 ) η2θ η2ω · 9C1 + 4 λC ηω · 12C2 + ( 9 λC + 2L23 ) η2θ η2ω 36 λC M−1∑ t=0 E‖∇J(θ(m)t )‖2
+ 4
λC
[ 12L25ηω + ( 9 λC + 2L23 ) 9L22 η2θ η2ω ]M−1∑ t=0 E‖θ(m)t − θ̃(m)‖2
+ 8
λC (C3 + C4).
Lemma D.8. Under the same assumptions as those of Theorem 4.5, the tracking error can be bounded as
E‖ω̃(m) − ω∗(θ̃(m))‖2 ≤ (1− 1 2 λCηω) mME‖ω̃(0) − ω∗(θ̃(0))‖2
+ 4
λC
( C3 + C4 ) 1 M + 4 λC H2ηω + 2 λC ( 2L23G 2 + 9 λC G2 ) η2θ η2ω .
Proof. Recall the one-step update at ω(m)t+1 :
ω (m) t+1 = ΠR
( ω
(m) t − ηωh (m) t
) .
Then, we obtain the following upper bound of the tracking error ‖ω(m)t − ω∗(θ (m) t )‖2.
‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤ ‖ω (m) t − ω∗(θ (m) t )− ηωh (m) t + ω ∗(θ (m) t )− ω∗(θ (m) t+1)‖2
≤ ‖ω(m)t − ω∗(θ (m) t )‖2 − 2ηω〈ω (m) t − ω∗(θ (m) t ), h (m) t 〉
+ 2〈ω(m)t − ω∗(θ (m) t ), ω ∗(θ (m) t )− ω∗(θ (m) t+1)〉
+ 2η2ωH 2 + 2‖ω∗(θ(m)t )− ω∗(θ (m) t+1)‖2.
Then above inequality can be further bounded as
‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤ ‖ω (m) t − ω∗(θ (m) t )‖2 − 2ηω〈ω (m) t − ω∗(θ (m) t ), h (m) t 〉
+ λCηω‖ω(m)t − ω∗(θ (m) t )‖2
+ ( 9 λC + 2L23 ) η2θ ηω G2 + 2η2ωH 2.
Taking conditional expectation on both sides of the above inequality, we obtain that
Em,0‖ω(m)t+1 − ω∗(θ (m) t+1)‖2
≤ Em,0‖ω(m)t − ω∗(θ (m) t )‖2 − 2ηωEm,0〈ω (m) t − ω∗(θ (m) t ), H (m) t (θ (m) t , ω (m) t )〉
− 2ηωEm,0〈ω(m)t − ω∗(θ (m) t ),−H (m) t (θ̃ (m), ω̃(m)) + H̃(m)〉
+ λCηω‖ω(m)t − ω∗(θ (m) t )‖2 + 9η2θ λCηω G2 + 2H2η2ω + 2L 2 3G 2η2θ
= Em,0‖ω(m)t − ω∗(θ (m) t )‖2 − 2ηωEm,0〈ω (m) t − ω∗(θ (m) t ), H (m) t (θ (m) t , ω (m) t )〉
+ λCηω‖ω(m)t − ω∗(θ (m) t )‖2
+ 2H2η2ω + ( 2L23G 2 + 9 λC G2 ) η2θ ηω
(25)
To further bound the inequality above, we first consider the following explicit form of the pseudogradient term:
H (m) t (θ, ω) =
[ (φ
(m) t ) >ω − δ(m)t+1(θ) ] φ (m) t
= φ (m) t (φ (m) t ) >(ω − ω∗(θ))+ [(φ(m)t )>ω∗(θ(m)t )− δ(m)t+1(θ)]φ(m)t = ( φ
(m) t (φ (m) t )
> − C )( ω − ω∗(θ) ) + C ( ω − ω∗(θ) ) + [ (φ
(m) t ) >ω∗(θ)− δ(m)t+1(θ) ] φ (m) t . (26)
By Assumption 4.3, we have
−2ηωEm,0〈ω(m)t − ω∗(θ (m) t ), C
( ω
(m) t − ω∗(θ (m) t ) ) 〉 ≤ −2ηλC‖ω(m)t − ω∗(θ (m) t )‖2. (27)
Substituting eq. (27) and eq. (26) into eq. (25) yields that
E‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤ (1− λCηω)E‖ω (m) t − ω∗(θ (m) t )‖2 − 2ηωEκ (m) t − 2ηωEς (m) t
+ 2H2η2ω + ( 2L23G 2 + 9 λC G2 ) η2θ ηω , (28)
where ς (m) t := 〈ω (m) t − ω∗(θ (m) t ), ( φ (m) t (φ (m) t ) > − C )( ω (m) t − ω∗(θ (m) t ) ) 〉,
and κ(m)t := 〈ω (m) t − ω∗(θ (m) t ), [ (φ (m) t ) >ω∗(θ (m) t )− δ (m) t+1(θ (m) t ) ] φ (m) t 〉.
Applying Lemma D.5, and Lemma D.6 to the above inequality, we obtain that
E‖ω(m)t+1 − ω∗(θ (m) t+1)‖2 ≤ (1−
1 2 λCηω)E‖ω(m)t − ω∗(θ (m) t )‖2
+ 2ηω ( C3 + C4 ) 1 M
+ 2H2η2ω + ( 2L23G 2 + 9 λC G2 ) η2θ ηω .
Telescoping the above inequality over one epoch, we obtain that
E‖ω(m)M − ω ∗(θ (m) M )‖ 2 ≤ (1− 1 2 λCηω) ME‖ω(m)0 − ω∗(θ (m) 0 )‖2
+ 2ηω ( C3 + C4 ) 1 M · 1− (1− 12λCηω) M
1 2λCηω
+ 2H2η2ω · 1− (1− 12λCηω) M
1 2λCηω
+ ( 2L23G 2 + 9 λC G2 ) η2θ ηω · 1− (1− 12λCηω) M
1 2λCηω
.
By definition, ω̃(m) = ω(m)M and θ̃ (m) = θ (m) M , and the initial parameter for the current inner loop is chosen as the reference parameter, ω(m)0 = ω̃ (m) and θ(m)0 = θ̃ (m). Then we have
E‖ω̃(m) − ω∗(θ̃(m))‖2 ≤ (1− 1 2 λCηω) ME‖ω̃(m) − ω∗(θ̃(m))‖2
+ 2ηω ( C3 + C4 ) 1 M · 1− (1− 12λCηω) M
1 2λCηω
+ 2H2η2ω · 1− (1− 12λCηω) M
1 2λCηω
+ ( 2L23G 2 + 9 λC G2 ) η2θ ηω · 1− (1− 12λCηω) M
1 2λCηω
.
Then, we unroll the inequality above and yield that
E‖ω̃(m) − ω∗(θ̃(m))‖2 ≤ (1− 1 2 λCηω) mME‖ω̃(0) − ω∗(θ̃(0))‖2
+ 4
λC
( C3 + C4 ) 1 M + 4 λC H2ηω + 2 λC ( 2L23G 2 + 9 λC G2 ) η2θ η2ω .

heading: E OTHER SUPPORTING LEMMAS
text: Constant Bounds: Lemma E.1. Within the set {θ : ‖θ‖ ≤ R}, there exists a constant C∇J such that
sup θ ‖∇J(θ)‖ ≤ C∇J . (29)
Proof. By Lemma E.9, ∇J(θ) is smooth. Hence, by the compactness of {θ : ‖θ‖ ≤ R}, we conclude that ‖∇J(θ)‖ is bounded by a certain constant C∇J .
Lemma E.2. Let G := rmax + (1 + γ)R + γ(|A|Rk1 + 1)R be a constant unrelated to m and t. Then ‖G(m)t ‖ ≤ G for all m and t.
Proof. By its definition, we obtain that ‖G(m)t ‖ = ‖ ( − δt+1(θt)φt + γ(ω>t φt)φ̂t+1(θt) ) ‖
≤ ‖ ( − δt+1(θt)‖‖φt‖+ γ‖(ω>t φt)‖‖φ̂t+1(θt) ) ‖
≤ rmax + (1 + γ)R+ γ(|A|Rk1 + 1)R.
Lemma E.3. Let H = (2 + γ)R + rmax be a constant unrelated to m and t. Then ‖H(m)t ‖ ≤ H for all m and t.
Proof. The result follows from the definition: ‖H(m)t ‖ = ‖ [ φTt ωt − δt+1(θt) ] φt‖
≤ (2 + γ)R+ rmax.
Lipschitz Continuity:
Lemma E.4. The mapping ω 7→ G(m)t+1(θ, ω) is L1-Lipschitz in ω for all θ.
Proof. See Lemma 3 of Wang & Zou (2020).
Lemma E.5. The mapping θ 7→ G(m)t+1(θ, ω∗(θ)) is L2-Lipschitz in θ.
Proof. See Lemma 3 of Wang & Zou (2020).
Lemma E.6. The mapping ω∗(·) is L3-Lipschitz.
Proof. See eq.(56) of Wang & Zou (2020).
Lemma E.7. The mapping ω 7→ H(m)t+1 (θ, ω) is L4-Lipschitz.
Proof. It follows that
‖H(m)t+1 (θ, ω2)−H (m) t+1 (θ, ω2)‖ = ‖
( δ
(m) t+1(θ)−
[ φ
(m) t ]T ω1 ) φ (m) t − ( δ (m) t+1(θ)− [ φ (m) t ]T ω2 ) φ (m) t ‖
≤ ‖φ(m)t ‖2‖ω1 − ω2‖ ≤ ‖ω1 − ω2‖.
Hence, L4 = 1.
Lemma E.8. The mapping θ 7→ H(m)t+1 (θ, ω∗(θ)) is L5-Lipschitz.
Proof. By definition, we have
‖H(m)t+1 (θ1, ω∗(θ1))−H (m) t+1 (θ2, ω ∗(θ2))‖ = ‖ ( δ
(m) t+1(θ1)−
[ φ
(m) t ]T ω∗(θ1) ) φ (m) t − ( δ (m) t+1(θ2)− [ φ (m) t ]T ω∗(θ2) ) φ (m) t ‖
≤ ‖δ(m)t+1(θ1)− δ (m) t+1(θ2)‖+ ‖ω∗(θ1)− ω∗(θ2)‖ ≤ ( (γ|A|k1R+ 1) + 1 + L3 ) ‖θ1 − θ2‖.
Hence, L5 = (γ|A|k1R+ 1) + 1 + L3.
Bounding Lyapunov function:
Lemma E.9 (L-smoothness of J). For any θ1 and θ2, it holds that
|J(θ1)− J(θ2)− 〈∇J(θ2), θ1 − θ2〉| ≤ L
2 ‖θ1 − θ2‖2.
Proof. See Lemma 2 of Wang & Zou (2020).
Lemma E.10. It holds that
‖θ(m)t+1 − θ̃(m)‖2 = η2θ‖g (m) t ‖2 + ‖θ (m) t − θ̃(m)‖2 − 2ηθζ (m) t
+ ηθ [ 1 βt ‖∇J(θ(m)t )‖2 + βt‖θ (m) t − θ̃(m)‖2 ] , (30)
where ζ(m)t := 〈g (m) t −∇J(θ (m) t ), θ (m) t − θ̃(m)〉.
Proof. Note that
‖θ(m)t+1 − θ̃(m)‖2 = ‖θ (m) t+1 − θ (m) t ‖2 + ‖θ (m) t − θ̃(m)‖2 + 2〈θ (m) t+1 − θ (m) t , θ (m) t − θ̃(m)〉
= η2θ‖g (m) t ‖2 + ‖θ (m) t − θ̃(m)‖2 − 2ηθ〈g (m) t , θ (m) t − θ̃(m)〉
= η2θ‖g (m) t ‖2 + ‖θ (m) t − θ̃(m)‖2 − 2ηθ〈g (m) t −∇J(θ (m) t ), θ (m) t − θ̃(m)〉
− 2ηθ〈∇J(θ(m)t ), θ (m) t − θ̃(m)〉
= η2θ‖g (m) t ‖2 + ‖θ (m) t − θ̃(m)‖2 − 2ηθ〈g (m) t −∇J(θ (m) t ), θ (m) t − θ̃(m)〉
+ ηθ [ 1 βt ‖∇J(θ(m)t )‖2 + βt‖θ (m) t − θ̃(m)‖2 ] .

heading: F DETAILS OF EXPERIMENTS
text: Garnet problem: The Garnet problem Archibald et al. (1995) is specified as G(nS , nA, b, d), where nS and nA denote the cardinality of the state and action spaces, respectively, b is referred to as the branching factor–the number of states that have strictly positive probability to be visited after an action is taken, and d denotes the dimension of the features. In our experiment, we set nS = 5, nA = 3, b = 2, d = 4 and generate the features Φ ∈ RnS×d 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 ∈ RnS×nA×nS via the uniform distribution on [0, 1] (with proper normalization). We set the behavior policy as the uniform policy, i.e., πb(a|s) = n−1A for any s and a. The discount factor is set to be γ = 0.95. As the transition kernel and the features are known, we compute ‖∇J(θ)‖2 to evaluate the performance of all the algorithms. We set the default learning rates as ηθ = 0.02 and ηω = 0.01 for both VR-Greedy-GQ and Greedy-GQ algorithm. For VR-Greedy-GQ, we set the default batch size as M = 3000.
Frozen Lake: We generate a 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 is generated via the uniform distribution on [0, 1] with proper normalization and the behavior policy is the uniform policy. We set the learning rates as ηθ = 0.2 and ηω = 0.1 for both algorithms and set the batch size as M = 3000 for the VR-Greedy-GQ. 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 θt is updated to θt+1, we estimate the corresponding reward by sampling a Markov decision process {s1, a1, s2, a2, . . . , sN , aN , sN+1} using πθ. Then we estimate the expected reward using
r̂t = 1
N N∑ i=1 r(si, ai, si+1).
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 t r̂t.
In the experiments, we set N = 100 when estimating the expected reward.

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

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