Finite-time Analysis of Single-timescale Actor-Critic on Linear Quadratic Regulator
Authors: Xuyang Chen
Jingliang Duan
Lin Zhao
Venue: Submitted to ICLR 2023 (2023)
Keywords: single-timescale actor-critic
linear quadratic regulator

Abstract: Actor-critic (AC) methods have achieved state-of-the-art performance in many challenging tasks. However, their convergence in most practical applications are still poorly understood. Existing works mostly consider the uncommon double-loop or two-timescale stepsize variants for the ease of analysis. We investigate the practical yet more challenging vanilla single-sample single-timescale AC for solving the canonical linear quadratic regulator problem. Specifically, the actor and the critic update only once with a single sample in each iteration using proportional stepsizes. We prove that the vanilla AC can attain an $\epsilon$-optimal solution with a sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2})$, which elucidates on the practical efficiency of single-sample single-timescale AC. We develop a novel analysis framework that directly bounds the whole interconnected iteration system without the conservative decoupling commonly adopted in previous analysis of AC. Our work presents the first finite-time analysis of single-sample single-timescale AC with a global optimality guarantee.

Under review as a conference paper at ICLR 2023
FINITE-TIME ANALYSIS OF SINGLE- ACTOR-CRITIC ON LINEAR QUADRATIC REGULATOR
Anonymous authors Paper under double-blind review
ABSTRACT
Actor-critic (AC) methods have achieved state-of-the-art performance in many challenging tasks. However, their convergence in most practical applications are still poorly understood. Existing works mostly consider the uncommon double- loop or two-timescale stepsize variants for the ease of analysis. We investigate the practical yet more challenging single-sample single-timescale natural AC for solv- ing the canonical linear quadratic regulator problem. Specifically, the actor and the critic update only once with a single sample in each iteration using proportional stepsizes. We prove that the single-sample single- timescale natural AC(NAC) attain an e-optimal solution with a sample complexity of O ?), which eluci- dates the practical efficiency of single-sample single-timescale NAC. We de- velop a novel analysis framework that directly bounds the whole interconnected iteration system without the conservative decoupling commonly adopted in previ- ous analysis of AC and NAC. Our work presents the first finite-time analysis of single-sane sample fingle-timescal NAC with a global optimality guarantee.
INTRODUCTION
Actor-critic (AC) methods achieved substantial success in solving many difficult reinforcement learning (RL) problems (LeCun et al. 2015; Mnih et al.] 2016; Silver et al.] 2017). In addition to policy update, AC methods employ a parallel critic update to bootstrap the Q-value for policy gradient estimation, which often enjoys reduced variance and fast convergence training.
Despite the empirical success, theoretical analysis of AC in the most practical form remains chal- lenging. Most existing works focus on either the double-loop setting or the two-timescale setting, both of which are uncommon in practical implementations. In double-loop AC, the actor is updated in the outer loop only after the critic takes sufficiently many steps to have an accurate estimation of the Q-value in the inner loop (Yang et al. 2019; Kumar et al. 2019 Wang et al. 2019). Hence, the convergence of critic is decoupled from that of the actor. The analysis is separated into pol- icy evaluation sub-puu sub-problem in the inner loop and perturbed gradient descent in the outer loop. In two-timescale AC, the actor and the critic are updated simultancously in each iteration using step- sizes of different timescales. The actor stepsize (denotes by ax) is typically smaller than that of the critic (denotes by 3e), with their ratio goes to zero as the iteration number goes to infinity (i.e., lim / 3r = 0). The two-timescale allows the critic to approximate the correct Q-value in an asymptotic way. This design essentially decouples the analysis of the actor and the critic.
The aforementioned AC variants are considered mainly for the ease of analysis. In practice, the single-timescale AC, where the actor and the critic are updated simultaneously using constantly proportional stepsizes (i.c., with a = Ca > 0), is more favorable due to its simplicity of im- plementation and empirical sample efficiency (Schulman et al., 2015 Mnih et al.) (2016). However, its analysis is significantly more difficult than the other variants. To understand its finite-time con- vergence, some recent works (Fu et al. 2020; Zhou & Lu 2022) consider multi-sample variants of AC, where the critics are updated by the least square temporal difference (LSTD) estimator rather than the TD(0) update. The idea is still to obtain an accurate policy gradient estima- tion at each iteration by using sufficient samples (LSTD), and then follows the common perturbed gradient analysis to guarantee the convergence of the actor, decoupling the convergence analysis of the actor and the critic. In addition to the mulpi-sample settings, there are few attempts that analyzed the single-sample single-timescale AC(NAC), and they only attest local convergence (Chen et al.

---

Under review as a conference paper at ICLR 2023
2021 Olshevsky & Gharesifard 2022). Besides, (Olshevsky & Gharesifard 2022 only considers the simple tabular case. We attempt to answer the more general yet more challenging question:
Can the single-sample single-timescale AC(NAC) find global optimal policy, especially on the general unbounded continuous state-action space with unbounded reward?
To this end, we make the first step to consider the classic Linear Quadratic Regulation (LQR), fun- damental continuous state-action space control problem that are commonly employed to study the performance and the limits of RL algorithms (Fazel et al. 2018 Yang et al., 2019 Tu & Recht [018] Duan et al., (021). In particular, under the time-average cost, the single-sample single-timescale AC(NAC) algorithm for solving LQR consists of three parallel updates in each iteration: the cost estimator, the critic, and the actor. Unlike the aforementioned double-loop, two-timescale, or multi- sample structures, there no specialized design in single-sample single-time timescaie AC(NAC) that fa- cilitates a decoupled analysis of its three interconnected updates. In fact, it is both conservative and difficult to bound the three iterations separately. Moreover, the existing perturbed gradient analysis can no longer be applied to establish the convergence of the actor either. To tackle these challenges in analysis, we instead propose a novel framework to directly bound the overall interconnected iter- ation system altogether, without resorting to conservative decoupled analysis. In particular, despite the inaccurate estimation in all three updates, we prove the estimation errors diminish to zero if the (constant) ratio of the stepsizes between the actor and the critic is below a threshold. The identified threshold provides new insights into the practical choices of the stepsizes for single-timescale AC.
Overall, our contributions summarized as follows:
Our work furthers the theoretical understanding of AC(NAC) in its most practical form. We for the first time show that the single-sample Ainll--imescall NAC can provably find the e-accurate global optimum with a sample complexity of ((-=)) for tasks with unbounded continuous state-action space. The previous works consider either specialized algorithm variants (Fu et al. 2020 Zhou & Lu 2022). or more restricted settings with only local convergence guarantee (Chen et al., 2021 Olshevsky & Gharesifard 2022).
We also contribute to the work of RL on continuous control task. It is novel that even with actor updated by a roughly estimated gradient, the single-sample single-timescale NAC algorithm can still find the global optimal policy for LQR, under general assumptions. Compared with all other model- free RL algorithms for solving LQR (see related work [.I]. our work the first one adopting the simplest Lingle-sample single-loop structure, which may serve as the first step towards understanding the limits of AC(NAC) methods on continuous control task. In addition, compared with the state- of-the-art double-loop AC for solving LQR (Yang et al. 20019), we improve the sample complexity from ( -5) ) to O)e-)). 2). We also show the algorithm is much more sample-efficient empirically compared few classic works in Section which unveils the practical wisdom of AC(NAC) algorithm.
Technically, we provide new proof framework that can establish the finite-imee convergence for single-timescale AC. In the finite-time analysis of double-loop AC (Yang et al. 2019) and two- timescale AC (Wu al.) 2020),, the previous techniques hinge on decoupling the analysis of actor and critic, establishing the convergence of critic first and then the convergence of actor consequently. The novelty of our proof framework is that we formulate the estimation errors of the time-average cost, the critic, and the natural policy gradient into an interconnected iteration system and establish the convergence for them simultaneously rather than separately. This proof framework may provide new insights for finite-time analysis of other dingle-timeseee algorithms.
1.1 RELATED WORK
In this section, we review the existing works that are most relevant to ours.
Actor-Critic methods. The first AC algorithm was proposed by Konda & Tsitsiklis (1999). Kakade (001) extended it to the natural AC algorithm. The asymptotic convergence of AC algorithms has been well established in Kakade (2001): Bhatnagar et al. (2009); Castro & Meir (2010): Zhang et al. (2020). Many recent works focused on the finite-time convergence of AC methods. Under the double-loop setting, Yang al. (2019) established the global convergence of AC methods for solving LQR. Wang et al. (2019) studied the global convergence of AC methods with both the actor and the critic being parameterized by neural networks. Kumar et al. (2019) studied the finite-time
2

---

Under review as a conference paper at ICLR 2023
local convergence of a few AC variants with linear function approximation. Under the wwo-timescale AC setting. Wu et al. 2 Xu et al. (2020) established the finite-time convergence to a stationary
point at sample complexity of ( 2.0). Under the single-timescale setting, all the related works
(Fu et al. 2020 Chen et al. 2021 Thou & Lu 2022 Olshevsky & Gharesifard 2022) have been
reviewed in the Introduction.
RL algorithms for LQR. RL algorithms in the context of LQR have seen increased interest in the recent years. These works can be mainly divided into two categories: model-based methods (Dean et al., 2018 Mania et al. 2019 Cohen et al.) 2019) Dean et al. 2020) and model-free meth- ods. Our main interest lies in the model-free free methods. Notably, Fazel al. (018)) established the first global convergence result for LQR under the policy gradient method using zeroth-order opti- mization. Krauth et al. (2019) studied the convergence and sample complexity of the LSTD policy iteration method under the LQR setting. On the subject of adopting AC to solve LQR, Yang et al. (2019) provided the first finite-time analysis with convergence guarantee and sample complexity under the double-loop setting. Zhou & Lu (2022) considered the multi-sample (LSTD) and single- timescale setting. For the more practical yet challenging single-sample single-timescale AC, there no such theoretical guarantee far, which is the focus of this paper.
Notation. Without other specification, for two sequences {In) and [yn], we write In = (yn) if there exists constant C such that 2n S Cyn. We use O(-) to further hide logarithm factors. For any symmetric matrix M RTx" let svec(M) Rn(a+1//2 denote the vectorization of the upper triangular part of M and smat(.) denote its inverse such that smat(svvec(A) = M. Finally, we denote by A &, B the symmetric Kronecker product of two matrices A and B.
2 PRELIMINARIES
In this section, we introduce the AC algorithm and provide the theoretical background of LQR.
2.1 ACTOR-CRITIC ALGORIHTM
We consider the reinforcement learning for the standard Markov Decision Process (MDP) defined by (X,UP,, C.c,, where X' is the state space, UI is the action space, P(x++1 12 Uz) denotes the transition kernel that the agent transits to state I++1 after taking action u, at current state 2t, and c(re, u,) is the running cost. A policy na (u(r)) parameterized by 0 is defined mapping from given state to a probability distribution over actions.
In this paper, aim to find policy my that minimizes the infinite-horizon time-average cost, which is given by
E
c( us)
8" = arg J(0) := lim Eg
E pappotte
[e(x, u)],
(I)
T-000
T
where Pe denotes the stationary state distribution generated by policy ma. In the time-average cost setting, the state-action value (Q-value) of policy To is defined as
Qo = Eel 1 (clx). u4) - J(8)) = x, uo = u],
(2)
1=0
which describes the accumulated differences between running costs and average cost for selecting in state x and thereafter following policy ma (Sutton & Barto 2018). Based on this definition, we can use the policy gradient theorem (Sttonn et al. 1999) to express the gradient of J (0) with respect to as
VoJ(O) = E V log (u(u))) w)].
One can also choose to update the policy using the natural policy gradient (Kakade 2001). which is given by
J(O) F(8))
(3)
where
F(0) E u
Ve log No ( Vo log (o(
3

---

Under review as a conference paper at ICLR 2023
the Fisher information matrix and F(8)t denotes its Moore Penrose pseudoinverse.
Optimizing J() in I with (3 requires evaluating the Q-value of the current policy тæ, which is usually unknown. AC estimates both the Q-value and the policy. The critic update approximates Q-value towards the actual value of the current policy To using temporal difference (TD) learning (Sutton & Barto 2018). The actor improves the policy to reduce the time-average cost J(0) via gradient descent. Note that the AC with natural policy gradient is also known as natural AC.
2.2 NATURAL ACTOR-CRITIO FOR LINEAR QUADRATIC REGULATOR
In this paper, we aim to demystify the convergence property of natural AC by focusing on the infinite-horizon time-average linear quadratic regulator (LQR) problem:
minimize (1c)
J((u}) == lim Σ
It Qxx + us Ruel
(4)
T-000
subject
I(+1 Ax, + Bu, + Ec:
(5)
where F4 Rdd is a state and u, R is a action; A E Rdxd and B Rdxk are system matrices; Q E gaxd and R E gixk are performance matrices; é, ~ NoO, Dn) are i.idd Gaussian random
variables with Do > O. From the optimal control theory (Anderson Moore 2007). the optimal policy of is a linear feedback of the state
U4 =
(6)
where K E R is the optimal policy which can be uniquely found by solving an Algebraic Riccati Equation (ARE) (Anderson & Moore, 2007) depending on A, B, Q, R. This means that finding K" using ARE relies on the complete model knowledge.
In the sequel, we pursue finding the optimal policy in model-free way by using the natural AC method, without knowing estimating A, B, Q, R. The structure of the optimal policy in (6) allows us to reformulate (4) as a static optimization problem over all feasible policy matrix E gkxd To encourage exploration, parameterize the policy
{-x(->>) = N((Kr,, o² 4)) K R
where > 0 is the standard deviation of the exploration noise. In other words, given state Zt. the agent will take an action u, according to u = -Kx, + ace, where Se ~ NN As consequence, the closed-loop form of system (5) under policy ( is given by
F++1 = (A BK)x, Ee.
where & = E, + BBC (O, D,) with D, Do 2 Note that optimizing over the set of stochastic policies 7 will lead to the same optimal K
The set K of all stabilizing policies given by
K = {K& E kxd p(A - BK) < <1},
where p(-) denotes the spectral radius. is well known that if K E K, the Markov chain in (8) yields stationary state distribution. (0, Dx), where Dx satisfies the following Lyapunov equation
DK D. + (A BK)Dx (A- - BK)T.
(10)
Similarly, we define Pk as the unique positive definite solution to
Pk = Q+QK+* RK + (A- (A-BK)) PK(A- BK).
(11)
Based on Dx and Pk. the following lemma characterizes [K) and its gradient V (K).
Lemma 2.1. (Yang et al. 2019) For any K E K, the time-average cost J(K) and its gradient
(KK( take the following forms
J(K)= = Tt(PxD.)+oPTH
(12a)
JKK(K) DK.
(12b)
where Eg. (R+ 12++R B Pk PR BTPx Px A.
4

---

Under review as a conference paper at ICLR 2023
Then, the natural gradient of (K) be calculated (Fazel et al. 2018 Yang et al. 2019
((K) V Vx Ex,
(13)
which eliminates the burden of estimating Dr. Note that we omit the constant coefficient since it can be absorbed by the stepsize.
Calculating the natural gradient J(K) requires estimating Pk. which depends A, B, Q R. To estimate the gradient without the knowledge of the model, we instead directly utilize the Q-value.
Lemma 2.2. BBaddtee et al. the following form
1994- Yang et al. 2019) For any K K, the Q-value QK k (z, u) takes
20 QK(x,u) = (x T )ak
o T PkBB "
Tr(PKDk), -
(14)
where
QK = [2
P B
P R+ PKB
(15)
Clearly, if we estimate Ωx then Fig in 13 can be readily estimated by using 2 and 2
3 SINGLE-SAMPLE SINGLE-TIMESCAN NATURAL ACTOR-CRITIC
In this section, we describe the single-sample single-timescale natural AC algorithm for solving LQR. In view structure the Q-value given (14), we define the following feature function
6(2, u) svec
2
Then, parameterize the Q-estimator (critic) by
= (x u) T w + b.
Using the TD(0) learning, the critic update follows by
W++1 = wi + B.[(c, - ((K + d(I++1, 1)+ Th. + Φ(x,, uz) we b)] u.), (16)
where B is the stepsize of the critic and K denotes the policy under which the state-action pairs are sampled. Note that the constant b is not required for updating the linear coefficient
Taking the expectation of wt-1 in 16 with respect to the stationary distribution, conditioned on wy the expected subsequent critic can be written
Blor+ [ww]] = we + Be(bb - Akwi),
(17)
where
J(K))o Ax (a. (o(,, u)(((, u) u')) bx - u)].
(18)
Note that for case of exposition, we denote (x', w') as the next state-action pair after (z, u) and abbreviate (e as (r,u))
Given a policy TK. is not hard to show that if the update in [17 has converged to some limiting point wk. i.e., lim Wi wic, Wik must be the solution of Agw bx-
Proposition 3.1. Suppose K K. Then the matrix Ag defined in [8) is invertible and Agw bx has a unique solution wix that satisfies
w svec(((x)
(19)
where Ωg is defined in
15
5

---

Under review as a conference paper at ICLR 2023
Combining 13
15 and 19) we can express the natural gradient of J(K) using wi:
V
X
(KK
2 K
S smat(w<)) )²* smat (
This allows us to estimate the natural policy gradient using the critic parameters wi. and then update the actor in model-free manner
K K₁ ar V K. (KK),
(20)
where On is the actor stepsize and V J(,,) is the natural gradient estimation depending on wti
K. (Kg) = smat(w,, (m smat(w>))
(21)
Furthermore, we introduce cost estimator 7): estimate the timeraverage cost J(2)). Combining the critic update (16) and the actor update 200.. the single-sample single-timescale natural AC for solving LQR is listed below.
Algorithm Sample Single-timescale Natural Actor-Critic for Linear Quadratic Regulator
Input initialize actor parameter Ko IK, critic parameter wo, time-average cost 1/o, stepsizes for actor, Br for critic, and "/e for cost estimator.
2: for 0, ... , do
3: Sample 2; from the stationary distribution pk.,
4: Take action u ~ k (-|22)) and receive ct = c(ar, us) and the next state x/-
5: Obtain u ~ k. (- (.1=))
6:
TD error calculation: d, = ct - 17t + 0(x': u/)) Tw) olxis T We
7:
Cost estimator update: Th+1 T)t + rcle - -Tp)
8: Critic update: W++1 = Il (wi + 3,0,0(1,, u))
9: Actor update: Ke+1 = K, arl (smat(ww) K2 smat(wy))1)
10:
end for
Note that "singic-sample" refers to the fact that only one sample is used to update the critic per actor step. Line 3 of Algorithm| [ samples from the stationary distribution induced by the policy TK., which is a mild requirement
the analysis of uniformly ergodic Markov chain, such as in the LQR problem (Yang et al.) 2019). It is only made to simplify the theoretical analysis. Indeed, as shown in Tu & Recht (2018), when K IK. (8) is geometrically 3-mixing and thus its distribution converges to the stationary distribution exponentially. In practice, one can run the Markov chain in (8) sufficient number steps and sample one state from the last step. In addition, "single-times timesealeecc refers to the fact that the stepsizes for the critic and the actor updates constantly proportional.
Since the update of the critic parameter in (66) requires the time-average cost cost (Kt), Line 7 provides an estimation of it. Besides, top of (16), additionally introduce a projection (ITa) in Line 8 to keep the critic norm- noundbounded, which common the literature (Wu et al.) 22200] Yang et al. 2019 Xu al. 2020). In our analysis, the projection relaxed using its nonexpansive property.
4
MAIN THEORY
In this section, we establish the global convergence and analyze the finite-time performance of Al- gorithm T
All the proofs can be found in the Appendix A
Before preceding, make the following standard assumptions.
Assumption 4.1. There exists a constant K > such that [|Kell < for all I.
The above assumes the uniform boundedness of the actor parameter (Konda & Tsitsiklis 1999; Kanmakar & Bhatnagar 2018 Barakat et al., 2022; Zhou & Lu (022). As can be seen from our proof, is only made guarantee the boundedness the feature functions, which is a standard assumption in the literature of analyzing AC: with linear function approximation (Xu et al. 2020
Wu et al. 2020, Zhou Lu 2022).
Assumption 4.2. There exists a constant p E (0, such that p(A BKs) for all t.

---

Under review as a conference paper at ICLR 2023
Assumption 4.2 is made to ensure the stability of the closed loop systems induced in each iteration and thus ensure the existence of the stationary distribution corresponding to policy тK,- In the single-samlle case, the estimation of the natural gradient of ((K)) can be highly noisy and biased. In general, is difficult to obtain a theoretical guarantee for this condition. Nevertheless, we will present numerical examples support this assumption. Moreover, the assumption for the existence of stationary distribution is common and has been widely used in Chen et al. (2021): Zhou & Lu 20222; Olshevsky & Gharesifard (2022).
Under these two assumptions, we can now prove the convergence of Algorithm which consists of three estimators: TT, We, and K,.
Theorem 4.3. Suppose that Assumptions 4.1 and 4.2 where is small positive constant. With probubility at least 10-10, have
4.242hhllle hold and choose C₁
vI+7 Bc 7 VI+T
T
1
E(n: - J(K,)) =0
VT
T-1
1
Bl|Wi - wk. =
T t=0
VT
1
min ())(K)) J(K)) =0 0
The theorem shows that the cost estimator, the critic, and the actor all converge a sub-linear rate of (T) Correspondingly, to obtain an 6-optimal policy, the required sample complexity O This order is consistent with the existing results on single-timescale AC (Fu et al. 2020 Chen et al. 2021 Olshevsky & Gharesifard] 2022). Nevertheless, our result is the first finite-time analysis of the single-sample single-timescale AC with global optimality guarantee.
4.1 PROOF SKETCI
The main challenge in the finite-time analysis lies in that the estimation errors of the time-average cost, the critic, and the natural policy gradient are strongly coupled. To overcome this issue, we view the propagation of these errors as an interconnected system and analyze them comprehensively. To see the merit of our analysis framework, we sketch the main proof steps of Theorem 4.3 in the following. The supporting propositions and theorems mentioned below can be found in the Appendix.
We define three measures A(T), B(T), C(T) which denote the average values the cost estimation error, the critic error, and the square norm of the natural policy gradient, respectively:
T-1 A(T) == T Σ Egi B(T) = + Σ E C(T) = T t=
EI EK 113
(22)
where V/ : 7/- ((+K) is the cost estimation emorr and 2, = we w/ with wi wk is the critic error. Note that EK, V X, J(K)) is the natural policy gradient according to (3).
We first derive implicit (coupled) upper bounds for the cost estimation error yt- the critic error 2, and the natural gradient Eg,, respectively. After that, solve interconnected system of inequalities in terms of A(T), B(T), C(T) to establish the finite-time convergence.
Step 1: Cost estimation error analysis. From the cost estimator update rule (Line 7 of Algorithm I}. we decompose the cost estimation error into:
2 = - 2n + 2n - ((K)) + (yr(J(K)) - ((K+1)) (J(KK) J(K+t1) + rc(c - m1
(23)
The second term the right hand side of 23 is noise term introduced by random sampling of the state-action pairs, which reduces to after taking the expectations. The third term is the variation of the moving targets J J(K,) tracked by cost estimator. is bounded by yts St, Fx, utilizing
7

---

Under review as a conference paper at ICLR 2023
the Lipschitz continuity of (K,) (Proposition A.6p. the actor update rule (21). and the Cauchy- Schwartz inequality. The last term reflects the variance in cost estimation, which is controlled by a high probability bound of (Proposition A.4).
Step 2: Critic error analysis. By the critic update rule (Line 8 of Algorithm we decompose the squared error by (neglecting the projection for the time being)
|| II =||=|| P 23, (zt, h(we, K.)) 23,A(O,,, K₂) + (3, (t, K:))
+ 2(,,,, wi wi-1) 1)- + (1 (,,,,,(,,,,,, K,) + Ah(O,, Tr K,)) + (wi - wi11)11 (24)
where the definitions of h, h. Ah, A, and On can be found in (27) in the Appendix. The second term on the right hand side of (24h is bounded by - where is a lower bound of a (Ax,) proved in Proposition (A.8) The third term is random noise introduced by sampling, which reduces to 0 after taking expectation. The fourth term is caused by inaccurate cost and critic estimations, which can be bounded by the norm of 1/s and 2, The fifth term tracks the difference between the drifting critic targets. We control it by the Lipschitz continuity of the critic target established in Proposition A.9 The last term reflects the variances of various estimations, which bounded by the diminishing P..
Step 3: Natural gradient norm analysis. From the actor update rule (Line of Algorithm I the almost smoothness property of LQQ (Lemma A.11 we derive
and
2Tr(DKe.1 EK, Ek.) = _ (J(K)) J ((K+1)) -TT (EK. EK.) Ek.)
at
To,Tr(DK.. -R Px,jkk...
(25)
where Exc, denotes the estimation of the natural gradient Fx.- The first term the left hand side of (25) can be considered as the scaled square norm of the natural gradient. The first term on the right hand side compares the actor's performances between consccutive updates, which is bounded via Abel summation by parts. The second term evaluates the inaccurate natural gradient estimation, which is then bounded by the critic error 2 and the natural gradient Ex,- The last term can be considered as the variance of the perturbed natural gradient update, which is controlled by the diminishing stepsize.
Step 4: Interconnected iteration system analysis. Taking the expectation and summing 23 and (55 from 0 to T 1, respectivelyy obtain the following interconnected iteration system in terms of A(T), B(T), C(T'):
A(T) SO
VT
B(T) <O( VT + A(T))(TT++CCCC)))
(26)
C(T) so( VT ) +
where b, d, e,g are positive constants. By solving the above system of inequalities, we further prove that if bef + bul 2eg² < 1, then A(T), B(T), C(T) converge at rate of O This condition can be easily satisfied by choosing the stepsize ratio ca to be smaller than a threshold defined in (52).
Step 5: Global convergence analysis. To prove the global optimality, we utilize the gradient dom- ination condition of LQQ (Lemma A.12). A.12)
1
J(K) - J(K*) G
Dx D
This property shows that the actor performance eттor can be bounded by the norm of the natural gra- dient (that is, Tr(Ex Ex)) )). Since we have proved the average natural gradient norm C(T) converges to zero, summation over both sides of the above inequality yields
min B(J(K, - J(K')] =0
which is the convergence of the actor performance error. We thus complete the proof of Theorem 4.3
8

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTS
We provide two numerical examples to illustrate our theoretical results. The first example is a two- dimensional system and the second example is four-dimensional system (See Appendix D for the system matrices and other settings). The performance of Algorithm is shown in Figure I where the left column corresponds to the first example and the right column to the second example. The solid lines plot the mean values and the shaded regions denote the 95% confidence interval over 10 independent runs. Consistent with our theorem, Figure
((a) shows that the cost estimation error, the critic error, and the actor performance error all diminish at rate of least T 2. The convergence also suggests that the intermediate closed-loop linear systems during iteration are uniformly stable.
We also compare Algorithm with the zeroth-order method (Fazel et al. 2018)) and the double-loop AC algorithm proposed in (Yang et al. 2019) (listed in Algorithm and Algorithm 3 respectively, Appendix D). We plotted the relative errors of the actor parameters for three methods in Figure
I(b] Algorithm [ demonstrates superior sample-efficinny compared to the other two algorithms,
which is well supported by our theoretical analysis.
10"
10
10"
10'
10'
10
16
Cost esllmaation error
Cost estimation error
Critic emror
10"
Crliic error
10-
performence error
10
10
10"
10
10" lleration
10"
10"
10"
10
10"
10"
10" lleration
10
10"
10"
(a) Learning results of Algorithm
T
10
10"
Singie-4maScalk AC
Sing wingiemmaaallee AC
Two-IimaScallat
10
Zaroth order
Doubte-lopp
Zaroth order Double loop AC
10
10
10"
10
10"
10"
10"
10"
10"
10"
Sample complexity
Sample complexity
(b) Comparison of Algorithm with two other algorithms
Figure 1: (a) Learning results of Algorithm
1
Here the cost estimation error refers 7 E (n
P(,))) Critic error refers to T TT ||w, wx 11 and the Actor performance error refers to + = (J(K,) - -J(K)), }}, corresponding to the conclusion Theorem 4.3 empirically, (b) Com- parison of Algorithm 1 with two other algorithms. The plots are the actor erfor || K*[[r.
6 CONCLUSION AND DISCUSSION
In this paper, we establish the first finite-time global convergence analysis for the single-sample single-timeseale natural actor-critic method under the Linear Quadratic Regulation (LQR) setting. Our work is the first one adopting the simplest single-sample single-timescale structure for solv- ing LQR, which may serve as the first step towards understanding the limits of the AC(NAC) on continuous control task. We provide novel analysis framework that systematically establishes the convergence of actor and critic simultaneously. Our framework can be extended to analyze other single-timescale reinforcement learning algorithms.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Brian DO Anderson and John B Moore. Optimal control: linear quadratic methods. Courier Cor- poration, 2007.
Anas Barakat, Pascal Bianchi, and Julien Lehmann. Analysis of target-based actor-critic algorithm with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 991-1040. PMLR, 2022.
Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. critic algorithms. Automatica, 45(11)244712248, 2009.
Natural actor-
Steven J Bradtke, B Erik Ydstie, and Andrew G Barto. Adaptive linear quadratic control using policy iteration. In Proceedings of 1994 American Control Conference-ACC volume 3, pp- 3475-3479. IEEE, 1994.
Dotan Di Castro and Ron Meir. convergent online single time scale actor critic algorithm. The Journal of Machine Learning Research, 11:367-410, 2010.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294 25307, 2021.
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only vT regret. In International Conference on Machine Learning, pp. 1300-1309, PMLR, 2019.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu, On the sample complex- ity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-679 2020.
Jingliang Duan, Jie Li, and Lin Zhao. Optimization landscape of gradient descent for discrete-tima static output feedback. arXiv preprint arXi::2109.13132 2021.
Maryam Fazel, Rong Ge, Sham Kakade, and Mchran Mesbahi. Global convergence of policy gradi- ent methods for the linear quadratic regulator. In International Conference on Machine Learning, pp. 1467-1476. PMLR, 2018
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy. arXiv preprint 20X1::2008.00488 2020.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Prasenjit Karmakar and Shalabh Bhatnagar. Two time-scale stochastic approximation with con- trolled markov noise and off-policy temporal-difee -ifferecee learning. Mathematics of Operations Research, 4301):130-151, 2018.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Karl Krauth, Stephen Tu, and Benjamin Recht. Finite-time analysis of approximate policy iteration for the linear quadratic regulator. Advances in Neural Information Processing Systems, 32, 2019.
Harshat Kumar, Ales Koppel, and Alejandro Ribeiro. the sample complexity of actor- critic method for reinforcement learning with function approximation. arXiv preprint arXiv:1910.08412. 2019.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 444, 2015.
10

---

Under review as a conference paper at ICLR 2023
Jan R Magnus. The moments of products of quadratic forms in normal variables. Statistica Neer- landica, 22(4):201-210, 1978.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Anirudh L Nagar. The bias and moment matrix of the general k-class estimators the parameters in simultaneous equations. Econometrica: Journal of the Econometric Society, pp. 575-595, 1959.
Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. arXiv preprint arXiv:2203.0259) 2022.
Mark Rudelson and Roman Vershynin. Hanson- wrightt inequality and uub-gaussian concentration. Electronic Communications Probability, 18:1-9, 2013.
Kathrin Schacke. On the kronecker product. Master's 's thesis, University of Waterloo, 2004.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 155077676)33543399 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Stephen Tu and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. In International Conference on Machine Learning, pp. 5005-5014, PMLR, 2018.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates convergence. arXiv preprint arXiv:1909.011 1500, 2019.
Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617-17628, 2020.
Tengyu Xu, Zhe Wang. and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint 2rXiv:2005.03557 2020.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critie: A case for linear quadratic regulator with ergodic cost. Advances in neural informa- tion processing systems, 32, 2019.
Shangtong Zhang, Bo Liu, Hengshuai Yao, and Shimon Whiteson. Provably convergent two- timescale off-policy actor-critic with function approximation. In International Conference on Machine Learning. pp. 1 11204-11213. PMLR, 2020.
Mo Zhou and Jianfeng Lu. Single time-scale actor-critic method to solve the linear quadratic regu- lator with convergence guarantees. arXiv preprint arXiv:2202.00044: 2022.
11

---

Under review as a conference paper at ICLR 2023
Proof of Main Theorems)
13
A.1
Cost Estimate Error Analysis
13
A.2
Critic Error Analysis
17
A.3
Natural Gradient Norm Analysis
21
Interconnected Iteration System Analysis
22
A.5
Global Convergence Analysis
24
Proof of Propositions
24
Proof of Auxiliary Lemmas
30
D Experiment Details
35
A PROOF OF MAIN THEOREMS
We choose stepsizes at VI++ Br = Vi+z Additional constant multipliers cp, Cy can be considered in similar way. Before proceeding, we define the following notations for the ease of presentation:
-
wt = wk.
y1 = 1): ((K),
2; = We - w
O, = (oe, ues Ile u(),,
ÊK, == J(K),
(27)
AN(O,)) m7 K) == (J(K) - n)0(11,1 u), w(O,w, K) = lc(2, u) J(K) + (6(z', u') 6(z, u)) w)o(z, u)
h(w, K) = B(z,a)) [|c(1, J(K) + (0(z', u') o(z, wlo(,, u)).
A(O,w, 45, K) (w wik M(0 w. K) h(w, K)).
In the sequel, we establish implicit (coupled) upper bounds for the cost estimator, the critic, and the actor in Theorem A.7 Theorem 10 and Theorem A.13 respectively. Then we prove the main Theorem 4.3 by solving interconnected system of inequalities in Appendix A.4
Before start, we define two notations which are frequently used in our proof.
Definition A.1. For any symmetric matrix M E S", we define the vector svec (M) E (R(++)) as
svec(M)= = (M11, V2man. 22m m222, v V2maz, V2m ,mn)
We further define its inverse smat(.) such that
smar(svec(M)) M.
A. COST ESTIMATION ERROR ANALYSIS
In this section, establish implicit upper bound for the cost estimator Mc. in terms of the critic error and the natural gradient norm.
We first give uniform upper bound for the covariance matrix D Dr.-
12

---

Under review as a conference paper at ICLR 2023
Proposition A.2. (Upper bound for covariance matrix). Suppose that Assumption 4.2 holds. The covariance matrix of the stationary distribution (0,,, Dx,) induced by the Markov chain in ( can be upper bounded by
C1
|D 1 1 )) Doll all t,
(28)
where 01 is a constant.
Note that the distribution of state-action pair is unbounded that the feature function is also un- bounded. We can establish an upper bound for the tail probability of (I, u) by the inequality, the proof of which can be found in Rudelson Vershynin (2013).
Wright
Lemma A.3. (Hansen- (Hansen--rriht inequality). For any integer > O, let A be matrix in Rmxm and let 1) ~ NO, Im bee the standard Gaussian random variable R Then there exists an absolute constant ε 0 such that, for any f 2 0, have
PInn An E(n) An)l 0) 2e 200 [|AI|, A| 1)
With this lemma, we can provide an uniform upper bound for the cost under high probability.
Proposition A.4. (Upper bound for cost). With probability at least 10-10, 10, for 0,1,2, T 1, the cost satisfies
| 112 |1ell s U, d ue) S U,
where
Ü =0222(0mma (Q) + mmax + 1)(o² + (1+ K2)
DD []]
(29)
1- (1+py
and C2 is a constant.
Hereafter, we use Ü an upper bound for all cost c(x,, uz). As consequence, we choose no Ü so that we have 1/2 < U for all L.
Lemma A.5. (Perturbation of Pk). Suppose K' is a small perturbation of K in the sense that
Mmin (D))
KK'
Kl
Dx B| (11 - BK + 1)-1
(30)
Then we have
Pk Pkll $60
(o) Dx (Do)
K R|] B||
|| - BK + B|| + 1)l[
K'
Proof. See Lemma 5.7 in Yang et al. (2019) for detailed proof.
With the perturbation of Pk. are ready to prove the Lipschitz continuous of J(K).
Proposition A.6. (Local Lipschitz continuity of J(K)) Suppose Lemma A.5 holds, for any K2, Ke+i, we have
[J(K+1)) J(Ki) S 1 Kell, -
where
D
:h=ccddKe oo oo (Do)
| [|[ + R|BBI| +1) + 1).
(31)
1 Lee (
Equipped with the above propositions and lemmas, we are able to bound the cost estimation error.
Theorem A.7. Suppose that Assumptions 4.1 and 4.2 hold and choose Cq VI7z 7
VI+ where ca is small positive constant. With probability at least 1 - 10 10, we have
T-
C1 T- T
T Σ Eyi < (4/ + +1)022
1
Σ
El 1
Σ
E 112. (32)
/T
T
t=
1=0
13

---

Under review as a conference paper at ICLR 2023
Proof. From line 5 of Algorithm
have
vi41 -In + J(K)) ((K(-1) + vele ne))
Syî + 22209l( - -11) 2t (J(,)) (((++1)) ((++1))+2(([C))) -
- I(K +222(a - =n)?
-(1 - (1-2%) 2))b² 27 - ((K))) + 27/(cc - -1x)²² + ()(()(K)) - J(K+11)
+ (() - -K(+1)))
Taking expectation up to (x', ux) for both sides, we have
nT)² (J(K)) J (K Blvin 5(1 - 2y. + 2y, - J(K))] +2 B2
+2E(J(K,) J ((K+1)))?
To compute (lye(e (0clec-[(A J((k)) we use the notation it to denote the vector (24, ue) and Uo:ee to denote the sequence un), (I1, u1), ... (Te, uz). Hence, we have
Elyi(c ((f(e-J((K))) J(K,))] =Bea. [ve J(K,)) = Eva. Evo.. (ee J(K))
Once we know V0:t-1, 1/2 is not random variable any more. Thus get
Evoie- Brns [Bc(ee (pocc)))00oo11]
Evoe- U1 Bun [[c+ [(Ke)))uox-1]]
-E 1 Bug (ee J(K,) [(Ke)|uo:t11)
=0
Hereafter, we need to verify Lemma A.5 first and use the local Lipschitz continuous property of J(K) provided by Proposition A.6 bound the cost estimation error. Since we have
[e++
K.ll a 22 smat(wx)21)11
to satisfy (30). choose
(1 (2) 0 (Do)
S 4er |D|| II| [1 ||A|| (I]BI)( 1)
(33)
Hence, according to the update rule, we have
K. =o>|((smat(uu) 222 K, smat(w;))1)
Ca
K (ssmma(a)) + (mma(ww)) 22
(1
t)
Ca
(K|Wwell + [|wel))
1)6
Co
(K- + 1)
1)6
(1
(2 J (Do)
4c1 || D3
B B|[ + |||| + K|| Bl]) (1 t)8
miin (D))
Dk. || -11 B| -1 (I|4 - BK + +1)
(34)
4
where the last inequality comes from 28 Thus Lemma A.5 holds for Algorithm T quence, Proposition A. also guaranteed.
As a conse-
14

---

Under review as a conference paper at ICLR 2023
Combining the fact 27, J = O. we get
E[y2+1] S(1 27, Eyy + 2kyx - J(K++1)) + (R(((K)) - -[(K E - 11)²
<(1 2% +
- - 27 - n))
-
<(1 27, 2y,)By 21, 2/ Ketill + ( -J(K++1)) + +27,TB(c+ - -1))
<(1 2y)) + Ely 11,, (I)( - - ((()))))) 2 -11)2
<( 2%, By, + Bly, ||| Ek. + Ex. + (B(((K))) - J(K++)))
2x/E(c= 71)
<(1 Buy 21 21 + +2// 1|==1| + 11 |1I (K()(K.) I(K+1)))
27/ n1)²
5( Byy 21, + +1)22² 112111/22 02 - || 122
+ (EE(J(K) - (((+1))) + 2n B(cz - nt)
<(1 (27H 23 (2 + 1)² + 2 1 110 +1,x Fx, 11
+ +2E(J(K,) - J(K++ E((c - n1)²
where we use the fact that
|KK Fx |l s 22(K + 1)llus will.
Choose ca small enough such that
1 )) s 1.
21 c2 + 1)
(35)
Then we get
7t 2 21ax(((K22 + 1)2 + 1 )/2
Thus we have
Blyž+1 S(1 Eot + h,,B/22111 + 11, Bo, 11 + (B((( J(K++1))++ 222 nn)²
Rearranging and summing from to T
1, we have
T-1
T
T
1
2
Ey
Bls
vit
B(J(K)) J(Ke+1))
2% E(c, - m1)
7t
Ft
1=
t=
00
12
Ta
|
Co
2 + lcco
E||Ex,112
In the sequel, we need to control we have
1,, 12, 1y respectively. For 4, following Abel summation by parts,
1
Ely?
22+2)
7'
t=0
1 + E(y
)E(())
B(D?))
7t
7t-1
70
-T-1
T-1
1
1
2
+
02
7t-
7-1
70
12
7T-1
= -T2
15

---

Under review as a conference paper at ICLR 2023
where we use the fact that 1yr| < U. For 12, get
T 2 12 = Σ
E(J(Ki) - ((K+1))
t= 7t
T-1
2K + 1)
Σ
- ?t 10
T-1
21 + 1)20022
v1++1
+1
where the last inequality is due
H T v(1+t) <
r 2VT.
For I3, we have
T-1
13 = Σ
Bica nz)
N.2
< VT.
where we use the fact 0 S ct 7h S U derived by Proposition A.4 Combining all terms together, get
T-1
T
Σ
Eyf <(4)( + 1)) 30 + 1c
E2 2 + 11ca
TE
Fx. 1
t=
t=
Dividing by T. have
T Σ
cc
T-1
1 T-1 T
Eyi
+30
+
Σ t=0
E
+
Σ 1=0
E EK, 11.
T
VT
T
t=
Thus we finish our proof.
A.2 CRITIC ERROR ANALYSIS
In this section, we derive an implicit bound for the critic error, in terms of the cost estimator error and the natural gradient norm. First, we need the following propositions. Proposition A.8. For all the K there exists a constant μ >> such that
6 m (A 2 μ.
Proposition A.9. (Lipschitz continuity of wf) For any wi wt+ we have ||w| witzll S 122 12 Ket1ll,
(36)
where
11BI)) (Do) Da
R|| (K
1g [(c]
(X] K| + + 1).
(37)
1+e
2
16

---

Under review as a conference paper at ICLR 2023
Theorem A.10. Suppose that Assumptions 4.1 and 4.2 hold and choose ai
VI+ 3o n
VTFP
1
where co is small positive constant.
With probability at least 1 - 10-10
we have
T-
T-1
4 + 200 + xه
12Co nT
Bl
Biiz
12
- (0
+ (2(5))
E| EK, ||
T
+
20
Σ
B|| 12)
(38)
#
1=0
1=0
Proof. Since we have Ax,ut = bk. where bx. further get
=E E uz) - (K)))))(2), uz)]. we can
||/||| = ||
1
0 (1
ut)l
02
where in the last inequality, the fact that
||ő(1,
u)ll = ||
(x JlI
(oT Tilll
S Tr(
(x (T))
= ||
||u|
s U.
Hence, we set
1 T2
(39)
/
such that all w/ lie within this projection radius for all From update rule of critic in Algorithm |
we have
Wt+1 (wr + Be uc),,
which further implies
W++1 w/+1 (wr + Bedr ui) wit! By applying I-Lipschitz continuity of projection map, we have ||++1 witl
= || (w, + 3, u)) - w
= Ia (wr + 3, uz) - (wi+11l)l
< <lwwr Wi + 3, u) wit1ll
=||w - wt + 3:8,00 se, ad) + (wt - - w(ll
This means
|| 2 <||=z + 3,5,0051, 0z) (w] 111
=I|2: + 3,(h(O,, W1, K1) + Ah(O,, nr Ki)) + (wt - w1+1)112
= -11=.112 + 2,2, (1, wi, K,)) 23 (z,, Ah(O,, ttt K.)) + 2(22, wit1)
+ +11,:(((O,,.,) W/. Ki) + Ah T/, K()) + (w] - 1)11
=1|=,|12 + +22,,4 2,, h(,, K))) + 23, 40, K,) + 2,, (ze, Ah(O,, nc: K,))
+ +2(2 wi - w/+1) (1 Wi, K,) + Ah(O,, 7/, K,)) + (wi - 1112
<11 + +23, h(w,, Ki)) +23,A(Or,, Wi, K.) + 2,, (ze, Ah(O,, Mc. K.))
2(2,, - w/41) 1 wi K₂) + Ah(O,, nr, K1)) + +2|lu, w 112
17

---

Under review as a conference paper at ICLR 2023
From Proposition A.8 we know that mmi)(Ak) 2 pa for all K,. Then we have (2t, h(we, K,))
(2x, dk. AK,W))
(2,, bk, - AK, We - (bx, - Ak,w;))
(2t, -AK,21 21)
-25 STAAK,2 2t
I -u|lzel??
where we use the fact Akwk. bk, = O. Hence, we have
| 5(1 - 22 2 11 2,3,A(O,, wh, Ki) + 23, Ah(O,, nr. Ki)) + w2 - -wit1) -wi+1l wi+1ll
22 + x)²² + 2| -
where we use the fact that
(r; K2) + AhiO,, n. K:))1l
[(((11,, me) 1/1 (1,,, uz) (d(r)) u4) 6(F,, ui) (ol)))wwllee) wip(E, ue)l
(((((1,, u4) u1)
T/ (x will + 11(b(a', u/)) - olx,; uz) wi ut)l
<0² + -202
-0²(1 + 22))
Taking expectation up to (Ix, Ue) and noticing that
E[A(Or, Wi, K,)] = E ((w2 wk, (0, K2) - h(we, K.)i
vost
=
E
E [(r wk. (1(0, Wr, K.) - -u(wr, Kt)) [oa-1]
nows
Nol4
= E (we wke [[h(OO,, wr, K₂) - h(we Ki) 1o:
v
0,
we get
E B 11 <(1 2//3, = 2,, Ah(O,, K.)) + 2T w/ wh+1)
+ + w/4 11 + 20 23.
(40)
Therefore, using |Ah(O,, Mu. K,) < 0 1//. we can further rewrite 40 as
E 2 1 <(1 3, ) B 2/ 1 + 2B(2 wt w(+1)
20 B ||||||
+ (1 2 2F||w wf+1ll?
Based on 366) we can rewrite the above incquality as
E
1| S(1 - 2F
212 ||| Kr - K--1ll
+ + K
<(1 - 22 + |=ll|||
+ 22 K
<(1 - +2 2l20r 1 BK. - Ex, + Ex,1
+
-M
<(1 2 | EK.1 |11 II]
+ 2. F
+ 27 21) 2 Ki+1 1|2
||=;112
+ |K 11?
<(1 - 22,0,,, + 1 +
2
+ 20 +1/A +2 Ketzll2
- [ 2 + (4K + E11201
+ E Ex, -1 1303)03
(41)
18

---

Under review as a conference paper at ICLR 2023
where the second inequality is due to |K Ki+1 - (1+2)5 c3 from 34
where
(1 - ( ) min (Do)
= 4c Do B|| |A + K BB)
(42)
Choose ca small enough such that
(4K + 552cca S
(43)
Thus we can rewrite 41 as
B1 12 S(1 14 + B + Bl,
+1( + 25) 12
Rearranging the inequality and summing from 0 to T - yields
11
E||z||
B(1|= - -||=+=11111= 20
Ely ||| + 12
E|EK 11?
Be
T-1
+ +1(00(1 + 20)² + +B2))
Σ
3r
t=0
T-1
B[11=e112 - || 112 +20
E Elyel 11 =+ll +12ca
Σ
E|| E 11?
1=0
t=0
12
+ 41 20)² + P3G)TT.
orc We need to control I and 12, respectively. For term 4. from Abel summation by parts, we have
1
B( B( 1|
2
|| 12)
B
T 1
|
+ Bu
2
32
B1-1
-r
1
BB
2
+
El =01?
31
B1-1
Bo
1
1
+
Br
3
3o
3T-1
For 12, from Cauchy-Schwartz inequaua we have
1
E Elyell xe|
(By?)² & (B
t=0
T-1
T-1
Ey?)
Bl| || P)
1=0
t=0
19

---

Under review as a conference paper at ICLR 2023
Combining the upper bound of the above two items, can get
T-1
T
4
12Ca
Σ
E|
- (1 + 200² +
12
E Ek, 1|
T-1
T-1
+ ú
Byy)
B| B1| 112)
1=
1=0
Dividing by T, we have
T
4
12Co
Bl
12
< (04(1 + 2002²
+ + 120))
E|| Ex, 11?
T
1
VT
nT
1=0
2 ū /
Byg )
Σ
B|| 12)2,
1=
which concludes he convergence of critic.
A.3 NATURAL GRADIENT NORM ANALYSIS
In this subsection, derive an implicit bound for the natural gradient norm in terms of the the critic eπror Before proceeding, we need the following two lemmas, which characterize two important properties of LQR system.
Lemma A.11. (Almost Smoothness). For any stable policies K and K', J(K) and J(K)) satisfy:
J(K)) - ((K) -2 T EK) (K)) B (K - K')).
Lemma A.12. (Gradient Domination). Let K* be an optimal policy. Suppose K has finite cost.
Then, holds that
1 |D [1E Ex)
miin R Px P S J(K) J(K*) S
min R
Theorem A.13. Suppose that Assumptions
4. and 4.2 hold and choose 04 VI+7
3r = 7t-
VI+e where co is small positive constant.
With probability at least 1 - 10 10, we have
U+ 2ca
cs(K
+ 1)
E EK, 12 <
1 T
Σ El
Σ
E FK, 1I)
T
20 Do
VT
mmin (D))
t=
t=
(44)
Proof.
Combining the almost smoothness property, we get
J(K+1) (Ki)
--2Tr(D K4+1 (Ki - K(+1) T Ek.)
+ KK., (K₁ - K(41) TR++ B PK, - K(t1))
=-2aiTr(DKK., F.K FK.) + of TT( (DK.1 A (R - B PP, B) Bx.))
--2aTT((DK... (EK, EK,) Tx,,) 20 Tr(D E,, Ex.)
+ + ET, (R+ B Pk, PP, Ex.))
By the similar trick to the proof of Proposition A.2 we can bound Pk, by
|| Pk. || <
QQ + KT RK]
Ltpp
è (o (2)
12 oax (R))
2
20

---

Under review as a conference paper at ICLR 2023
where é₁ is constant. Hence further have
T1( P (R + Bd Pk, B) B) D ||| R + B Pk. B FxK. 1|
<d(K 1)? 01 Drll (o (R) + o (B) é1 (mmu (Q) + m (R)))(R)
22
1- ( (-
where we use |xx || 5 (K 1)m. Hence we define c4 follows
:=:d(K + +1 C1 D1
(a (I)) + maax (B) è1 O max (Q) + K2 max (R)
(45)
1 (
2 22
Then we get
J I(K+1)) - ((Ke)
$ - - Da,,T((Dr++ (EK, - -EK,) Ek.)
(KK)) - -2,,TT(DK.,, EK.) + c102
<0² 2 |D |FK, lKK EKell - -20,0 min (Do) EK, 112 c402
(2
=c00 Fxx |11 F.k, F:K,
20 (D)) Fx, 1|2 cani.
where
2c, 2c |
C5
(46)
Taking expectation up to (I4, u²) and rearranging the above inequality, we have
E EK I [[J(K,) J(K++1)
E Ex, ||||| Ex,
EK, ll + 20 (Du)
C4
2an (Du)
20 min (Do)
Summing over & from to T gives
EK 112
B(J(Ki) J(K++1)
C5 20 (D)))
E EK || EK.
20 min (Do)
t=
1=0
1
12
C1Ca VT.
Miin (Do)
For term I1 using Abel summation by parts, we have
(K,) J(K++1)]
2a (Dp)
T
1 [K]](K]] B[J(Ko] 1
B[J(Kr)))
mi (Do)
a
a;
ag
aT-1
T
1
S 20 (D))
+
a:-1
au
20 (Do) oT-1
Ü VT.
2 (Do)
For term 1z. by Cauchy-Schwart Schwartz inequality, we have
T-1 12x
E EK. EK, Ek. <
E EK,
(
E ÉK.
t=0
t=0
21

---

Under review as a conference paper at ICLR 2023
Combining the results of 1 and 12, we have
El EK 112 5( 2i Do)ca
Ü + 20
VT
c5 min (Do)
B|EK, 112)
T-1
Σ
B|| Ex. Exi11
t=0
t=U
Ú 201
Cs K 1)
VT
Bl|ze|1
Σ
B Ex,E),))
min (o
o min (Du)
Dividing by T. get
1
Σ E Ex, 12 S (22 2in (Do)
Ü + Cc
1
1)(
Co(K + 1)
1
Σ
B|
El
+
1
Σ
Bl| E
T
VT
miin (Do)
T
T
t=0
1=0
Thus we conclude our proof.
A.4 INTERCONNECTED ITERATION SYSTEM ANALYSIS
From the definition in 22 we have
A(T T
Σ Eyi B(T = - El.... 1
Σ
+
Σ E E 1P.
(47)
T
==
In the following, we give an interconnected iteration system analysis with respect A(T), B(T) and C(T).
Theorem A.14. Combining 32
38 and
we have
1 0
1
A(T) = 0 VT
B(T)
C(T)
= 0
(48)
VT
VT
Proof. From
32
38
and
we have
A(T) (KI)
+
1) + 3
+
+
/T
4 B(T) < (ū
250 - + (20)) 2 (
2
12 C(T),
4
VT
0 + 204
cs ck(k 11)
C(T) <
B(T)C((T)
min Do) Ca
VT
min (Du)
For simplicity, we denote
= +1) +332
VT'
b =lca
(1+ + /2 + +g0
VT
d U,
P
1oca
Ú + 22ac2 1
f = 20 (Do)ca VT'
cs (K +1)
9
miin (D))
Thus we further have
A(T) Sa bB(T)
(49)
+ C(T) Sf +
B(T) Sc+ (VTT))++(A(BBB
22

---

Under review as a conference paper at ICLR 2023
Then we have
B(T) S c+ (((AA)())+++ + EC(T),
B(T) S 2c+ A(T) + 2cC(T).
(50)
For C(T), get
C(T) / 1 5 +
C(T) s 2f B
(51)
Combining 49
50 and 51 we have
(T))
22c d bB(T) + b(2f (() + 26(ff g2
=2c ad 2bd 4ef (bd? + bd g² B(()
If bel + bel-g2 + 2eg² < 1, we have
+ ad 2bd f fef
B(T) v 1 1 bd? bul g² - 2eg²
Note that
4 [ + hca
4
r2 E + 1)²
+ 212ca cg(K + 1)²
bu + bd? + 2eg² =laa
1
Th (Do)
Imm (Do)
4
+ 11 4 02
CK +13 (Do)
=co (1
02
+
112
p (Do)
Thus we can achieve bd? + bel + 2eg² following threshold:
< 1 by choosing the stepsize ratio smaller than the
1/(4 1 02 -
4
-11-
(2
CK +1) 2 (Do)
222 + 11²
(52)
112
no min (Dp)
Therefore, we get
2c + ad + 2bd² + 4ef
B(T) _ 1 bdd bul 2egz
0
C(T) 22f + B(T) = 0 1
- )
A(T) <a+ C(T) 0 1
}
Thus have
B(T) = 0 1
- C(T) = 0 o(-L)
A(T) = 0
which concludes the proof.
A.5
GLOBAL CONVERGENCE ANALYSIS
Proof of Theorem 4.3
Proof. From gradient domination, we know that
DK ||
B(J(K,) - J(K*)) minn
(R) 1D [[ETT((E, Ex,)) <
E| Ex, 11?
(53)
min R
From the convergence of C(T), we know that
1
O( 1
Σ
E|J,,,
T
E=
23

---

Under review as a conference paper at ICLR 2023
Hence, we have
d D
d
d
T-1
min 0St<T miin R)
Bl Ex,
B
Fx. 1| 01
VT
min
R
T
1=
Therefore, from 53 we get
min B(J(K)) J(KJ()))))))))))))))) O
OStET
VT
Thus we conclude the proof of Theorem 4.3
B PROOF OF PROPOSITIONS
To establish the Proposition 3.1 we need the following lemma, the proof of which be found in
Nagar 1959): Magnus (1978).
Lemma B.1. g ~ (O, In) be the standard Gaussian random variable in R and let M, N be two symmetric matrices. Then we have
Elg Mgg Ngl 2Tr(MN) + TMMM)(N).
Proof of Proposition 3.1
Proof. This proposition is a slight modification of lemma 3.2 in Yang et al. (2019) and the proof inspired by the proof of this lemma.
For any state-action pair (z, u) E Rd+*, we denote the successor state-action pair following policy TK by (x', n²). With this notation, we defined in 7 we have
x' d'= + Bu +e, u' = - Ka' + +oG.
where e ~ (O, Do) and ( NN(0, Tt). We further denote (æ, u) and (x', u') by i and o' respec- tively. Therefore, we have
8' = L0+
(54)
where
A KA
B
17 -K]
[A B] [ -Ketos)
L:
KKB
=
Therefore, by definition, have ~N, Do) where
DOKT Do -KDo KD.K + 12
Do
Since for any two matrices M and N, it holds that p(MN) MM Then get p(L) P(A - BK) < 1. Consequently, the Markov chain defined (54) have a stationary distribution (0, Dx) denoted by Pk. where Dx is the unique positive definite solution of the following Lya- punov equation
DR LD T + 5o
(55)
Meanwhile, from the fact that NO, Dx) and -Kx + oç. by direct computation have
Dx -KDx KDKK + 21
Dr - KT
0
0
o²
0
I
+
la K
Dx
La
K
From the fact that ||AB||: I ||||||| BI| and ||||| < ||A||, we have
| | o² l: + |D (ldd [
24

---

Under review as a conference paper at ICLR 2023
Then get
(a, u)0(1, u) "1 Eo [000))
(0)))
Let M, . be any two symmetric matrices with appropriate dimension, we have
svec(M) En--xx ((()) ((se) (N))
Ba-Px T (()))(()))))))))))))))))))(()))) ( sv)c(NN)
Ex-px [000 MM NN)
Ea-px (0 M00 NO
E D MDK 99
1/2 T T K g).
where 22 is the square root of Dx. By applying Lemma
we have
svec( T Ex-pp (Q()))(U) ((())(())(ssvc(())))
-Eg-N(0. (g D MD 99 DK? gl -2Tr(D) M + Tr MD K THOK
-2(M, NKNDK) + (M, (K),,) DK)
Jsvec(N), =svec(M)) (2DD @. DR + svcc(D ()v))cs((()))))))
where the last equality follows from the fact that
sveel, (NSM + +SSN)) = (M 8, N)svec(S).
for any two matrix N and symmetric matrix S (Schacke
2004 Thus have
Ba-ix (+)))(())))))))))))))))))))))) 2Dx @ Dx + (x)(vv)sve(()
(56)
Similarly
o(0') = sveel(Lo + (L) +=)
svec(LØv L LUe =0 L + +EE²)
Since is independent of 0, we get
Ea-px (d(0) EΦNØx (0 (eC0)) LT Do)l.
By the same argument, we have
svec(M) T (6()))()') [Isee((N)
Eo-iR 1000 M) (LOOT L + NN)
EBNAR 10T MOOT L L NL Dx) (D,
-ByeNtO.Ja D MD L
+ (M, (M, (Do,N)) N))
-2Tr(MDRL) NLDR) TT(MDR)T((L (
+MM, DKY (D..
-2(M, D NLDK) + (M, ,NY
(M, DR)(Do,N)
-2(M, (...NNIDD)) + +M, Dx) N)
=svec(M)] (22D 8. LT
svec )svec Dx) ))vee((N) (D))Sv)
25

---

Under review as a conference paper at ICLR 2023
where we make of the Lyapunov equation (55 Thus get
Ex-ax [ = 2D 8. DKL + (xxeo(D)))ve)(Dk)
(57)
Therefore, combining (56) and 57 we have
2(Dx 8n -xL @. D Ax
2(xx 8, DK)(1 - L 0g 1)
where in the last equality we use the fact that
(A 8, (C @ D) 1 ((C 8, BD AD @, BC)
for any matrices A, B, C, Since pLL) 1, then / LT @. L is positive definite, which further implies Ax is invertible.
From Bellman equation of Qk. have (ø(r, u), svec((x)) = c(a, u) - J(K) (Blo(z', u() u), svec((x)).
Multiply each side by 6(x, u) and take a expectation with respect to (I, u), we
[[ (0(x u) -lo('', w2) ul) ]svec([(x) = Blø(x, u) (c(a, u) - J(K))
We further have
() ()(r,, B[o((', w/),,, u]) o(2',1/)) =
=Ak,
where the first equality comes from the low of total expectation and Therefore, we get
Bio(z, u)(c(z, J(K)) bк
Axsvec(S(x) = bk.
which implies w = svec((xx). Thus we conclude proof.
Proof of Proposition A.2
Proof. Since Dk, satisfies the Lyapunov equation defined in (10). we have
Dk. =
D D
k=
From Assumption 4.2 we know that p(A - BKt) < p Thus for any > 0, there exists
sub-multiplicative matrix norm || I]. such that
||A - BKil+ S p(A - BK,) +e.
Choose 1-,, get
1+
A S
2
Therefore, we can bound the norm of Dk, by
|D <
Σ
|A- BK, |
DDll
k=
1 p
P22
< |D |
2
k=0
1
< D. ||
1 22
26

---

Under review as a conference paper at ICLR 2023
Since all norms equivalent on the finite dimensional Euclidean space, there exists constant C1 satisfies
C1 Do
|D 1 $
1+e
which concludes our proof.
Proof of Proposition A.4
Proof. Since It ~ (O, Dx,) and or - Kette + Then we denote the joint distribution of dr (Ie, u4) by PK, (O, where
DR. K,DKi
- -R,KT KT
DK.- =
K,Dx, K, + +
0
0
la Ki
la Kr.
0²
I2IK
+
DK:
(58)
Based on Lemma A.3 for (xz, u.) N(0, Dx.) with DR. defined in 58 we obtain
P 11 + ||u,112 11 Tr xx.) 8 2e (0 2 "0
Choose 0 c2log(10)) Dx.l with 02 sufficiently large such that 002 12 and 02 Dx, IF
0|| D] ||| where we make use of the fact that || lIr bounded. Hence we have the following probability inequality
P[ 112 1|w.113 Tr(Dx,)l colog II] 2 - 2e -e- Rezeoogg(())
We define the following event
A. (111 + ||u 11 Tr(D S 02 log(11))
Then we have P(A,) 2 2e (o0
2 10-10-1 10-11, We further define
A= 0
Thus we get P(A) 2 1- 10 In the sequel, we only consider the case when À holds. That is,
for any 0 < t = T - 1, we have
||a + || 2 < colog(10)] tr(Dk.)
S (oolog(10) + +
+>)l
< 202log (10)|
< 2czlog(10)(o*k) (d + |[ I|2 Il].
where the third inequality holds since we choose 02 large enough such that 02 log(10) 2 + & and the last inequality is due to the fact
||
ll
S o (d + [[K,)))
From Assumption
4.1
we know that |K.l < so we have
|| + ||u 2 < 20 2c2log(10) + d(1 + R2)
(59)
From Proposition A.2 we know that
Dxx 11 < 1 1
DD
Substitute Dxx
into we get
1x + || 120
d(1+ K2)
9
Da Il]
(60)
1
1+2 2
27

---

Under review as a conference paper at ICLR 2023
Notice that c(z, u) x =xTQx
Qu + u² Ru, combine with (60). get
c(zi; u1) max (2) 1| + max (R) |lell
20 (Q) + max (R) + 1)(02k d(1 + R2) 1 (-+2)² Dr [10))
==Ū.
Thus can use U as upper bound both c(2, u) and || [12 | 1ee which concludes the proof.
Proof of Proposition A.6
Proof.
[J(K++1) - [(K))
-Tr(((Pee: Pk. Dx)l
Do PK| PK.
<Gd|| Dar Dallo (Do) Dx, [||||||||||([|]]]||||]| BIII BK, K, |II| B|| + 1)]1
Kell
<6c,dKo (Do) | 1|
[R]] ( B (|| + -||B| + 1) + 1) K++1 Kell
( e
-1, K.ll. where the second inequality is due to the perturbation of Pk in Lemma A.5 and
|
|
4 Ge min (Do)
[2] [K]
B || + B 1) 1).
Thus we finish our proof.
Proof of Proposition A.8
Proof. From Proposition 3.1
we know that
Ak, 2(DK, 8. DK, (I - L 8, L.). By Assumption 4.2 we have p(L) = p(A - BKt) S < 1. Then we have
| ||
(1 - L 8. L ) @, DK.)-11
< (1 L 8, L --1-111((Xx 8. Dk.)
<
2(1 - /²) | 1
1
1
2(1 f min (Dx.)
To bound miin (Dk.). for any E Rd and E R we have
(o)
(aT bT) Dr)
Dx.
b
(i Dx. (a bT) (
u (ET
(xT wJ) ())()) (
-B I((aa ll(a bb K.) + ab² () ((a) T - bT K.) ob [
-B..W. - b JJKa)an' TTa (a KTb) b) o² TTTcTT
20 (Dx, K, 6112 + 02|1b|12.
28

---

Under review as a conference paper at ICLR 2023
For ||a
K2 bl1,, we have
l|a K, bll = 6|2 |||a|| K ||]||
+
>||a|| - -
1 =||a|| 2 (Ilall 4 1681)
2 ||al1 2k 21121
Hence we get
(aT bJ) DK. (b)
20 (Dx,) 1|a K, b112 + o 0b11b11
20 (Dx, ||a122 2k |b|| 11b11
a² min(omin (Do)
tK2 |(
||all2 1121111 1
min (D))
0²
o²
min{
H[lal1 + +111))
2
8K2
2
Thus we have
m (Do) o² 0²
m (Dx.) 2 minf
0,
2
'822
which further implies
1
| -
2(1 - p²) (πx,)
2(1 p²) (min amin (D)) 0² g²
})2
SR 2
We define
mmin (D))
o² q² })²
= 2(1 - (min)
2
8K22 2
such that get
mmin mmin (Ak.) 2 4.
which concludes the proof.
Proof of Proposition A.9
29

---

Under review as a conference paper at ICLR 2023
Proof.
1u0 wi+1ll
|[svec(Sex, 11ke11)
11Qx. -Sxc.1all lle
=I| [AT(P,, Pkeii
AT(P,, Pk( ||e
BT(PK. - Pkit1 A
B (PK. Pkiy B
-IIA" (PK, -P ||AT(PKs -KK441
+ +IBB (PK. - -K 1|B (PK. PB..IBBB
<da() + +|1B11@||PX, Pk+till
36d (1]A| + 11B1)) min (Do)l X Kell
(|] BK. |1 || || 1) K.ll
|D P||-
3e ([A4I + | (Do)
1- 2=
(I]I + K| + 1) + 1)|| Kell
-1211 Kell,
where
[[|A|] |1B11) (m)))))))))))))))) | R||
12 :b:
[K] 1) +))
(61)
1 22)
C PROOF OF AUXILIARY LEMMAS
The following lemmas well known and have been established in several papers (Yang et al.
2019 Fazel et al. 2018). We include the proof here only for completeness.
Proof of Lemma 2.1
Proof. Since we focus on the family of linear-Gaussian policies defined in (7). we have
(K) (m,,, [e(zz u)]
-B (x Qx + T Ru]
= Ea (x Qx + (-Kx + oC) R(-KK-KKK
Kx o() Barax Be- 1 [x. (Q + KT RK)x ox T K RC
-T RK d²c TR(RRC) RC]
RRONDX (x' T (Q KT RK)a) + T²)
=Tr((Q+ + K TRRK)
Tr)
(62)
Furthermore, for K E exd such that p(AB K) < and positive definite matrix E Rddd we define the following operators
[x(S) Σ (A BK)))(A-BB))T
120
[T( = Σ [(A - BKYT S(A - BK).
(63)
120
Hence, (S( and (S) satisfy Lyapunov equations
Tx(S) S (4 BK)T - BK)T, Tk(()) S (A BK) T BK)
(64)
(65)
30

---

Under review as a conference paper at ICLR 2023
respectively. Therefore, for any positive definite matrices S₁ and S2, get
Tr(S)Tx((s)) = Tr(Si (A ( -A (B)[(()))]]]))))
220
- B BKY'S,
(S)))).
Combining (10). 55
64
and 665
we know that
Dк Dk=o)( Pk Px=TRQ+KTRKK
(66)
Thus implies
J(K) Tr((Q + RK)
Tr((Q K (())) + TT(T + KT (KK)a))+o'l) TT(PxD,) + Tr((
remains to establish the gradient of J(K). Based on 62 we have
J(K) -V =T K RK)CM)o=D> V (cC RTRK
where we use C7 to denote that we compute the gradient with respect to and then substitute the expression of C. Hence we get
VKJ(K) = 2RKDR V
(67)
Furthermore, we have
VxTH(CDDR)
=V<T((GT[((D.))
=VxTH(COD, + Co(A - BK)))
=VxTr(CoDa) +
BK)Tx((D))
--2B Ca(A- BK)Tx x).])<(D)+++>>> TxTT+ (TT)) -644-))))
Then reduces to compute V TaT Applying this iteration for
times, get
VxTr(C,DR)
2B
Σ
G(AABK)]<(D),
1=0
+ V I
(68)
Meanwhile, by Lyapunov equation defined in
we have
Σ = Σ (A (K)
KT RA
1=
t=0
-Pk-
Since p(A BK) < 1, we further get
lim ((CC)Tx(Do))
n-000
lim
[I(Q KT RK) p(A 3K) (D.))
31

---

Under review as a conference paper at ICLR 2023
Thus by letting go to infinity in 668
get
2B Px(A- (D))
2B PR(A BK)DK.
Hence, combining 667
we have
VKJ(K) 2RKDK - -2B 1 ((ABB)))A
2 B B)K P
which concludes our proof.
Proof of Lemma 2.2
Proof. By definition, we have the state-value function as follows
Vo(x): Σ Eol(c(12 u4) J(0)) = x.]
t=
= (10)
(69)
Therefore, we have
Vx(x)) =
B[((xr, uz) J(K) = xx =4, KKx + [6e
t=
00
Σ
[ (Q KJ RK
+ TTT(( K
J(K)}.
(70)
Combining the linear dynamic system in 8 and the form of (70), we see that VR (a)) is a quadratic function, which can be denoted by
(x(x)= = PςΣ + CK.
where Px is defined in (1] and Ck only depends on K. Moreover, by definition, we know that Ex-px (Vx(x)) which implies
Ex-px (x T PR + Ck] Tx(x OK =
Thus we have CK -Tr(PxDK) Hence, the expression of Vx (x) given by
Vx(x) = T PKx - Dr))
Therefore, the action-value function QK (x, u) be written
Q(x, u) =c(x, u) J(K) BVVx (2') |2,
=c u) J(K) (Ax + Bu) Px + Bu) Tr(PxDo) TrrPp
=x =x u. Ru + (Ax + Bu) Px + Bu) +P - Er(p
Thus finish the proof.
Proof of Lemma A.II
Proof. By the definition of operator in (63) and (66). we have
x PR
= TQ + KT RK')'
= => x [[A BK' (Q + KT RK' 2K')x.
120
32

---

Under review as a conference paper at ICLR 2023
Hereafter, we define (A - BK 24 and u/ =.''//, Hence, we further have
x² PRIX
Σ T K"T RK')4
120
Σ
(xl Qel + ud Rui))
120
Therefore, we get
x. PRIx xx Præ
> [1, Qzl, + uf Rul) + x4 PKTY TT Px - 2 Paa'o
120
>1(a) Qui + n Ru4) x x Pk xtt Provl]
(1/ Qxl, + ut Ruf) [[A BK') PK (A BK P/P
120
Σ (or [Q + (K" K K) R(K' - K K))a
120
+ 1
[A BK B(KK K)T Pk(A BK B(K'
K))a4 Px
(K)-K) [2x] (K' - K)T((R + PRB)K - ( PRA
120
+ 2/4 (K' - -K)T B' PRB)(K' - -KY'
220 (K' - K) Exa, + xt, (K' - K)T(R+ BT PR - K)a{)
120
Define
AK (I)) = 2x (K' KY EAT +x [KK (K) (R+ BJ PR K)x. (71)
Then, from the expression of J(K) in (2a). have
J(K') J(K)
-BZuN(0.D.)1 (P
Σ (x))
-BagNN(0.D.)
-B2,NA(00DD))
(2xg (K' - -K)T Exg, + oK ()T(RR BJ PK - KYa')
120
-Tr(2E,G~
(T ''J[K' - -K) EK)+
(20
Tr(Bu,,N(O.D..)
2 24 [K'
BJ PR K))
120
= - 2TT( - K') Ex) + Tr(D (R+
(R+ BT (xB)(K-KY)
where the last equation is due to the fact that
Ez [1
120
-E,~N
(A BK" Fx [A - B
t20
-Ix: = DK-
Hence, finish our proof.
33

---

Under review as a conference paper at ICLR 2023
Proof of Lemma A.12
Proof. By definition of AK. in 71 we have
AK,K' (z)
-2x 22xT(K' (K' K)
+ (K' -) B PKB)(K K)æ
=Tr(xx [K' - + (R+ B ExB)-
(R + B Px PKB) - B
TT(xx' BB+
2 Tr(ax' EK (R+ B -x
where the equality is satisfied when K' =K K-KKKA0 -(R+ BT Pk -x.. Therefore, have
J(K) J(K) -2g Σ 120
AK.K (x.)
Tr(D E + B Pk Pg
DK [T(EE] (R B Px
Dg [||(R B
|D (Tr F.R).
min
R
Thus we complete the proof of upper bound.
remains establish the lower bound. Since the equality is attained at K' K (R+
B Bx ( EKK, we choose this K' such that
J(K) J(K*) 2 J(K) J(K')
= Bn6~N((,DD)
AK, (x()
120
= Tr(Dxr x - Pk B) Exk
> Ominl (Do)ll B Px B 1
'Tr TT((E Ex).
Overall, have
miin (Do) + TT Pk B|
"Tr(F [x) 2 J(K) J(K))
DK- (T(EE
miin Rt)
which concludes our proof.
D EXPERIMENTAL DETAILS
Example D.I. Consider a two-dimensional system with
0
1
0
[
2
1
2
A
-
R
Example D.2. Consider a nour-dimensional system with
0.2
0.1
1
0
E0.3
0
0.2
0.1
0.1
0
0.2
0
0.3
A
.
0
0.1
0.5
0
1
0.3
0
0.5
0.3
0.1
0.1
0
0.2
0
1
0.1
1
0.1
RR
1
0.5
0.2
0.1
1
0.1
1
0.5
0
0.1
34

---

Under review as a conference paper at ICLR 2023
We compare considered single-sample single- timeseli AC with two other baseline algorithms that have been analyzed the sfte-of-the-an art theoretical works: the zeroth-order method (Fazel et al. 2018) (listed in Algorithm 2 on the next page) and the double loop AC (Yang et al. 2019)
(listed in Algorithm on the next page).
For the considered single-sample single-timescale AC, we set for both examples az
/T A
0.005
vI+7: 7t vI+ 1.7 = 10 Note that multiplying small constants to these stepsizes does not affect our theoretical results.
0.01
For the zeroth-order method proposed in Fazel et al. (018), we set 2 = 5000, = 20, r = 0.1, stepsize ア 0.01 and iteration number J = 1000 for the first numerical example; while in the second example, we set = 20000, / = 50, = 0.1,7 0.01, J = 1000. We choose different parameters based on the trade-off between better performance and fewer sample complexity.
For the double loop AC proposed in Yang et al. (019)) we set for both examples a, = 0..11
VI+t*
0,2, 7- 0.05, inner-loop iteration number 7 500000 and outer-loop iteration number J 100.
We note that the algorithm is fragile and sensitive to the practical choice of these parameters. More- over, found that is difficult for the algorithm to converge without an accurate critic estimation in the inner-loop. to barely get the algorithm converge the global optimum. This nevertheless demands significant amount of computation. Higher 7 iterations can yield more accurate critic estimation, and conse- quently more stable convergence, but a price of even longer running time. We run the outer-loop for 100 times for each run of the algorithm. We run the whole algorithm 10 times independently to get the results shown in Figure. With parallel computing implementation, takes more than 2 weeks on our desktop statin (Intel Xe) W-2225 CPU @ 4. 10GHz x 8) to finish the computation. In comparison, takes about 0.5 hour run the single-sample tinleetimescale AC and 5 hours for the zeroth-order method.
our implementation, we have to set the inner-loop iteration number to T = 500000
Algorithm Zeroth-order Natural Policy Gradient
stabilizing policy gain Ko such that p(A BK)) < number of trajectories z, roll-out length perturbation amplitude stepsize 1) while updating current policy do Gradient Estimation:
Input:
for = 1,......... .2.....00 do
Sample vo from D
Simulate K, for steps starting from no and observe you Vt-1 and co, ..-1 Draw U3 uniformly over matrices such that ||AÍ|| and generate policy KJU, K2 + rU,.
Simulate Kj,,, for steps starting from zy and observe do ... .
Calculate empirical estimates:
J
Ct.
Cik
youk
JK
d.
t=0
1=0
1=0
end for Return estimates:
JKYN,
JKy JKi Un, LK, = Σ Ck.
1
VJ(K))
r
1=1
s=1
Policy Update:
K,+1= = Kg - (K,)(K j j=j+1. end while
35

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Double-loop Natural Actor-Critic
Input:
Initial policy т*, such that p(A BKo) 1, stepsize y for policy update.
while updating current policy do
Gradient Estimation:
Initialize the primal and dual variables by do E Xe and wi E Xq. respectively.
Sample the initial state z0 E from stationary distribution pk, Take action uo TK, (+120) and obtain the reward co and the next state æ1. ... Take action 24 according to policy TK,, observe the reward and the next state rt-1-
for 1, .... T do
& 0/-1 1 Cc-1 [0(I1-1, u1-1) - 0(2,, ue] vf-11.
oo vi-1 ai [r|W]/i + (1 u111) [ I].
of vi-1 ai a 4-1) p(1e, uell Φ(zr-1, ux-1) wp-1-
Wi az)li + a - 4-1).
W (1 at)u? + a1 11-1).
Project U, and w, to E d' and wp E Nq.
end for Return estimates:
at); θ smat(
Policy Update:
Kj+1 = K2 n0²2, - j=j+1. end while
36


Reviews:
[{"review_id": "eIWw5Mme4Bd", "reviewer": "Reviewer_HWQj", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper proposes a single time-scale actor-critic (AC) algorithm to solve the LQR problem. The authors establish an $O(1/\\sqrt{T})$ rate of global convergence. Numerical simulations are provided to demonstrate the performance of the proposed algorithm.", "summary_of_the_review": "Since the proposed algorithm is in fact two time-scale, and there are many existing papers analyzing two time-scale actor-critic and its variants, the main contribution (i.e., analysis of single time-scale actor-critic) claimed by the authors is unclear. In addition, some of the assumptions are not realistic. In view of these two point, I cannot recommend accepting this paper to ICLR.", "strength_and_weaknesses": "Major Comments:\n\n(1) The claim of \"single time-scale\" is not correct. The constant $c_\\alpha$ in the stepsize $\\alpha_t$ is in fact not a constant, but depends on the final iteration number $T$, as shown in Eq. (52). Since $t\\leq T$, we still have $\\alpha_t/\\beta_t\\rightarrow 0$ as $t$ goes to infinity, and the algorithm is in fact two time-scale. In view of this, the contribution of this paper is unclear.\n\n(2) As a follow-up comment to (1), the motivation of using diminishing step sizes is that the agent does not need to choose the stepsize based on the final iteration number $T$, otherwise one can simply use constant stepsize designed based on $T$. Since $c_\\alpha$ depends on $T$, this contradicts to the motivation of using diminishing stepsizes.\n\n(3) The authors tried to justify the i.i.d. sampling assumption by stating that one can wait until the Markov chain is sufficiently mixed and then collect one sample. However, this contradicts to the \"single sample\" claim made in this paper. Also, in terms of analysis, the i.i.d. assumption greatly simplifies the proof, and hence is not mild in this viewpoint. In addition, there are many existing papers successfully handled Markovian sampling. \n\n(4) While the authors justified the use of Assumption 4.1 and Assumption 4.2 by citing existing papers and providing numerical simulations, these two assumptions are not logical. Before we run the algorithm, there is no guarantee on the size of $K_t$ and the stability of the system. Assuming something that may or may not happen in the future does not make sense.\n\n(5) When talking about finite-time bound, one should avoid using the big O notation and explicitly characterize all the constants. Theorems involving big O notation are not finite-time bounds but asymptotic bounds.\n\nMinor Comments:\n\n(1) Please change the title to \"... natural actor-critic ... \" to avoid confusion with vanilla actor-critic (without fisher information preconditioner). \n\n(2) There are many related papers studying natural actor-critic (even beyond LQR) and established $O(1/\\epsilon^2)$ sample complexity, just to list a few:\n\n[1] Xiao, L. (2022). On the convergence rates of policy gradient methods. arXiv preprint arXiv:2201.07443.\n\n[2] Lan, G. (2022). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 1-48.\n\n[3] Chen, Z., & Maguluri, S. T. (2022, May). Sample Complexity of Policy-Based Methods under Off-Policy Sampling and Linear Function Approximation. In International Conference on Artificial Intelligence and Statistics (pp. 11195-11214). PMLR.\n\n(3) The authors should make clear about what is established in the literature and what is the contribution of this work. For example, in Section 3, is everything before the algorithm a contribution of this work or already established in literature (e.g., Proposition 3.1)?\n\n(4) Notation such as svec and smat should be properly defined.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LOkr4KU_O6", "reviewer": "Reviewer_Me62", "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": "This paper proposes a single-sample single-timescale Actor-Critic method for the linear quadratic regulator (LQR). The main contribution with respect to the available literature is that the authors suggest the epsilon-optimal solution with a sample complexity \\tilde{O}(epsilon^2) and provide some convergence analyses.", "summary_of_the_review": "Post rebuttal: \n\nI found the paper unready for publication. The importance and novelty of the results is unclear, e.g., the superiority of the suggested method over the existing ones that are faster, more flexible, and can be implemented in an online manner. The technical assumptions, e.g. stability, are strong, while they are studied in the literature. The literature review is also incomplete in other places, e.g. RL in LQR. The main theoretical contribution lacks scalability and it is not clear how the failure probability affects the convergence results. Also on the main theorem, the main convergence rate which is the last one, is not as strong as one expects, and I believe that it can be improved to 1/T. ", "strength_and_weaknesses": "For the policy defined in (7), authors can provide better exploration methods such as optimism or Thompson sampling. The suggested exploration methods can over-explore over time. Also, policies with better exploration methods may improve the theoretical results. \n\nFor experiments, it would be interesting to see comparisons between the single-timescale and two-timescale AC as well. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "51DZwaXppcM", "reviewer": "Reviewer_KvYy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The work considers the linear quadratic regulator problem, and studies the natural actor critic algorithm’s convergence under the single-timescale update, where the step-size of actor and critic variables are proportional by a constant. They show that the algorithm attains the global optimum with the sample complexity of $\\tilde {\\mathcal{O}}(\\epsilon^{-2})$.", "summary_of_the_review": "I have the following main comments:\n\n- The title and the abstract are quite misleading, in which the authors claim that they obtain the convergence of single-timescale AC under LQR problem. After going through the paper, the authors only consider natural AC (NAC). AC and NAC are two quite different algorithms. Hence, the authors must revise any related claims accordingly to reduce confusion. \n\n- From my understanding, Assumption 4.2 is mainly used to ensure the existence of stationary distribution. Is it possible to remove the assumption by considering using the sample from a trajectory? (as in [1, 2])\n\n- Can you also provide convergence of AC under the online update? Even without the knowledge of the model? NAC often has more complex oracle than AC. What is the motivation to consider NAC rather than AC?\n\n- There are works [3, 4, 5] that study the single-timescale AC’s sample complexity for finding a stationary point under the general cost function (rather than LQR). Can their results be extended to LQR problem and obtain the same rate for global convergence? In LQR, the gradient domination property (also known as Polyak-Łojasiewicz inequality) implies that the optimal gap converges in the sample rate as the gradient norm square.\n\n- The authors missed the related reference [4], which gives convergence results for single-timescale AC under the general cost function.\n\n\n[1] Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator.\n\n[2] On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost.\n\n[3] Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.\n\n[4] Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic.\n\n[5] A small gain analysis of single timescale actor critic.\n\n", "strength_and_weaknesses": "Strength:\n- The work considers the single-timescale update, which is more practical than the double-loop update analyzed in previous works.\n- The paper proposes a new analysis framework for the algorithm and establishes the sample complexity of $\\tilde {\\mathcal{O}}(\\epsilon^{-2})$, which matches the best existing sample complexity for single-timescale AC algorithm.\n\nWeakness:\n- Previous works [1, 2] which study the LQR problem seems to have weaker assumption: They only require that initial policy is stable, instead of being stable for each iteration, as assumed in this paper.\n- Since the paper only presents the convergence of the natural AC instead of the AC for the LQR, I suggest the author to add more discussions on the convergence of AC in the introduction.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject