Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
Authors: Zuyue Fu
Zhuoran Yang
Zhaoran Wang
Venue: ICLR 2021 Poster (2021)

Abstract: We study the global convergence and global optimality of actor-critic, one of the most popular families of reinforcement learning algorithms. While most existing works on actor-critic employ bi-level or two-timescale updates, we focus on the more practical single-timescale setting, where the actor and critic are updated simultaneously. Specifically, in each iteration, the critic update is obtained by applying the Bellman evaluation operator only once while the actor is updated in the policy gradient direction computed using the critic. Moreover, we consider two function approximation settings where both the actor and critic are represented by linear or deep neural networks. For both cases, we prove that the actor sequence converges to a globally optimal policy at a sublinear $O(K^{-1/2})$ rate, where $K$ is the number of iterations. To the best of our knowledge, we establish the rate of convergence and global optimality of single-timescale actor-critic with linear function approximation for the first time. Moreover, under the broader scope of policy optimization with nonlinear function approximation, we prove that actor-critic with deep neural network finds the globally optimal policy at a sublinear rate for the first time. 

Published as a conference paper at ICLR 2021
SINGLE-TIMESCAA ACTOR-CRITIC PROVABLY FINDS GLOBALLY OPTIMAL POLICY
Zuyue Fu Northwestern University
Zhuoran Yang Princeton University zy 60pr inceton edu
zuyue. fuêu. www.nowwwweeenneeeee edu
Zhaoran Wang Northwestern University shaoranwang@@maii..... com
ABSTRACT
We study the global convergence and global optimality of actor-critic, one of the most popular families of reinforcement learning algorithms. While most exist- ing works on actor-critic employ bi-level or two-timescale updates, we focus on the more practical dingle-timeseee setting, where the actor and critic are updated simultaneously. Specifically, in each iteration, the critic update is obtained by ap- plying the Bellman evaluation operator only once while the actor is updated in the policy gradient direction computed using the critic. Moreover, we consider two function approximation settings where both the actor and critic are represented by linear or deep neural networks. For both cases, we prove that the actor sequence converges to a globally optimal policy at a sublinear O(K 112) rate, where is the number of iterations. To the best of our knowledge, we establish the rate of convergence and global optimality of single-timescale actor-critic with linear function approximation for the first time. Moreover, under the broader scope of policy optimization with nonlinear function approximation, we prove that actor- critic with deep neural network finds the globally optimal policy a sublinear rate for the first time.
INTRODUCTION
In reinforcement learning (RL) (Sutton et al. 1998). the agent aims make sequential decisions that maximize the expected total reward through interacting with the environment and learning from the experiences, where the environment modeled as a Markov Decision Process (MDP) (Puterman) 2014). To learn policy that achieves the highest possible total reward in expectation, the actor-critic method (Konda and Tsitsiklis 2000) is among the most commonly used algorithms. In actor-critic, the actor refers the policy and the critic corresponds to the value function that characterizes the performance of the actor. This method directly optimizes the expected total return over the policy class by iteratively improving the actor, where the update direction is determined by the critic. In particular, recently, actor-critic combined with deep neural networks (LeCun et al., (2015) achieves tremendous empirical successes in solving large-scale RL tasks, such as the game of Go (Silver et al. 2017). StarCraft (Vinyals et al. 2019), Dota OOenAA 2018). Rubik's 's cube (Agostinelli et al., 2019 Akkaya et al. 2019), and autonomous driving (Sallab et al. Li for a detailed
survey of the recent developments of deep reinforcement learning.
Despite these great empirical successes of actor-critic, there still an evident chasm between theory and practice. Specifically, to establish convergence guarantees for actor-critic, most existing works either focus on the bi-level setting or the two-timescale setting, which are seldom adopted practice.
In particular, under the bi-level setting (Yang al.) 2019a; Wang et al., 2019 Agarwal et al. 2019
Fu et al. 2019 Liu et al. 2019 Abbasi- Yadkori et al.) 201 9a b Cai et al. 2019: Hao et al. 2020
Mei et al. 2020: Bhandari and Russo (020), the actor is updated only after the critic solves the
policy evaluation sub-problem completely, which equivalent to applying the Bellman evaluation
operator to the previous critic for infinite times. Consequently, actor-critic under the bi-level setting

---

Published as a conference paper at ICLR 2021
is a -loop iterative algorithm where the inner loop is allocated for solving the policy evaluation sub- problem of the critic. In terms of theoretical analysis, such a double-loop structure decouples the analysis for the actor and critic. For the actor, the problem is essentially reduced to analyzing the
convergence of a variant of the policy gradient method (Sutton et al. 2000) Kakade 2002) where the error of the gradient estimate depends on the policy evaluation error of the critic. Besides, under the two-timescale setting (Borkar and Konda, 1997; Konda and Tsitsiklis) 22000; Xu et al.] [020] Wu et al., 2020] Hong et al. 2020), the actor and the critic are updated simultaneously, but with disparate stepsizes. More concretely, the stepsize of the actor is set to be much smaller than that of the critic, with the ratio between these stepsizes converging to zero. In an asymptotic sense, such a separation between stepsizes ensures that the critic completely solves its policy evaluation sub-problem asymptotically.
other words, such a two-timescale scheme results in a separation between actor and critic in an asymptotic sense, which leads to asymptotically unbiased policy gradient estimates. In sum, in terms of convergence analysis, the existing theory of actor-critic hinges decoupling the analysis for critic and actor, which is ensured via focusing the bi-level or two-timescale settings.
However, most practical implementations of actor-critic are under the single- timescale setting (Pe- ters and Schaal 2008a [Schulman et al. 2015) Mnil et al., 2016 Scchumann et al.] [2117] Haarnoja al. 2018), where the actor and critic simultaneously updated, and particularly, the actor is updated without the critic reaching an approximate solution to the policy evaluation sub-problem. Meanwhile, in comparison with the two-timescale setting, the actor equipped with much larger stepsize in the the single-time single-timescale setting such that the asymptotic separation between the analysis of actor and critic is no longer valid.
Furthermore, when it comes to function approximation, most existing works only analyze the con-
vergence of actor-critic with either linear function approximation (Xu al. 2020 Wu et al. 2020
Hong et al.) (020), or woelllo-neural-nee In contrast, practically used actor-critic methods such as asynchronous advantage actor-critic (Mnih) et al. 2016) and soft actor-critic (Haarnoja et al. 2018) oftentimes represent both the actor and critic using deep neural networks.
parameterization (Wang et al., 2019 Liu et al.. 2019).
Thus, the following question is left open:
Does single-timescale actor-critic provably find globally optimal policy under the function approximation setting, especially when deep neural networks are employed?
To answer such a question, we make the first attempt to investigate the convergence and global optimality of single-times timescale actor-critic with linear and neural network function approximation. In particular, we focus on the family of energy-based policies and aim to find the optimal policy within this class. Here we represent both the energy function and the critic linear deep neural network functions. In our actor-critic algorithm, the actor update follows proximal policy optimization (PPO) (Schulman et al.) 2017) and the critic update is obtained by applying the Bellman evaluation operator only once to the current critic iterate. As a result, the actor is updated before the critic solves the policy evaluation sub-problem. Such coupled updating structure persists even when the number of iterations goes to infinity, which implies that the update direction of the actor is always biased compared with the policy gradient direction. This brings an additional challenge that absent in the bi-level and the two-timescale settings, where the actor and critic are decoupled asymptotically.
To tackle such a challenge, our analysis captures the joint effect of actor and critic updates on the objective function, dubbed as the "double contraction" phenomenon, which plays pivotal role for the success of single-timescale actor-critic, Specifically, thanks to the discount factor of the MDP, the Bellman evaluation operator is contractive, which implies that, after each update, the critic makes noticeable progress by moving towards the value function associated with the current actor. As a result, although use biased estimate of the policy gradient, thanks to the contraction brought by the discount factor, the accumulative effect of the biases is controlled. Such a phenomenon enables
characterize the progress of each iteration of joint actor and critic update, and thus yields the convergence to the globally optimal policy. In particular, for both the linear and neural settings, we prove that, single-timen timescale actor-critic finds a O(K-1/())))) -/gglbbbblly optimal policy after K iterations. To the best of our knowledge, seem to establish the first theoretical guarantee of global convergence and global optimality for actor-critic with function approximation in the single- timescale setting. Moreover, under the broader scope of policy optimization with nonlinear function
2

---

Published as a conference paper at ICLR 2021
approximation, our work seems to prove convergence and optimality guarantees for actor-critic with deep neural network for the first time.
Contribution. Our contribution is two-fold. First, in the single-timescale setting with linear function approximation, we prove that, after K iterations of actor and critic updates, actor-critic returns policy that is at most (K221/2) inferior to the globally optimal policy. Second, when both the actor and critic are represented by deep neural networks, we prove similar O(K rate of convergence to the globally optimal policy when the architecture of the neural networks are properly chosen.
Related Work. Our work extends the line of works on the convergence of actor-critic under the function approximation setting. In particular, actor-critic is first introduced in Sutton et al. (2000); Konda and Tsitsiklis (200)). Later, Kakade (2002); Peters and Schaal (2008b) propose the natural actor-critic method which updates the policy via the natural gradient (Amari) 1998) direction. The convergence of (natural) actor-critic with linear function approximation are studied in [hattagarr eet al.] (2008) 2009); Bhatnagar (2010); Castro and Meir (2000); Maei (2018). However, these works only characterize the asymptotic convergence of actor-critic and their proofs all resort to tools from stochastic approximation via ordinary differential equations (Borkar 2008). As a result, these works only show that actor-critic with linear function approximation converges to the set of stable equilibria of set of ordinary differential equations. Recently, Zhang et al. (2019) propose variant of actor- critic where Monte-Carlo sampling is used to ensure the critic and the policy gradient estimates are unbiased. Although they incorporate nonlinear function approximation in the actor, they only establish finite-time convergence result to a stationary point of the expected total reward. Moreover, due to having an inner loop for solving the policy evaluation sub-problem, they focus the bi-level setting. Moreover, under the two-timescale setting. Wu et al. (2020): Xu et al. (2020) show that actor- critic with linear function approximation finds e-stationary point with (ss-5/2) samples, where e measures the squared norm of the policy gradient. All of these results establish the convergence of actor-critic, without characterizing the optimality of the policy obtained by actor-critic.
In terms of the global optimality of actor-critic, Fazel et al. 20188;; Malik et al. (2018); Tu and Recht (2018); Yang et al. (2019a); [Bu et al. (2019); ; Fu et al. (2019) show that policy gradient and bi-level actor-critic methods converge to the globally optimal policies under the lincar-quadratic setting, where the state transitions follow linear dynamical system and the reward function is quadratic. For general MDPs, Bhandari and Russo (0199) recently prove the global optimality of vanilla policy gradient under the assumption that the families of policies and value functions are both convex. In addition, our work is also related to Liu et al.] (2019) and Wang et al. (2019), where they establish the global optimality of proximal policy optimization and (natural) actor-critic, respectively, where both the actor and critic are parameterized by two-layer neural networks. Our work is also related to Agarwal et al. (2019): Abbass Yadkori et al. (2019a by: Cai et al.) (2019); Hao et al. (2020); Mei et al. (2020); Bhandari and Russo (2020), which focus on characterizing the optimality of natural policy gradient in tabular and/or linear settings. However, these aforementioned works all focus bi-level actor-critic, where the actor is updated only after the critic solves the policy evaluation sub-problem to an approximate optimum. Besides, these works consider linear or two-layer neural network function approximations whereas we focus on the setting with deep neural networks. Furthermore, under the two-timescale setting, [uu et al. (2020): Hong et al. (2020) prove that linear actor-critic requires sample complexity of O(=-4) for obtaining an s-globally optimal policy. In comparison, our -1K2/22 convergence for single-timescale actor-critic can be translated into similar Ö(=-4) sample complexity directly. Moreover, when reusing the data, our result leads to an improved Ö(e-2) sample complexity. In addition, our work is also related to Geist et al. (2019). which proposes a variant of policy iteration algorithm with Bregman divergence regularization. Without considering an explicit form of function approximation, their algorithm is shown converge to the globally optimal policy at a similar O(K-1/2 rate, where K is the number of policy updates. In contrast, our method is single-timescale actor-critic with linear or deep neural network function approximation, which enjoys both global convergence and global optimality. Meanwhile, our proof is based on a finite-sampl analysis, which involves dealing with the algorithmic errors that track the performance of actor and critic updates as well as the statistical error due to having finite data.
3

---

Published as a conference paper at ICLR 2021
Our work is also related to the literature on deep neural networks. Previous works (Daniely 2017
Jacot et al. 2018; 88; Wu et al. 2018
Allen-Zhu et al. 2018a b Du et al. 2018 Zou et al. 2018 Chizat
and Bach 2018 acot al. 2018 Li and Liang 2018 Cao and Gu 2019a b Arora et al. 2019 Lee
et al. 2019: Gao et al. 2019) analyze the computational and statistical rates of supervised learning
methods with overparameterized neural networks. In contrast, our work employs overparameterized
deep neural networks in actor-critic for solving RL tasks, which is significantly more challenging than supervised learning due the interplay between the actor and the critic.
Notation. We denote by [n]] the set f1,2.... n1.. For any measure and S p S oc, we denote by Ilf (fx (f())) and If (xx [f()) /p, where y is the Lebesgue measure.
BACKGROUND
In this section, we introduce the background on discounted Markov decision processes (MDPs) and actor-critic methods.
2.1 DISCOUNTED MDP
discounted MDP is defined by a tuple (S, A. P,).r,)). Here S and A are the state and action
spaces, respectively, P: S x S x A + [0, 1] is the Markov transition kernel, Ç: S + [0, 1] is the initial state distribution, r: S A
I is the deterministic reward function, and y E [o, 1) is the
discount factor. A policy <a [s) measures the probability of taking the action a at the state We focus on a family of parameterized policies defined as follows,
I (To(- P(A): E S),
(2.1)
where P(A) is the probability simplex on the action space A and 0 is the parameter of the policy Ty. For any state-action pair (s.a) a) E S x A, we define the action-value function as follows,
(s) (1 71 ET Σ r r(s,, ar)
0, = o).
(2.2)
where 8141 ~ P(- St, az) and 0+41 ~ [-- 81+1) for any / 0. We use E. [-] to denote that the actions follow the policy n,, which further affect the transition of the states. We aim to find an optimal policy n² such that Q" (s,a) 2 Q* a) for any policy and state-action pair (s,a) S x A. That is to say, such an optimal policy '' attains a higher expected total reward than any other policy æ, regardless of the initial state-action pair a). For notational convenience, we denote by Q* @"(ssa) a) = Q (s,a) for any (s.a) S x A hereafter.
Meanwhile, we denote by Vn (s) and prr = Vn (s) T(a|s) s) the stationary state distribution and stationary state-action distribution of the policy æ. respectively, for any (s,a) SX A. Correspond- ingly, we denote by v² (s) and p²(ssa) a) the stationary state distribution and stationary state-action distribution of the optimal policy T², respectively, for any (s.a) E S A. For ease of presentation, given any functions 91 S + R and g2: S x A + R, we define two operators IP and I as follows,
[P911(s. a)= = E[gg(s;) so = s, ag = a). [P gel(s, a) = Ex (x1g2(11, so = 8, ag = a), (2.3)
where 81 P( so, an) and a a(- s1). Intuitively, given the current state-action pair (p), the operator P pushes the agent to its next state 81 following the Markov transition kernel P(-1so, (o) while the operator jat pushes the agent its next state-action pair (s1,ar) following the Markov transition kernel P so, an) and policy T(- 81). These operators also relate to the Bellman evaluation operator T", which is defined for any function g: S x A R as follows,
T"
7)
P"
(2.4)
The Bellman evaluation operator T is used to characterize the actor-critic method in the following section. By the definition in (2.2). it is straightforward to verify that the valuee function QT is the fixed point of the Bellman evaluation operator T defined in (2.4). that is, Q" = T QT for any policy For notational convenience, we let IP denote the f-fold composition PP... P. where there are & operators composed together. Such notation is also adopted for other línear operators such as pa and T
4

---

Published as a conference paper at ICLR 2021
2.2 ACTOR- CRITIC METHOD
To obtain an optimal policy π², the actor-critic method (Konda and Tsitsiklis 2000) aims to maxi- mize the expected total reward as function of the policy, which is equivalent to solving the follow- ing maximization problem.
max (Tt) Ex- ()) [Q a)],
(2.5)
Tell
where ( is the initial state distribution, Q" is the action-value function defined in (2.2). and the family of parameterized polices II is defined in (2.1). The actor-critic method solves the maximization
problem in (2.5) via first-order optimization using an estimator of the policy gradient VoJ (T). Here
0 is the parameter of the policy In detail, by the policy gradient theorem (Sutton et al. 2000 we
have
(T - (s. a)- Ve T( ss].
(2.6)
Here es is the state-action visitation measure of the policy म, which is defined as 2
(1 7) Ex=or" Pr(s* 8, G = a]. Based on the closed form of the policy gradient in (2.6). the actor-critic method consists of the following two parts: (i) the critic update, where a policy eval- uation algorithm is invoked to estimate the action-value function Q", c.g. by applying the Bellman evaluation operator T to the current estimator of Q and (ii) the actor update, where policy improvement algorithm, e.g., the policy gradient method, is invoked using the updated estimator of Q*.
In this paper, we consider the following variant of the actor critic method,
Tk+1 < argmax Fyy., [(Qu(8,) ) x 8)) - B (I.( 8) [x(-1s)]],
TE
Qx+1(s,a) + - [(1 [(1-7) r r(00 0o) + + Qu(s), ai) so= = 00 = =a], (2.7)
for any (s, E S x A, where 81 ~ P(: so. ag). a1 ~ T. (-1s), and we write Ey_, [:] =
Ex-rey [-] for notational convenience. Here is defined in (2.1 and KL(TT. (s) || Th [s)) is the Kullback-Leibler (KL) divergence between π(- s) and Tx(: s), which is defined for any
S as [a| s) [x s)) T(a s). In (2.7). the actor update uses the proximal policy optimization (PPO) method (Schulman et al. 2017). while the critic update applies the Bellman evaluation operator T defined in (2.4) to QA only once, which is the current estimator of the action-value function. Furthermore, we remark that the updates in (2.7) provide general framework in the following two aspects. First, the critic update can be extended to letting Qk+1 + (T**+1) Qu for any fixed T > 1, which corresponds to updating the value function via T- step rollouts following Tx+1- Here we only focus on the case with T = for simplicity. Our theory can be easily modified for any fixed 7. Moreover, the KL divergence used in the actor step can also be replaced by other Bregman divergences between prohability distributions over A. Second, the actor and critic updates in (27 is general template that admits both on- and off-policy evaluation methods and various function approximators in the actor and critic. In the next section, we present an incarnation of (.7)) with on-policy sampling and linear and neural network function approximation.
follows, (L s)
[= ='ae log(n(a
Furthermore, for analyzing the actor-critic method, most existing works (Yang et al., 2019a Wang al. 2019 Agarwal et al.) 2019 Fu et al. 2019 Liu et al. 2019) rely on (approximately) obtaining Q at each iteration, which is equivalent to applying the Bellman evaluation operator T infinite times to Q2. This is usually achieved by minimizing the mean-squared Bellman error I|Q method (Sutton 1988), to update the critic for sufficiently many iterations. The unique global minimizer of the mean-squared Bellman error gives the action-value function QT*++I, which is used in the actor update. Meanwhile, the two-timescale setting is also considered in existing works (Borkar and Kondal 1997] Konda and Tiitsiklis, 2000) Xu al. 2019:] 2020; Wu et al., 20200 Hong et al. 2020). which require the actor to be updated more slowly than the critic in an asymptotic sense. Such requirement is usually satisfied by forcing the ratio between the stepsizes of the actor and critic updates to go to zero asymptotically.
T |2 1 2 using stochastic semi- semi-gradient descent, e.g., as in the cemporal-differeee
In comparison with the setting with bi-level updates, we consider the single-timescale actor and critic updates in (.7). where the critic involves only one step of update, that is, applying the Bell- man evaluation operator T to Qs only once. Meanwhile, in comparison with the two-timescale
5

---

Published as a conference paper at ICLR 2021
setting, where the actor and critic updated simultaneously but with the ratio between their step- sizes asymptotically going to zero, the single-iimssall setting is able to achieve a faster rate of convergence by allowing the actor to be updated with larger stepsize, while updating the critic simultaneously. In particular, such a single-timeseee tical algorithms (Peters and Schaal 2008a| Schulman et al. 2015 Mnih al. 2016 (Schulman al.) 2017 Haarnoja et al. (2018), where the stepsize of the actor is not asymptotically zero. In { we discuss the implementation of the updates (2.7) for different schemes of function approximation. In $4
setting better captures a broader range of prac-
we compare the rates of convergence between the two- so-tiiesc and single- sigge-timesccle settings.
3
ALGORITHMS
We consider two settings, where the actor and critic are parameterized using linear functions and deep neural networks (which is deferred to A of the appendix), respectively. We consider the energy-based policy (a | s) x exp(r-"Jo( [s( a.), where the energy function so(s, a) is parameter- ized with the parameter 0. Also, for the (estimated) action-value function, we consider the parame- terization (w, a) for any (s, a) E S x A. where is the parameter. For such parameterizations of the actor and critic, the updates in 2.7) have the following forms.
Actor Update. The following proposition gives the closed form of Th+1 in 2.7
Proposition 3.1. Let To, (al (als) eXp(Te So, (s, be an energy-based policy and T argmax, Fe, [[Qun (), (-)))) 3 (L(T(( 8) To, (+1s)]] Then #x+1 has the following closed form: T (a 5) x exp(B-1QQ. (s, a) + Tk "So a)). for any (8,a) E x A, where
P/= Vxoz
is the stationary state distribution of Te..
See I for a detailed proof of Proposition 3.1
Motivated by Proposition 3.1 to implement the tor update in (27)). we update the actor parameter 0 by solving the following minimization problem,
0k+1 f- argmin Epp [fo(ss a) Tx+1 18 (8, + Th So, (8, (s)
(3.1)
where Pk PMey the stationary state-action distribution of max
Critic Update. To implement the critic update in 2.7 update the critic parameter w by solving the following minimization problem,
Wk+1 f argmin TrgminEEp.11 [(IQw (1 7) - y - (s,
(3.2)
where Pk++1 Pao is the stationary state-action distribution of Mo and the operator IP is
defined in 2.3
3.1 LINEAR FUNCTION APPROXIMATION
In this section, we consider linear function approximation. More specifically, we parameterize the action-value function using (s, a) = w ((s,a) and the energy function of the energy-based policy ze using fo(s,a) a) 0 ((ss Here ((s,a) E Rd is the feature vector, where d > 0 is the dimension. Without loss of generality, we assume that ||sp(,, l|2 S for any (s,a) E S x A. which can be achieved by normalization.
Actor Update. The minimization problem in 3.1 admits the following closed-for solution,
0 Tk+1 (8 Wk + T +bx))
(3.3)
which corresponds step of the natural policy gradient method (Kakade 2002
Critic Update. The minimization problem in 3.2) admits the following closed-form solution,
Wy+1 (E li(s, a)y((s, a) T) "
Epe.. [[(1 () r + - 1s a) (pss, a)). (3.4)
Since the closed-form solution We+1 in (3.4 involves the expectation over the stationary state-action distribution Pa+1 of Th we use data to approximate such an expectation. More specifically, sample ((s,,) ae1)), and {S8,2, 02,2, r2,2, 86,29 d' d),2)) such that (s,11, Pk+1,

---

Published as a conference paper at ICLR 2021
(st,2, a2,2) Pk+1, T2, r(s,,2 012)), 8/222 P(: 88,2, a.22), and d/,2 ( where N is the sample size. We approximate Wk+1 using wh+11 which is defined as follows,
N
Wh+1 = L'R
(( ((l".....))p(()))....))
(3.5)
t=1
N ((1 (1--)) -2, www. (56,2 de22)) p(502.002)
Σ
Here Lg is the projection operator, which projects the parameter onto the centered ball with radius R in R.. Such projection operator stabilizes the algorithm (Konda and Tsitsiklis 2000, Bhatnagar step of the least-squares temporal difference method (Bradtke and Barto. 1996), which can be modified for the
al. 2009). It worth mentioning that one may also view the update in (3.5)
off-policy setting (Antos et 2007 Yu 2010 Liu et al. 20018] Nachum al.) 2019 Xie et al.) 2019 Zhhang et al.) 20200 Uchara and Jiang 2019 Nachum and Dai 2020). Such a modification
allows the data points (3.5) to be reused the subsequent iterations, which further improves the sample complexity. Specifically, let Paav E PPS A) be the stationary state-action distribution
induced by a behavioral policy mbhy. We replace the actor and critic updates in (3.1) and (3.2) by
0k+1 + argmin E pan. (ffoss, a) Tk+1 (8- Qui (s, a) + Th for (s, (s).))))
(3.6)
Wk+1 argmin Ep [1Qw (1 7) 7 4 Qun Quil(s,)))
(3.7)
respectively. With linear function approximation, the actor update in (3.6 is reduced to the critic update in (3.7 admits a closed form solution
3.3 while
Wk+1 (E [s((s, a))((s, a) T)) Ep... [[(1 -) 7 1 1 Qun (s, a) a).
which can well approximated using state-action pairs drawn from Phhv. See $ for detailed discussion. Finally, by assembling the updates in (3.3) and (3.5). we present the linear actor-critic which is deferred to of the appendix.
method in Algorithm] I
THEORETICAL RESULTS
In this section, we upper bound the regret of the linear actor-critic method. We defer the analysis of the deep neural actor-critic method to of of the appendix. Hereafter we assume that [r(s, a)] S T'ax for any (s, a) E S x A, where mmax a positive absolute constant. First, we impose the following assumptions. Recall that p" is the stationary state-action distribution of x², while Pk is the stationary state-action distribution of T0, Moreover, respect to which aim to characterize the performance of the actor-critic algorithm. Specifically, after K + actor updates, we are interested in upper bounding the following regret
P(S x AA be a trate-action distribution with
K (1QQ QTae (1laa)
K (s, - -
E
( (s.
(4.1)
k=
K=O
where the expectation is taken with respect {0p] and (s, a) ~ p. Here we allow p to be any fixed distribution for generality, which might be different from p².
Assumption 4.1 (Concentrabilliy Coefficient). The following statements hold.
(i) There exists a positive absolute constant o" such that Φ7 < 6² for any k 2 1, where oi /dpklleep.
(ii) We assume that for any 1: 2 and a sequence of policies { J221, the k-step future-state- is absolutely continuous with respect to p", where p is the
action distribution pl ........P ...Ipr
same as the one in (4.1) Also, holds for such o that Cp.0" = (1 (1- >e km k2 c(k) < xo, where c(k) (T. ||d Ip=)) |,0"....
In Assumption Cp.o+ is known the discounted-averann concentrability coefficient of the future-state- distributions. Such an assumption indeed measures the stochastic stability prop- erties of the MDP, and the class of MDPs with such properties is quite large. See (Szeeesááii and
7

---

Published as a conference paper at ICLR 2021
Munos (2005) ): Munos and vzepesvári (2008); : Antos et al. (2008a b); Scherrer (2013)) Scherrer et al.
[013): Farahmand et al. (2016); Yang et al. (2019b); Geist et al. (2019): Chen and Jiang (2019) for more examples and discussion.
Assumption 4.2 (Zero Approximation Error). It holds for any w, 0 E
B(0, R)
that
(n), pp_g [[[TT Q~ a (o((s.)) 0, where T is defined in (2.4).
Assumption imposes structural assumption of the MDP under the linear setting. Specifically speaking. it assumes that the Bellman operator of each policy maps a linear value function to a linear function. Therefore, the value function associated with each policy (which is the fixed point of the corresponding Bellman operator) lies in the linear function class. Since the value functions are linear here, the energy-based policy class approximately covers the optimal policy the temperature parameter т goes to zero. In summary, our Assumption 4.2 ensures that the mnergy-based policy class approximately captures the optimal policy and thus there no approximation error. When Assumption does not hold, we only need to add an additional bias term to the regret upper bound in our theorem without much change in the proof.
Assumption 4.3 (Well-Conditioned Feature). The minimum singular value of the matrix Ep, (p((s, a) (s, a) is uniformly lower bounded by a positive absolute constant o² for any k 2 1.
Assumption 4.3 ensures that the minimization problem in 3.2) admits a unique minimizer, which is used in the critic update, Similar assumptions are commonly imposed in the literature (Bhandari
al. 2018 Xu et al. 2019 Zou et al. 2019 Wu et al. 2020).
Under Assumptions 4.1 theorem.
and 4.3 we upper bound the regret of Algorithm in the following
Theorem 4.4. We assume that Assumptions 4.1 and 4.3 hold. Let be a state-action distri-
bution satisfying (ii) of Assumption 4.1 Also, for any sufficiently large K >> 0, let B = K3/2,
N ((( C p.p- (Ø0 (er/a"> /a*)² log² N). and the sequence of policy parameters {0x) be gen- erated by Algorithm It holds that
K E
Σ
((9 (s. s (2(1-7) log (A| +OL)) K2/22
(4.2)
where the expectation is taken with respect to (0x ]E([K+]] and (s, a) p.
We sketch the proof in D See E.1 for a detailed proof. Theorem 4.4 establishes an O(K)))
regret of Algorithm D where K is the total number of iterations. Here ((-) omits terms involving (1-7)-1 and log A. To better understand Theorem 44.4 we consider the ideal setting, where we have access to the action-value function Q" of any policy æ. In such an ideal setting, the critic update is unnecessary. However, the natural policy gradient method, which only uses the actor update, achieves the same ((K1/2) regret (Liu al. 2019: Agarwal et al. 2019 Cai et al. 2019). In other words, in terms of the iteration complexity, Theorem 4.4|shows that in the single- tinescle setting, using only one step of the critic update along with one step of the actor update is as efficient as the natural policy gradient method in the ideal setting.
Furthermore, by the regret bound in (4.2 to obtain an e-globally optimal policy, it suffices to set K (1-?) 7)-6 g- log² [AA] in Algorithm i and output a randomized policy that is drawn from (To,) K+1
R=1 uniformly. Plugging such a K into N = S2(K? p.p- ( /a*)² log" N), we obtain that N Ō(= 2) where Ō()) omits the logarithmic terms. Thus, to achieve e-globally optimal policy, the total sample complexity of Algorithm Ö(e-4). This matches the sample complexity results established in Xu et al.] (2020); [Hong et al. (2020) for two-timescale actor-critic methods. Meanwhile, notice that here the critic updates are on-policy and we draw N new data points in each critic update. As discussed in 1 under the off-policy setting, the critic updates given in (3.7) can be implemented using a fixed dataset sampled from Patve the stationary state-action distribution induced by the behavioral policy. Under this scenario, the total number of data points used by the algorithm is equal to N. Moreover, by imposing similar assumptions on Patv as in (1) of Assumption
4.1 and Assumption 4.3 we can establish a similar O(K1/2) regret as in (42) for the off-policy setting. As result, with data reuse, to obtain an e-globally optimal policy, the sample complexity
of Algorithm is essentially O()-2), which demonstrates the advantage of our single-timescale
8

---

Published as a conference paper at ICLR 2021
actor-critic method. Besides, only focusing the convergence e-stationary point, Wu et al. 2020) Xu al. (2020) establish the sample complexity of ((=5//2) for two-timescale actor-critic, where measures the squared Euclidean norm of the policy gradient. In contrast, by adopting the natural policy gradient (Kakade, 2002) in actor updates, we achieve convergence the globally optimal policy. We remark that the idea of off-policy evaluation cannot be applied to typical two- timescale setting (Wu et al., 2020 Xu et al., 2020). where the critic is updated using TD learning (e.g. TD(O) and TD(A)), since it is shown that off-policy TD method may diverge even with linear function approximation (Baird et al., 1995, SStton et al.] 2008). To the best of our knowledge, we establish the rate of convergence and global optimality of the actor-critic method with function approximation in the single-timen timescale setting for the first time.
Furthermore, we will show in Theorem C.5 of B when both the actor and the critic are repre- sented using overparameterized deep neural networks, we establish a similar 0((1-)) log [A|- K1/3) regret when the architecture of the actor and critic neural networks are properly chosen. To our best knowledge, this seems the first theoretical guarantee for the actor-critic method with deep neural network function approximation in terms of the rate of convergence and global optimality.
REFERENCES
Yobasi-Yadkorr Y., Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C. and Weisz, G. (2019a). Poli- tex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning.
Abbasi- Abbasi-Yadkori, Y., Lazic, N., Szepesvari, C. and Weisz, G. (2019b). Exploration-cehaanee politex. arXiv preprint arXiv: 10479.
Agarwal, A., Kakade, S. M., Lee, J. D. and Mahajan, G. (2019). Optimality and approximation with policy gradient methods in Markov decision processes. arXiv preprint arXiv:1908. 00261.
Agostinelli, F., McAleer, S., Shmakov, A. and Baldi, P. (2019). Solving the Rubik's 's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1 356-363.
Akkaya. I.. Andrychowicz, M., Chociej, M., Litwin, M., McGrew, B., Petron, A., Paino, A., Plappert, M., Powell, G., Ribas, R. et al. (2019). Solving Raubik's 's cube with a robot hand. arXiv preprint arXiv:1910.077
Allen-Zhe Zhu, Z., Li, Y. and Liang, Y. (2018a). Learning and generalization in overparameterized neu- ral networks, going beyond two layers. arXiv preprint arXiv: 1.04918.
Allen-Zhu. Z., Li, and Song, (2018b). convergence theory for deep learning via over- parameterization. arXiv preprint
Amari, S.-I. (1998). Natural gradient works efficiently in learning. Neural Computation, 10 251- 276.
Antos, A., Szepesvári, and Munos, R. (2007). Value-iteration based fitted policy iteration: Learn- ing with single trajectory. In IEEE International Symposium on Approximate Dynamic Program- ming and Reinforcement Learning.
Antos, A., Szepesvári, C. and Munos, R. (2008a). Fitted Q-iteration in continuous action-space MDPs. In Advances in Neural Information Processing Systems.
Antos, A., Szepesvári, C. and Munos, R. (2008b). Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71 129.
Arora, S., Du, S. S., Hu, W. Li, Z. and Wang, R. (2019). Fine-grained analysis of optimiza- tion and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: UrXiv:/901.00 0wt.:990000555 08584.
Baird, L. et al. (1995). Residual algorithms: Reinforcement learning with function approximation. In International Conference on Machine Learning. Elsevier.

---

Published as a conference paper at ICLR 2021
Bhandari, J. and Russo, D. (2019). Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.01786.
Bhandari, J. and Russo, D. (2020). A note on the linear convergence of policy gradient methods. arXiv preprint 1rXiv:200..11120.
Bhandari, J., Russo, D. and Singal, R. (2018). A finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv:
Bhatnagar, S. (2010). An actor-critic algorithm with function approximation for discounted cost constrained Markov Decision Processes. Systems & Control Letters, 59 760-766.
Bhatnagar, S., Ghavamzadeh, M., Lee, M. and Sutton, R. S. (2008). Incremental natural actor-critic algorithms. In Advances in Neural Information Processing Systems.
Bhatnagar, S., Sutton, R., Ghavamzadeh, M. and Lee, M. (2009). Natural actor-critic algorithms. Automatica, 45 2471-2482.
Borkar, V. S. (2008). Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge Uni- versity Press.
Borkar, V. S. and Konda, V. R. (1997). The actor-critic algorithm as multi-time-scale stochastic approximation. Sadhana, 22 525-543.
Bradtke, S. and Barto, A. G. (1996). Linear least-squares algorithms for temporal difference learn- ing. Machine Learning 33-57.
Bu, J., Mesbahi, A., Fazel, M. and Mesbahi, M. (2019). LQR through the lens first order methods: Discrete-time case. arXiv preprint arXiv: 19tp,09077.021
Cai, Q.. Yang, Z., Jin, and Wang. Z. (2019). Provably efficient exploration in policy optimization. arXiv preprint arXiv: 1912.0580.
Cao, Y. and Gu, Q (2019a). Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint 1rXiv:1905.13210.
Cao, and Gu, Q. (2019b). A generalization theory of gradient descent for learning over- parameterized deep ReLU networks. arXiv preprint 112.0:1902.01384.
Castro, D. D. and Meir, R. (2010). convergent online single-time-scale actor-critic algorithm. Journal of Machine Learning Research, 11 367-410.
Chen, J. and Jiang, N. (2019). information-theorete considerations batch reinforcement learning. arXiv preprint arXiv: 1905000000000000000
Chizat, L. and Bach, F. (2018). note on lazy training in supervised differentiable programming. arXiv preprint arXiv: 18/2.07956.
Daniely, (2017). SGD learns the conjugate kernel class of the network. Advances in Neural Information Processing Systems.
Du, S. S., Lee, J. D., Li, H., Wang, L. and Zhai, X. (2018). Gradient descent finds global minima of deep neural networks. arXiv preprint
Farahmand, A.-m., Ghavamzadeh, M., Szepesvári, C. and Mannor, S. (2016). Regularized policy iteration with nonparametric function spaces. Journal of Machine Learning Research, 17 4809- 4874.
Farahmand, A.-m., Szepesvári, C. and Munos, R. (2010). Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems.
Fazel, M., Ge, R., Kakade, S. M. and Mesbahi, M. (2018). Global convergence of policy gradient methods for linearized control problems. arXiv preprint arXiv: 000111001..033
10

---

Published as a conference paper at ICLR 2021
Fu, Z.,, Yang, Z., Chen, Y. and Wang. Z. (2019). Actor-critic provably finds Nash equilibria of linear- quadratic mean-field games. arXiv preprint arXiv:1910.07499.
Gao, R., Cai, T., Li, H., Wang, L., Hsieh, C.-J. and Lee, J. D. (2019). Convergence of adversarial training in overparametrized networks. arXiv preprint arXiv: petp::9060099111
Geist, M., Scherrer, B. and Pietquin, O. (2019). theory of regularized markov decision processes. arXiv preprint arXiv: arXiv: 1901.1125.
Haarnoja, T., Zhou, A., Abbeel, P. and Levine, (2018). Soft actor-critie: Off-policy maximum entropy deep reinforcement learning with stochastic actor. arXiv preprint arXiv:
Hao, B., Lazic, N., Abbasi- Yadkor, Y., Joulani, P. and Szepesvari, C. (2020). Provably efficient adaptive approximate policy iteration. arXiv preprint arXiv:200..0369..
Hong, M., Wai, H.-T., Wang, Z. and Yang, Z. (2020). A two-timescale framework for bilevel opti-
mization: Complexity analysis and application to actor-critic. arXiv preprint 1rXiv:200..51770.
Jacot, A., Gabriel, F. and Hongler, C. (2018). Neural tangent kernel: Convergence and generaliza- tion in neural networks. In Advances in Neural Information Processing Systems.
Kakade, S. M. (2002). natural policy gradient. Advances Neural Information Processing Systems.
Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. In Advances in Neural Information Processing Systems.
LeCun, Y., Bengio. Y. and Hinton, G. (2015). Deep learning. Nature, 521 436-444.
Lee, J.. Xiao, L.. Schoenholz, S. S.. Bahri, Y., Sohl-Dickstein, J. and Pennington, J. (2019). Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv:/902.00 06720.
Li, Y. (2017). Deep reinforcement learning: An overview. arXiv preprint arXiv:1701.0777:
Li, Y. and Liang, Y. (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data, Advances in Neural Information Processing Systems.
Liu, B., Cai, Q.. Yang. Z. and Wang, Z. (2019). Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv:1906. 10306 10564-10575
Liu, Q., Li, L., Tang, Z. and Zhou, D. (2018). Breaking the curse of horizon: anfnite-horizon off- policy estimation. In Advances in Neural Information Processing Systems.
Maei, H. R. (2018). Convergent actor-critic algorithms under off-policy training and function ap- proximation. arXiv preprint a
Malik, D., Pananjady, A., Bhatia, K., Khamaru, K., Bartlett, P. L. and Wainwright, M. J. (2018). Derivative- free methods for policy optimization: Guarantees for linear quadratic systems. arXiv preprint arXiv:1812.08300
Mei, J., Xiao, C., Szepesvari, C. and Schuurmans, D. (2020). On the global convergence rates of softmax policy gradient methods. arXiv preprint arXiv:2005.0633
Mnih, V., Badia, A. Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D. and Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning. In- ternational Conference on Machine Learning.
Munos, and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. Journal of Ma- chine Learning Research, 9 815-857.
Nachum, O., Chow, Y., Dai, B. and Li, L. (2019). Dualdice: Behavior-agnostic estimation of dis- counted stationary distribution corrections. Advances in Neural Information Processing Sys- fems.
11

---

Published as a conference paper at ICLR 2021
Nachum, O. and Dai, B. (2020). Reinforcement learning via Renchel-Rockafellar duality, arXiv preprint arXiv:2001.0186.
OpenAl (2018). Openai five.
Peters, J. and Schaal, S. (2008a). Natural actor-critic. Neurocomputingg 71 1180-1190.
Peters, J. and Schaal, S. (2008b). Reinforcement learning of motor skills with policy gradients.
Neural Networks, 21 697.697.
Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.
Sallab, A. E., Abdou, M., Perot, E. and Yogamani, S. (2017). Deep reinforcement learning frame- work for autonomous driving. Electronic Imaging, 2017 70-76.
Scherrer, B. (2013). On the performance bounds of some policy search dynamic programming algorithms. arXiv preprint arXiv:1306.05339
Scherrer, B., Ghavamzadeh, M., Gabillon, V., Lesner, B. and Geist, M. (2015). Approximate mod- ified policy iteration and its application to the game of Tetris. Journal of Machine Learning Research, 16 1629-1676.
Schulman, J., Levine, S., Abbeel, Jordan, M. and Moritz, P. (2015). Trust region policy optimiza- tion. In International Conference on Machine Learning.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A. and Klimov, O. (2017). Proximal policy opti- mization algorithms. arXiv preprint arXiv: (707006777
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A. et al. (2017). Mastering the game of Go without human knowl- edge. Nature, 550 354-359.
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 9-44.
Sutton, R. S., Barto, A. G. al. (1998). Introduction Reinforcement Learning. MIT press.
Sutton, R. S., McAllester, D. A., Singh, S. P. and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Process- ing Systems.
Sutton, R. S., Szepesvári, C. and Maei, H. R. (2008). convergent (n) algorithm for off off-policy temporal-difference learning with linear function approximation. Advances in neural information processing systems, 21 1609-1616.
Szepesvári, C. and Munos, R. (2005). Finite time bounds for sampling based fitted value iteration. In International Conference on Machine Learning. ACM.
Tosatto, S., Pirotta, M., D' D'Eramo, C. and Restelli, M. (2017). Boosted fitted Q-iteration. In Inter- national Conference on Machine Learning.
Tropp, J. A. (2015). arXiv:1501.01571
An introduction to matrix concentration inequalities.
arXiv preprint
Tu, and Recht, B. (2018). The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv:
Uehara, M. and Jiang, N. (2019). Minimax weight and Q-function learning for off-policy evaluation. arXiv preprint arXiv: 1910. 1910..2809.
Vinyals, O., Babuschkin, I., Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W., Dudzik, A.,
Huang, A.. Georgiev, P., Powell, R. et al. (2019). Alphastar: Mastering the Real-
Time Strategy Game StarCraft II. /
httpp:://deeppinnd.comm////g 1lppastar-matterree. ort.rr/aeee.c..e..aeeeeeeeeeeaan
12

---

Published as a conference paper at ICLR 2021
Wang, L., Cai, Q.. Yang, Z. and Wang. Z. (2019). Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint 1rXiv:1909.01159.
Wu, L., Ma, C. and Weinan, E. (2018). How SGD selects the global minima in over-parameterized learning: A dynamical stability perspective. In Advances in Neural Information Processing Sys- tems.
Wu, Y., Zhang. W., Xu, P. and Gu, Q. (2020). A finite time analysis of two time-scale actor critic methods. arXiv preprint arXiv:2005.0135.
Xie, T., Ma, Y. and Wang, Y.X. (2019). Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems.
Xu, T., Wang, Z. and Liang, Y. (2020). Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.03557,
Xu, T., Zou, S. and Liang, (2019). Two time-scale off-policy TD learning: Non-asymptotic anal- ysis over Markovian samples. In Advances in Neural Information Processing Systems.
Yang, Z., Chen, Y., Hong, M. and Wang, Z. (2019a). On the global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. arXiv preprint arXiv: 19Xvv:107..02266.
Yang. Z., Xie, Y. and Wang, Z. (2019b). A theoretical analysis of deep Q-learning. arXiv preprint
Yu, H. (2010). Convergence of least squares temporal difference methods under general conditions. In International Conference on Machine Learning.
Zhang, K., Koppel, A., Zhu, H. and Başar, T. (2019). Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprint arXiv:1906.00 08333.
Zhang, R., Dai, B., Li, L. and Schuurmans, D. (2020). Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.0900
Zou, D., Cao, Y., Zhou, D. and Gu, Q. (2018). Stochastic gradient descent optimizes over- parameterized deep ReLU networks. arXiv preprint 1rXiv:1811.08882
Zou, S., Xu, T. and Liang, Y. (2019). Fimite-sample analysis for SARSA with linear function ap- proximation. Advances in Neural Information Processing Systems.
13

---

Published as a conference paper at ICLR 2021
A DEEP NEURAL NETWORK APPROXIMATION
In this section, we consider deep neural network approximation. We first formally define deep neural networks. Then we introduce the actor-critic method under such parameterization.
A deep neural network (DNN) ue (2) with the input x R depth H. and width m is defined as
x (0) = I, (b) 1_
Vm o oW,, 1( for h E [M], ua( = 6 (H))
(A.1)
Here a: Rm - Rm is the rectified linear unit (ReLU) activation function, which is define as a(y) (max((. yn hn..... max(0, (0, Vm }) for any (yn..... ..n) ) E R Also, we have b E {-1,1) 1, H. Meanwhile, we denote the parameter of the DNN ug as 0 (vec(W,) ..... vec H) ) E Rm with mall md + (H 1)m²² We call he the weight matrices of 0. Without loss of generality, we normalize the input x such that ||a|||== 1.
W1 E [dxm and WR E R g for S
We initialize the DNN such that each entry of W,, follows the standard Gaussian distribution (O for any h E [H) while each entry of follows the uniform distribution U (,,,),,,)).. 1}). Without loss of generality, we fix b during training and only optimize (Wa Hugee We denote the initialization of the parameter 0 as Og- (vec(WP)
vec(W Meanwhile, we restrict 0 within the ball
B(0,. Rt) during training, which is defined as follows,
BiOo, R) = {0 E RT |WA- Wxll= S R, for h E [H]]-
(A.2)
Here (Wi. [e(H] and (e]]e are the weight matrices and lg. respectively. By A.2 we
have |10 - 0oll2 S RVH for any 0 E B(Oo, R). Now, we define the family of DNNs as U(m, H, Rt) = (uo: 0 E R)),
(A.3)
where ug is DNN with depth H and width m.
We parameterize the action- value function using as) E U(m., He, Re) and the energy func- tion of the energy- based policy He using fo(s, a) U(ma, Ha. Ra). Here U(me He, R.) and U(m,, Ha, Ra) are the families of DNNs defined in (A.3). Hereafter we assume that the energy function ʃo and the action-value function Qu share the same architecture and initialization, i.e., = me. Ha He. Ra = Re, and 0g- wo. Such shared architecture and initialization of the DNNs ensure that the parameterizations of the policy and the action-value function are approxi- mately compatible. See SSuttnn et al. (2000); Konda and Tsitsiklis (2000); Kakade (2002); Peters
and Schaal (2008a); Wang al. (2019) for a detailed discussion.
Actor Update. To solve has the following form,
3.1 we use projected stochastic gradient descent, whose n-th iteration
((n + 1)
-LB(,.. (0(m)) a a- (Fo(n)(s,a) Tk+1
+
Velo(m (s.aa)
Here Il) is the projection operator, which projects the parameter onto the ball B(Oo, Ra) defined in (A.2). The state-action pair (s, a) is sampled from the stationary state-action distribution
Pk. We summarize the update in Algorithm 3 which is deferred to ( of the appendix.
Critic Update. To solve 3.2). we apply projected stochastic gradient descent. More specifically, at the n-th iteration of projected stochastic gradient descent, sample a tuple (s, a, r, 8', a'), where (s, ~ Ph+-1, r(s, a), s' ~ P(-1s.a), and a' ~ Taxay (+Is"). We define the residual at the n-th iteration as d(n) (win)(s, a) (1 (1->) -r- --7- 7 Qwi (8 aa). Then the n-th iteration of projected stochastic gradient descent has the following form,
w(n +1 - I (t)), (w(n) (w)) - 17 8(m) (s,ma))
Here I IB R2 is the projection operator, which projects the parameter onto the ball B(wo, R.) defined in We summarize the update in Algorithm|4] which is deferred to of the appendix.
By assembling Algorithms andd 4 we present the deep neural actor-critic method in Algorithm 2 which is deferred to B of the appendix.
Finally, remark that the off-policy actor and critic updates given in 3.6 and 3.7 also
incorporate deep neural network approximation with a slight modification, which enables data reuse in the algorithm.
14

---

Published as a conference paper at ICLR 2021
B DETAILS OF ALGORITHMS
In this section, we summarize the algorithms in [3 linear function approximation in Algorithm
We first introduce the actor-critic method with
Algorithm Linear Actor-Critee Method
Input: Number of iterations K, sample size N, temperature parameter 3 Initialization: Set TO f- oo, and randomly initialize the actor parameter 9g and the critic param-
eter wo.
for 0,1,2,.... do
Actor Update: Update 0k+1 via (3.3) with 'K41 (1+
Critic Update: Sample {sE,1 hea)) and (4,22, T22 & d22)be specified
in 3.1 Update wK+1 via 3.5
end for Output: (To, kE]K-+1), where Te, & exp(TT' foz)
We introduce the actor-critic method with DNN approximation in Algorithm which relies on Algorithms 3 4 for the actor and critic updates.
Algorithm Deep Neural Actor-Critic Method
Input: Number of iterations K, Na. Ne, Na, stepsizes a,, 1), and temperature parameter 3. Initialization: Set т6 t- oc and initialize DNNs fo, and Quo as specified in A
for k 0, 1, K do
Actor Update: Update 0241 via Algorithm] 3 with input TH,, Oo. Qwe G, Th41 = (k+1)-1.
8, and No.
Critic Update: Update wh+1 via Algorithm with input T Qwes wo, and No.
end for
Output: (To, be(KK+))) where To, x exp(Tx foa).
Algorithm Actor Update for Deep Neural Actor-Critee Method
Input: Policy Te oc exp(r fe), initial actor parameter 6g action-valle function Qwi stepsize o, temperature parameter 3, temperature F, and number of iterations N..
Initialization: Set ((0) + On-
for = 0, ...., N_ do
Sample (s, a) as specified in A
Set ((n + 1) +- (.) (n)) (s, 7 Q., + --f(s(ss a))
Vafu(m)) (s, a)).
end for
Output: 1/Na EN= 0m))
Algorithm 4 Critic Update for Deep Neural Actor-Critic Method
Input: Policy To, action-value function Qu. initial critic parameter wo. stepsize n,, and number of iterations Ne-
Initialization: Set (0) +- wn. for m = 2, N. do Sample (s, r, s', a') as specified in A
Set (m) + Qw(n) a) - (1- -) 7 as) 6(n) (s)na)))
Set wnn + 1) + 1 L'B(wa. (w(()
end for
Output: w = 1/Ne IN= w(n).
No
15

---

Published as a conference paper at ICLR 2021
C CONVERGENCE RESULTS OF ALGORITHME 2
In this section, we upper bound the regret of the deep neural actor-critic method. Hereafter assume that [r(s, a}l I Tmax for any (s, a) E x A. where Tmax positive absolute constant. First, we impose the following assumptions in parallel to Assumption 4.1 Recall that pt is the stationary state-action distribution π², while Pk is the stationary state- action distribution TB.-
Assumption C.1 (Concentrability Coefficient). The following statements hold.
(i) There exists a positive absolute constant 6* such that 0% S 6- for any k 2 1, where of ||pp /dpelpp..2-
(ii) For the state-action distribution o used to define the regret (4.1) we assume that for any h: 2 1 and sequence of policies (T:) the k-step future-state-actinn distribution
pP ...PAA is absolutely continuous with respect to p² Also, holds that
20
Cp. = (1
Σ
c(k)) <0,
k=1
where e(k) sup(m. hew ||d(pPP ... ...IPTA)) // l1p-
Meanwhile, we impose the following assumption in parallel to Assumption 4.2
Assumption C.2 (Zero Approximation Error). For any Qu E U(me, He. Re) and policy æ, it holds that T T UMme, He, Re), where T is defined in (..4)
Assumption C.2 states that ((me, He, Re) closed under the Bellman evaluation operator T
which commonly imposed in the literature (Munos and Szepesvári 2008 Antos et al. 2008a
Farahmand et al.) 2010 2016 Tosatto al., 2017: Yang al. 20199b Liu al. 2019)..
We upper bound the regret the deep neural actor-critic method in Algorithm 2 in the sequel. To establish such an upper bound, we first establish the rates of convergence of Algorithms 3 and as follows.
Proposition C.3. For any sufficiently large Na 1/2 RRR3)) / 3/2), H, O(N2/1) and R, 0(m 2(d/2 ( 3/2 We denote by 0 the output of Algorithm with input Ta x exp(T-1 fo), 0o. Qu a. B. and No. Also, let f F (B-1Qu. + + With probability at least 2/3 H.)) over the random initialization Go. we have 1 - --exp(-A((R ma
0, let
ma
log(ma
1/2 H 6log
=
E (f - a(s, OR R. m 1/0 H log m.).
Here the expectation is taken over the randomness of 9 conditioning the initialization Og and (s, a) ~ P... where Pr, is the stationary state-action distribution of my.
Proof. See G.2 for a detailed proof.
Proposition C.4. For any sufficiently large No > 0(23/2 He 3/2 log(m! ///2/R2)//), He O(N!/A) and R. O(m! Hlog me) 3). We denote by w the output of Algorithm g with input no. Qu: wa. y, and N Also, let (1-2 t Q.. With probability at least e 2/3 Hc)) over the random initialization Wo. we have
O, let me
-((s=(s.a)=((s.a)} = O +R /2333/mm H me).
Here the expectation is taken over the randomness of w conditioning on the initialization wy and (s) PT.. where Pro, is the stationary state-action distribution of TT.
Proof. See G.3 for detailed proof.
16

---

Published as a conference paper at ICLR 2021
Propositions C.3 and C.4 characterize the errors that arise from the actor and critic updates in Algo-
rithm 2 respectively. In particular, if the widths Ma and m. of the DNNs fo and Qu are sufficiently
large, the emrors characterized in Propositions C.3 and C.4 decay to zero at the rates of O(N 1/2)
and O(N respectively. Propositions C.3 and C.4 act as the key ingredients to upper bounding the regret of the deep neural actor-critic method.
Based on Propositions C.3 and C.4 we upper bound the regret of Algorithm in the following
theorem, which is in parallel to Theorem 4.4
and C.2 hold. Let p be state-action distri- bution satisfying (i)) of Assumption C.T Also, for any sufficiently large K 0, let N₂ QKK2C
Theorem C.5. We assume that Assumptions
O 1/2 p.p- (0 1 + 1) No QKK C1 pip de R2), H. H. O(N!/1) Rg R
H- (lo 33) m. m. = (dd//2 K p.p" +1 +1)12 R H. log(me / / /Re)3/2).
3 = K and the sequence <0 be generated by Algorithm 2
With probability at least
1 - 1/K over the random initialization On and wp. it holds that
E
Σ Qs(ss - T (s, a) s (2(1 -el -) logg |A| O(1) KK
-
where the expectation taken over the randommess of (s, a) ~ and { (0x+1kEE(K) conditioning on the initialization 0g and wp.
Proof. See
E.2 for detailed proof.
When the architecture of the actor and critic neural networks are properly chosen, Theorem C.5 establishes an O(K1/2) regret of Algorithm where K is the total number iterations. Specifically speaking, to establish such a regret upper bound, we need the widths m, and of the DNNs So and Qw to be sufficiently large. Mcanwhile, to control the errors of actor update and critic update in Algorithm
also run sufficiently large numbers of iterations in Algorithms 3 and
In terms of the total sample complexity, to simplify our discussion, we omit constant and logarithmic terms here. To obtain an e-globally optimal policy, it suffices set K = in Algorithm
By
plugging such a K into Na = Q(K K
P.p" (Ø" + 8 + 1)* I²²R) and N: = C
p.p" o+
as
required in Theorem C.5 we have N, ( and N. Ō )) Thus, to achieve an e-globally
optimal policy, the total sample complexity of Algorithm is Ō(E 6). With the modification to off-
policy setting as in 1 the total sample complexity of Algorithm 2 Ō(s=)). In comparison, Liu al. 2201)) requires total sample complexity of ((s-5) achieve e-globally optimal policy, which is worse than our single-timescale algorithm. Meanwhile, since Liu et al. (2019) uses TD(O) in the critic update, which shown diverge under off-policy setting even with linear function approximation (Baird et al. 1995), the method of data reuse cannot be applied to Liu et al. (2019) to eliminate the total sample complexity.
To the best of our knowledge, we establish the rate of convergence and global optimality of the actor-critic method under single-timescale setting with DNN approximation for the first time.
D PROOF SKETCH OF MAIN THEOREM
In this section, sketch the proof of Theorem 4.4 Recall that is state-action distribution
(s((ss,) a) QT 12 (s,a), for any satisfying (ii) of Assumption 4.1 We first upper bound " a) E S A in part 1. Then by further taking the expectation over in part 2, we conclude the proof of Theorem 4.4
See E. for detailed proof.
K Part 1. In the sequel, upper bound =k=o (s" first decompose Q* - "0 into the following three terms,
(Q" a) T (s, a)) for any (s,a) E A. We
k 10 Q 2 66+ [8, k=0
Σ - 7p -1 (Ai, + A2 + Aa.x)
(D.1)
k=0
17

---

Published as a conference paper at ICLR 2021
the proof of which is deferred to EE.1 and E.2 in E.1 of the appendix. Here the operator PT is
defined in (2.3 (7 -Ip
)-1 2i=0 (7 pm )" and AI, A2, and A3,a are defined as follows,
A1, a) = 17( p )Qun (s,
(D..)
A2, a) = [xP" 00+ - Qux )] (s,a). A3, a) = (T Qwe = [[,,)]]{s,)) (8)
(D.3)
(D.4)
To understand the intuition behind A1,k- A2,k. and As,k, we interpret them as follows.
Interpretation of AI,e, As defined (D.2). AI, arises from the actor update and measures the con- vergence of the policy 802+1 towards globally optimal policy n², which implies the convergence of pT towards pa
Interpretation of Ag.s- Note that by (2.2) and (2.4), we have Q T Q and T is y-contraction, which implies that applying the Bellman evaluation operator T to any Q. e.g. Qwe. infinite times yields Q 2 As defined (D.4), As.k measures the error of tracking the action-value function 2* of Th+.1 by applying the Bellman evaluation operator T to Qua only once, which arises from the critic update. Also, as A3, T (Qw.. - 1= A3.2 measures the difference between QToe, which approximated by Qwz as discussed subsequently, and 0** Such difference can also be viewed as the difference between TØ, and Toe which arises from the actor update. Therefore, the convergence of A3.s to zero implies the contractions of not only the critic update but also the actor update, which illustrates the "double contraction" phenomenon. We establish the convergence of A3,5 to zero in (D10)) subsequently.
Interpretation of A2 Assuming that A3, converges to zero, we have T Quz- R Q Moreover, assuming that the number of data points N is sufficiently large and ignoring the pro- jection in (355), we have T Qwe- = Qüa RJ Qwe as Wh defined in (3.4) is an estimator of wk. Hence, we have QTa = Qwz Such an approximation error is characterized by & defined in (D.5) subsequently. Hence, A2,1 measures the difference between To, and To..1 through the difference between R = Qwa and QT which relies on the convergence of A3,k-1 to zero.
In the sequel, we upper bound ALks A2, and A3,k, respectively. To establish such upper bounds, we define the following quantities,
(s. a) < 11Qu (s,a))
(D.5)
(s, (w,, + Quy
(D.6)
0x(s) (<(s)=KL(='()) (.1s) [T (.22(()))) (L(TT((11) To (+1s)).
(D.7)
To understand the intuition behind 4 CR+1, and 0s. we interpret them as follows.
Interpretation of + Recall that W is defined in (3.4), which parameterizes T Que (ig- noring the projection in (355) Here c++ arises from approximating Wk+11 using Wk+1 as an estima- tor, which is constructed based on Wk and the N data points. In particular, ch41 decreases zero as N + oo, which is used in characterizing A2, defined in (.3).
Interpretation of ex+1- Assuming that A3, defined in (.44 and of defined in (D.) converge to zero, which implies T Qwe-, 23 TT and T Que x Qwe, respectively, we have Quy R Qrea. Therefore, as defined in (D.6). Cx+1 Qua T Que TT. TT 12 QTax TT - T T measures the difference between Te, and T which implies the difference between T and #11, We remark that + fully characterizes As, defined in (D.4) as shown in (D8) subsequently.
Interpretation of 0І. As defined in (.7). Os measures the difference between Ta, and T8 in terms of their differences with n², which are measured by the corresponding KL-divergences. In particular, Og is used characterizing A1, and Ag,x defined in (D.2) and (D33). respectively.
We remark that c measures the statistical error in the critic update, while 9, measures the opti- mization error in the actor update. As discussed above, the convergence of A3,8 zero implies the
18

---

Published as a conference paper at ICLR 2021
Qux
Que+1
Critic Update:
Ch-1
k++
T Qua
T Quk
A3,
A3,k
Ix
Actor Update:
Q
Q 2x+++
A1,
A A1,4+1
T Qwn
T Qwx+1
A2
A2,k
T Q
T Q
Figure 1: Illustration of the relationship among A1,k, A2,k, A3, 4+1 Ck+1, and dg. Here {0k, wx) and (0++1 are consecutive iterates of actor-critic. The red arrow from Qu Qwa+n represents the critic update and the red arrow from Q to Q* represents the action-value functions associated with the two policies in any actor update. Here 0y given in (D.7) quantifies the difference between iTe and Th in terms of their KL distances to x². In addition, the cyan arrows represent quantities A1,k, 42,s and As,s introduced in (D.2) D.4). which are intermediate terms used for analyzing the error Q* Q Finally, the blue arrows represent E and ck+1 defined in (D.5) and (D.6), respectively. Here c corresponds to the statistical error due to having finite data whereas 1k+1 essentially quantifies the difference between TT, and T8
contraction of both the actor update and the critic update, which illustrates the "double contraction" phenomenon. Mcanwhile, since ex+1 fully characterizes A3, as shown in (D.8) subsequently, ex+1 plays key role in the "double contraction" phenomenon. In particular, the convergence of ek+1 1 to zero is established in (D.9) subsequently. See Figure for an illustration of these quantities.
With the quantities defined in D.5). D.6.. and D.7 we upper bound AL,k- A2, and As, as follows,
as) S S.8 [s),,,,,a),
k-1
A2 s (
yu+ (sn)) 73
(s,
[6) ) (s,
==
1-1
> [(22p (
+
1=0
(x, = [yTp (>))=)))>>> - (1p= ek+ (8,
(D.8)
the proof of which is deferred to Lemmas
E.
E.2 and E.3 in
E.1 of the appendix, respectively.
Meanwhile, by recursively expanding (D.5) and (.6
we have
(s, <
e1
amdd ) F Dep (s,a),
(D.9)
1=1
s11+1
19

---

Published as a conference paper at ICLR 2021
the proof of which is deferred to Lemma E.4 in E. of the appendix. By plugging D.9 into D.8 we have
A3,x(s,0) pprootts (1-pittt
Nodd 61
(D.10)
1 (T (1- (0,
To better understand (D.10) and how it relates to the convergence of As,k. A2 and A1, to zero, we discuss in the following two steps.
Step (i). We assume ef = 0, which corresponds to the number of data points N - 00. Then D.10) yields A3.8 = O()*), which implies that A3.k defined in (D4) converges to zero driven by the discount factor y. As discussed above, the convergence of A3.e zero also implies the contraction between Té, and T of the actor update and the contraction between Qwe and Q of the critic update, which illustrates the "double contraction" phenomenon.
Step (ii). The convergence As.k k zero further ensures that A2,* converges to zero. To see this, we further assume A3,k = O, which together with the assumption that c+1 = 0 implies Q = + Qw, Que+n by their definitions in (D.4) and (D.5). respectively. Then by telescoping the sum of A2,x defined in (D.3), which cancels out Quai and Q**++1, we obtain the convergence of 42,x to zero. Meanwhile, telescoping the sum of A1 defined in (D.2) and the sum of its upper bound in (D.)) implies that A1, converges to zero.
Now, by plugging D.8 and D. into (.II. we establish an upper bound of E (Q" a) TT (s, a)) for any (s, a)
the appendix. Hence, S x A. which is deferred to (E.12) E..
we conclude the proof in part 1. See part of E. for details.
Part 2. Recall that p is state-action distribution satisfying of Assumption 4.1 In the sequel, we take the expectation over in (E.12) and upper bound each term. We first introduce the following lemma, which upper bounds 4 defined in D.5).
Lemma D.1. Under Assumptions
4.2 and
4.3 it holds for any k 2 that
16(rmax RT)2 log(N d)
(Q (s)
Q (ss
No
where the expectation is taken with respect to randomness of wk+1 and (s, a) Pk+1-
Proof. See H.I a detailed proof.
On the right-hand side of E212) in E. of the appendix, for the terms not involving 1 i..., M1, M2. and M2 in (E.13). we take the expectation over p and establish their upper bounds in the & norm over (s, a) in Lemma E.5 On the other hand, for the terms involving 4 i.e., M, and M; in
E,14) we take the expectation over and then change the measure from to Pk+1- By Assumption
4.1 and Lemma D.I which relies on Pk++1 we establish the upper bounds in Lemma E.6 See part
of E. for details.
Combining Lemmas
B.5 and
E.6 yields Theorem 4.4 See E. for detailed proof.
E PROOFS OF THEOREMS
E. PROOF OF THEOREM 4.4
Recall that p is a state-action distribution satisfying (ii) of Assumption 4.1 We first upper bound K ( (s. a) Q* (s) for any (s, a) S x AA in part 1. Then by further taking the expectation over p and invoking Lemma D.I in part 2, we conclude the proof of Theorem 4.4
20

---

Published as a conference paper at ICLR 2021
Part 1. In the sequel, upper bound [k=o(Q'ss the definition of Q" in (2.2). holds for any (s, a) E S that
(Q" (s,a) - (s. for any (s, E A. By
(Q' Q x12 k1)]
Σ (1 7) (61P" (5, Quou+i (s,a)
Σ [1 7) (71p (-p" y++ ( (1p" - (s,
Σ[ (1 7) (ΛTP= yr + (7/p" ) (7p=*) ) (8,
2=
(7IpT ((1 r v. pa QT0 Q Q ((o,,))
(E.1)
where pp" is defined in 2.3 We upper bound (1-7) + g. -p Quaets - Q ( a) on the RHS of FE.1 the sequel. By calculation, we have
[(1 7) r +r++ 7 IPt Q - - (s.
[(LL -7) + y- pd (=*++1) - ((1 7) . Qwx) (s.0)
+ +[((1 -1)--)))- 7) r+ ppt Qwe) ((1 -7) rr pp Quil
(wx)) (8,a)
+ [(1 10---) 7) r 1 o+ Qwe) x=+ (s,aa
(s,
(s, a) A2, a) (3,
(E.2)
where AI,,, A2,s, and A are defined as follows,
AL,(s, a) = [>(PT' - p )Qual (s, A2, a) [NPT (0 Qui (s, A3, a) (T Que - (s)
(E.3)
Here T is defined in (.4). By the following three lemmas, upper bound A1, A2, and A3, on the RHS (E.2), respectively.
Lemma E.1. It holds for any as, E S A that
(s, [>(ITT' - 1 1m S [78 P(D, + + (s,,))
where In and 1 are defined as follows,
(s) KL (-1s) To. (-1s)) - (L(== Torm (-1s)),
(E.4)
c (8) (log( me.. (- s)/ 1s)) 3-1 Qwi (8, xx (-((=(())) 1 (.11)).
(E.5)
Proof. See H.2 for a detailed proof.
We remark that of included in Lemma I only aiming to generalize to the deep neural actor-critic method. Lemma E.2. It holds for any (s,a) E S A that
O for any k in the linear actor-critic method. Meanwhile, such term is
A-1
A2, a) s y - Qua)) (s, a) + 78
Σ
3t +f4)))(ss,))
==
Iy y G4 (8)
where 9, is defined in E.4 of Lemma E.I E is defined in E..)) of Lemma E. and e is defined as follows.
(s, a) + - Qw: Qus)i(ss,a)
(E.6)
21

---

Published as a conference paper at ICLR 2021
Proof. See H.3 for detailed proof.
O for any k in the linear actor-critic method. Meanwhile, such term is included Lemma H.2 only aiming to generalize to the deep neural actor-critic method.
We remark that &
Lemma F.3. It holds for any (8, E A that
A3, [ pT (T - 7 (8,
where 6k41 is defined as follows,
(x+1(s,a) (Qw, -T as)
(E.7)
Proof. See
H.4 for detailed proof.
We upper bound et+1 in E.7 of Lemma E.3 using Lemma E.4 follows.
Lemma E.4. It holds for any (s,a) S A that
A II pTo.) sm44-1
cx+1(s,0) z 7
p
El +
(1:3Peh/t++ + (1 Jef) (0.a).
where ef(s,a) a) is defined in (E.6) of Lemma
E.2 and eb 1 (8) is defined as follows,
ci (s) (log To (-1s)/ no. (-1s)) g-2 Qw. (s, .), ne. (-1s) To (-1s).
(E.8)
Proof. See
H.5 for detailed proof.
We remark that e 0 for any i in the linear actor-critic method. Meanwhile, such term is included Lemma E.4 only aiming to generalize to the deep neural actor-critic method.
Combining Lemmas
E.3 and
E.4
we obtain the following upper bound of As,k
As, = Fp (I
>P 1) -text1] (s,
k
< M (1 ( -
p
el
(E.9)
II p
(s, as,
a=141
Combining
E.1 E.2
Lemma
E.1 and Lemma
E.2
it holds for any (s,a) E x A that
K
10"
Q n ((, a)
k=
k (I - 7pp= 11 ( Qwo) ->
(2/1p*) ) + +
k=
4=0
Σ (ppp m- c4t + As. As. (s,a)
:
K
K Σ>
17 - -pp=
(ypp) 1
-Qwn) +
(yp b y
(E.10)
k=0
0== 1=0
K
(11p" ) -k- E-ieg
E
+
A3,
par y (s)a),
k= 1=
k=0 0
k= 0=0
22

---

Published as a conference paper at ICLR 2021
where ih,, +1 1 and 6x+1 defined in (E.4) of Lemma E.1
(E.5) of Lemma E. (E.6) of
Lemma E.2
and (E.7)
of Lemma
E.3 respectively. We upper bound the last term as follows.
K
K
(7lp
3P0; (8,
=
78
)'OrR (0,aa
k= 2=0
k=U 1=0
y5(PP" yPP Σ
8x-i (s,
79 Y'P
(L (To-..) KL(TT) m0a- (8,a)
k=
(B 1M' yPP(KL(T [T.))) - KL(TT" Tex (s,a)
yB pd ((PK)""""P((FF TT.) (s,
(E.11)
where we use the definition of dR-c in E.4 of Lemma E. and the non-negatyvity of the KL. diver- gence in the second equality and the last inequality, respectively. By plugging (E.9) and EE.11 into E. we have
K
Q T0 (v)
k=0
[I ypp" )-1
Σ
(ypp pk+1(Q"* Qwa) + Σ>
(np² yk= 35-2y330 yyPe
(E.12)
k=0
k= i
K k-
k
(71pp y
k+ 4+118001111 (I - --
II
f+11
km0
1=0
km0
K
-I- yIpoue )ct) ) (s)
prm.)
(1/SFc + (I-
k=0
8=1
a=t+1
K
+
Σ 1=0
(1/P** 1' TTo))
We remark that ca c/ 0 for any i in the linear actor-critic method. Meanwhile, such terms is included in [.. only aiming to generalize to the deep neural actor-critic method. This concludes the proof in part
Part Recall that p is a state-action distribution satisfying iii) of Assumption 4.1 In the sequel, we take the expectation over in (2.12) and upper bound each term. Recall that c = c for any in the linear actor-critic method. Hence, we only need to consider terms in (E.12) that do not involve ct or ch We first upper bound terms the RHS of (E.12) that do not involve c
More specifically, for any measure satisfying satisfying iii of Assumption 4.1 we upper bound the following three terms,
Mi Ep (I 7p
Σ
(Q" (xpa")httl
(xpp" yu+
Qun)].
M2 = E, (1 - 11pp )-1
A+1 1 (1 700004411
el
k=0
M₁ Ep [1 - 7p
(y1p= ) 3 (ou)
(E.13)
We upper bound M1, M2. and M3 in the following lemma.
23

---

Published as a conference paper at ICLR 2021
Lemma E.5. It holds that
Mil - 4(1 -7)- (Fmax + R),
|M2 (1 3 (2R Tmax);
Ma - (1 -2 logg [A]
K2/2,
where M1, M2, and M3 are defined in EE.33)
Proof. See H.6 detailed proof.
Now, upper bound terms on the RHS of (E.12) that involve e;-1. More specifically, for any measure P satisfying (1i) of Assumption 4.1 we upper bound the following two terms,
M4 Fp (T- yTp "
pr
9+1
(E.14)
A==
1=0
K
Ms = Ep (1 yP
p #+1 (I
71
E+1
II s=t+1
Pr )1 70
k=
t=1
We upper bound M1 and M3 in the following lemma. Lemma E.6. holds that
|a & 3KCPpp EQ.
[Msl S KC EQQ
where M4 and M3 defined in E4.14)
Proof. See H.7 for detailed proof.
Now, by plugging Lemmas E.5 and
E.6 into E.12). we have
E,
Q" (s a) = (s, a)
k=0
$ 2(1 - 7) log [A] 1/12 + 4KC,pp . + O(1).
(E.15)
Meanwhile, by changing measure from p" to PM+1. it holds for any k that
Ep- Ge-lee+ill S
B [[eg a)) Øi+1>
(E.16)
where o,+1 is defined in Assumption 4.1 Also, by Lemma D.I it holds that
Ep [6 (s. a))²] O(L((VNo") log N).
(E.17)
Now, by plugging E7.17) into EE. 1. combining the definition of EQ max; Ep [ we have
sQ = ((8b"((VNo')) log N).
(E.
Combining E.15
E.18 and the choices of parameters stated in the theorem that
N = Q(K p.p- /0")2 N).
we have
K ('( 2 (s, s (2(1-2) -3 log |A| + O(1)) K//2
E
p
A=
which concludes the proof of Theorem 4.4
24

---

Published as a conference paper at ICLR 2021
E.2 PROOF OF THEOREM C.5
We follow the proof of Theorem in E.1
Following similar arguments when deriving E. E. in
E.1 we have
Q 100x+=)(e (()
k=0
K ( jetttt" Qwo)
(I 1-pprii-1
Σ
(yp jk- 3/Pc
(E.19)
k=0
A=U
K k-
(11p" yk- 1+1
(" y 7BPP. KL(TT" || TTo)
k=0
1=0
1=0
1pt1 (I -yyppan 71
pmas e1
K
+
[+oe+1 (1 - pp )-1
6+1
(SWPEL+1- - (1-71p0) )e})
(s, (s.
k=0
s=t+1
for any ()) E E x A. Here c+ 44 441 and are defined in
F.5
E.
E.6
and
respectively.
Now, it remains upper bound each term the RHS of E.19 We introduce the following error propagation lemma.
Lemma E.7. Suppose that
Ep (0, Th+1 (8-1Quu Th Th (s, (s)))))) s Ek41ff
(E.20)
Then, we have
Eg (s) I 22rit Ext1, (0) + +%)) Eg [|ck (s)l S 2 Ekti, (1 + th),,
where 4 and b k441 are defined in E.5 and E.8 respectively, of and +f defined in Assump- tion
Proof. See H.8 for detailed proof.
Following from Lemma F.4 with probability at least ((H.) (m))) have 1wus S 2. Also, from the fact that (r(s,a) < Tmax- we know that |Q" & Ymax- Therefore, for any measure p, we have
Bp (T -1p="
Σ
(1p Sopt"y+t((Q QQaa)l
K
$ Ep (1 - ypp=
(ypp y - Qwol
km0
Tmaxx (1- 71
A+1 1 < Tmax (1 77)
(E.21)
k=0
25

---

Published as a conference paper at ICLR 2021
Also, by changing the index of summation, have
Bp
(1 - y1p
2=0
K
Ep
( pp
y:
k=0 2=0 3=0
K
(sIp) ) y ]1
E
k=0 i=0 1=
6
17BPettlll
(B.22)
k=
where we expand -1- --1""">-11 into an infinite sum in the first equality. Further, by changing the measure of the expectation the RHS of (E.22). we have
K
Ep y
373
B ++ c(I) E. (le
(E.23)
O i=0
km
tmk-
where c(l) is defined in Assumption on the RHS of E.23p, we have
C.I
Further, by Lemma E.7 and interchanging the summation
Bp (I yp
(yip) y 3y3Pe+11
k= i=0
K
8
k
(((t)(()) ( + +
k= 1=0 max (U,k-t}
K
8
4kt ++ c(t)) - + +*)
0= t=0
K
< 7
4C Eg(Ø" + +b² S 27KC + + -gs
(E.24)
k=0
where e max, E (3
a))))//1 and Cp,p- is defindd
in Assumption C.I Here in the second incquality, use the fact that T441 (i + 1) 8-1, and oi I 6" and vhe * by Assumption C.I
By similar arguments in the derivation of E.24
have
K R-1
Ep [1 [1 (1-1pp0")
(MIP* jk-
< 2(K + 1)C:,p- -QQ
(E,25)
i=0
F.p [T (T- (I-1 y-1
(7Tp=" ) "73PKKL (To)
< log |Al K1/2(1 - -
k=0
k
E2 (T 7pp=")
k+ p (I =
pTo,
e1
(2 Tmax) (1 733
where ba max; Ep [1k And we the fact that = K1/2
26

---

Published as a conference paper at ICLR 2021
Now, it remains to upper bound the last term on the RHS of (E.19) We first consider the terms involving c241 We have
K p To (I - 7P ?
k
Ep (I
7p")
II
pns. BrTPEE+1
sm8+1
Bp (SiPe ((SIIP ) g
By Sy/PPE241
8=6+1
H4 E,- (Pe c(i + j + k - 1
K
< 27
(L+ 1)es (1 w2) cii + j - -++ (E.26)
1=0
where we expand (I ) and (I - - to infinite sums in the first equality, change the measure of the expectation in the first inequality, and use Lemma E.7 in the last inequality. Now, by changing the index of the summation, we have
00 00
H4jtk-441
(1+1)))(1++00 dit + + k -
E
+e+ (2) c(t)
41
Σ
Σ
(e + 1)8y (1 + x²) c(1);
(R.27)
ma.
where we use the fact that v. 30 from Assumption C.1 in the last inequality. By further manipu- lating the order of summations of the RHS of (F.27). we have
Σ
(e c(t)
km j-
max (0.+ ++1]
8 ++++1
Σ (t
k - +
Σ (=j+k+2
12 -/((t) = + +T)
k=0j=0 1=
Σ
Σ
(t- + -
K=0
j= (0,-
1-k-
k2 r'((t)) .ey +²))
t=k+2
j=1
k
20
--tt//ll c(t) + Σ
h² tr nn'((t) ( (1)
k=0
t=l
< 20 K
Cp.p () + +b*),
(F.28)
where we use the definition of Cp.o" from Assumption C.1 in the last inequality. Now, combining
E.26
E.27
and E.28 we have
K
Ep
(I yp
P (I p
k E+1
II s=
prw.)
By
k=0
8=
$ 20yK Cp.p" Ef (1 v²)).
(E.29)
27

---

Published as a conference paper at ICLR 2021
Following from similar arguments when deriving (E.29). we have
Ep (1 7/p= 1 (1 71p
II 1 )
8=8+1
S 20K Cp.r Ø EQ
(B.30)
Now, by plugging (E.21) (E.24)
(E.25).
(E.29)
and
EE.0 into E 1.
with probability at least
- O(Ho) exp( S2 H me]), we have
K
E
(s, 1 ())
(B.31)
k=
< 2 log |A| k2 7) 60KKKK
GOOK pppp (0" + +0* + +1)- Ey + S - EEQ-
Meanwhile, following from Propositions C.3 and C.4 it holds with probability at least 1/K that
f = 0 O + R m, 1 (logg m,, 1/22)
EQ O ( + R m 1/12 H (m.
(E.32)
Combining
E.3
EE.2 and the choices of parameters stated in the theorem, it holds with proba-
bility at least that
1/ K
K
Σ
- & (2(1 -3 log |A| + 0(1) K1/2
(s.
p
A=
which concludes the proof of Theorem C.3
F SUPPORTING RESULTS
In this section, provide some supporting results in the proof of Theorems 4.4 and C.5 We
introduce Lemma E.T which applies to both Algorithms | and 2 To introduce Lemma for any policy π and action-value function Q, we define ((a Lemma F.. For any E S and n we have
x exp B Q(s. x(a s).
8-1 (Q(, (+ # 8)} (L (-] (r) [[- |s))
(log(=(-10)//(( (8) - -(s,
) + ( # #(-1a)).
Proof. By calculation, it suffices to show that
H(-1s)) (1gg((((1s)//((1)))==))))) --
(-1ss
(L(T*(-Is)) [[ [s)).
By the definition of the KL divergence, it holds for any S that
<L(=((-|>) ( 8)) KL( (1s)
= -logg(#( ( s)/ ()) m² m 8)).
(EI)
Meanwhile, for the term on the RHS of (F.Ip. have
(- (
+ ((og([[(1)//(((]))))(( -7(1ss)
(lg(((((1))/((11)))=((((1 -i-- + KL(F((1ss) [[ [T)
(log(#(:1s)) (f)) (-1s) 7 7(-1s))
(R2)
Combining F.I and (22). we obtain that
(log (00((7(())//((())))
#(-1s))
<L (((1s)) (L( ()) ((.15)))
which concludes the proof of Lemma E1
28

---

Published as a conference paper at ICLR 2021
F.1 LOCAL LINEARIZATION OF DNNS
In the proofs of Propositions C.3 and C.4 in G.2 and GG.3] respectively, we utilize the lincarization
of DNNs. We introduce some related auxiliary results here. First, we define the linearization To of the DNN E ((w, H. R) as follows,
(g(-) = uo (+) + (0 0b) Ve, 2o
where 0o is the initialization of ugg The following lemmas characterize the linearization error.
Lemma F.2. Suppose that H Omm//12p R - (logmm)1113 and m 22(d//2R-11 -- log(m" 1/1mmm////// /R)8/2) Then with probability least 1 - (xxp(-2((4 (2333//mm//))))) over the random ini- tialization og, holds for any 0 E B(O,, R) and any (s, E S x AA that
Vouo (s. Vous, (s, = = 0 2 (log m)
and
[Vong(s, 2 =
Proof.
See the proof Lemma A.5 in Gao et al. (0199) for a detailed proof.
Lemma F.3. Suppose that H = O( R-6 (log (1) and m 22d
log(m!/2/RB /2)/)))). Then with probability at least 1 - exp(-S(R'') mmm3//) over the random ini- tialization fg. holds for any 0 B(0,, R) and any (8, E x A that
()) (s a)l m01 5/ (log m) 1/3).
Proof. Recall that
üs (s a) = uo, [s, a) (0 - To) (s)
By mean value theorem, there exists E [0, 1). which depends on 0 and (8, a), such that
ug a) uo a) (0 6n) T (Vaue n0) (s, Vaua, (s, a)).
Further by Lemma [22 we have
[uo(s, a) uo(s, a)l < | 00112 V (s. Vouo, (8, a)ll
0 5 (log m)
where we use Cauchy-Schward inequality in the first inequality. This concludes the proof of Lemma
We denote by (b) the output of the h-th layer of the DNN E U(m, H, R), and (*).0 the output of the 1-th layer of the DNN uso E U(m, H, R). The following lemma upper bounds the distance between (N) and (N).0
Lemma F.4. With probability at least 2m H)) over the random initialization fo. for any 0 E B(0o, R) and any h E [I]], we have
(h) - x (h). = 0 (log (logm))/2) 1/2
Also, with probability least O(H) exp( (xp((SS(H-1m)) over the random initialization fo. for any 0 E Bi0n, R) and any h E [H], it holds that
2/3 < (h)
(h) 2|2 < 4/3.
Proof. The first inequality follows from Lemma A.5 in Gao et al. (001)) and the second inequality follows from Lemma 7.1 in Allen-Zhu et al. 2018b).
29

---

Published as a conference paper at ICLR 2021
G PROOFS OF PROPOSITIONS
G.1 PROOF OF PROPOSITION
The proof follows the proof of Proposition 3.1 in Liu et al. (2019). First, write the update
Tk+1 f- argmax, Eug [Quu (5,-),=(( (-(1s) B- K-- [T[ 8) To. (-1 as a constrained optimiza-
tion problem in the following way,
max Eyg
(TT 8), Qwn (s, - 3 (L(T(. (8) To (:1)))
S.L.
Σ aEA
(a 8) 1, for any & E
We consider the Lagrangian of the above program,
J (m (o((-|s), s), Qw, (s, -)) 3 KL (L
dr)(s)+ (=1s)))dr((s)) To, (- (-1s))
/ <Er(a)
x(a| 8) 1) dd(ss,
LES aEA
where A(-) is the dual parameter, which is a function on S. Now, by plugging in exp(TT (s.aa) Te. (a s) En'e exp(TT So (s,
we have the following optimality condition,
Qun (8, + BTÆ² fo, (8, a) - 3 (1og Σ
exp(TT So, So (s,aa))) + log ((a))) +1)
A(s)
0,
(s)s)
a'EA
for any (8, ESS Note that log En exp(Tx explT for as)) is only function of Thus, have
aa+1(a| s) (s, + Tk fo. a))
for any (s) E S x A, which concludes the proof of Proposition 3.1
G.2 PROOF OF PROPOSITION
We define the local linearization of Sa as follows,
Jo Soo + (0 - -0) Vo.So
(G.1)
Meanwhile, denote by
Jn (Je(n) - 7. 13-1uu + +
[o)) Vols(n)
9h Epn, [gn],
In (Fe(m) - 7. 18- + - f0)) Vofe.
9h E Bag [mm]
9. (fo. F (8- Qu - fo)) Vofe..
g. E Epro [g=),
g. (Jo. - (8 'Qu + - (-(() VoJeo,
G. = E Epng [T,]:
(G.2)
where 0, satisfies that
0, = (8) (0, a g.).
(G.3)
By Algorithm
we know that
( 1) (8)00. gn).
(G.4)
By G.3
and G.4 we have
Ep [] + 1) 1 [(n)]
Ep., [I[L' (w) (0(n) gn) - -I' L'. ( (0. g.)11 [())
< Epro [1l(8(n) a gn.) -00 a 31 (m))
= =10(n) - 0. 1 + 2a (0. - B(n), 9f. ..) +a² E
[llgn 501l [(m)].
(G.5)
pry
(ii)
30

---

Published as a conference paper at ICLR 2021
where we use the fact that I T(,,. R.) is contraction mapping in the first inequality. We upper bound term (i) and term (ii) on the RHS of G.55 in the sequel.
Upper Bound of Term (i), By (0. ((),, Sh 9.) (0. 0(1), Ih 9n)) + (0. (()), In 92)
inequality. holds that
I 10. 0(n)ll2 l9 - g2 + (0.- (m)), In - g.)
I 2R. ll Filll + (0. - 0 -
(G.6)
where we use the fact that ((n), 0. B(Ou, Ra) in the last inequality. Further, by the definitions in G.2.. it holds that
(0. ((n). Ih
g.) Ep [(fo(n) fo.) (0. - -()), Vefa.)l
= Epe, [[o(m) - fo.) ). (Fo. - [o(m))]
= Bpe, [[F((n) )o.)²1,
(G.7)
where we use GG. in the second equality. Combining (G.6) and G.7 we obtain the following upper bound of term (i).
(0_ 0(n), In -.. S 2R. l9 - Tfll2 Epe, [[o(n) - fo.)"].
(G.8)
Upper Bound of Term (ii). We now upper bound term (ii) on the RHS of G.5 It holds by Sauchy-Schware inequality that
Ep-, [ll9= 5f1l2 [n))] I pE [llan gill2 [())] + 2 - 32
$ 2 pep [llon
9 19ll [(m]]
+4 I Fall
+4
(G.9)
(ii).a
(ii..
(i..c
We upper bound term (ii).a, term (ii).,, and term (ii..c in the sequel.
Upper Bound of Term (ii).a Note that
Epzn [ll.. If 1 (n) Ep,, [11. 11 11 1B (()) S Ep_, [1 12 0(n)). |
(G.10)
Meanwhile, by the definition of in (G.2), it holds that
11 11 (Fo(m) 7. 1u fo)= 2 Vofe(m)l1
(G.11)
We first upper bound Se as follows,
fo x (Ha) bb
TT (Ha) = (Ha)T (HH (HH,) |اا 1
where z (Ma) is the output of the Hy-th layer of the DNN fe. Further combining Lemma R4 holds with probability at least O (H.) exp( - Q(H (117-mm,] ma)) that
[fl 2.
(G.12)
Following from similar arguments, with probability at least 1- [ 5 2.
we have
Qu
< 2,
(G.13)
Combining Lemma F22
G.10
G.
G. and G.I3 it holds with probability at least 1
exp(-S2 R2 m
2/3
H.))
that
E Pro
[1g..
1: 0(n)] = O(H3),
(G.14)
which establishes an upper bound of term (ii).a.
Upper Bound of Term (ii).b. It holds that
F2l12 ||12-1022 [pps [[Je(n) - 7 Qw- + [0)) Volo())
(Fo(m) - 7- Qu + 7 fo)) Vofa.
$ pno [1|5a()) Vole()) - Fo(m) Volo,
7 Epsa |1[0-- Q. + -- fo) (Vofe, Vofa(n)) 1z]
$ Ep., [I]fo(n) Vole. Fo(m) Volaol12 [||| + +Ep,, [I]fo(m) VoJo(n) - So(n) Volaoll l12
(G.15)
+ Ep. [1[7 1 (8- Qw + - f6) (Vefe. Vofomm))
31

---

Published as a conference paper at ICLR 2021
We upper bound the three terms on the RHS of (G.15) in the sequel, respectively.
For the term (lfo(m) Vefe. - fo(m) Vofaulla on the RHS of G.15), following from Lemmas F.2 and F3 it holds with probability at least (
mm Ha)) that
2/3
(lfo(m) Vofo. fa(m) Vofo. = O
/m 1/6 H
R m
(log (2)2))
(G.16)
For the term (1 Vofo(n) - F0c Vofe,ll2 on the RHS of (..5). following from (G.13) and
Lemma F.2 with probability at least exp(- R2/3 ms
2/3 Ha)), we have
[s((m)) Vole(n) Se(n) VoJa. 11 = 0 p2_ m m m,,6 H (log ma 1/2))
(G.17)
For the term ||F 18 fo) (Vefen Vefomm))l2 on the RHS of G.15 we first upper
bound 7 (B- + fo- as follows,
1-18-1Qu + fo) 2. F (8 Qu
where we use G2112). G.13). and the fact that 7-1 = =3- +0-+--1 +r- Further combining Lemma F.2
holds with probability at least exp( 22 2/2 2/3
ma Ha)) that
| (3 Qu + So) (VoJo, Vole(w) Ill = ( m_ -1/6 1//6 1/2). (G.18)
Now, combining G.15).
G..7 G.
and G.18). it holds with probability least
exp(-S2( 2/3 2/3 ma Ha))
that
llff
T.. 1 = O m 1/3 H logma),
(G.19)
which establishes an upper bound of term (ii.b.
Upper Bound of Term (ii).c. holds that
c 1
Ep., [(fo()) fo. Vo.o.ll Epp, [(Fo(n) VVooo,,,
Further combining Lemma
Ha)) that F22 holds with probability least 1 exp( ( 22/3 2/3
mia
lg
gfll3 O(H2) Ep., [(Fo()) )1
(G.20)
which establishes an upper bound of term (ii..c.
Now, combining
G.14).
G.19p and G.20 we have
Ep,, [llon - g. 2 [n)) s 0 ORR m
1/3 H logma) + O(H)) Epe, [(fam) - fo.) (G.21)
which is an upper bound of term (ii) on the RHS of (G.5).
By plugging the upper bound of term (i) in G.8) and the upper bound of term (ii) (..2 into
G.5 combining [G.19.. with probability at least exp(-S((R"" ma 2/3 Ha)), we have
E Peg [||0(n + 1) 0x 11113(((m))
< [10(m) 112 + 2a (O(R7/5 m 1
H/ (logm.) 1/2) Eps [(f(() - Fo.)²1
(G.22)
a² (O(R)/3m, 1/3 H log m.) + 0(H3) Ep., [(fo(m) Fo. 31)
Rearranging terms in G.22 holds with probability least 1 expl exp(-S((16) /2 2/3 m2 H.)) that
(2a- 222 .O(H)) Ep,, [[Fo(n) fo.)² < ((((m) 0.113 B,., []10(n 1) 0-113 [())) +a O 1/r6///=1//// 11/6 H log m.).
(G.23)
32

---

Published as a conference paper at ICLR 2021
By telescoping the sum and using Jensen's 's inequality in (G.23). we have
N
Epnp [Vo [o. 5
po [[Je()] - 1o.
Na
n
$ 1//Na (2a - a² ((H))) (1100 - 0.113 + a.a. O m 1/6 H log ma)) 1/6
S N/ -160 - 12 + (
1/2
3 m m H² log ma),
where the last line comes from the choices that a = No 1/2 N/2 and H3 O(N)/4). Further combining Lemma F.3 and using triangle inequality, we have
Ep-o [[fo - )o = O 1/2 + R8/3 m
m - 1/6 H² log ma).
(G.24)
By the definition of 0. in G.3 we know that
G 0_) 2 0,
for any 0 E B(Oo, Ra)-
(G.25)
By plugging the definition of g. into G.25 we have
Ep-, [ffe. F (3 Qu for. -fo.'] 2 0,
for any 01 E B(0.. Ra).
which is equivalent to
0, argmin
E Ep.. (Foo F. (B- (0)))
(G.26)
a (BB
Meanwhile, by the fact that 0g wp. have
7- (8- Qu + [o) = 7. (g-1 (Quo + (w- - ww) T VuQuo) + (Jao + (0--00) 0n) Vola.))
= fo. + (F (8 w + 10) 10) - 00) VoJen
where the second line comes from F-1 = 3-1 + + Note that B()), w E Blwo, Re), to wo, and Ra = Re, we know that 7 ( + 0) E B(0,, Ra). Therefore, with probability
2/3 least 1 (P((-S((RR ma Ha)) we have
Epe (Fo. - 7. 18- + - f-))
< pNo [ . Qu -11 (0) - - 7- fo)) }
< 72. 8-2 Ep., 11Qw Qw) 31 + 72
7- 2 Ep [1Fo fo
= ( m 1/3 H log m.),
(G.27)
where the first inequality comes from G (6) and the last inequality comes from Lemma F.3 and the fact that R. = Rg. me = ma. and He = Ha. Combining (.24 and (G.27). by triangle incquality, we have
Ep ((f(s, a) -
N. 1/2 R8/3 m 1/6 H. log ma).
which finishes the proof of Proposition C.3
G.3 PROOF OF PROPOSITION
The proof is similar to that of Proposition C.3 in G.2 it here. We define the local linearization of Q., as follows,
For the completeness of the paper, we present
Qu Qwp + (w wo) T Vuu VwoQu Qw
(G.28)
We denote by
9n. (Qw(n) (s0, ao) - Qu (1) - (1 - (1))) - mp)
V_Qu(n) ao),
9 = Er, [gn],
fn (Qu(n) (s0, 2o) - 7 Qu 01) - (1 -1) TV)
Va (0))
0 = Ero 17n,
g+ (Qw, (50, ao) 7 a1) - (1-7) -ro)
VuQu. (50, ao),
9 Exo [9+]]
g. (ue. (s0, an)
- Q0( (1-7) .ro)
Vu (50:00);
DE E [g-],
(G.29)
33

---

Published as a conference paper at ICLR 2021
where w. satisfies that
We = T R. - a. T.).
(G.30)
Here the expectation Exy [1] is taken following (so, an) Pro (.), P(. 80, ao): an ~ no( 11),
and rp = r80: (o). By Algorithm 4
we know that
w 1)
I' -'o((a, (w)) -1 -n)).
Note that
E [[ 1) - ww 1121 w(n)
EiT [||I' [(l')(.o. (w)
(wh 17- g2)1 [ 7) 9n) - Biss, (1/
Eio [l[(w(n) [n) -ww- 17.00 (100") 113 w [n)]
[[((n) w- 1/2 2m- (w. w()). of g.) +np
E [llgn
F.ll2 [n)]
(G.31)
(m))
(iv)
We upper bound term (iii) and term (iv) on the RHS G.31 in the sequel.
Upper Bound of Term (iii). By Hölder's inequality, it holds that
(w,, ((n), In - g-))
(w,, (n). In gn) + (w,, w(n), Tr - S I|,, - w(n)lle ll Gfll2 + (w. w(n), In g.) 2Re ll Tfll2 (w. w(n). gE),
(G.32)
where we use the fact that w(n). wx E B(wo, Re) in the last line. Further, by the definitions in G.29.. holds that
(ws w()), Ih -ー))
Ex [(Qu(n) (50, ao) Qw. on)) (w. w(n), Qw aol]]
Ex, (Qu(n)) (Su, ao) Qw. (8o, 0n)) )- (Qw. (So, an) (80, an))]
= E (Su, ao) Qu. (80, an))² - Epe, [1Qw(m) Qw.)²
(G.33)
where the second equality comes from G.288), and the last equality comes from the fact that the expectation is only taken the state-action pair ag). Combining (G.32) and (G.33). obtain the following upper bound of term (i),
(w - w()), oh - g.) s 2R. ll - Fill2 Epro [(Qm(n) - )3.
(G.34)
Upper Bound of Term (iv). We now upper bound term (iv) on the RHS of G.31 It holds by Cauchy-Schwarz inequality that
Ex [llgn Ffll2 113 w())
< 2B []l.nn - 3 (n)) + 2l1gh gfll2
< 2 Era [llan
Iff ll [n)] +4 l F..
+4
(G.35)
(iv).a
(iv).b
(iv).c
We upper bound term (iv).a, term (iv).b, and term (iv).c in the sequel.
Upper Bound of Term (iv).a. We now upper bound term (iv).a on the RHS of (.355). By expanding the square, we have
Exs [1lg. of 2 [n)] = E.o [ll... 13 lo w(n)] s Em. [lle, [[(]]]]
(G.36)
Meanwhile, by the definition of gn in G.299.
holds that
|g,, l1 (Qw(n) oo) (s1, a1) - (1-7) ro)2 - (o
(G.37)
34

---

Published as a conference paper at ICLR 2021
We first upper bound Q follows,
L x (H)) bb (H) = =x(H.)T ( (HH)) ||o:(He>)13
where x. (He) is the output of the He-th layer of the DNN Qu- Further combining Lemma R.4
holds that
1Qw1 S
(G.38)
Similarly, we have
(Q)()) 2
(G.39)
Combining Lemma F22
G.36),
(G.37),
(G.38)
and (G.39). have
Exo
[llg.
- [n)] = O(H2).
(G.40)
Upper Bound of Term (iv).b. We now upper bound term (iv).b on the RHS of G.35 It holds that
llg. Tall2
= Bro (QQu())(8s, an) - Qu(s), -1 ro) V (u
- -(Qu()) ao) - 7 (1(
ro) Vu (s0,
s ET [][(> Qu a1) (1 7) 11) (V.Ruo an) V Qu an))
+ Epp, [I[Qw(n) Vo Qw(x)) - Qw(n) VoQual12]
- ETo [|( Qw a1) + (1 .r)) Vv ao) V. (w() an))ll2 (G.41)
+ Epey [w))Q((m) Qm())) Qw. [1a] + Ep,, [1[Qu(m) (V V V Qwo)ll
We now upper bound the three terms the RHS of (G.4l) in the sequel, respectively.
For the term Ep-, (Q(())))))) - Qw(n)) V Qwn [|a] on the RHS of G.44 following from Lemmas and
it holds with probability at least exp(-S2(He 2/3 me He)) that
2/3
p [I((Qu(m) Qu(n)) VuQua [Il] OO m. 1/6 H
(G.42)
For the term E [11Qw(m) Quw - V Qw, |1l] on the RHS of (G.41) following from (G.39)
and Lemma F22 with probability at least 1 - exp(-
2/3 m He)), we have
2/3
Epro [1]um)) (VuQu(m)) Vulu, |12 0 OR!
1/3
mm
m- 5/2 / (logm.)
1/6
(G.43)
For the term E E., (y (s a1) - 7) 7). (V (So, (80, - Quiui) (su: (12) on the RHS of (.4T) we first upper bound 1 Qu (81, (1) + (1 - -7) rol as follows,
h Qu( a1) + (1 7) rol 2 Timax
where
G.38 and the fact that (r(s, a)] < mmax for any (s, a) S x A. Further combining
2/3 He)) we have Lemma R22 with probability at least exp( 12 R2 me
E [l[(> (w 01) + (1 7) ru) - (V Qwn (8g. an) (a an)) = -O(R//3m_11/ H5/2 ( 1/22.
(G.44)
Now, combining G.41).
G.42
G.43
and G.44). it holds with probability at least
2/3 (Rp(- m H²)) that
l1o
0. 12
/3 m. 1/3H7 log me).
(G.45)
Upper Bound of Term (iv).c. We now upper bound term (iv).c on the RHS of G.35) holds that
1o 3.113 = Ep., [[Qw(n) -
Ex,, [(Qw(n) Qu.)? ) || Qw,
35

---

Published as a conference paper at ICLR 2021
Further combining Lemma
F.2
it holds that
Emp
[19h
9
[[)] s O(H))) Epn [(Qw())) Qw.
(G.46)
Combining (.35). p. (G.0
(.45). and G.46), we obtain the following upper bound for term (iv)
on the RHS of G.31.
E [11ga
me 1.112 [m)] < O m 1/3 H log m.) + O(H2) Ppy, [(Qw(x) - Qw.)
(G.47)
We continue upper bounding (G.3I)
By plugging (G.34) and (G.77) into G.31 it holds with 2/3
probability at least 1 - exp( (
me Hc)) that
ET (n + 1) w.112 ((1))
$ [[w(n) w.1l3 2n (O // m
- 1/6 H (log 1/2) Epep [(Qw(n) - Qu. )2.
+ + (O / /
m 1/3 H² log m.) + OHH) Epe, [(Qw(n) Qw.) )w.
(G.48)
Rearranging terms in G.48 holds with probability least 1 exp(-S2(Ri,
2/3 2/3 He)) that Q(R me
(2n - 172 .OHH)) pMp [[Qw(n) - )2
S [w(()) w-112 Epz, [[w(( 1) - w. [[)]] + v) O
m 1/3 HH? log me).
(G.49)
By telescoping the sum and using Jensen's inequality in G.49) we have
N
Bpn, [1Q - Qw.)) No
E Epp [(Qw(m) - Qw.)
n=0
$ 1/Ne. (2n - 172 ((H))) (1lwoo - Wo 112 + nNVo O m/ 1001//6H log m.))
< NN-1/2 |10 0.11 O
1/6
H² log mc),
where the last line comes from the choices that 17 No 1/2 and He (4) Further combining Lemma F3 and using triangle inequality, we have
E Ep., [QQ Qw.) ) O(R@N-1/ mm/smm1// H mc).
(G.50)
To establish the upper bound of E,., I(Qw. - 2) we upper bound Ep., (Qu. Q) in the sequel. By the definition of w. in G.30). following a similar argument derive G.26 we have
Wx argmin Ep,, [[Qwt (t (So, au) - ((5. a.))
(G.51)
wtEB(wo.Re)
From the fact that Q U(me, He, Re) by Assumption C.2 we know that Q Qx for some w E Blwo, Ro). Therefore, by (G.5l), with probability at least exp(-SQ(RA 2/3 me He)). we have
2/3
Ep., [(Q.. (Q)..-Q)? Ep,, [10 - 2)² O m 1/3 H log m.),
(G.52)
where we use Lemma M& in the last inequality. Now, combining (G50 and G.52) by triangle inequality, with probability at least 1 exp(- ( RR
2/3 2/3 m H.)), we have
Ep [12 - 2)21 < 2E,r, [(Q0 - Qw. )2 + 2E,,, [1Qw. =OREN 12// m 1/6 H. log me),
which concludes the proof of Proposition C.4
36

---

Published as a conference paper at ICLR 2021
H PROOFS OF LEMMAS
H. PROOF OF LEMMA D.
W denote by Q T Que- In the sequel, we upper bound p (Q Qua )²) where Wk+1 = (=+(()++1) and Wk+1 is defined in (344) Note that by the fact that (| a) |l uniformly,
suffices to upper bound || W 2. By the definitions of wk+1 and Wh+1 1 in 3.5 and (3.4 respectively, we have
||x+1
@k+1ll2 1 100 Ø I 11 ||0 u112 + 1 1112 |01|2
(H.1)
Here, we use the fact that the projection (-)(-) is a contraction in the first incquality, and triangle inequality in the second inequality. Also, for notational convenience, we denote by o o, T and (H.I as follows,
Φ - (Bemn_l(s,,
t=
1
0 N
Σ (11 r2,,2 7Qua (8 2)2)) (((8,2 ac,2),
e p [(1 - 7)r + Qui) a) cp(s, a)]
By the fact that || || - 1, |r(s, a)l S Tmax. and || 2l2 S R we have
| S 1/0", |01| S Tmax + R.
(H.2)
Now, following from matrix Bernstein inequality (Tropp 2015) and Assumption 4.3
we have
B 11
log(N + dd,
(H.3)
VN
where o* is defined in Assumption 4.3 Similarly, have
E [
v v|lk] S 2(Tmax + R)/VN. llggNN d).
(H.4)
Now, combining H.1
H. and (H.4). we have
E. [[[w++] wx+1 1|2] 4(rmax + R)) Vo
-log(N (N d).
Therefore, it holds that
16(rmax + R)2
E (Que+) Quren )
lo + d).
(H.5)
Noo
Meanwhile, by Assumption 4.2 and the definition of Wk+1, we have
= =Qwet1
(H.6)
Combining H.5 and H.6 we have
16(rmax + Rt) Naa log? (N + d),
[[(Que+:
2))
which concludes the proof of Lemma D.I
H.2 PROOF OF LEMMA
Following from the definitions of Ipt and IP in (2.3 we have
A1, (8, a)
[>
1 Qun, (s, a) [>P(Qu n²" [00+1))
(H.7)
By invoking Lemma F.I and combining H.7 it holds for any (s E S x A that
A
p Qua (s, a) < [78 P(0s + c (s,
where 0r and c are defined in and E.5) of Lemma E.T respectively. We conclude the proof of Lemma R.
37

---

Published as a conference paper at ICLR 2021
H.3 PROOF OF LEMMA E.2
By the definition that Q the action-value function of an optimal policy x², we know that (s, 2 Q= a) for any policy and state-action pair (s, E S x A. Therefore, for any (s, x A. we have
A2) = [<>1p=' (Q Qwx (s) h-1p (Q" Qwe (s,
(H.8)
In the sequel, upper bound (s, Qwa (8. a) for any (8, a) E x A. We define
Qx+1 = (1- .r 1p Qwn
By its definition, we know that Qx+1= T Qwx holds for any (s,a) E SSx x A that
(x. a) - (8,
()) Qu+1(8, Q4+1(8, -um
Qwi+i
[((1 -7) r p Q*) - (11-)) - 1p Qu (+)(s,a)
[P" Q' - Pm
y [PT qp"'Q" pm Qw, +7. p- Qu Pu (0,
? [P" (Q"
11, (s,
S 7 |P" (Q" Qu (s.a)) P(Ox + (s,)) + (s,
(H.9)
where c:41 and A1,s are defined in E.6) and (E.3)
respectively. Here, we use Lemma E. to upper
bound AL the last line. We remark that H..9
upper bounds Q" QWEil using Q Qwa By
recursively applying similar argument as in H.9
we have
(s) - Qwi (s,a)
111p=* Qu.)) 73
Σ
I )hi + (( (H.10)
1=0
--1
Σ 16pp y (s,a)
Combining H.& and H.10),, it holds for any (s, x A that
12, a) < [>pp" (Q" - (s,a)
< [(>Ta (otpor)++((C (Q' -Qun)) (s, 7B
+(t))(ss
1-1
[(ylp i (8,
where 0,, ei and eL_, are defined in EE.4 of Lemma E.1
E.5
of Lemma E.1
and E.6 of
Lemma H.2 respectively. We conclude the proof of Lemma 6.2
38

---

Published as a conference paper at ICLR 2021
H.4 PROOF OF LEMMA E.3
Note that for any (s, a) E x A, we have
As, a) = (1 Que Q ((s
((1 - 7) r + Tp Qui) - Q (s,a)
[(1 7) ++ Qwa) Σ (1 (yIP )er (s,
==
- (n )'Que - (x)Prro=1))t Qwi)
-E (1 (1->)(>1p jor (s,a)
1=1
(s)pTet+s) ((Qu, - --pooeti - -(1-7) (77)).))(00)) (0,
(>1p (Quu, - Quei) (5.
( > [>Ip (I- (
where the term Ck+1 in the last line is defined in E. We conclude the proof of Lemma
H.5 PROOF OF LEMMA
We invoke Lemma F.1 which gives
g- 1 (Que (s, )) To.
Toa+1 (- {))
I (log( mo [8)/ no, (.1 {)) -g- Qwa (T a (.18))
KL (.1 s) To... (-1
S (log(Tex41 s) no. {)) g-1 Qwe (s, ), Tox (ox (-1s) Tozti (. (.1s) (s))
(H.11)
Combining (H.Il) and the definition of 1 in 2.3 we have
p Qwa - -P - Qun](s,a) S 3[Pe)+1l(s).
(H.12)
By the definition of ek+1 in E..7. we have
ek+ (8, a) [Qum - 7. T Qwe. - -11-7)-r) (s,
S [Qwm - 7 Tp Qwi - 71 r] (s, a) + By. IPe ((s,)))(s,a))
(H.13)
12x -y- pate Qx (1- ( (s) [ (1 (1-110 (1
where we use (2.12) in the first inequality, and
Q+ (1 7) . + y p Qwa-
(H.14)
For the first term on the RHS of H.13). by (H.14), holds that
Q 7 p Q2 (1 ()
(1 -1-7) 7) 7 p Qwi-n 7( - 7) 1p - (ypT0e)) )2Qum. -(1-7) -r
= 77 1p (Qur-1 - po Qwa- (1 7)r) 7/ 1p ek.
(H.15)
Combining (H.13) and H.15). have for any (s, a) E S x A that
(s a) S h ex) a) [SyPck (I -pp (s,
(H.16)
By telescoping (H.16). it holds that
Ck+1 (5.
[ N6.
pmo. ( (ByPe -T- (5.0).
s=1
s=i+1
This finishes the proof of the lemma.
39

---

Published as a conference paper at ICLR 2021
H.6 PROOF OF LEMMA E.5
Note that ||2l|22 < R and (r(s, a)l S Ymax for any (8, a) E S x A. which implies that IQ (3,, a)l S
R and [Q" (8, a)l Tmax by their definitions. Thus, for Mi. have
MM S Bp (T (T- y1-
Σ (ypp QQ Qwo!
K
$ 4(1 - ((11-))-1
h+1 (Fmax + R) $ 4(1 - 7) -2. -Fmmx + R).
(H.17)
km 0
For M2, by the definition of el in
E.
|wl S R. ((s, S and |n(s, a)l &mmax we have
lei(s,a) [[w
T Qwel(s.o)
= Ww o(s, we [p (3 - (1 (1-7) r(s, a)l
S 2R rmax
(H.18)
for any (s,a) 8 x A. Therefore, we have
|22 S (1 (1-7)- .2R + Tmax).
(H.19)
Meanwhile, by the initialization To oc in Algorithm| the initial policy no, (: (1)8) uniform distribution over A. Therefore, it holds for any E S that
/ π (a log
n²" <a s) Ta. (a s)
KL (x' (+1(s) || ne,(1 (-)
da
S (a) log ne, (a s)da
π (al log (a s)da
A
n" (a) log Te (a s)da
A
n (a|s)) 8) logl log AA.
(H.20)
Therefore, by (H.20), we have
M3 S (1 (1-7)-2 log |A| K1/2
(H.21)
where B 1/2 We that (H.17). (H.19). and H.21 upper bound M1. M2, and M3. respectively. We conclude the proof of Lemma E.5
H.7 PROOF OF LEMMA E.6
For M4. by changing the index of summation, have
Ma
E
K
R
(7p
k=0
1=0 ビ=k-i
K
k
Ep [(r (eg
(H.22)
where we expand (I- 1--pp">- into an infinite sum in the first equality. Further, by changing the measure of the expectation from to p" on the RHS of (H.22), we have
k
k
K
k
E,((TT
<
Σ
o fe(t)
Ep- 11e
(H.23)
k=
1=
t=k-
40

---

Published as a conference paper at ICLR 2021
where c(t) is defined in Assumption 4.1 of (H.23). combining (H.22). we have
Further, by changing the index of summation the RHS
k
M
7'(() EQ
R=0 1=0
i=max i= (0,k-0)
K
2t (t)) EQ
k=0 1=U
K
p.p EQ 333K -Q.
(H.24)
k=
where eq- = max; Bp- [1 I|. and Cp.e is defined in Assumption 4.1 Now, for M5, by similar argument as in the derivation of (H.24). we have
20
00
&
Ms -
(i+ -e+ 1)- EQ
(+1
30
Σ
xc(t)
EQ S ΣΣΣ cytc(t EQ S KCp.p' EQ.
(H.25)
1=++++1
We see that (H.24) and
H.25
upper bound M4 and Ms, respectively. We conclude the proof of
Lemma E.6
H.8 PROOF OF LEMMA
Part We first show that the first inequality holds. Note that
Te. (a 8) exp(Tx) fo, (s, a))a/a)) (s), Te (a (8) exp(Txt1 (s, a)) (s),
Here Zo, (8), Zon+a (3) E R are normalization factors, which are defined
(s) =
Σ
explTx (s,a'),
(8))((5)
Σ
exp(Ti (s,
a'EAA
a'EAA
Thus, we have
(Tog( (115)/
'uz (s. )) (-1s) To (-1s))
Sritifeew (s, ( (s, -) + Tx fex (s. )), T² (:1 () - To. (+1s))
(H.26)
where use the fact that
(log Zou (8) - log Zo. (8), (1 - T. (.18))
(log Zozei (s) log Zo. (s))
Σ (Tr (a' (a'ls)
Jo (a' (d|ss)
a'EA
Thus, remains upper bound the right-hand side of H.26 We have
(TTh for. (s, 10
Qwi (s. + Th for (s. +), n" (-|s) To._ (-1s))
(H.27)
π (-1s)
Torer (-1s)
= (3. (s, + Tr So. (8, 1)) Fe, (.18)-
no, (:
To, (8)
41

---

Published as a conference paper at ICLR 2021
Taking expectation with respect 2n on the both sides of (H.27) and using the inequality, we obatin
Eyg [I TT+t fo (s, ( (8, + Th foa (s, 1), a (-1s))
nh (- (+1)))]]
[81 144110L=1(811 (3% Que (s, + Th for (s.
π (-(-1))
Toi_, (-15)
)
v2(s)
T0 (118) (x)))
1/ (s) ds
To (-18) To, (.18)
SSXA Tk+1 1o4ts (8,0)
(3 Qwi (8,0) + Th So, (s.a))
p² pa(a|s)
To (al 8) vV
Pk((a dpp(8,a)
Pk(aa 8)
dp"
d(ToLLI r²)
dpk 1111
13/3111 1/2
$ Epx (T#t1 forts (s, -
(s, + Th for (s, (s))
Epp
dp=
I <2 EE4+1 (ot x1))
where in the last inequality we use the error bound in (E.20) and the definition of of and v in Assumption C.1 This finishes the proof of the first inequality.
Part The proof of the second inequality follows from a similar argument as above. We have (log(TTe::) (- (1))) - Qu, (s, )), no. (11s) (- -TTtti (s.-) (8- (8-1Que (s, + Tk for ()).))) To (-1s)) Toet (-1s)),
(H.28)
where we use the fact that
(log Zo (8) - log Zo, (s), 1T (1)
TBx11 (: (.]5))
= (log Zo. (8) - log Zop (s))
Σ
(To, (a' (8) To (al1s) = O.
a'EAA
Thus, it remains to upper bound the right-hand side of (H.28). We have
fotiJon (8. - (.5 Qwi, (8, + Tx= So. (8, 1), To, (: 18) T. (-1)))
(H.29)
(TTt (8,-) Qu., (8, + Tk - fo, (8, 1), no, (.1 (1- To (. (.1s)
To (. (.(s)
Taking expectation with respect to vd on the both sides of H.29 and using the Cauchy-Schwaad inequality, we obatin
Eg- (1 T for. (s, :) 1ur Qui (s,
+ Tx for (s, }), no, (-1s) To (-1s))]]
To (. (-1s) To, (.18)
T TotiSon Son (8, 10 (s.:) Th Sor (8. )): no (- (-18) )-) ux vx(())
v (8)
ds
(x((s
-SS T fort (0: (s, Q3. T fo. (s, ()))))] |1- To (a 8) (s)
dpp dpx(s,a)
Pk(a s)
< Epe (TTtii (s,a) (3 (s, + + 2o (s, Epu |1 d d( v²)
22
dpk
< <2r Sktif (1 +1))
where in the last inequality we use the error bound
(E.0 and the definition of 26 in Assumption
C.I This finishes the proof of the second inequality.
42


Reviews:
[{"review_id": "qHB96PfSkd", "reviewer": "AnonReviewer1", "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": "Summary:\n\nThe paper studies global convergence of actor-critic methods in the single-timescale setting, where in each iteration, the critic is update using the Bellman operator only once. The authors consider a setting where both the actor and critic are represented with either a linear model or a deep neural network. For this, the paper shows a sublinear rate of convergence of O(1/\\sqrt{K}) to the optimal policy.\n\nComments:\n\n- I think the analysis in the single timescale setting is an interesting question and probably more challenging than the two-timescale setting where the critic is assumed to be trained to (near) optimality. However, I am not sure how useful the result itself is - it matches the results for two-timescale settings. Why is such a result interesting? The authors don't show any lower bounds. Intuitively, one might expect the single timescale setting to converge faster than a double loop kind of algorithm. In some ways the paper leaves me more confused. \n\n- The authors claim the one advantage of the single timescale setting is the fact that it is amenable to the off-policy setting. I seem to be missing something here. Why can't the same argument be made for the two timescale setting? It might be useful to have a discussion on this in the paper. \n\n- Another confusion I have is that the paper nowhere assumes that the optimal policy is contained in the policy class. How does one get a global optimality result without this? In the function approximation setting, with the class of energy based policies, is there a characterization of the best policy in the policy class and the approximation error it incurs? Intuitively, I was expecting a residual error term in the bound.\n\n- Lastly, and this is one of my main complaints, I tried very hard to follow the proofs in the Appendix and despite my best efforts over a couple of days, I still don't have any intuition why this result holds - specifically, why only a single application of the Bellman operator to update the critic is enough. What do the authors mean by 'double contraction', a term often used in the paper. Clearing out Section D in the Appendix would be helpful - currently there are a bunch of equations, some with proofs in Appendix E etc. I am unable to verify these easily and hence not sure how the authors got the results. The main text only spells out the setting along with a rather long section on related works etc. but gives no intuition.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gZciFfzTWV_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 studies the finite time performance of actor-critic algorithm with PPO-type update. Global convergence  is provided by exploring the convex-like property of the objective function in the distributional space. Different from previous studies that focus either on two time-scale update or nested-loop update, this paper studies the single time-scale update scheme. Thus the result in this paper is somehow meaningful.\n\nI have the following questions for the author:\n\n(1) The algorithm proposed and stuided in this paper can be implemented in a \"single time-scale\" way only at a cost of high computational cost at each iteration, making the motivation of using this algorithm in practice less clear. The AC algorithm in this paper need a near-optimal solution in both policy optimization (actor) and policy evluation (critic) at each iteration, thus requires the critic to perform LSTD instead of TD(0). However LSTD requires computation cost of O(d^2) and TD(0) only requires O(d), thus TD(0)-typer critic is more favored in practice, especially when the dimension d is very large. Since this paper is a pure theoretical paper so let's forget about the practical concern first. Can the author highlight the technique challenging of using LSTD-critic instead of TD(0)-critic compared with previous work Liu et al. (2019)?\n\nBoyi Liu, Qi Cai, Zhuoran Yang, Zhaoran Wang, (2019) \"Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy\"\n\n(2) The critic stuided in this paper adopts projection to enable the whole proof go through. The projection is a practical issue which has been criticized by many researchers in the RL community. Can the author provide an upper bound for the projection radius so that the algorithm can be at least implemented in practice.\n\n(3) It seems that the neural network parameterization studied in the appendix is still a nested-loop algorithm, not a single-timescale algorithm that highlighted in the title and the story of this paper. I agree that it is meaningful to study the DNN in AC for the first time, but can the author compare the overall sample complexity in this paper with the sample complexity in Liu et al. (2019)? Does the LSTD-critic help to improve the overall sample complexity comparied with the TD(0)-type critic in Liu et at. (2019)?\n\n(4) It seems that the global convergence guarantee is highly depend on the soft-max parameterization, which has limited practical applications. Can the author still establish a similar result in the infinite-action space case by using a similar proof in this paper?\n\nI will keep my score if the author can answer the above questions.\n\n=== post rebuttal ===\n\nI am satisfied with the response and i will keep my score.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "O0oO0Ac7hDf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "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": "Summary:\n\nThis paper proves that the proposed single-timescale actor-critic algorithm with KL regularization converges to a globally optimal policy when appropriate function approximation is used. The authors define a specific form of actor/critic updates, which are PPO update for the actor and the single application of Bellman evaluation operator for the critic. Given such an algorithm, the authors provide an upper bound of the regret for linear and deep neural network function approximation (although there are some strong assumptions, e.g. no approximation error). \n\nReasons for score:\n\nOverall, I vote for strong acceptance. While I am not capable of fully checking the proofs, I understand the importance of the result. Based on the mathematical rigorousness of the main text and the proof sketch, I assume that the paper is technically correct. Given that the paper is technically correct, it is the first convergence result for a single-timescale actor-critic algorithm as far as I know (and the paper claims so). This work will be very significant as it theoretically grounds the single-timescale actor-critic algorithms, where the state-of-the-art deep RL algorithms are mostly single-timescale actor-critic algorithms.\n\nPROS:\n* The paper (at least the main text and the proof sketch) is well written.\n* First result on convergence rate and global optimality of single-timescale actor-critic, which is very significant.\n\nCONS:\n* No further discussions based on the results for better design of an actor-critic algorithm. It would be helpful if there are more discussions about the algorithm choice, i.e. being off-policy, broken assumption, etc.\n\nQuestions:\n* I still do not understand how this result can be applied to off-policy results, where we have $\\mathbb{P}^{\\pi_{\\theta_{k+1}}}$ in e.g. equation 3.4 and 3.7. How can the samples be reused if $(s,a)$ are not from $\\rho_{k+1}$ but from previous $\\rho$s?\n\nTypo:\n* Specifically, after K + 1 actor updates, we are interest -> we are interested? : before eq (4.1).\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AljIbLyWOjd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a theoretical paper. The paper studies convergence and optimality of the actor-critic with the function approximation in a single-timescale setting. The proposed single-timescale AC applies PPO for the actor and updates the critic by applying the Bellman operator to the critic one time. Despite the actor-critic coupling, the paper establishes global convergence with sublinear rates for the proposed AC method in both linear and neural network function approximation.  \n\nStrong points:\n\n(1) The paper is well-written, and the motivation is easy to follow. The paper also provides detailed literature on related works. \n\n(2) The studied AC is practical in the sense that both the actor and the critic can take function approximation and their updates work in the one-timescale. The proposed scheme could complement the previous study of the AC methods in the two-timescale.\n\n(3) The provided convergence theory could be some new insights into dealing with the coupling of the actor and the critic. The provided intuition makes sense to me although I didn’t get time checking proof details. \n\nWeak points and comments:\n\n(1) Although the paper provides a general setup for the one-timescale AC method, it is worth providing some generic examples to explain the theory, e.g., the energy-based policy with direct parametrization. \n\n(2) The theory seems to be specific to the energy-based policy. Are there any other types of policies that can also be considered? If not, it would be helpful to comment on the importance of the energy-based policy in practice or from the theoretical point of view? \n\n(3) The proposed AC methods rely on the population quantity, e.g., expectation over state-action visitation probability. How practical are they? Or how is the proposed AC related to practical one-timescale AC methods mentioned in the Introduction? \n\n(4) In (2.7), the critic depends on the current policy at k+1. What do you mean by they are updated simultaneously in the Abstract?\n\n(5) It would be helpful to make a table comparing the proposed AC with others in terms of sampling assumptions, policy classes, and convergence. \n\nI believe my concerns can be addressed during reviewing. For me, the development of this paper is new, and I am more inclined to agree with the acceptance.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most reviewers agree that the paper makes valuable contribution in analyzing single-timescale actor-critic algorithms. There were some doubts on the theoretical advantage over two-timescale algorithms and the realizability assumptions, but the authors made satisfactory clarifications. 

Therefore, acceptance is recommended, though I strongly suggest the authors to explicitly state key assumptions required to ensure global optimality in the abstract and introduction to avoid confusion. 

Decision: Accept (Poster)