Asynchronous Advantage Actor Critic: Non-asymptotic Analysis and Linear Speedup
Authors: Han Shen
Kaiqing Zhang
Mingyi Hong
Tianyi Chen
Venue:  (2021)

Abstract: Asynchronous and parallel implementation of standard reinforcement learning (RL) algorithms is a key enabler of the tremendous success of modern RL. 
Among many asynchronous RL algorithms, arguably the most popular and effective one is the asynchronous advantage actor-critic (A3C) algorithm.  
Although A3C is becoming the workhorse of RL, its theoretical properties are still not well-understood, including the non-asymptotic analysis and the performance gain of parallelism (a.k.a. speedup). 
This paper revisits the A3C algorithm with TD(0) for the critic update, termed A3C-TD(0), with provable convergence guarantees. 
With linear value function approximation for the TD update, the convergence of A3C-TD(0) is established under both i.i.d. and Markovian sampling. Under i.i.d. sampling, A3C-TD(0) obtains sample complexity of $\mathcal{O}(\epsilon^{-2.5}/N)$ per worker to achieve $\epsilon$ accuracy, where $N$ is the number of workers.  Compared to the best-known sample complexity of $\mathcal{O}(\epsilon^{-2.5})$ for two-timescale AC, A3C-TD(0) achieves \emph{linear speedup}, which justifies the advantage of parallelism and asynchrony in AC algorithms theoretically for the first time.
Numerical tests on synthetically generated instances and OpenAI Gym environments have been provided to verify our theoretical analysis. 

Under review as a conference paper at ICLR 2021
ASYNCHRONOUS ADVANTAGE ACTOR CRITIC: ANALYSIS AND LINEAR SPEEDUP
Anonymous authors Paper under double-bling review
ABSTRACT
Asynchronous and parallel implementation of standard reinforcement learning (RL) algorithms is a key enabler of the tremendous success of modern RL. Among many asynchronous RL algorithms, arguably the most popular and effective one is the asynchronous advantage actor-critic (A3C) algorithm. Although A3C is becom- ing the workhorse of RL, its theoretical properties are still not well-understood, including the non-asymptotic analysis and the performance gain of parallelism (a.k.a. speedup). This paper revisits the A3C algorithm with TD(O) for the critic update, termed A3C-TD(O), with provable convergence guarantees. With linear value function approximation for the TD update, the convergence of A3C-TD(O) is established under both i.i.d. and Markovian sampling. Under i.i.d. sampling, A3C- TD(0) obtains sample complexity of ( 2.5 /N) per worker to achieve c accuracy, where N is the number of workers. Compared to the best-known sample complex- ity of (E -2.5) for two-timescale AC, A3C-TD(O) achieves linear speedup, which justifies the advantage of parallelism and asynchrony in AC algorithms theoretically for the first time. Numerical tests on synthetically generated instances and OpenAl Gym environments have been provided to verify theoretical analysis.
INTRODUCTION
Reinforcement learning (RL) has achieved impressive performance in many domains such as roboties 222 and video games (3] However, these empirical successes are often at the expense of significant computation. To unlock high computation capabilities, the state-of-the the art RL approaches rely
sampling data from massive parallel simulators on multiple machines 3 4 3]. Empirically, these approaches stabilize the learning processes and reduce training time when they implemented in an asynchronous manner. One popular RL. method that often achieves the best empirical performance the asynchronous variant of the actor-critic (AC) algorithm, which referred as A3C 3
A3C builds on the original AC algorithm 6 At high level, AC simultaneously performs policy optimization (a.k.a. the actor step) using the policy gradient method (7) and policy evaluation (a.k.a. the critic step) using the temporal difference learning (TD) algorithm [8]. To ensure scalability, both actor and critic steps can combine with various function approximation techniques. To ensure stability, AC is often implemented in a two time-scale fashion, where the actor step runs in the slow timescale and the critic step runs in the fast timescale. Similar to other on-policy RL algorithms, AC uses samples generated from the target policy. Thus, data sampling is entangled with the learning procedure, which generates significant overhead. To speed up the sampling process of AC, A3C introduces multiple workers with shared policy, and each learner has its own simulator to perform data sampling. The shared policy can be then updated using samples collected from multiple learners.
Despite the tremendous empirical success achieved by A3C, to the best of our knowledge, its theoretical property is not well-understood. The following theoretical questions remain unclear: Q1) Under what assumption does A3C converge? Q2) What is its convergence rate? Q3) Can A3C obtain benefit (or speedup) using parallelism and asynchrony?
For Q3), interested in the training time linear speedup with N workers, which is the ratio between the training time using a single worker and that using workers. Since asynchronous parallelism mitigates the effect of stragglers and keeps all workers busy, the training time speedup

---

Under review as a conference paper at ICLR 2021
can be measured roughly by the sample (i.e., computational) complexity linear speedup (9. given by
sample complexity when using one worker
Speedup(N) average sample complexity per worker when using N workers
If Speedup(N) (NN, the speedup is linear, and the training time roughly reduces linearly as the number of workers increases. This paper aims to answer these questions, towards the goal of providing theoretical justification for the empirical successes of parallel and asynchronous RL.
1.1 RELATED WORKS
Analysis of actor critic algorithms. AC method was first proposed by 6 10), with asymptotic convergence guarantees provided in [6 I0 IT]. It was not until recently that the -onmasymtoiicc analyses of AC have been established. The finite-sample guarantee for the batch AC algorithm has been established in [12 1 with i.i.d. sampling. Later, in [14], the finite-sample analysis was established for the kouble-loop nested AC algorithm under the Markovian setting. An improved analysis for the Markovian setting with minibatch updates has been presented in [I5] for the nested AC method. More recently, [16 have provided the first finite-time analyses for the two-timescale AC algorithms under Markov sampling, with both Ö( 2255) sample complexity, which is the best- known sample complexity for two-timescale AC. Through the lens of bi-level optimization, [18] has also provided fimite-sample guarantees for this two-tttoee timescale Markov sampling setting, with global optimality guarantees when natural policy gradient step is used in the actor. However, none of the existing works has analyzed the effect the asynchronous and parallel updates in AC
Empirical parallel and distributed AC. In [3) the original A3C method was proposed and became the workhorse in empirical RL. Later, [99 has provided a GPU-version of A3C which significantly decreases training time. Recently, the A3C algorithm is further optimized in modern computers by [20). where a large batch variant of A3C with improved efficiency is also proposed. In (21), an importance weighted distributed AC algorithm IMPALA has been developed solve a collection of problems with one single set of parameters. Recently, a gossip- cossip-based distributed yet synchronous AC algorithm has been proposed in [. which has achieved the performance competitive to A3C.
Asynchronous stochastic optimization. For solving general optimization problems, asynchronous stochastic methods have received much attention recently. The study of asynchronous stochastic methods can be traced back to 1980s 222] With the batch size M, [23] analyzed asynchronous
SGD (asyne-SGD) for convex functions, and derived convergence rate of O(K- à M- à) if delay Ko is bounded by O OK ... This result implies linear speedup. [2 extended the analysis of 23 to smooth convex with nonsmooth regularization and derived a similar rate. Recent studies by [25] improved upper bound of Ko to O(K + M However, all these works have focused on the single-timescale SGD with single variable, which cannot capture the stochastic recursion of the AC and A3C algorithms. To best of our knowledge, non-asymptotic analysis of asynchronous two-timescale SGD has remained unaddressed, and its speedup analysis is even an uncharted territory.
1.2 THIS WORK
In this context, we revisit A3C with TD(0) for the critic update, termed A3C-TD(0). The hope is to provide non-asymptotic guarantee and linear speedup justification for this popular algorithm.
Our contributions. Compared to the existing literature on both the AC algorithms and the async- SGD, our contributions can be summarized as follows.
c1) We revisit two-timescale A3C-TD(O) and establish convergence rates with both i.i.d. and Markovian sampling. To the best of our knowledge. this is the first non-asymptotic convergence result for asynchronous parallel AC algorithms.
c2) We characterize the sample complexity of A3C-TD(0), In i.i.d. setting, A3C-TD(0) achieves sample complexity of O(c-2.5/N) N) per worker, where N the number of workers. Compared to the best-known complexity of O 2.5) for i.i.d. two-timescale AC [18), A3C-TD(0) achieves linear speedup, thanks to the parallelism and asynchrony. In the Markovian setting, if delay is bounded, the sample complexity of A3C-TD(() matches the order of the non-parallel AC algorithm [17.
2

---

Under review as a conference paper at ICLR 2021
<3) We test A3C-TD(O) on the synthetically generated environment to verify our theoretical guarantees with both i..dd and Markovian sampling. We also test A3C-TD(O) on the classic control tasks and Atari Games from OpenAI Gym. Code is available in the supplementary material.
Technical challenges. Compared to the recent convergence analysis of nonparallel two-timescale AC in [16 17 [8], several new challenges arise due to the parallelism and asynchrony.
Markovian noise coupled with asynchrony and delay. The analysis of two timescalcale AC algorithm is non-trivial because of the Markovian noise coupled with both the actor and critic steps. Different from the nonparallel AC that only involves a single Markov chain, asynchronous parallel AC introduces multiple Markov chains (one per worker) that mix different speed. This is because
given iteration, workers collect different number of samples and thus their chains mix to different degrees. As we will show later, the worker with the slowest mixing chain will determine the convergence.
Linear speedup for SGD with two coupled sequences. Parallel asyne-SGD has been shown to achieve linear speedup recently 26 Different from asyne- SGD, asynchronous AC a wootimmeceale stochastic semi- gradiegr algorithm for solving the more challenging bilevel optimization problem (see 18) ) The errors induced by asynchrony and delay are intertwined with both actor and critic updates via nested structure, which makes the sharp analysis more challenging. Our linear speedup analysis should be also distinguished from that of mini-batch asyne-SGD [27], where the speedup result of variance reduction thanks to the larger batch size generated by parallel workers.
PRELIMINARIES
2.1 MARKOV DECISION PROCESS AND POLICY GRADIENT THEOREM
RL problems are often modeled an MDP described by M = (8, A. P, r), where S is the state space, A is the action space, P(s'|s 8 a) is the probability of transitioning to s' E S given current A, and r(s, a, s') is the reward associated with the transition (s, a, s'), and 7 E [0, 1) is a discount factor. Throughout the paper, we assume the reward r is upper-bounded by a constant Tmax. A policy π. S - A(A) defined as a mapping from the state space S to the probability distribution over the action space A.
state 8 E S and action
Considering discrete time in an infinite horizon, a policy и can generate trajectory of state-action pairs (Su, ao $1, ......) with at ~ (T-(st) and S1+1 ~ P(-ss), a.). Given a policy æ, we define the state and state action value functions as
(s( E Σ rrssss, so = (s
Σ o rr(ss,, (4,))) so = s, a0
(2)
where E is taken over the trajectory (5o, 0n 81, 81, .I,.... generated under policy π. With the above
definitions, the advantage function is (s, == (= a) V=()). With denoting the initial state distribution, the discounted state visitation measure induced by policy is defined as ds)(s) = (1 - 7) 000 Ere D 7'P(s,
3 50 ~ T), and the discounted state action visitation measure is (s,a) = (1-7) Eo 'PP(s = So ~ 17, (a)s))
The goal of RL is to find policy that maximizes the expected accumulative reward J(T) = (=))] When the state and action spaces are large, finding the optimal policy æ becomes computationally intractable. To overcome the inherent difficulty of learning function, the policy gradient methods search the best performing policy over a class of parameterized policies. We parameterize the policy with parameter E Rdd and solve the optimization problem as
max J(Ø) with ((0) = E [Vz, (s)). 9ER
(3)
To maximize J00) with respect to 0, one can update 0 using the policy gradient direction given by 7
V = E (A a)voo(,)))) s.a-d'
(4)
where (s)ss = V log To (a)s). s). and dz == (1 7) Ee PP su. no (a)s) Since
computing E in 44) is expensive if not impossible, popular policy gradient- gradient-based algorithms iteratively
update 0 using stochastic estimate of (4) such as REINFORCE 28 and G(PO)MDP 29
3

---

Under review as a conference paper at ICLR 2021
2.2 ACTOR-CRITIC ALGORITHM WITH VALUE FUNCTION APPROXIMATION
Both REINFORCE and G(PO)MDP-baseee policy gradient algorithms rely on a Monte-Carlo estimate of the value function VT (s) and thus (J( by generating a trajectory per iteration. However, policy gradient methods based on Monte-Carlo estimate typically suffer from high variance and large sampling cost. An alternative way is recursively refine the estimate of V For a policy TT. known that Va (s) satisfies the Bellman equation [30], that is
VT (s) (=xxo(ll).."=(((ex. [r(s, a, s') + 7V As E.
(5)
In practice, when the state space S is prohibitively large, one cannot afford the computational and memory complexity of computing Vz, (s) and (s, a). To overcome this ours--ffddimensinnalll a popular method is to approximate the value function using function approximation techniques.
Given the state feature mapping Φ6-) S + Rd for some d' > 0, we approximate the value function linearly VA (s) (s) == (ss) Tw, where E Rd is the critic parameter.
Given a policy Ty. the task of finding the best such that V.o (s) (s) is usually addressed by TD learning [ Defining the kth transition as 2. == (8k, ak, 8k+1) and the corresponding TD-error ((sk) Wk, Twk, the parameter is updated via
as 8(T, Wk) = r(sk, aks Sk+1) + 70(sk+1)
Wk+1 IR (wk + (eg(zx. with g( wx) 8(1x) wi) Vwe Vwz (5k)
(6)
where 3% is the critic stepsize, and IR, is the projection with R being a pre-defined constant. The projection step is often used to control the norm of the gradient. In AC, it prevents the actor and critic updates from going a too large step in the 'wrong' direction; see e.g.,
66 16 17].
Using the definition of advantage function Ano (8,aa) Ee- a, can also rewrite 4 as (() = Bs,and [(r(x, a, 8') + 7V (5') Vn (+)) (5 a)}. Lever-
+V (x)] V (6),
aging the value function approximation, we can then approximate the policy gradient as
( = (r(s, a, xs) - (L)) vn(s, a) = ((o,w)
(7)
which gives rise to the policy update
0 02 + az 02 wx) with v(zK, 0k, = 0 (x /o, ak)
where 0% is the stepsize for the actor update.
To ensure convergence when simultancously performing critic and actor updates, the stepsizes ag and Bg often decay at two different rates, which is referred to the two-timescale AC [17 18.
3 ASYNCHRONOUS ADVANTAGE ACTOR CRITIC WITH TD(0)
To speed up the training process, we implement AC over N workers in a shared memory setting without coordinating among workers a setting similar to that in A3C [3] Each worker has its own simulator to perform sampling, and then collaboratively updates the shared policy To using AC updates. As there no synchronization after each update, the policy used by workers to generate samples may be outdated, which introduces staleness.
Notations transition (s, a, 8"). Since each worker will maintain a separate Markov chain, we thereafter use subscription l. in (St. at, 8t+1) to indicate the 7th transition on a Markov chain. We use to denote the global counter (or iteration), which increases by one whenever worker finishes the actor and critic updates in the shared memory. We use subscription (k) in ($(K). ((k), (w)) to indicate the transition used in the kth update.
Specifically, we initialize Og wo in the shared memory. Each worker will initialize the simulator with initial state sp- Without coordination, workers will read 0, w in the shared memory. From each worker's 's view, it then generates sample (St, at 8t+1) by either sampling 8; from (e(-), where (o(+)) is the stationary distribution of an artificial MDP with transition probability measure P(- ax) == yP(()se, a.) + (1 7))()),, or, sampling 8t from a Markov chain under policy no. In both cases, each worker obtains a, ~ (-(ss))) and s,+1 ~ P(-Ist, a.). Sampling 81+1 from (-|ss,, ax) can be achieved by sampling 8 from 17(-) with probability 1 7 and from P(-|st, ax) otherwise. Once
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Asynchronous advantage AC with TD(0): each worker's s view.
Global initialize: Global counter & 0, initial 0g. wi the shared memory.
2: Worker initialize: Local counter = 0. Obtain initial state so.
3: for t = 0, 1, 2.... do
4: Read 8, w in the shared memory.
5: Option 1 (i.i.d. sampling):
6:
Sample s; ~ (u)()), at ~ (T(-(s), S141 ~ P(-1st, ar).
7:
Option 2 (Markovian sampling):
8:
Sample aa (-)s),, 81+1 ((.1s),at) at).
9:
Compute (()r,w) = r(st, 0e; 8t+1) (8e41) (o()
10: Compute g(x,,w) = ((x,,W) V (st).
11:
Compute 0 = 8(12, w w)o (5t: a+).
In the shared memory, perform update
13:
end for
obtaining I; == (st, ae, St+1), each worker locally computes the policy gradient v(z,, 0, and the TD(0) update g(re, w)), and then updates the parameters in shared memory asynchronously by
W Rm.. (wx + (agg(rre)) wk-r))
(9a)
0x+1 02 (x 0 Wk-r2):
(9b)
where Ty is the delay in the kth actor and critic updates. See the A3C with TD(0) in Algorithm !
Sampling distributions. Since the transition kernel required by the actor and critic updates are different in the discounted MDP, it is difficult to design a two-timescale AC algorithm. To address this issue, adopt the sampling method introduced in the seminal work 31 and the recent work which inevitably introduces bias by sampling from the artificial transition P instead of P. However, as we will mention later, this extra bias is small when the discount factor is close to 1.
15
16
Parallel sampling. The AC update (6) and (8) uses samples generated "on-the-fly" from the target policy Ty. which brings overhead. Compared with (6) and (8. the A3C-TD(O) update ( allows parallel sampling from N workers, which is the key linear speedup. We consider the case where only one worker can update parameters in the shared memory at the same time and the update cannot be interrupted. practice, can also be performed
mini-batch fashion.
Minor differences from A3C 33. The A3C-TD(O) algorithm resembles the popular A3C method 3. With mmmx denoting the horizon of steps, for n E (1, ..., Mmnax) J. A3C iteratively uses n-step TD errors to compute actor and critic gradients. In A3C-TD(O), we use the TD(0) method which is the 1-step TD method for actor and critic update. When Rmmax 1, A3C method reduces to A3C-TD(O). The n-step TD method is hybrid version of the TD(0) method and the Monte-Carlo method. The A3C method with Monte-Cart sampling is essentially the delayed policy gradient method, and thus its convergence follows directly from the delayed SGD. Therefore, we believe that the convergence of the A3C method based on TD(O) in this paper can be easily extended to the convergence of the A3C method with n-step TD. We here focus on A3C with TD(0) just for ease of exposition.
CONVERGENCE ANALYSIS OF TIO-TIMEE A3C-TD(O)
In this section, we analyze the convergence of A3C-TD(0) in both i.i.d. and Markovian settings. Throughout this section, the notation (-) contains constants that are independent of N and Kn-
To analyze the performance of A3C-TD(O), we make the following assumptions.
Assumption 1. There exists Ko such that the delay at each iteration is bounded by Th S Ko, Vk.
Assumption T ensures the viability of analyzing the asynchronous update; see the same assumption in e.g., 5 25
In practice, the delay usually scales as the number of workers, that is K₂ O(N).
With P (s'1s) EaEa P( a))((ss))) we define that:
As,s S"pp.
(6(3)(10(6)) [ b s-epe anpp s')s,,, (10)
E.
5

---

Under review as a conference paper at ICLR 2021
It is known that for given 8, the stationary point wg of the TD(0) update in Algorithm 1 satisfies
Agg + b = O.
(11)
Assumption 2. For all E S, the feature vector o(s) is normalized that [lo(s)]2 S 1. For all 7 E [0, and 0 E R., A is negative definite and its max eigenvalue is upper bounded by -X
Assumption 2 common in analyzing TD with linear function approximation; see e.g., I1 32 33 With this assumption, Ag.o is invertible, so we have wh be Define Rw := Tmax/ X, then
we have | I Rw. It justifies the projection introduced in A Algorithm In practice, the projection radius R. can be estimated online by methods proposed in 32 Section 8.2] or 34 Lemma 1].
Assumption 3. For any 0, 8' Rd Cz.; üi) (1, - sha (8, a)ll2 S T. 0 22 iii (Taaa))) To (a|s) S T 1= 0-
and E A. there exist constants such that: i) (o a)lla
Assumption B is common in analyzing policy gradient-type algorithms which has also been made by e.g., [34 35 [36]. This assumption holds for many policy parameterization methods such as tabular softmax policy [6). Gaussian policy (37) and Boltzmann policy 31.
Assumption 4. For any E R., the Markov chain under policy To and transition kernel P(+|s, a) or ((-ss, a) irreducible and aperiodic. Then there exist constants k. > 0 and p E (0, 1) such that
sup drv (P(s: -|soo s, To), pa) S kpp, VL
(12)
#ES
where po is the stationary state distribution under ng. and 8t is the state of Markov chain time t.
Assumption 4 assumes the Markov chain mixes at geometric rate; also [32 33
The stationary
distribution Hl of an artificial Markov chain with transition P is the same the discounted visitation measure dg of the Markov chain with transition P (6) This means that we sample according to To To[ (-]s:), St+1 ((-|se, az), ). the marginal distribution of (st, az) will converge to the discounted state-action visitation measure (s a), which allows to control the gradient bias.
4.1 LINEAR SPEEDUP RESULT WITH I.I.D SAMPLING
In this section, consider A3C-TD(O) under the i.idd sampling setting, which is widely used for analyzing RL algorithms; see e.g.. 13 18 38
We first give the convergence result of critic update follows.
Theorem 1 (Critic convergence). Suppose Assumptions 7+ hold. Consider Algorithm 7 with
i.i.d. sampling and (s) = d(s) w. Select step size ag [I+K) 3r
C2
where
(1+ky'2
0 < 02 <0i and cı, C2 positive constants. Then it holds that
K
K
Σ
wā. -1: E W
Ki-02
10
K2101-007
t0
Kō K202
Ka Koi
+0
K
(13)
Different from async-SGD (e.g.. 1., the optimal critic parameter wp constantly drifting as changes at each iteration. This necessitates setting σ > d2 to make the policy change slower than critic, which can be observed the second term 13). of > σ2, then the policy static relative to the critic in an asymptotic sense.
To introduce the convergence of actor update, we first define the critic approximation error as
Capp
max 9g3d
V+, (s) Va, (8) S 6ta Esps
(14)
where μo is the stationary distribution under Ty and P. The error Capp captures the quality of the critic approximation under Algorithm [ can be further decomposed into the function approximation error éta. which is common in analyzing AC with function approximation [14] [5 17, and the sampling error <pp = 0(1 - 7), which is unique in analyzing two-timescale AC for a discounted MDP. The error capp is small when the value function approximation is accurate and the discounting factor is close to 1; see the detailed derivations in Lemma 7 of supplementary material. Now we are ready to give the actor convergence.

---

Under review as a conference paper at ICLR 2021
Theorem 2 (Actor convergence). Under the same assumptions of Theorem L select step size cu. 02
5k
(142)=2, where 0 < 02 < 01 < 1 and 0₁2 C2 are positive constants. Then it holds that
(1+4)*7
Ko Koi
Kō K200
K Σ E
K
E ( =
Ki-oi
+0
+0
+
K
1oar
wāz 112
+O(spp))
(15)
Different from the analysis of asyne-SGD, in actor update, the stochastic gradient v(x, 0, ) is biased because of inexact value function approximation. The bias introduced by the critic optimality gap and the function approximation error correspond to the last two terms in (15).
In Theorem D and Theorem optimizing σi and 0% gives the following convergence rate.
Corollary 1 (Linear speedup). Given Theorem 7 and Theorem 2 further assume Ku = O(K K3) )) then it holds that
select 01 &hS and 02 .. we
==VOO) - o (K (Eapp)
(16)
where (-) contains constants that are independent of N and Ko-
By setting the first term in (T6) e, we get the total iteration complexity to reach e-accuracy is O(c-2.5) Since each iteration only uses one sample (one transition), it also implies a total sample complexity of (c--2.). Then the average sample complexity per worker is ((-22))NN) which indicates linear speedup in ( Intuitively, the negative effect of parameter staleness introduced by parallel asynchrony vanishes asymptotically, which implies linear speedup terms of convergence.
4.2 CONVERGENCE RESULT WITH MARKOVIAN SAMPLING
Theorem 3 (Critic convergence). Suppose Assumptions hold. Consider Algorithum with Markovian sampling and (s) (0s) w. Select step size ork [+FKJT 3x
[I+b)o2 where
02 01 and C1, C2 are positive constants. Then holds that
K
11: 0 (Ri-oz) +0
KJ K200
Kō log Koi
Ko log K K
E Fl
112
+0
+0
+0
K
K2 -22
(17)
The following theorem gives the convergence rate of actor update in Algorithm 1
Theorem (Actor convergence). Under the same assumptions of Theorem 3 select step size ogk- (1+k)=1 3h (2+ where 0 < 02 < <a, < and 0₁, C2 are positive constants. Then it holds that
K3 log K Koi
Kō R2202
R ( =0
Ki-oi 10
+0
R
lwo
win 112 +O(Eap))
K
(18)
Assume Ko = O(Kt). Given Theorem
select 01 = and 02 = 2. then it holds that
K Σ
= = -(koK B) O(Fopp),
(19)
where Ō(.) hides constants and the logarithmic order of K.
With Markovian sampling, the stochastic gradients g(æ, w) and 0(2,, O, w) are biased, and the bias decreases as the Markov chain mixes. The mixing time corresponds to the logarithmic term log K in (17) and (18). Because asynchrony, at a given iteration, workers collect different number of samples and their chains mix to different degrees. The worker with the slowest mixing chain will determine the rate of convergence. The product of Ko and log K in (17 and (8) appears due to the slowest mixing chain. As the last term in (17) dominates other terms asymptotically, the convergence rate reduces as the number of workers increases. While the theoretical linear speedup is difficult to establish in the Markovian setting, will empirically demonstrate it in Section 5.2
7

---

Under review as a conference paper at ICLR 2021
80
53
280
100
200
Trokiigg
Figure 1: Convergence results of A3C-TD(O) with iid. sampling in synthetic environment.
worbers
89
80
80
75
workers
workers
M550001 -
werdwr
wodan 2
worders 4
workan 4
66
worder 8
warowss
wodee 16
203
200 Tran rg Time (bec)
102
Tranking Timee (ow]]
Trikiigg Sampes
Nunberrl WNotoo
Figure 2: Convergence results A3C-TD(0) with Markovian sampling in synthetic environment.
NUMERICAL EXPERIMENTS
We test the speedup performance A3C-TD(O) on both synthetically generated and OpenAl Gym environments. The settings, parameters, and codes are provided in supplementary material.
5.1 A3C-TD(0) IN SYNTHETIC ENVIRONMENT
To verify the theoretical result, we tested A3C-TD(O) with linear value function approximation in synthetic environment. We use tabular softmax policy parameterization (36). which satisfies Assumption 3 The MDP has state space |S] 100, an discrete action space of |.A| = 5. Each state feature has dimension of 10. Elements the transition matrix, the reward and the state features are randomly sampled from uniform distribution over (0, 1). We evaluate the convergence of actor and critic respectively with the running average of test reward and critic optimality gap || - w7, ll2-
Figures D and 2 show the training time and sample complexity of running A3C-TD(0) with i.i.d. sampling and Markovian sampling respectively. The speedup plot is measured by the number of samples nceded to achieve target rumning average reward under different number of workers. All the results are average over Monte-Carlo runs. Figure [ shows that the sample complexity of A3C-TD(O) stays about the same with different number of workers under i.i.d. sampling. Also, can be observed from the speedup plot of Figure [ that the A3C-TD(O) achieves roughly linear speedup with i.i.d. sampling, which is consistent with Corollary []] The speedup of A3C-TD(() with Markovian sampling shown in Figure 2 roughly linear when number of workers is small.
5.2 A3C-TD(O) IN OPENAI GYM ENVIRONMENTS
We have also tested A3C-TD(0) with neural network parametrization in the classic control (Carpole) environment and the Atari game (Seaquest and Beamrider) environments. In Figures 3 each curve generated by averaging over 5 Monte-Carlo runs with 95% confidence interval. Figures the speedup of A3C-TD(0) under different number of workers, where the average reward is computed by taking the running average of test rewards. The speedup and runtime speedup plots are respectively measured by the number of samples and training time needed to achieve target running average reward under different number of workers. Although not justified theoretically, Figures 3 Suuggest that the sample complexity speedup is roughly linear, and the runtime speedup slightly degrades when the number of workers increases. This is partially due to our hardware limit. Similar observation has also been obtained in aSyn 9
show
8

---

Under review as a conference paper at ICLR 2021
140
R.rfer Spenthp
120
10
Pastage
wokin
50
voton 2
votan
vaten +
vaten
106
126
1
1.2
19
Traning Tine
Takking
Wackers
Number Worcems
Figure 3: Speedup of A3C-TD(0) in OpenAl gym classic control task (Carpole).
2000
Norles
500
Surbie Speedae
wathers
Aectage Nowest
300
250
200
253
100
0.0
Time (h%
Nambor ofrbourdWoodee
Namber Workers
Figure 4: Speedup of A3C-TD(0) in OpenAl Gym Atari game (Seaquest).
Wahhara
vothera-
4000
801
Bestkin Speeks
802
3000
493
200
0.0
0.5
Training Timel
Namber Workers
Nurte' of Wenee'
Figure 5: Speedup of A3C-TD(O) in OpenAl Gym Atari game (Beamrider).
6 CONCLUSIONS
This paper revisits the A3C algorithm with TD(0) for the critic update, termed A3C-TD(0). With linear value function approximation, the convergence of the A3C-TD(0) algorithm has been established under both i.i.d. and Markovian sampling settings. Under i.i.d. sampling, A3C-TD(0) achieves linear speedup compared to the best-known sample complexity of two-timescale AC, theoretically justifying the benefit of parallelism and asynchrony for the first time. Under Markov sampling, such linear speedup can be observed in most classic benchmark tasks.
REFERENCES
[1] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. "Continuous control with deep reinforcement learning," Proc. of International Conference on Learning Representations, 2016.
[2] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski el al., "Human-level control through deep rein- forcement learning," Nature, vol. 518, no. 7540, p. 529, 2015.
[3] V. Mnih, A. P. Badia. M. Mirza, A. Graves, T. P. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu, "Asynchronous methods for deep reinforcement learning." in Proc. of Interna- fional Conference Machine Learning, 2016.

---

Under review as a conference paper at ICLR 2021
[4] A. Nair, P. Srinivasan, S. Blackwell, C. Alcicek, R. Fearon, A. De Maria, V. Panneershelvam M. Suleyman, C. Beattie, S. Petersen et al., "Massively parallel methods for deep reinforcement learning," arXiv 0eeprint:150.0422900 2015.
[5] M. Assran, J. Romoff, N. Ballas, J. Pineau, and M. Rabbat, "Gossip-based actor-leamnr architectures for deep reinforcement learning," in Proc. of Advances in Neural Information Processing Systems, 2019.
[6] V. Konda, Actor-critic algorithms. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2002.
[7] R. Sutton, D. McAllester, S. Singh, and Y. Mansour, "Policy gradient methods for reinforcement learning with function approximation." in Proc. of Advances in Neural Information Processing Systems, 2000.
[8] R. Sutton, "Learning to predict by the methods of temporal differences," Machine Learning. vol. 3, pp. 9-44, 1988.
[9] X. Lian, H. Zhang, C. Hsich, Y. Yijun Huang. and J. Liu, "A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order"" in Proc. of the Advances in Neural Information Processing Systems, 2016.
[10] V. Borkar and V. Konda, "The actor-critic algorithm as scesi stochastic approxima- tion," Sadhana, vol. 22. no. 4. pp. 525-543, 1997.
[11] S. Bhatnagar, R. Sutton, M. Ghavamzadeh, and M. Lee, "Natural actor critic algorithms." Automatica, vol. 45, pp. 2471-2482, 2009.
[12] Z. Yang, K. Zhang, M. Hong, and T. Başar, "A finite sample analysis of the actor-critic algorithm," in Proc. of IEEE Conference on Decision and Control, 2018, pp. 2759-2764.
[13] H. Kumar, Koppel, and A. Ribeiro, "On the sample complexity of actor-critic method for reinforcement learning with function approximation." arXiv preprint: 19100041,,20
[14] S. Qiu, Z. Yang, J. Ye, and Z. Wang, "On the finite-time convergence of actor-critic algorithm."" in Optimization Foundations for Reinforcement Learning Workshop at Advances in Neural Information Processing Systems, 2019.
[15] T. Xu, Z. Wang, and Y. Liang. "Improving sample complexity bounds for (natural) actor-critic algorithms," in Proc. of Advances in Neural Information Processing Systems, 2020.
[16]
"Non-asymptotic comeareer analysis of two time-scale (natural) actor-critic algorithms," arXiv preprint:2005.003533 2020.
[17] Y. WU, W. Zhang, P. Xu, and Q. Gu, "A finite time analysis of two time-scale actor critic methods," in Proc. of Advances in Neural Information Processing Systems, 2020.
[18] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang, "A two-timescale framework for bilevel opti- mization: Complexity analysis and application to actor-critic," arXiv preprint:2077.02 200:::0570000000000 050 2020.
[19] M. Babaeizadch, I. Frosio, S. Tyree, Clemons, and Kautz, "Reinforcement learning through asynchronous advantage actor-critic on a gpu," in Proc. of International Conference Learning Representations, 2017.
[20] A. Stooke and P. Abbeel, "Accelerated methods for deep reinforcement learning," arXiv 1reprint:8803.mm 02811, 2019.
[21] L.. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, S. Legg, and K. Kavukcuoglu, "Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures." arXiv 1reprimt:10020111 1802.01561, 2018
[22] D. Bertsekas and J. Tsitsiklis, Parallel and distributed computation: numerical methods. Prentice-Hall, 1989.
10

---

Under review as a conference paper at ICLR 2021
[23] A. Agarwal and J. Duchi, "Distributed delayed stochastic optimization," in Proc. of Advances in Neural Information Processing Systems, 2011.
[24] H. Feyzmahdavian, A. Aytekin, and M. Johansson, "An asynchronous mini-batch algorithm for regularized stochastic optimization." arXiv preprint:1505.c 04824, 048.44444, 2015.
[25] X. Lian, Y. Huang, Y. Li, and Liu, "Asynchronous parallel stochastic gradient for nonconvex optimization." in Proc. of Advances in Neural Information Processing Systems, 2015.
[26] T. Sun, R. Hamnah, and W. Yin, "Asynchronous coordinate descent under more realistic assump- tions," in Proc. of Advances in Neural Information Processing Systems, 2017.
[27] X. Lian, C. Zhang, H. Zhang, C.-J Hsieh, W. Zhang, and J. Liu, "Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent," in Proc. of Advances in Neural Information Processing Systems, 2017.
[28] R. J. Williams, "Simple statistical gradient-foloowing algorithms for connectionist reinforcement learning," Machine Learning, vol. 8, no. 3-4, pp. 229-256, May 1992.
[29] Baxter and L. Bartlett, "Infinite-horizon policy-gradiese estimation," J. Artificial Intelligence Res., vol. 15, pp. 319-350, 2001.
[30] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction.
MIT Press, 2018.
[31] V. Konda and V. Borkar, "Actor-critic-type learning algorithms for markov decision processes." SIAM Journal on Control and Optimization, vol. 38, no. 1, pp. 94-123, 1999.
[32] J. Bhandari, D. Russo, and R. Singal, "A finite time analysis of temporal difference learning with linear function approximation." Proc. of Conference on Learning Theory, 2018.
[33] T. Xu, Z. Wang, Y. Zhou, and Y. Liang, "Reanalysis of variance reduced temporal difference learning," in Proc. of International Conference on Learning Representations, 2020.
[34] Zou, T. Xu, and Y. Liang, "Finite-sample analysis for SARSA with linear function approxi- mation," in Proc. of Advances in Neural Information Processing Systems, 2019.
[35] K. Zhang, A. Koppel, H. Zhu, and T. Başar, "Global convergence of policy gradient methods to (almost) locally optimal policies," arXiv preprint: 1906. 08383, 2019.
[36] A. Agarwal, M. Kakade, J. D. Lee, and G. Mahajan, "Optimality and approximation with policy gradient methods in markov decision processes." in Proc. of Thirty Third Conference Learning Theory, 2020.
[37] K. Doya, "Reinforcement learning in continuous time and space," " Neural Computation, vol. 12, no. pp. 219-245, 2000.
[38] R. Sutton, H. Maei, D. Precup. Bhatnagar, D. Silver, and E. Szepesvári, C.and Wiewiora, "Fast gradient-descent methods for temporal-diiffernce learning with linear function approximation." Proc. of International Conference on Machine Learning, 2009.
[39] A. Y. Mitrophanov, "Sensitivity and convergence of uniformly ergodic markov chains," Journal of Applied Probability, vol. 42, no. 4, pp. 1003-1014, 2005.
[40] Dgriff, "Pytorch implementation of a3c," https://gittbbccomm/////177//1/ a3c pytorch 2018.

---

Under review as a conference paper at ICLR 2021
Supplementary Material
A PRELIMINARY LEMMAS
A.1 GEOMETRIC MIXING
The operation p & q denotes the tensor product between two distributions p(x) and q(v), i.e. (p Ø (x, 3) = p(æ) 4(v).
Lemma 1. Suppose Assumption 4 holds for Markov chain generated by the rule at nT((1s)).
8141 P(.)s a.). For any 0 R.d, we have
sup drv (P((s)) S141) -|s0, Te), Me 2 To p P) Kxp'.
(20)
soES
where (-)))) is the stationary distribution with policy and transition kernel P(.18,
Proof. We start with
sup drv (P((5), (1: S1+1) -10. no). #oES
sup drv )7) mGES
1180, m @0
1
IP(s ds|so, no (dass hadc SES aEA J'ES
Σ
/
sup #5
2
1
[((:: ds)so, s0, xo) [o(ds) Σ no(a|s) / P(ds'(s,a)
sup #5
2 SES
aEA S'ES
sup drv (P(s To) p2)) #GES
S kpp,
which completes the proof.
For the in the later proof, given K 0, we first define m as: mg = min m E N+ |xp" S minfar, 3x3}
(21)
where x and p are constants defined in 4 mk is the minimum number of samples needed for the Markov chain to approach the stationary distribution so that the bias incurred by the Markovian sampling is small enough.
A.2 AUXILIARY MARKOV CHAIN
The auxiliary Markov chain is virtual Markov chain with no policy drifting - technique developed in [3 to analyze stochastic approximation algorithms in non-stationary settings.
Lemma 2. Under Assumption and Assumption 3 consider the update (9) in Algorithu / with Markovian sampling. For given number of samples m, consider the Markov chain of the worker that contributes to the kth update:
ak-dm 1, 0t-m++1 St-1 02-d; a 02-dy at Si+1,
8t-m am am m _ 81 8t-m+1
where (st, Ce, S1+1) = (5(K); a(k), (,)) and (dg (d is some increasing sequence with do = Tk-
Given (si-m: ac-m, 8t st-m+1) and 0m-dm we construct its auxiliary Markov chain by repeatedly
applying T0
8t-m Oe-Amy Ot-m p 8t-m11 Pe-dm a 5t-1
6 Bu-dm a.-1 _ St
Oa den a _ $111
Define D4 == (st, Ge, 81-1). )) then we have:
dTv (P -10k-dm 3t 35-+11,,P(P PPTT -10p-am st-m++))
dm
L
Σ 1=Te
E [110,=
20-dml1210k-o 10:00=mmm:tmpmm st-m+1).
(22)
12

---

Under review as a conference paper at ICLR 2021
Proof. Throughout the lemma, all expectations and probabilities are conditioned on 8 and 8t-m+1- We omit this condition for convenience.
First we have
drv (P(6--1 E P(), E.))
2 f Jes
[P(81+1 = ds') - -P((5++1 = ds')l
[
2 JHeS
Σ
P(st = ds,as ar - a, 80+1 = ds') P((., ds, āz = T141 = do')
JES aEA
$ 2 S'ES J SES
[P( = d8, 0r = aa, 81+1 -,+1+1 = ds') Pp. ds, ār = a, 8t41 = ds')l
aEd
Σ
[P(5t - ds, ar a, 8141 = ds') P3 ds, ãr = a, 8 = ds')l
2 SES aEA SES
= drv (IP(z, E E.), P(T, E.))
(23)
where the last second equality is due to Tonelli's 's theorem. Next we have
drv (P(x, E PP),)(
2 S. E/
[((: ds, at a, S141 ds') P(5 ds, ãz a,,3+11 ds')l
aEd J'ES
|P(: ds, ar = a) P(
ds, ãz = =a)l
P(sc+1 ds'ls: ds, ar a)
2 JES
juES
[P( ds, ar = a) P( ds, ãة = =a]
JES aEA
drv (P ((se, at) E ((3,, E -))
(24)
Due to the fact that Ox-re dependent on st, we need write (( 0z) as
/
P(s.. at)
P(st, Ok Ok-TL, az)
1 ERd
{ P(sx) = ddf(s)) ( T0 (asl
JoEzd
=P(st) JOER"
P(Ak-Tu = dd(ss))To.-., (ag(s))
=P(s)) E[TTOL-- (at
Then we have
drv (P ((s), a.)
.), (. -))
1
P(s: ds) El E| (at als; ds) ds} - -P(5 dd) (ā. a ds)
2
.ES
1
P(s: ds) E T0 (at alsı ds) ss ds} P(st ds) ds)To (a: als: ds)
2
JEE
nEAA
1
|P(st ds) Tex- (āt als ds) Pr.t ds) (ā= =als ds)
JES aEA
1
P(ss ds)
Σ
E E|TO2-T (as alsa ds)(ss ss dss T8L-A... (ar alst ds)
2
JES
aEA
1
[P(ss ds) P(. ds)l.
(25)
2
13

---

Under review as a conference paper at ICLR 2021
Using Jensen's inequality, we have
dr (P ((5t, ur) E E,), ((5r, (+) ar) E-)
1
P(s: ds) Σ
E
Top (ar - alst ds) T0
(a: 0/ ds)
81 ds
SES
aEd
1
/
[P((5t ds)
P( ds)l
2
SES
1
P((: = ds) Σ
E x110 0g 08-dmll21 12 = ds] + -ds++
/ |P(s ds) - P( da)
2 J
aEd
1
L E 0k
0k-dm 212 + drv (P(st E P, E))
(26)
2
where the last inequality follows Assumption
Now we start to prove 22
drv (P(x E ), e
drv (P((s), E P),((((, E .))
drv (P(s; ), E )) + 2 L La 1100-1 0x-dmll ll2
drv (P(x--1 E P(T+11 E.)) + 1 11x0- On Ok-dm112
Now we have
1
drv (P(x) E P,T( E +) S drv (P(I E (, P(r-11 E E) + A E 1102-Tx - -0 122
(27)
Since drv (P(xe-m )), P(xe-m )) = 0, recursively applying 27 for {t - I, t - m} gives
drv (P(x, E .), E +)
- 2/4 L Σ
|1 d, 0R 0R-dmml ll2
j=0
dm
A bmm
Σ
E Ok Ox 0x-dmmll2
2
im
which completes the proof.
A.3 LIPSCHITZ CONTINUITY OF VALUE FUNCTION
Lemma 3. Suppose Assumption 3 holds. For any 01, Hd and E we have
V (s)ll2 S Lv,
(28a)
IV Vo, (s) Vao, [s)] S Lv -21122
(28b)
where the constant is Lv = CyTmax/ /aae//////-- 7) with Co defined as in Assumption
Proof. First we have
20
Qx( = E
Σ
(St. at, 8141)180 8, ao = a
Tmux
Traax
1 1-7"
1=0
14

---

Under review as a conference paper at ICLR 2021
By the policy gradient theorem
77. we have
IV Tay (s)]l2
| Qms, (8, (s.a)lll2
|| Tre, (s. (s,a)]s
E [10me (s. ve (s.a)]l2]
maxx Co: 1-7
where the first inequality is due to Jensen's ss inequality, and the last inequality follows Assumption 3
and the fact that Q (8, S Tmax
T-y By the mean value theorem, we immediately have
VTTe (8) Viog (+) S sup ||VV=,, (+)]l, 110 - 02l12 - Lv100 - 02112:
ORER"
which completes the proof.
A.4 LIPSCHITZ CONTINUITY OF POLICY GRADIENT
We give a proposition regarding the Ly-Lipschitz of the policy gradient under proper assumptions, which has been shown by (35).
Proposition 1. Suppose Assumption 3 and 4 hold. For any 0' E Rd, we have [
V | 811,, where L is a positive constant.
A.5 LIPSCIITZ CONTINUITY OF OPTIMAL CRITIC PARAMETER
We provide a justification for Lipschitz continuity of wg in the next proposition.
Proposition 2. Suppose Assumption
3 and hold. For any 0,, O2 IRd, we have
1 - wā_ll2 S L 1| 02112,
where La = 2r max (AL== +x + (1 + log, x- + (1 11-p)) p)
Proof. We use A1, A2, dj and by as shorthand notations of Ame,, Aroz DTo, and dman respectively. By Assumption 2 Ag,o is invertible for any 0 E Rd, so we can write wp = - bo Then we have
||w]- w 2 = || - A b, + A
b2 l2
|| - b 1/ 122 + 2 + A b2112
|| A - b2) (AT - 2 )b2112
$ || |AAT'(6i - b2) + |I -A," )b2112
< ||4 |12/ll b2ll2 + ||4 A7 15'1lel1b2l1
= ||2111
b2/12 + 1 - A1) 1lellll
$
bel12 + ||, 1
A1ll2
S X 1 16 -b2l2 A 2 3/ax || A
(29)
where the last inequality follows Assumption 2 and the fact that
b|bz 12 = =|[[r(ss, a, s')(())]]l - E [| a, s' (s())l S E [Ir(s, a, )l()(()) I Tmaxx
Denote (s² ",,at,"" and (s2,a², 522 as samples drawn with 0, and 02 respectively, i.e. st p0 at ~ nB,, 8rl ~ P and s² ~ mez, a² ~ T8,, s22 ~ P. Then we have
|b be a|l [r(s*, at, )0s)() - E [r(s", a. 8 )
sup ||r(s, a, s (0)( (P a², E -P((s? 5²) E ))l
s.a.s'
< Smax (P((s) a. 8 E - P(s 2 E -lll
= 22 po, @ T8, & P, no @ To, @ P)
2r IA T., (1 + log, n 1 + p) - 0| 02112.
(30)
15

---

Under review as a conference paper at ICLR 2021
where the first inequality follows the definition of total variation (TV) norm, and the last inequality follows Lemma A. in [17]. Similarly we have:
||| A2l 12 - 2(1 + d)dTV (Me, & TTo M4g (T²2)
(1 + +++)) A= (1 log, 15 + p)11) 82ll2.
(31)
Substituting
30 and
into
completes the proof.
B PROOF OF MAIN THEOREMS
B.1 PROOF OF THEOREM !
For brevity, we first define the following notations:
= as,
8(x, w) = r(s,a, + v0(s') o(s) w.
g(r, w) = ((1,w)((s),
g(0,w) = smporarstoss (g(sr,
We also define constant C3 == mmax + (1 + 7) max rime R. and we immediately have
(1 12 S [r(x) + 70(s') w d(s) wl S rmax + (1 + Re S &Cs
(32)
and likewise, we have ||و w S Cs.
The critic update in Algorithm can be written compactly as:
Wk+1 = IRR (wx + (xg(Z())) w)-)))
(33)
where is the delay of the parameters used in evaluating the kth stochastic gradient, and ((x)) = (s(K): a(K):
(wy) is the sample used to evaluate the stochastic gradient at kth update.
Proof. Using w shorthand notation of wp we start with the optimality gap
| 1 112
||[RR_ (wk + Beg( (x))) 11
$ ||wx + (ag(IT()) Wk- wh+1
1| - will2 25 (wi wh (k + (wx - wi wh+1) + || wh+1 + Beg( wk-T))
||m - -wlll² 2Bx (wx wt, g 9(10) W k (( wx)) + 23, (wx - w/: (((K) wk) ((0))W1))
+ 2,8 (w) - wh, g(0k, wx)) + 2 (w> w w wh+1) + ||4 - wh+ + (x )11
< || - willi 2 (wr - wh: 9 (T W Wh- g( wx)) + 233x (wi - w/: g( wx) g(Ov,w)))
2,8 (wi - w g(0,. wx)) 2 (wx w wt wh+1) 2 ll - wh+z +C7388
(34)
We first bound (w), w 70 wx)) in 34 as
(wk wt. (0,, w₂ = (wk wh: g
g(o., Wk) - g(A,, wf:))
w E (77(5')) - x0s)) T (wi - (())(())))))
Wi:
Wi wHo E (5)) (76(5") - ((s)) [] (wi wf)
WR wp, Ano, (wi - wx))
< - Allwux wll1..
(35)
where the first equality is due to 7(. (.)
Ao, + = O. and the last inequality follows [ssumption Substituting (35) into (4). then taking expectation on both sides of (34) yield
E [| 11 < (1 -2 E ||ا - will + 2,3 E (wx - wt. g(F())) W.-re) - g ((x())) wx))
2,8 E (wk g((m) g(kk,
wx)) wx + 22 (wx wā, W w +
+ E | w1+1 20
(36)
16

---

Under review as a conference paper at ICLR 2021
We then bound the term E (wx- wt. ((0()), Wk - (()(())))))) in (36)
E (wi wk, (Z((6)) wk- ((T((): = EE We wh: (70(0(1)) ((o())) -wi-rx w. (x)
$ (1 + 7) B [| - will2 lIkk wxll2l
(wi+1 11411-W)) wi)
(1++)) E
| - wēll2
(1++)) R
|k - wtlla Σ
Bella wirn
k=
R-1
$1++7) E
| - wfllz
Σ
Bx Bx-Kollg
k=k-
E ||ا
w
(37)
where the second last inequality due to the monotonicity of step size, and the last inequality follows the definition of Cs in (32)
Next we jointly bound the fourth and fifth term in (36)
2 (wk wh. wi - wh+1i + 2 w wi 11
$ 2 [llE - Willz |uv - wh+ [1l] + +2 |lu| - wh++111 112
2Lw E [||ux - willz 110, Ou+ [12] + 22 E 110 0u+1 112
az E - wfll2 [((x(() wh -u No (())))
||we-willk
" (3))), a(s)) 1
+2L 1
< Cpa ||w - w 221222200 + 2L3 Oga
(38)
where constant Cp == CsCos The second inequality is due to the Lu-Lipschitz of wg shown in Proposition 2
and the last inequality follows the fact that
(5(H), a())ll - CCOC2 Cp--
(39)
Substituting 337 and 38 into (36) yields
ak 3x E || wh+1ll 12 S (1 2A3x) E ||wx - w 23x(Ci
+ (2 - wxll2
23 E (wn wh, ( wx) (()x + Cg
(40)
where C == L.C C2 C5 (1 + +7) and C = 2C3 + +2L C2 max c = 2C3 + +2L3,00
For brevity, we use æ ~ 0 to denote s ~ ua. a ~ Te and s' ~ P in this proof. Consider the third term in 40) conditioned on Os, Wh, Pk- We bound it as
E (w> wh: (( wh) (02, wx)) 10 O 0p-rel
Wk= w m 0r
E
[9( wa [w]] g(0n. wi))
w (( wk) J(0k, wx) 08-
We
< | willa 17 O1- wx) - g(0,. ww)l2
< 2R...
E xmde-TA
[o(),w))) - E [0(2,, wx))
xn0e
2R, sup (x)(
pee "k
8 Td
8 p - --o 2 Toe & P
TV
< AR. CodTy mmx--
2 P. uoe 2 Te @ P),
(41)
17

---

Under review as a conference paper at ICLR 2021
where second last inequality follows the definition of TV norm and the last inequality uses the definition of C3 in (32).
Define constant C3 2R. Co + log x- + (1 1)= Then by following the third item Lemma A.I shown by [17. we can write (41) as
[ws - why ((((k) - g(0,, wx)) Wk,WK. Wk, Ox-Tu] 1 4R Cadrv((ue-s Tek-ra @ P, M&g 2 TTB P)
C3 110k-T 0x11
k-1
C3
Σ
i=k-Tk
- C.CgK
(42)
where we used the monotonicity of ag and Assumption TI
Taking total expectation both sides of 42 and substituting it into (40) yield
E ww++1 wh+ < (1 2A will2 2.x (1 3x C2KooSe-Ko) K.) E lave
w
112
+2CgCsKoBaan--k + C.
(43)
Taking summation on both sides of (45) and rearranging yield
K
K +Cg
1
2A
E Wk
w
E Iwk
will E ||a+11 w
Bk
3x
A= Ko
= Ko
k= Ku
J1
I2
+ 2 2CgCsKgar-Ke Ko
Σ
K
+2
Σ
K
(c)
O
C2Kosk Ko
E Blwu
3x
km Ko
kmm
f3
1a
(44)
We bound 7 as
K
Σ
E Ilwk
wil2
E B|
wh+t 112)
BR
k=Mx
1
E Wk will2
||wxxx - whr
E Bllwk+1 w
Bg
3k-1
Bask-1
3r.
Mx
1
E wk
will2 +
E
WlWM wiscell 112
3x
3k-1
BasK-1
1m Mx
K
4R3 O(Km),
< 4R3
+
(45)
Bk
BR
Baxx
A Md
where the last inequality is due to the fact that
||wx w6 ||2 S ||wx|12 1 + ||w/|12 < 2
We bound /2 as
K
K
Σ
3 = Σ
O(K1-K1
(46)
(1 + k)oz
k=Mx
k=M
where the inequality follows from the integration rule 56 Σk=a k-o 61-0
T-
18

---

Under review as a conference paper at ICLR 2021
We bound as
K-Ko
13 Σ
2CaCoKoaR-Ko
20yCse
Σ
(1+
O(Kokk--)) (47)
Ko
For the last term 11. we have
K Σ
(c.
4
ak +2KKnBR-Ka Ko
+
E llw wxll2
3k
k= Ky
K
K
Ci
Olk
+ C2KKoBkKKo Ko
E Wa - 2
Bk
A= Ku
k=
K
K
Σ k=
Ci
OKk
+ C2KoBB-Ko
Σ k=
E
||ا
(48)
BE
where the first inequality follows Cauchy-Schwand inequality, and the second inequality follows Jensen's 's inequality. In (48). we have
K-Ko
Σ K=KD
ak C 3k
+ +C2KaBk-Ka
C
atk
+ C2KoBk
3R
k=U
Ko
K-Ko
K-Ko
C7
C2Ko
Σ ag
C2 Σ
B
B
k=U
0
(kloozoiitt)
O (Ko + 0 k2-
(49)
where the first inequality is due to the fact that o* and Bx-Ko are monotonically decreasing.
Substituting (49) into (48)
gives
K
4 (O + O +
Σ
E IWE will (50)
A= M
Substituting (45)
(46).
47
and
(50
into 44). and dividing both sides of (44) by K Ko + 1 give
21
E Wk w1ll
Ko
+1
Ko
(k2(0=-01)+2) O (KoK- + (K3K1-22
Σ E |wk - will
K Ko+1 +1
A=Ko
1
Kg
+ 0
(51)
K1-0z
K
Ka
We define the following functions:
K
T(K)=
Σ
E
[W
will?
Ko +
k=Ko
1
Ko
T2(K) = 0
+0
+
Kl-02
Koo
Ko
TKK)= 0 (K2()--0)+1))
m1)
+ O [KoK -ott) O (K3K' 1-23)
K Kn +1
19

---

Under review as a conference paper at ICLR 2021
Then (51 can be written as:
(K) 2A (Ti(K) S T2(K).
-
2A
Solving this quadratic inequality in terms of Ti (K), we obtain
1
1
Ti(K) < x
T2 (2( + 2x TKK),
(52)
which implies
K
E ||wE - will
K
Ko +1
ko
1
K2
Kg
1
=0
+ 0
+
+ 0
+0
K1-02
K2(m m02)
K20z
K
Ko2
We further have
K
Kg
K
1
E
B
-
4R +
Σ
E
[k - wfll2
K
K
k=1
k= Ko
K
Ko
K
Ko +1
1R.
+
Σ k=
E |w - =tll2
K
K
K - Ko +
Ko
1
0
+0
+
E Blos w
K
K
Ko
k=Ku
K
0
1
Σ
E 1 =0El1
(53)
K
Ko
+
k= Ko
which completes the proof.
B.2 PROOF OF THEOREM 2
We first clarify the notations:
= (s),,
8(x,w) w) = r(s, as) + 70(s') w Ø(s) Tw,
5(x, 0) = r(s, a, s') + 7 (s') Vxa (s).
The update in Algorithm [ can be written compactly as:
8x+1 = 0g + 6 W ($(K), a()))
(54)
For brevity, we use w as shorthand notation of wā. Then we are ready to give the proof.
Proof. From Liy-iischitz of policy gradient shown in Proposition | we have:
J(Ox+1) 2 J(O+) + (VJ(()), 0x+1 - -p0) - LJ
2 |10k+1 0x113
= J((a)) + au (VJ(O)). ((1 5(0(M) wit) Voo-n, (1(0))(()))
+ + (vJ(O=), 8(T())))) wz) Vo. (8(0), aww)
LJ
a (11 10 ((()))
2
2 J(At) + an (VJ(O)). (8(5()) wk - 5(1(M)) wh))
Vo0-on (())))())))
LJ
+ az (J(()),, 8( W0 (110), ((e))
CZ
2
where the last inequality follows the definition of Cp in (39
20

---

Under review as a conference paper at ICLR 2021
Taking expectation on both sides of the last inequality yields
[[J(0x+1)] 2 E[J(O.)] + on E (Okk), (6(3)19)) -k---)) ((0(0)).45)) vou-re ((()).
11
(s0))))))) + Or E ((00))) (igce (()))) 2
Ls
Cgaa.
(55)
12
We first decompose 1 as
11 = E V((kk). - ((0(1))
- wt)) vua-T (s(K): ((5(()) E VJ((s), (8( - wx) voa- (5(K)) a(k))
15
+ E VJ(O)), (6(2(1)) - ((((()) Vonn-1 (5()))(()))
13
We bound 1
1 = E V(((O)) (10(((()) -((()) (Wx-T= - ww-eum ia (s(0), ((a)))
2 - E [IVJ((0)]lal100()))))) - *(8w)))llalu - wa-re 1all (s(s) ac)))l
2 2C [[]] wk-Fe l12]
2 B
where the last inequality follows
W/ - Wh- 112
(ws+1 wi)
i=k-Te
|Bag(es, Wi-
im Tx
< B 10(
$ S
where the second inequality is due to the monotonicity of step size, and the third one follows 32 Then we bound (2)
1 E v (((k), (B(I()) (()))) v'x- (8(8), a(x))
E VJ((z), ()0()))) )(s())) (wt wk)o am))
E [VJ( ((sm))llaa (, (m))l)
2C E [ wfll2).
Collecting the lower bounds of T(1)) and 1(2) gives
2 2C, E (PLA (C3Ko 1 will2)]
(56)
21

---

Under review as a conference paper at ICLR 2021
Now consider 1z. We first decompose I2
1 = E (O,) ((T(A)) (5()), (13))
E (.(w)). (()) 5(0(M)) wh = xn)) Won-r (8(K), a(x)))
15
VJ(Os), (6()()) - (( (n-r))--e)))) voa-re (81)))
1
E (7(00),0(((()) Ox- Voon = ((a))a())) - VJ(O.)) (J(ON))+IVJ(..)) +IVJ)(0)1
12
We bound 1 as
1 = E (Bb)), (8(T))) - (k von-., (s(x), a(x))
= E v.((s), (70(5(1)) - )((())) T (Wk - wh-rr) von-i ($(8), a(s)))
2 - E |V.J(ea)laal (10(6(1)) ((w))) T 1l2 ||l - wi ll 11 (8(K), (mw))]2
2 Lv (1 + + El wh-re ll2
2 -Lv + + E 1 - Oz 0x-Tall2
-. Cp (1++1)++)0 Koa
where the second last inequality follows from Proposition 2 and the last inequality uses
(39 as
100 - 06-rol12 S
|0:+1 - 01ll2
k=
wi wi (8i, a:)ll
k=k-
ak- Cp
k=
$ CpKoak-Ko Ko-
(57)
We bound (2) as
2 E (J(()). (S(0()) - 8 ((z(1)) Bk- m)) von-, (8(0), a()))
2 E [II 8(0(M)) - ((((K)) Ok 0k-Tu) liba on (())))
2 C E (0x)) 21 (t - 6(((1)) Ox 0n-nell
(0(5(1)) T Wh-TE - Vion ve (6(e))) + Vane t (8(1)) - )((())) T TW 1|
= - C. E
(7 (((())) T Wh-T - Vi (6(o)) + |VooL.. (8(K)) )(3(w)) T whtrza) 1)]
M C. E
[VJ(0=)]] E (>) ( ( TWi - Van--n (0(e)) + Viog-n (8(M)) - (((())) (oon))Tfe Twin 0z. Ok 0k-TZ
= - C2 E
2 2Cpcupp
E (.)+)))
2
2C 6x B VJ(=))]l
(58)
22

---

Under review as a conference paper at ICLR 2021
where the second last inequality follows from the fact that
> ((()))
T w Vaue-r (5(1)) + Vzou-re (8(8) (((())) Tww wk-Fu/
s ( Vion (5(w)) + V VV (8(x)) ((8(N)) wot
$ 2ppp-
Define artificial transition (1x) == (S(K)) a(z), ((x) ~ P), then 1/2 can be bounded as
% = E V((()), ((x()), On Wo (8(1), a()) - vJ((o))
E E [VV 0() On ) (8(1), a(k)) - vJ((E)) 02 0z-n 0n] (6(=()): OK OK- 6( 0%- (2) )) 1h.-- (8(4), a(x)) 6x 0x- 0k)
E (VJ(()). E
E (VJ(O)), E
(T(0)) OK )oo - (8(k), ((3) (())) Ok OK 0s vJ(Ok))
2 [[VJ(O>)]l>
E (8(2T()) mx) (z Ok 0k-Tz)) VOR-TI (8(1)) acwi) 0x-
[VV(()))
IE ((((()) Ou- Wo. (8(K)) ((3)) OK 0n) - vJ((K)]
(59)
The first term in the last inequality can be bounded as
E (o(a(s)) (x-n)) - (z) Ok (R-rr)) VUE-TA ((()))())) On Ou- Oo]
E (d(or())) O2-T)) 800-880440 ((3 0k-TH vho T (s()) OK-Te 0z)
E
(r(2)())) + /E(r(s),, s0)] (((((()) + + Elr a' sn)l)) von-,, (s()). 0 -2. Ok
20 Tmaxll mnax||P= P y 7),
(60)
where the last inequality follows
of JES
= 2(1 - -7) / /es [P(5'(s,)) m(s')) s 4(1 - 7).
- -llvv = 2
- ()
(61)
The second term in 59 can be rewritten as
E ((T()) O2 n. Dohr-r ($(K), ((1) Ok , 0z]
(M(E(M)) + VNn - (B(x)) Vana - (8(22)) D/r-ry (8(0), (m)) Ox Tu. 0k.
E 8(6) (16)~186-7 ((1)) 0(1)) 7 8/1)~
(Tre (s(p); Vion (((6)) thoa-r, (S(N)) a(w)) 0x 12 0k
E S(E) Maye-
Arenrn (S(K): (w) - (5(a). ((w)) 0x mu: Or
E S(E) "Pay
ap2 -T
E 6(N) -do -N ana) -0
Arep (()))) -x (B(K); (()))
Ok 0k- Oz
-(
(62)
where the second last equality follows n.)()) do(.) with de being shorthand notation of d
6
23

---

Under review as a conference paper at ICLR 2021
Substituting 660 and 662 into 599
yields
(3)
S Tmaaa (1 7) E -/000)/ll--I/////0))1111/1001100
[J(a))]la
2 C (1 7) E V J(())) - LvL, 1 - 0% 12
-C maax (1 7) E. (J(+))ll2 Lv Kogosc
(63)
where the second last inequality is due to Ly-Lipschitz of policy gradient shown Proposition) and the last inequality follows (57).
Collecting lower bounds of I _ and 1 33) gives
12 2 Di Ko e2p 8C EVJ))) 2C + [V:(
(64)
where the constant is D1 == Ly Cop
Lv
Substituting (56) and 64 into (55) yields
([ 1)] [(2))] 20h Cs (Eap + 4r mr (1 - 7) + C8KK0 + | - 2 (J)()))l
-
LJ
-ayD,Koak-a
CoLCa + as ax V.++a
Czaz.
(65)
2
By following Cauchy-Schward inequality, the second term in 65 can be bounded as (Cap mrmax - 7) + C3Ko + lwy. wt 22) E J ((x))
E (((x)
12 E
(Eap + 4r - 7) + CgKo + | - w(,ll2)
E [(x)) 13
EE [407K30R 411200 w6 12 + 4c2 + -64r (1 -
2 B (0x)ll where the last inequality follows the order of exp in Lemma 7 Collecting the upper bound gives
C3K
w|w wfll O(epp)
(66)
[[ 2 B[J(+A)] - 40m BI EIV
E
||wk will O
L CzaZ.
ork Kook-Ko Cg + as | (
(67)
Dividing both sides of 667 by agk, then rearranging and taking summation on both sides give
K
K
L + caaa
E [(
- +
DDKoaasKo
2
Ko
Ko
No
4C [
/CKK38 E Wu w + (c,p)
k= Kg
1.
Ivv - Ko 1)cta-
(68)
We bound T3 as
=
Σ
E -B((()))
akk
Ko
1
1
- E [(x+())
B[J(ON]
[[ )1
Oak-1
Oi
aMK-1
aK
k=
<
E [[[(Ok+1)
aк
Tmax
1 O(K*),
(69)
Yk
24

---

Under review as a conference paper at ICLR 2021
where the first inequality is due to the ag is monotonic decreasing and positive, and last inequality is due to Vi (s) S Emax for any s E and mg.
1-y
We bound 4 as
K Σ
K-Ko Ko Σ
LJ + 2
D2Koax + Ls
1
DiKoaa-Ko
czax
$
czas) = -..
2
Rim Kg
km0
We bound I5 as
K
1s Σ
V
B
C2KE + +B Blw +
k= Kb
Σ E [(+b)
+ B Iwo (
will2 + O(?g))
Ka
E BI
C2K3
Σ k=
Σ
E Blwa - O(K)g),
(70)
K=
k=
where the first inequality follows Cauchy-Schwarde inequality.
In 70
we have
K
Kb
K Kb
Σ
B
S
Σ
200 = -0H2
k=K
Substituting the last equality into
(70)
gives
K
K
15 S
Σ
E
[
0003 +
E - w O(K
(71)
k=
Am
Mr
Dividing both sides of by Ko + 1 and collecting upper bounds of Is. 17 and Is give
67
K
E
K Ko +
k=
40,
Σ
E [(a+)(
O(K3K1-200)
E |lws will 2(K2g))
K
Ko
k=Ko
Ko
Ko Koi
+
+ +
+ (eta).
(72)
Ki-01
Define the following functions
T((K) = K -oo +1
E V
K
Ts(K) = K - 6Koo +1
O(K3 - 202 )
+
E
llw - w 0(K)))))
Jom Ko
Kg KoL
To(K) o
+0
O(Eaa)
KI-0i
Then can be rewritten as
Ta(K) < To(K) v2 (2
25

---

Under review as a conference paper at ICLR 2021
Solving this quadratie inequality in terms of TI))), we obtain
(a(K) S (K)(K)))))))))))))( + 4(1 + 7)
(73)
which implies
K
1
K- - Ko +1
k= Ko
00
1
+
Kg K
+ 0
K3
+0
1
Σ
K
E
|w will3
+ ((app).
K2-0l
K202
K
Ko
+
k=
We further have
K Σ
Ka-1
K
K EIVJOO
S
LV +
Σ E ((x)) k=
K
k=1
K
Ko
K
Ko +1
1
L
+
K
K
K
Ko
+ 1
Am Ka
Kg K
1
0
+0
E (0xv)
K
Kn +1
Kg
K
1
Σ
EE E
(74)
K
Ko
+
k=Ko
which completes the proof.
B.3 PROOF OF THEOREM 3
Given the definition in Section B.I we now give the convergence proof of critic update in Algorithm
with linear function approximation and Markovian sampling.
By following the derivation of (40), we have
E ||w2+1
w 112 < (1 2A3x) E lwae - wāll2 (Ci + C2KKnBA Elwax - wkll2
3x
+ 23 E (w> wh. 9 (x())) wk) - ((p2 + Cg
(75)
where Ci = CpLw,i C2= = C5(1 + 7) and C, = 2C3 + 21 Of max(k) पि. 2C + 213
a
Now we consider the third item in the last inequality. For some m E N+, we define M = (Ku + 1)m + Ky. Following Lemma (to be presented in Sec. C.I. for some dm I M and positive constants C2, Cz. Co. C7, we have E (wi - wh (Z(()) wx) - ((0xwwx).
dm
< C. E 110 0x-d dm 112 + +3
Σ
E Bl002-i - 0k- dm 1l2 + C6 [|w - Wk-dm. d + C7mpm-1
i=re
k-1
dm -1 k-1-1
k-1
S C4
Σ
E E100,+1- - 0,112 + Cs
Σ
E B100+1-0011 + Co Σ
Σ
Ellw++1- - wallz + CTkpm-1
E
i=k-dm dm
1=TL j=k-dm
imk-dm
k-1
dn h-i-1
k-1
S C4
Σ
a,Cp Σ
Σ
a,C, Co
Σ
B,Cs + C7ripm-1
i=k-dm
imTk j=k-dm
i=k-dm
k-1
dmn-1 A-i-11
Cjak-dm
Σ
SCp
Cp+ 6p+Csh C5ak-dm
Σ
Σ
Cp Co3k dm
Σ
Cs -1
imk-dm
i=th kmm
imk-dm
< Cidm Cpark- + Cs(dm - -TT) + ChBsm
+ Crmpp=1
dm
< (CrM + CGAl²) Cpax-Ms + CcMCC3Br- + -1,
(76)
26

---

Under review as a conference paper at ICLR 2021
where the third last inequality is due the monotonicity of step size, and the last inequality is due to Th 2 and dm I M.
Further letting mg which is defined in 21 yields
E (wo: whs (Z)(K)) - g(8k, wk))
(C,M* CgMRk Cpak-Mx CoCgMM BK- Mx C-Fpp*K-1
S (C4MK + CsMRk) Cpark- + CGC MM C7ark,
(77)
where Mx = (Ko + 1)mx + Ko. and the last inequality follows the definition of m.-
Substituting
77 into 75
then rearranging and summing up both sides over k MK.,.. K yield
K Σ
K
2A
E lk
wil2 -
E Wk
wille E Bllaat1 Wk+1 12)
+C
Σ
Bk
A Mx
R= Mx
km Mx
I1
12
K
((C4Mx + C&M CR + C&C MN.MMBBB--- Mx + CTax)
k=
1s
K
+
Σ
Ci ak
+
C2KoBB
Ko
E llwe - w 12
(78)
Be
k=MR
14
where the order of I, 12 and 1 have already been given by
(45
46 and 50
respectively.
We bound 13 as
Is (C,MK + CGM Cp
Σ
ax CoCsMM Σ
Bk + Crax Σ 1
km MK
Acm Mx
km M
Kl-m
K1-m2
{G,MK +GM Cp 1-01 + CcCsMMas
+ CTecK((1 +1 K)
1-02
= =0 ((K) log² K)K!-o) + O ((Kooool log K) K)K
(79)
where the last inequality follows from the integration rule Σk k- < b- T-o and the last equality is due to O(Mx) = O(Komx) = O Ko log K).
Collecting the bounds of J1 I2, Is and Ja, and dividing both sides of by Mr + 1 yield
21 K MK +1
Σ
E || - wfll
k Mx
O
(K2102-01144) + OKoK + OK
K
E llwk w
K MM-M +1
k=
K3 log? K
Ko log K k
+
+ +
O
(80)
Kl-02
K
Similar to the derivation of
52).
80 implies
K
1
Blww
will2
MR
+1
k=MK
K2 K2az
[2 log² K
Kn log K Koa
0
+
+
+
+0
K1-00
(22)
Kdi
27

---

Under review as a conference paper at ICLR 2021
Similar to (53). we have
Ko log K
1
B 1|w - will2 - 0
+0
+
I 1ww
will2
K
K
K
MK +
K
1
0
18 ||ws - will2
(81)
K
MK
+
k= k=
which completes the proof.
B.4 PROOF THEOREM 4
Given the definition in section B.2. we now give the convergence proof of actor update in Algorithm wwih linear value function approximation and Markovian sampling method.
I
By following the derivation of 55 we have
(0++)) )) 2 [[)) + E VJ(O)), (6(2())) wx-) 8(((()) vo (8(K),
11
+ Ork E VJ((O)), wi) (w))))()))
LJ
Gga
(82)
2
The item I can be bounded by following (56) as
1 22 [(=)ll (Cs Ko + 1llk wxll2)]
(83)
Next we consider 12. We first decompose
1 = ((Ox). 8 (2)(()) w v (8(R), (6(H)) (()))
VJ((K)) (8(2()) - 8(z(k), 0m)) 00 ((()).
+ E (J((6)) On Wo--, (s()), VJ((K)) E (
(84)
1
For some N+, define M (Ky + 1)m Ko. Following Lemma for some dm I M and positive constants D2, D3, D4, Ds, ((1) can be bounded as
T = T. (V]())). (8()()): - 5(x(k): 0k)) tho--a ((R))(())
Th
D2E Ok-dmml dm 1|2 D3 D3 10x 0k- D4
BI00; On Ok-dmml 1|2
D5xpm-11 - -20 e0p E V
2 - -D2(dm Cxp)ppa D3dm Cp Da(am Tx) Tx
-Doxp=-1- 2C 20 E [
(85)
where the derivation of the last inequality is similar that of 76p.
By setting m = mK in 85 and following the fact that dmng S MM and Th 2 0, we have
(
PyM&Crans- Mx - DDM DDMRCC mx-1 -2CLLvC 20 E [VJ(())
-(D22 + Dr + DDC.MMR) Ci-MMK DsKp -2CyLven 2C wc EIV))
-((02+ DDD)C,,K'' D4C,MM3
OK-MK DsaK 2C 22 E E|| 2|
(86)
28

---

Under review as a conference paper at ICLR 2021
where the last inequality is due to the definition of m-- Following Lemma for some positive constants Da, D7, Dg and Da, we bound 122) as
1 E (1))(
0x) 0x) ((())) VJ((k))
dm
Dg E x 0k-dm dm 112 D7 0k-dm dm 112
Dg
E 110k=s
0x-dm
im
- F (1 y [VJ(()))
Similar to the derivation of 86). we have
1 (Ds + Dy + D&MR) CpMras-MK DgacK - (87)
Collecting the lower bounds of 12 and 12 yields
1 2 -2C - 20 (Eap + +=
-DK0g-Mr - (D3 + Dg)ak:
(88)
where we define Dx = (D1 + Ds) + +D2 + D3 Do + Mr for brevity.
Substituting 83 and 88
into
82 yields
B[J ) [(,)] 20 Cs [| (Ox) la (Esp + 4r 7) + C3 + |w - wxll2))
L Cgaf.
a& (Dxak-MR + (Dg Dg)aR) 20 + au B B
2
Similar to the derivation of 67]. the last inequality implies
([ 2 B[J(O,)] - 4a Css (1)) + + w + (
Ls CRaa.
O (Dxok-My Mx + (Ds + D9)aK)
+ as B|/JJ(0+2)1 2
Rearranging and dividing both sides by yield
1
(EE](O ( (E)(())))) + DRok-Mr + (Ds + Dy)ax + L Gaas.
E J
+ +C
E E C + E - ( 2C Lvefa.
Taking summation gives
Σ E VJ <
Σ
[E] - ([J()))))
akk
R= M=
R= MK
LJ Goa + (Ds + Do)aR
DRak- Mx
k=Mx
4C
Σ
V BIIIJ(ON)
C +
+ +Ell w + OE2
k=MR
Is
+ 2C (K - Mr + 1)et.
(89)
in which the upper bounds of Ia and have already been given by 69 and (1 respectively.
29

---

Under review as a conference paper at ICLR 2021
We bound 4 as
Is
Σ
DKax=Mx* czaz + (Ds + Dy)ax)
km MK
L CaasMMr (Ds Da)ax DKOk-MR* 2
R= Mx
Ls L1O?)
K
Dr +
Σ
Ok- Ok-Mx Mx + + Do)(K - Mx + 1)ak
2
k=MK
K-
Dx + LJ 1/33)
2 0
Σ
0 + (D5+DD)((K Mx + 1)oK
k=0
1 Dx +
LJ c2
C1
K1-0 + cDs + Db)(K + 11)--a
2 1-
O (KK) log K)K--01)
(90)
where the last inequality uses Σ Ek=ah k- -- and the last equality is due to the fact that
O(Dk) = O + MK) = ((KKmk))² + Komx) = OKK log? K).
Substituting the upper bounds of Is. 11 and Is into 89 and dividing both sides by K - Mr + give
1
Σ
E
V
K MK + 1
kmm
4C
K
5 K KMMx +1
Σ
-(K3 +
Σ M=
E Ilw wil2+ O(K 2pp)
b=MK
K3 log" K K
log"
0
+
O(ta))
(91)
Following the similar steps of those in
91
essentially implies
K
1
Σ
E
(
K
MK
+1
k=M
K3 log K
K3 K2
K
=
Kl-mi
K
+0
K
+0
+0
K-
Mr +
E
|kw - 26
+ (Capp)
k=
Similar to 74p. we have
K
K
1
E
O
Ky log
+
Σ
E E
K
K
K MM +
k= k=
K
=
1
Σ
Mx
+ 1
Mx
which completes the proof.
30

---

Under review as a conference paper at ICLR 2021
C SUPPORTING LEMMAS
C.I SUPPORTING LEMMAS FOR THEOREM 3
Lemma 4, For any m and l 2 (Ko + 1)m + Ko + 1, we have
B (ww ((T - F(0k. S C4 18 1|0 Ox-dm 1l2 + C3
E E110k= Ox-dmll 112
+ C B I|ws - Wk dm 112 + C7Aipm-
where dm S (Ko + 1)m + Ko, and C₁ 20 + Co log K + (1 (1-p) (1-p)-1) 1)
C3= C8 Cs and C. 4(1 + + + 20s, C7 = C..
Proof. Consider the collection of random samples {0 Ko- -13, F(k Ko) ... [(k) Suppose I(k) is
sampled by worker n, then due to Assumption 1 { (0 ko- 1)+ 2 (1: (h- Ko) 1() will contain at
least another sample drawn by worker n. Therefore, {I(k- (Ko (Jo+) 2( (Ko 1)m 11)=1;)
will contain at least samples from worker n.
Consider the Markov chain formed by m + samples in ( (Ko (1)m) Lik
((k)
81-m Oa-dmy at-m p
Op at-m+1" ... 81-1 02-d1
P
Pn-do at
P Sc+1.
8t-m+1
al11
St
where (st, Ce S1+1) = (s))) a(k), (x)) and {dz (d is some increasing sequence with do == Tk.
Suppose Ok-dm was used to do the kim th update, then we have Tt-m = [(km) Following Assumption
I we have Tkim kmm (k d I Ko- Since I(k...) is in (I(k-(Ko+ .... I(k)]. we have km 2 k (Ko + 1)m. Combining these two inequalities, we have
dm S (Ko + 1)m + Ko-
(92)
Given (8t-m- am-m; 8t-m+11 and On dm we construct auxiliary Markov chain as that in Lemma
8t mm
Re-dm Ot-mm m
P mt-m+1
8e-dm 0r-m411 8t-1
8k 6k-dm Ūe-1
_ St
Ok dm
Tz - 3141.
For brevity, we define
A A1 0,w) = (w - wp. g(r, g(0ww))
Throughout this proof, we use 0, 8', w. w', , x and Tt as shorthand notations of Os. On Pm-dm- Wk. We dm.. I, and 3, respectively.
First we decompose A (I, 0,w) as
(r, 0,w) = Ai O, w) A ( 0',
()+ w)
A (1 0',
(x, w) - AI 0' ,','')
h
I2
+ A 0' (,,') A (T. 0¹ w/) + A (7, (',))
(93)
1a
14
We bound I in (93 as
A (xr, w,w) A ( 0' w) = (w - wo--w wp. g(0, w)) - (ww wp: (ww g(0',
(w wh 00 F(f, w)) -w- 1 7(0, w|)l
kww wp. ((, o(0,w)) (w wp. g(I,w) 5(0', ((),)))
(94)
For the first term in (94) we have
( wp. g w) -(0,ww)) w)) (w - (w-w (l g(0,w))l
1w w g(r w) ( ())
< l/ي - wer 12 (0,ww)]
2Css || wgrl22
2Cs Inn. 100 8'112.
31

---

Under review as a conference paper at ICLR 2021
where the last inequality is due to Proposition 2
We use 0' as shorthand notations to represent that 8 por, a To,, s ~ P. For the second term in 94 we have
[w ( w) u(0,w)) (w wyr ((r,w) g(0', ww)l
1wo War, "og.g'0'' .) g(0,w)))
< || wig 12 10:1221100'''4 .w - F(0,w)l:
I 2R ,w) g(0 1l22
2R
Lo(a (3( E [o( - E and
I 2R sup 11 w) Mlello & Te @ P - pe 3 To @ Pllzv
22R & TO 2 - 10 0 n0 1 Pllrv
-RR, CaRTC NNW @ ne & P, P4 no 8 P)
S 4R + log, A
p) ||0
0 12,
where the third inequality follows the definition of TV norm, the second last inequality follows 32 and the last inequality follows Lemma A.I. in 17].
Collecting the upper bounds of the two terms in yields
1 S [2Cg Tew + 4 C& (1 + log, K
+ (1 - p)] 110 - -0112
Next we bound [ in 93 as
E[/2]
| (xx, 0' w) A (2, 0,,0
EE (w W g w) 5(0', w)) - (/w' wag ((,, 3(0',w'))
s E (w W g02, w) g(6' W)) - -(w- (w-wi - g(2, g(0' w())
| wa. g(,, w²) g(0', w/)) -(w' w.. g(2 g(0 w
(95)
We bound the first term in 95 as
E Kw g(x,w) g(0', w)) - (w war g(z, g(x,w²) g(0', (,"') )
= E ((w - ((x, g(z,w() + w') 3(6'.w0) ww)l
< 2R (Bllg(z,w) (0) + 10 w5) g(0', (()))
E 19( 10 w]] )
< 2R,
E [l)g(I, 0(2 w/)l2 + E
E 3-
19(2, wa)l zng
2R [B]((p(ss) - (s)) (w w')ll + E
E [[>0())) ((s) [[]))) (w' -w)( mod
< 2R (11+ || w'll2
+ (1 + 7) E -| w'll2)
= 4R. (1 + || 112
We bound the second term in (95) as
E (w ww.
((,,w") w g(0',u') wu')) - (w-' - wp - '''0'''''
= E (w w/, (6,, g(0' ,w'))l
< 2C, EE ||ا 112
Collecting the upper bounds of the two terms in 95) yields
E < (4(1 + R Re + 2Ca) E ||l - w'll2
We first bound Is as E[La 0', w/, St mt]m+1]
= | 1 (z. 0' - -i w')'' w st-m+1]
< E A (I, 0¹ w') w/ s+1+ E E[A, "')i( "u'l',''',, st-mll
< sup Dr 0' IP(x E -16 w/ s1) - P(o E -16', 88-mm)))
< Cadrv (P(x 10 sm)) E -10 s)-m))))
(96)
32

---

Under review as a conference paper at ICLR 2021
where the second last inequality follows the definition of TV norm, and the last inequality follows the fact that
A1 0', w')l || - wi. 12lllg(0,, g(0', w') I Cs
By following 22 in Lemma
we have
drv (IP(x E 100, 3/mm++)) 1),, P(ū E -10", 8t-m++)) - |A
E [110-1 - 0k-dm 1121 86-m+1l.
Substituting the last inequality into (66). then taking total expectation on both sides yield
E [a] S T
Σ TE 10 Ok 0k-dmll2
Next bound 4. Define I 3') where 3 po, To and 5. P. It is immediate that EIA1 1'' w', 81-m+1] (w' wag B[g((T w/) ,'' , m =00',(0'))
(w' wa. 700' w/) ,''''')))
(97)
Then have
E| w/ 8t m1
E [[A] (T, 0' 0') - (1 0' w') 00' w/ st-
E | (I, 0 w/) 16' w 8t-m+1 E|A (I, 0¹, w') 1100,, w', semmill
sup A1 (I. f w |P E -10', 8t-m+1) P E .66 mlmmtl)
I CRdrV (P( E sl- P(T E . 8 stmm11)
&R.Cadrv (P(5 E -10", 8t-m+11 ), por @ m ? p)
(98)
where the second inequality follows the definition of TV norm, and the third inequality follows (97
The auxiliary Markov chain with policy nor starts from initial state 8t-m+ and 8 the (m 1 1)th state on the chain. Following Lemma]
1 we have:
drv (PI(T E 110 8t 8tmm++), Po0 @ ko 60 P)
dTv (IP ((5,, ãe 3411) E -10 st-++1) per & Te 2 P) S kp" =pm-1
Substituting the last inequality into (98) and taking total expectation on both sides yield
E[4] < Canp"
Taking total expectation on 93 and collecting bounds of I1, Iz. 13, Ia yield
dm
E (x, w)]
C₁ E 0x 0p-dmml 112 + C3
Σ
E 10 02 0x-dmll
1=
CG 1o Wk-em 1l2 C7npmt11
where C4 = 2C + 4R, Co (1 + log, x + (1 - p) -)), Cs = 4R Co
4(1 + BR + 20, and C7 == Cs.
C.2 SUPPORTING LEMMAS FOR THEOREM
Lemma 5. For any m and 2 (Ko + 1)m + Ko + 1, we have
E (VJ(OL), (8(0r())) wi) - 5(((1)) 0k)) Von-re (408))(0))) 2 -D₂ - 02 0x-dmll2
dm
DD E 110 On 0k-dm111 - D4 E 11-=
On De-dm112 D5 - 2C E
where D2 = LL Cr. D3 = (2 CL + LV) + 7) + 20 ) D4 =
2TyCo.CaAA and D3 Csy
33

---

Under review as a conference paper at ICLR 2021
Proof. For the worker that contributes to the kth update, we construct its Markov chain:
OR- Rm-dm mm-m E, 82 m
Pk-dm- 11 at-m++1
02-d,
Oa-da at P 81+1;
8t-m
8t-1 Or11
where (st, 0t, 81+1) = (8()), a(k); (1))) and {dz} is some increasing sequence with dg == Tk. By in Lemma 4, we have dm S (Ko + 1)m + Ko-
Given (8t (5t-m; Ot-my 8t-m mt-m+1) and 0k-dm- we construct an auxiliary Markov chain:
0e-Am Oc-m Lx sc-m+1
Oe-dm dc-m+1 58-1
6u-dm āc-1
P St Or-dm ās P 8141.
St-m
First we have
(vJ(OL). ( 1o61- (5(4), (())))
((z()))))))
-VVJ(O)), (S(r(H)) 5(5(())00)) 0k)) (vto. i (s(k)) vu dm (s(0))
+ (VV((O)) (8(0)1) wi) -0((()) 0k)) Q/ (1(6).
(99)
We first bound the fist term in (99) as
(J(()), wi)) - ((z
0k)) 8x))
(Wo--r (8(K)) ((x)) - 1o0--n ($(8), aw)))
2 (1))((6) la ((F(M)) wf) 8(5(M) 0% 01l (S(M); ((w)) 10, - (5(N). a(x))ll
2 - -11((0))l2 (16(m()) wf) + (6( 0w)) (x)l
|| (8(K) a(k)) - v (5(k), (x))ll2
2 Lv ((() + (6(r)), 11 (s(M), a(x)) th (8(M):
z - 2T. Callvo0 (a(K), ((w)) - v',, am (+(R),
2 -22 Lo 08110=-Z - 0x-dmll 112.
(100)
where the last inequality follows Assumption and second last inequality follows
((x, S [n(x)) + 7 (l2la=l= + [10(6) ll2 S Tmax + (1 + R) S Csi
1,(x; 0) S [n(x)) + > VT (s')l 1 + VV (8) S Tmax + (1 + +7) Tmax
S Cs.
1
Substituting (100) into (99 gives
(((K)) (6()())) - 5(F(M); 0k)) who (#(H): (s()).(()))
2 Le 0x-ddml ll2 + (VJ(Ok), (B(=(a) - 8(I(K): 02)) von-en (8(K): a(n))) (101)
Then we start to bound the second term in (IOI). For brevity, we define
A2 0) (J)()), (8(z, 6(1, 0)) -om (8,a))
In the following proof, we use 0, 8', wg. war x and To as shorthand notations for lg. 0x-dm Wh. wi-dm. , and o, respectively. We also define E = (3, a. 3'), where 3 ~ na. T ~ z and 3' ~ P.
We decompose the second term in [OT as
A2 = A2(x, 0) - A2(x, 0¹) + A2 0) - Ae(ā, 0") + A2( 0¹) A2( 0') Ag I
4
12
We bound the term I as
h = (VJ(O), (8(x,w)) - 5(2z, 0)) tha (s, (8,a)
- 5(2,, 5(x;,") 00)) (VJ(O)), (5(z,w)) - 6(z, 0)) sher (s, a)) (8,x0),(((,,,))))
(JJ()',, (S(2. (((),u))) (5(7))(((
vor (s)
= -(VJ(O), (5(z,u0) _(x, 0)) tho (8, a))
+ (VJ(('), (8(1, - 5(z, (2: so (s, (s.a)) - (V.(("), (6(2,ub) 6(x, 8)) the (s,
34

---

Under review as a conference paper at ICLR 2021
For the first term in 1,, we have
(J(()), (6(z,w))) 5(2, 0)) wo (s, a)) (VJ(O)), (8) 8(2, vor (s,
(V](0) - VJ(0), (6(x, wp) - 6(2, 0) si (0r(s, a)) 2 -IVJ](0) - (=((0))2110() wz) 5(2, 1221 (s, a)ll2
= -CJ(C VJ(("))
2 L2 12
where the last inequality is due to the L, LipLsschiitz of policy gradient shown in Proposition ! For the second term in 41, have
VJ('),
(0000)(((1;1))))))))))( (6(x,40) - 8(x, 0) the (8, a)) ----VVV1 (VJ(O"), (8(z, wō.) o(x,0') vo (8,
(J(()), (6(z, wF) - 8(1, W(r + 6(x, 8² - 6(2; 0)) (8)
2 - Lr w8) 8(x, wg) - 8(r, 0') - 8(x, 0)
Lv TTo(s') [w@ w + (ss) (wg. wß) + 7 rg (s') =o + (s) - Va (s)
LVC (rillsg - wigh [l2 |w wille 7 >/V (s') - VU (s') 1V (8) Viarr (s))
Cv (1 0' lla | 0'1l2 + yIv 11 + Lv |10 11))
-L + (1 7)110 1'112.
where the last inequality is due to the Lupsiiischizz continuity of wi shown in Proposition 2 and
Ly-Lipschitz continuity of V (s) shown in Lemma Collecting the upper bounds of In yields
4 2 - (2C + Lv
(1+++)))) 110 - 0'112.
First we bound I2 as
E
12'000 8
= E (1x 0¹) - A2 (0)'0'00'' 81-m+1]
N JE (1r, 03) 81 81-m+1] - E [ (T. 0') 0', st-m+i]l
2 sup A2(x. 80) P( E 166 s0-m11) - P(ž E -10" 110' s1-m+1)llv
2 -4L C. (P(x E 18' s1-m)),, P(T E .10', st-m++))
dm
2 2-2LyC Σ E1 - 22 || 0¹ stmm
(102)
where the second inequality is due to the definition of TV norm, the last inequality follows Lemma 2 and the second last inequality follows the fact that
22 in
[ 0') < VVJ 8(x, wyr) - 6(z, 6' (s, a)lla S 22Ly
(103)
Taking total expectation both sides of (102) yields
E[12] >- -L
E El On 02-dmp 112.
Next bound T3
E 1/ 8t m1]
= E [A2(2, -2 (0,,,,0")),,,mmm++)) stmm+1]
N IE (ū, 0') 0² st-m+1] - E 1A2 0') st-mlllll
2 sup (z 00) [P(x E -10' 8+-8))+1) - P(x E .00' st-m+1)llvv
N --LL C Cadry (P(2 E -10', st-m+1), pg X T& P))
(104)
where the second inequality is due to the definition of TV norm, and the last inequality follows 103
35

---

Under review as a conference paper at ICLR 2021
The auxiliary Markov chain with policy Ter starts from initial state 81-m+1, and St is the (m 1)th state on the chain. Following Lemma] [ we have:
drv P( -16", st-m+1), po 2 Tor P)
=drv ((5,, ae 8e+1) E -10", 8t-m+1) po & ny & PP) S kp" kpm-1
Substituting the last inequality into (104) and taking total expectation on both sides yield
E E[1a] 2 -4Lv bp Conp""
We bound 1
[[/4|0']= = E [( (VJ(O'), -(xx, sia (s, (0) 0¹
M -C | wij) - 6(z, 8¹) 8¹
-Co1VV.(00)12 |/> (0(3)) T wwg - V (3 + Vi (3) - 2(3) T wirll 11 0¹
-Cw1lv./00)la (7 [10(s') WT. Vay 6/'l 07 + E [IV (s) w/: 1| (T)
(VV [|((3")T w6. V (3')
(3') 2/ 0¹] + E [IV (3) (55) wT. 1 0r)
7 V 3'mpper
E [6(3))ug. Van (8)12 (5)11
E srupeg
(c)TTs)) Tw 12 V (8) (55)
2 2C (=((6")l2Eaa))
where the second last inequality follows Jensen's inequality. The last inequality further implies
B[4]] 2C E |1 [|V)(0)) VJ(0))-v((())) VJ())==
Cap E (J VJ(()]12 - Cap (
2 2ap E ( VJ(0)] 2C E [V](() - 20 Ly
Lc Jeapp E |0 - 0'112 - 2C E [()]( LV
where the last inequality follows Proposition
Taking total expectation on both sides of (OT). and collecting lower bounds of /1, 12. I3 and 1 yield
E (VJ(OO), (8(m(1)) w/) (1)(1)) vio, vu (((()))
dm
2 DD2 10 0k 0k-ddml 112 D3 D3 - 0k-dm D4
E
11 - Ok Ok-dmml ll
T=
-Dampm=1 - -C 2C E ((
where D2 LL D3 = (20 + Lv (Iw + [v) + 20 Leapp)) D4 2Lv Ca and D5 CgCs
Lemma 6. For any m 2 and 2 (Ko + 1)m + Ko + 1, we have
E (VJ(Ok)) 0z) 02)o (S(k): a(k)) vJ(Ok)) 2 -Dg E 110 On dm-1m1l2
dm
- 1,EE 0k 112-D2 Dg
E El00-1 0x-dm - --grgapp-- (
where Do = LvCgLog Dj == C,L, + (1+ C + 2L + La Ds =
Lv(C,, +.C,+LVv)lo Lv) Dg = (C, Lv).
Proof. For the worker that contributes to the kth update, we construct its Markov chain: P. Ou-dg at 8t+1s
O dm Ot-m
Pk-dm-1
02-di
8t-m
81 m1
01-mn
at-1
36

---

Under review as a conference paper at ICLR 2021
where (st, de, S1+1) (s( a(j), s(1)) and {dy J is some increasing sequence with do Tk. By (92
in Lemma we have dm S (Ko + 1)m + Kg-
Given (st-m: m st-m+1) and Ok-dm: we construct an auxiliary Markov chain:
Oe-Amy Om-m 8t-m+1
Or-dmy 0c-m+1 ... 5c--
Bx-dm ae-1 - 5t Oa-am as P 81+1.
81
First we have
VJ(OL); 0n
0k) ((0)))(()))))) - vJ((O))
(VJ(O)),&(T(A)) 02) (voL_, (5(A), a(x)) V4 am (5(8), (())))
(T](()))(((())) 0k) (k))bon-da (8(K): vJ(O)))
(105)
We bound the first term in
105 as
(J()),, O&) (DOL- (5(1); ((k)) db (#(K), (()))
2 - [VJ((N)]22 (((()()) (6))l2/1000- (8(K): ((k)) - 10l-am (()))l
- -VV1)((0()) 0k) 02) 1211100, -n (1(8), (())))())))))))))))())))))))(( 1ho, (8))):
-Iv (s(A), ((k)) 1h am (1(8); 1(2))ll
-Ly 0k-dmll 112.
(106)
where the last inequality follows Assumption 3 and the second last inequality follows the fact that
10(2, 0) S [r(=)) - >I (s)) + V (s)l I mmax + (1 + 7) Tmax
1- S Cs.
Substituting (106) into 105 gives
VJ((O). 0x) vo (S(K), (xx)) - VJJ(O)))
2 CpCCoLll0 Ox 0x-dm ll2 + (VJ(()), (( Ox) (8(K). - -JJ(k))) (107)
Then we start to bound the second term in 107 For brevity, we define
As(r, (0), ((x, 0)vo, (s, VJ(O))
Throughout the following proof, we use 0, 0r, and T as shorthand notations of 0g. az-dm dn and Fe, respectively.
We decompose As(r, 0) as
Aa As(2,0) As(xx, As(x, As(T, 0') Ag
12
We first bound I as
Mh - As(x,0))
((2,
< (1T3(0)).022.0))oo)ss..)
< (IV.(00).662.0)0)0ss.)))
((,, || (108)
37

---

Under review as a conference paper at ICLR 2021
where the last equality is due Ly-Lisschitz of value function and L LipLschhit of policy gradient. We bound the first term in (108) as
KV (O)( 8(z, () - (111,)))))(
S -
+ +1177000065550000000000110100110 (sb,
VJ(0')]2
=LvCw Va (s Vig (s) (s) + -)
L (r (7. VT (8') + V (8) VG. (8)] + Cpl v.(0))
LvC (rlv 8'112 + Lv |v1 - -ll) + CpL, - 0'112
(C,Ls + 1) Cv) 10-1-11..
Substituting the above inequality into (088) gives the lower bound of IT:
1 2 (CyLs + +1+ Lo) 110 0'12-
First we bound 12
E E[
1 E (2, 0¹) As st-ma11
- A 3t-m+1] - ('' st-m+1]l
2 sup Aa PP(( 81-))))m+1) PP E -10 st-m+1)llzv
x
2 (I, - Lv)dry (P(x E 100 8 8t-,sm IP E -10" st-m+1))
(Iv(C + A
E [10 0x-dmll22 8 smm- Σ
(109)
where the second inequality is due to the definition of TV norm, the last inequality is due Lemma [ and thesecond last inequality follows the fact that
22 in
(a, 0') = J(0)ll (11 0)ve, a), + [[V(()))2) & Lv + Lv).
(110)
Taking total expectation on both sides of (109) yields
1 N - (C + LV
E B1 0x 0
Define I = 2,,",,),, where do,, a oe and 3' P. Then we have
E = [ 0*) (z) E
(111)
We bound the first term in as
E A 8* A3 8t-m+1]
2 [ 0') st-m+1] - E [A 0') st-m+1ll
2 - sup Aa(z, (z, 0') PT E st-m))++1) - PTT E -10 st st-m+1)llzv
2 (C, + Lv)dTV (P(T E -10 s m 1), [P 100,, st-m+1))
(L, + Lv)drv
(P(6 110 st-m+1), de 2 गe &
-L.v + Lvvdrv (P(T E 100,, . st 140 3 To. P)
(112)
where the second inequality follows the definition of total variation norm, and the third inequality follows (110). The last equality is due to the fact shown by ( that (.)r()) = dor (-), where par is the stationary distribution of artificial MDP with transition kernel P(-|s, a) and policy wo-
38

---

Under review as a conference paper at ICLR 2021
The auxiliary Markov chain with policy Ter starts from initial state 8t-m+1, and St is the (m 1)th state on the chain. Following Lemma]]
[] we have:
drv (p(ē E 100,, s--+1)); po 2 Tg. 2 P) = drv (P((5) S641) E s1-m+)) por @ Tg. @ P)
< kpm--!
Substituting the last incquality into [12 and taking total expectation on both sides yield
E [As
0") (T 8'] 2 -2v (Cp + Lv)mp"
Consider the second term in 1111. Note its form is similar 59 so by following the derivation of 663 we directly have
(T, (T, 8'] = E (VJ(6)) 8(T, We (3.0) (B. - 2 8 (1 B
which further implies
B (T, 0')
-8 Tax (1 [|
T (1 V.]('' - - 8 [|
+ mesommaxxall Ly 7) E 012- &C (1 --)) VJ((|l
where the last inequality follows from Proposition
Collecting the lower bounds gives
[[[T] 2 (C, + Lv)ss""- mm -000--)000 (L, 0112 1 -
Taking total expectation A2(x, 0) and collecting lower bounds of Z,, 12, 13 yield
E (a, 0)) (Cpt. + (1 + T2 2L T., 80 max [. 7)) E 1 02 - 1/2
dm
Lv + Lv)
0x-dm 2Lv(C, Lv) 8 - -) [( E 11 Σ
Taking total expectation on (00 and substituting the above inequality into it yield
E VJ((O)), ((I()) 0x 0x) ((m))9m)) - v.((Ew)) 2 E 10x 02 dmdll2
D/0 Ok-dm |12 D2
E El Ok-dml12 D- max (1 [J](4ll))
T=
where D6 = LvCoLyn Dr = C,Ls + +1+ L3 + Ly + 80 m - 7), Ds
Ly (Cp + Lv I.. Dg = 2I (C, +.v.
C.3 EXPLANATION OF THE APPROXIMATION ERROR
In this section, will provide justification for the circumstances when the approximation error Capp defined in 14 is small.
Lemma 7. Suppose Assumption 2 and 4
hold. Then it holds that
Capp
S max PER
V
E. grupen
VVo Vaz(s) + 4r (X-1 -2 2 (1+1og, x -1 + (1 7))
1 -
(113)
where wi the critic stationary point of original Markov chain with policy my and transition kernel P.
In 113.. the first term captures the quality of critic function parameterization method which also appears in previous works [4] [3] [7]. When using linear critic function approximation, it becomes zero when the value function V=, belongs the linear function space for any 6. The second term corresponds to the error introduced by sampling from the artificial transition kernel P(-|s, = (1-7)P(-1s,d) vn(.). For a large close to 1, the artificial Markov chain is close the original
39

---

Under review as a conference paper at ICLR 2021
one. In this case, the second error term is therefore small. This fact also consists with practice where large is commonly used in two time-scale actor critic algorithms
Before going into the proof, we first define that:
Ag,o P'
(o(s)(r0(s') - o(s)) "
60.s aa s' [r(s, a, s (s)),
E
where jig the stationary distribution of the original Markov chain with my and transition kernel P.
Proof. Recall the definition of the approximation error:
Eapp
max
E
(V Vug (8)
BER
snopt
where μi is the stationary distribution of the artificial Markov chain with my and transition kernel P. and wg is the stationary point of critic update under the artificial Markov chain.
We decompose Capp as
Eapp
max
E scupta
ViO (8)
Vag (8) + Vag (s) - Vazz (s)
BER4
max
E stupto
Vi (s)
Vag (s)12 +
max
E erupa
VVz (s) - Vaz (s)
(114)
DER4
Exp
where the first term corresponds to the function approximation error éta and second term corresponds to the sampling error Esp-
With A, b and A, 5 as shorthand notations for Ag,u. b and Āg, b respectively, we bound the
second term in (114 as
(Vags)) Vs)(s)
= [d(s) w/ (5s) [aaaaa)) wb/
$ |A-Lb b - A-1b/12 6-
AA-6 A A A A
A A- 1
$ ||A'(6 b)]l2 + ||(A-) - A 1-/0
S A -=11 b1|2 + Tinax ||A-1 - 1
A ||6 6112 Tmax
I|A (A 1A)A 111
$ X ||b b112 + Tmax
A A |A-Al1g
(115)
We bound the first term in last inequality as
bb B
E
ar a, sp()(
E s~
|r(s (ss,,,s')(0))
I sup ( a (')(s) 3 no
no Tg PlIav
< 2r 2maadrv (Mg To @ P. ni & ne P).
(116)
We now bound the divergence term in the last incquality as
drv (mo & Th P. To
To P)
= -/ Σ
:ES AEA BES
El
JOES aEA JES
<
Ho(s)oo(als) /
P(s'|s, - P(s P(s'1s, - 6E8
(MO(s) po(s)] (117)
SES AEA
40

---

Under review as a conference paper at ICLR 2021
We bound the first term in
f ((s' s, a) P(s ((s')ssa) a) = =1 (1-1)
/
[P(s'|s,a)
- - - -1).
(118)
EES
E'ES
Following 39 Theorem 3.1J. I. the second term
117
can bounded as
/ J (s((s) po(s))
log n
sup
Σ To(als)
-P((11s))
EEES
/
logp fi
sup
Ta(as))
(p(sss) a)
p
J'SS
S
log,
(1 7),
(119)
p
where the last inequality follows (18 Substituting
118 and
1199 into
117
gives
1+ log, n -= + -11++
drv (Hg
2
ne
P.
2
1- (1 - 7).
Substituting the above inequality into 116p gives
b112 S 4r max
[+ log, A
1 1-p) p (1 (1-7).
(120)
Similarly, also have
AA
Alla
4r max
1 1+ log x
(1-
(121)
Substituting 120 and
121
into
115 then substituting
115 into 114) completes the proof.
D EXPERIMENT DETAILS
Hardware device. The tests on synthetic environment and CartPole was performed 16-core CPU computer. The test on Atari game
in 4 GPU computer.
Parameterization. For the synthetic environment, we used linear value function approximation and tabular softmax policy (3).. For CartPole, used a 3-layer MLP with 128 neurons and sigmoid activation function in each layer. The first two layers are shared for both actor and critic network. For the Atari seaquest game, used convolution-L.STM network. For network details, see [40).
Plyper-parameter
Value
Number of workers
16
Optimizer
Adam
Step size
0.00015
Batch size
20
Discount factor
0.99
Entropy coefficient
0.01
Frame size
80 x 80
Frame skip rate
Grayscaling
Yes [-1,1]
Training reward clipping
Table 1: Hyper-parameters of A3C-TD(0) in the Atari seaquest game.
For the synthetic environment tests, we run Algorithm | with actor step size ag (1+ and critic step size 3x = (1+4)0.4 In tests of CartPole, we run Algorithm with
Hyper-parameters.
0.05
0.05
minibatch of 20 samples. We update the actor network with step size of og [T+R)o
0.01 and critic
network with step size of 3g (I+A).. See Table for hyper-parameters to generate the Atari
0.01
game results in Figure
41


Reviews:
[{"review_id": "mbcU4eABwPk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 studied the two time scale A3C in discounted MDP based on recent development in the finite sample analysis of A2C. The sample complexity result in this paper matches previous result in two time-scale A2C in terms of the dependence of \\epsilon, and this paper further shows the benefit of \"linear speed up\" brough by the structure of A3C. Given the practical usefulness of A3C, the result established in this paper is meaninful.\n\nAlthough most of the technical proof seem correct to me, the algorithm studied in this paper has the following issues.\n\n(1) In the policy evaluation part (critic), samples are generated according to the the \"hybrid\" transition kernel \\tilde{P}, which is not reasonable. The purpose of the policy evaluation is to evalue the value function, thus the samples used by the critic need to follow the transition kernel P not \\tilde{P}. Otherwise, the value function learned by the critic would be different from the pure TD(0). I understand that the the author adopt this sampling method because the author want to make a \"two time-scale\" algorithm to study here. However, under such a sampling startegy only the actor can obtain appropriate samples. In fact, it is very difficult to design a two time-scale algorithm for a discount MDP, as the transition kernel required by actor and critic are different. I suggest the author to study \"averaged MDP\" instead. In the averaged MDP, both the actor and critic can share the same transition kernel, which make designing a two time-scale algorithm possible.\n\n(2) Another problem is the projection used in the critic. The projection in linear SA is a practical problem, as we do not have prior knowledge of the radius before we run the algorithm. The projection issue has been criticized by many researchers' in the RL community in the last few years thus should not be ignored here. In fact, the projection issue can be avoid if the author adopts a nested-loop structure, and I think the sample complexity result can even be  improved in the nested-loop setting. Thus I suggest the author to used nested-loop structure to avoide this projection issue.\n\nOverall I think the paper is well written. However, considering the two problems that I mentioned above, I think the current version is not ready to be published.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hjlzbveTWb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 revisits the A3C algorithm with TD(0) for the critic update to provide better theoretical analysis of A3C. A3C-TD(0) achieves linear speedup and it also matches our intuition. To show the empirical results, the authors provide convergence results of A3C-TD(0) with Markovian sampling in synthetic environments and speedup of A3C-TD(0) in CartPole and Seaquest.\nIn this paper, the theoretical and experimental results show that using multiple workers in parallel improves learning speed without loss of sample efficiency. I think it is a valuable research direction. \nHowever, A3C-TD(0) is limited compared to A3C because A3C-TD(0) does not use multi-step TD or TD(\\lambda). Moreover, the authors use only two gym environments, which seems insufficient.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-ivt84HV2KR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 studied the convergence rate of the asynchronous actor-critic algorithm (with linear value function approximation)  for RL. This paper showed A3C-TD(0) has O(\\epsilon^{-2.5}/N)  sample complexity per worker where N is the number of workers., which means the per-worker sample complexity can be reduced linearly with respect to # of worker. \n\nIn general, this paper is well written and easy to follow. The sample complexity results are insightful.  Could the authors address my following comments/questions?\n\n(1)$w_\\theta^\\ast$ or $w_{\\theta_k}^\\ast$ are never formally defined. Please clarify the notations properly. \n(2)Unlike \"linear-speedup\" in setting such as convergence rates for SGD,  the linear speedup is not so \"idea\". The gradient norm has a constant error floor term $O(\\epsilon_{app})$, which eventually dominates the error as K increases.   To my understanding, an error term is unavoidable because the valuation is approximated by a linear function.  I wonder if the results in the current paper can be easily extended to cover the situation where no linear approximation is used, in which case I expect the error terms disappears totally. \n(3)  This is also related to (2). It is reasonable that the critic-convergence (Theorem 1) uses  a drifting $\\theta_k$. But if we look at the actor and critic together, our goal is to converge to a fixed policy, am I right? If so, is it necessary to define $\\epsilon_{app}$ in (13) as the error regarding to the worst \\theta? (In other words, can we remove $max_{\\theta\\in R^d}$ in (13) and define $\\epsilon_{app}$ using a single $\\theta$? By doing that, $\\epsilon_{app}$ can be much smaller)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although the reviewers found the paper well-written that analyzes a relatively popular algorithm (TD(0) version of A3C), there are concerns regarding the novelty of the convergence results given those for A2C, the comparison of the results with those for A2C, and the sufficiency of the experiments. Although the authors addressed some of these issues/comments during the rebuttals, it seems none of the reviewers is excited about the paper and there still exist concerns regarding the novelty of the results and how they are compared with those in the literature. I would suggest that the authors take the reviewers' comments into account, have a more comprehensive discussion about the relation of their results with those in the literature (two-time scale algorithms), and prepare their work for future conferences. 
Decision: Reject