--- title: "Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator" authors: - "Xuyang Chen" - "Jingliang Duan" - "Lin Zhao" doi: "10.24963/ijcai.2024/422" url: "https://ijcai.org/proceedings/2024/422" pdf: "https://ijcai.org/proceedings/2024/0422.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "3816-3824" track: "Main Track" keywords: - "Machine Learning: ML: Reinforcement learning" - "Machine Learning: ML: Learning theory" --- # Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator Xuyang Chen, Jingliang Duan, Lin Zhao *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 3816-3824. DOI: [10.24963/ijcai.2024/422](https://doi.org/10.24963/ijcai.2024/422) ## Abstract Actor-critic methods have achieved state-of-the-art performance in various challenging tasks. However, theoretical understandings of their performance remain elusive and challenging. Existing studies mostly focus on practically uncommon variants such as double-loop or two-timescale stepsize actor-critic algorithms for simplicity. These results certify local convergence on finite state- or action- space only. We push the boundary to investigate the classic single-sample single-timescale actor-critic on continuous (infinite) state-action space, where we employ the canonical linear quadratic regulator (LQR) problem as a case study. We show that the popular single-timescale actor-critic can attain an epsilon-optimal solution with an order of epsilon to -2 sample complexity for solving LQR on the demanding continuous state-action space. Our work provides new insights into the performance of single-timescale actor-critic, which further bridges the gap between theory and practice. ## Full text ## 1 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 a 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 in training. Despite the empirical success, theoretical analysis of AC in the most practical form remains challenging. Existing works mostly focus on either the double-loop or the twotimescale variants. 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 the critic is decoupled from that of the actor. The analysis is separated into a policy evaluation sub-problem in the inner loop and a perturbed gradient descent in the outer loop. In twotimescale AC, the actor and the critic are updated simultaneously in each iteration using stepsizes of different timescales. The actor stepsize (denoted by αt in the sequel) is typically smaller than that of the critic (denoted by βt in the sequel), with their ratio going to zero as the iteration number goes to infinity (i.e., limt→∞αt/βt = 0). The two-timescale allows the critic to approximate the correct Q-value asymptotically. This special stepsize design essentially decouples the analysis of the actor and the critic. The aforementioned AC variants are considered mainly for the ease of analysis, which, however, are uncommon in practical implementations. In practice, the single-timescale AC, where the actor and the critic are updated simultaneously using constantly proportional stepsizes (i.e., with αt/βt = c > 0), is more favorable due to its simplicity of implementation and empirical sample efficiency [Schulman et al., 2015; Mnih et al., 2016]. For online learning, the actor and the critic update only once with a single sample in each iteration using proportional stepsizes. This single-sample single-timescale AC is the most classic AC algorithm extensively discussed in the literature and introduced in [Sutton and Barto, 2018]. However, its analysis is significantly more difficult than other variants, primarily due to the more inaccurate value estimation of the critic update and the stronger coupling between critic and actor. More recent works [Chen et al., 2021; Olshevsky and Gharesifard, 2023; Chen and Zhao, 2022] investigated its local convergence and on the finite state- or action-space only. Given that most practical applications in real world are of continuous state-action space, it is demanding to ask the following challenging question: Can the classic single-sample single-timescale AC find a global optimal policy on continuous state-action space? To this end, we take a first step to consider the Linear Quadratic Regulation (LQR), a fundamental continuous stateaction space control problem that is commonly employed to study the performance and the limits of RL algorithms [Fazel et al., 2018; Yang et al., 2019; Tu and Recht, 2018; Duan et al., 2023]. We analyze the same classic singlesample single-timescale AC algorithm as those studied in the references listed in Table 1. As compared in Table 1, our result is the first to show the global optimality on continuous (infinite) state-action space, while achieving the sample complexity as the previous studies. Specifically, we consider the time-average cost, which is a more common case for LQR formulation and more difficult to analyze than the discounted cost. The single-sample single-timescale AC 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 or two-timescale, there is no specialized design in singlesample single-timescale AC that facilitates 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. Table 1: Comparison with other single-sample single-timescale actor-critic algorithms | Reference | Setting - State Space | Setting - action space | Optimality | Sample Complexity | |-----------------------------------|-------------------------|--------------------------|--------------|---------------------| | [Chen et al., 2021] | infinite | finite | local | O(ϵ-2 ) | | [Olshevsky and Gharesifard, 2023] | finite | finite | local | O(ϵ-2 ) | | [Chen and Zhao, 2022] | infinite | finite | local | O(ϵ-2 ) | | This Paper | infinite | infinite | global | O(ϵ-2 ) | To tackle these challenges in analysis, we instead directly bound the overall interconnected iteration 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 singletimescale AC. Compared with other single-sample single-timescale AC (see Table 1), the state-action space we study is infinite. We emphasize that moving from finite to infinite state-action space is highly nontrivial and requires significant analysis. Existing works [Chen et al., 2021; Chen and Zhao, 2022] derived key intermediate results such as many Lipschitz constants relying on the finite size of the state-action space (|S|, |A|). These results however become immaterial in the infinite state-action space scenario. Some other analysis [Olshevsky and Gharesifard, 2023] concatenates all state-action pairs to create a finite-dimensional feature matrix. However, this will not be possible when the state-action space is infinite. Consequently, existing analyses are not applicable in our context. We also distinguish our work from other model-free RL algorithms for solving LQR in Table 2, in addition to AC methods. The zeroth-order methods and the policy iteration method are included for completeness. In particular, we note that [Zhou and Lu, 2023] analyzed the single-timescale AC under a multi-sample setting, where the critics are updated by the least square temporal difference (LSTD) estimator. The idea is still to obtain an accurate policy gradient estimation at each iteration by using sufficient samples (in LSTD), and then follow the common perturbed gradient analysis to prove the convergence of the actor, which decouples the convergence analysis of the actor and the critic. Moreover, the analysis requires a strong assumption on the uniform boundedness of the critic parameters. In comparison, our analysis does not require this assumption and considers the more classic and challenging single-sample setting which is also considered by the previous works as listed in Table 1. Overall, our contributions are summarized as follows: - Our work furthers the theoretical understanding of AC on continuous state-action space, which represents the most practical usages. We for the first time show that the singlesample single-timescale AC can provably find the ϵ-accurate global optimum with a sample complexity of O(ϵ-2 ) for tasks with unbounded continuous state-action space. The previous works consider the more restricted finite stateaction space settings with only local convergence guarantee [Chen et al., 2021; Olshevsky and Gharesifard, 2023; Chen and Zhao, 2022]. - We also contribute to the work of RL on continuous control tasks. It is novel that even with the actor updated by a roughly estimated gradient, the single-sample singletimescale AC 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 Table 2), our work adopts the simplest single-sample singletimescale structure, which may serve as the first step towards understanding the limits of AC methods on continuous control tasks. In addition, compared with the state-of-the-art double-loop AC for solving LQR [Yang et al., 2019], we improve the sample complexity from O(ϵ-5 ) to O(ϵ-2 ). We also show the algorithm is much more sample-efficient empirically compared to a few classic works in Experiments, which unveils the practical wisdom of AC algorithm. ## 1.1 RelatedWork In this section, we review the existing works that are most relevant to ours. Actor-Critic methods. The AC algorithm was proposed by [Konda and Tsitsiklis, 1999]. [Kakade, 2001] 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 and Meir, 2010; Zhang et al., 2020]. Many recent works focused on the finite-time convergence of AC methods. Under the double-loop setting, [Yang et 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 local convergence of a few AC variants with linear function approximation. Under the two-timescale AC setting, [Wu et al., 2020; Xu et al., 2020] established the finite-time convergence to a stationary point at a sample complexity of O(ϵ-2.5 ). Under the singletimescale setting, all the related works [Chen et al., 2021; Olshevsky and Gharesifard, 2023; Chen and Zhao, 2022] Table 2: Comparison with other model-free RL algorithms for solving LQR. | Reference | Algorithm | Structure | Structure | |-----------------------|------------------|------------------|---------------| | [Fazel et al., 2018] | zeroth-order | | | | [Malik et al., 2019] | zeroth-order | double-loop | | | [Yang et al., 2019] | actor-critic | | | | [Krauth et al., 2019] | policy iteration | multi-sample | multi-sample | | [Zhou and Lu, 2023] | actor-critic | single-timescale | multi-sample | | This paper | actor-critic | single-timescale | single-sample | 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 methods. Our main interest lies in the model-free methods. Notably, [Fazel et al., 2018] established the first global convergence result for LQR under the policy gradient method using zeroth-order optimization. [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 and Lu, 2023] considered the multi-sample (LSTD) and singletimescale setting. For the more practical yet challenging single-sample single-timescale AC, there is no such theoretical guarantee so far, which is the focus of this paper. Notation. We use non-bold letters to denote scalars and use lower and upper case bold letters to denote vectors and matrices respectively. We also use ∥ω∥ to denote the ℓ2-norm of a vector ω, ∥A∥ to denote the spectral norm of a matrix A, and ∥A∥F to denote the Frobenius norm of a matrix A. We use Tr(·) to denote the trace of a matrix. For any symmetric matrix M ∈ Rn×n , let svec(M) ∈ Rn(n+1)/2 denote the vectorization of the upper triangular part of M such that ∥M∥2F = ⟨svec(M), svec(M)⟩. Besides, let smat(·) denote the inverse of svec(·) so that smat(svec(M)) =M. Finally, we denote by A⊗sB the symmetric Kronecker product [Schacke, 2004] 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 Algorithms We consider the reinforcement learning for the standard Markov Decision Process (MDP) defined by (X, U,P, c), where X is the state space, U is the action space, P(xt+1|xt,ut) denotes the transition kernel that the agent transits to state xt+1 after taking action ut at current state xt, and c(xt,ut) is the running cost. A policy πθ(u|x) parameterized by θ is defined as a mapping from a given state to a probability distribution over actions. In this paper, we aim to find a policy πθ that minimizes the infinite-horizon time-average cost, which is given by where ρθ denotes the stationary state distribution generated by policy πθ. In the time-average cost setting, the state-action value (Q-value) of policy πθ is defined as which describes the accumulated differences between running costs and average cost for selecting u in state x and thereafter following policy πθ [Sutton and Barto, 2018]. Based on this definition, we can use the policy gradient theorem [Sutton et al., 1999] to express the gradient of J(θ) with respect to θ as One can also choose to update the policy using the natural policy gradient [Kakade, 2001], which is given by where is the Fisher information matrix and F (θ)† denotes its Moore Penrose pseudoinverse. Optimizing J(θ) in (1) with (2) requires evaluating the Qvalue 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 πθ using temporal difference (TD) learning [Sutton and Barto, 2018]. The actor improves the policy to reduce the time-average cost J(θ) via policy gradient descent. Note that the AC with a natural policy gradient is also known as natural AC, which is a variant of AC. ## 2.2 Actor-Critic for Linear Quadratic Regulator In this paper, we aim to demystify the convergence property of AC by focusing on the infinite-horizon time-average linear quadratic regulator (LQR) problem: where xt ∈ Rd is the state and ut ∈ Rk is the control action at time t; A ∈ Rd×d and B ∈ Rd×k are system matrices, and the (A,B)-pair is stabilizable; Q ∈ Sd×d and R ∈ Sk×k are symmetric positive definite performance matrices, and hence, the (A,Q1/2 )-pair is immediately observable; ϵt ∼ N(0,D0) are i.i.d Gaussian random variables with positive definite covariance D0 ≻ 0. From the optimal control theory [Anderson and Moore, 2007], the optimal policy of (4) is a linear feedback of the state where K∗ ∈ Rk×d is the optimal policy which can be uniquely found by solving an Algebraic Riccati Equation (ARE) [Anderson and 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 a model-free way by using the AC method, without knowing or estimating A, B, Q, R. The structure of the optimal policy in (5) allows us to reformulate (4) as a static optimization problem over all feasible policy matrix K ∈ Rk×d . To encourage exploration, we parameterize the policy as where N(·, ·) denotes the Gaussian distribution and σ > 0 is the standard deviation of the exploration noise. In other words, given a state xt, the agent will take an action ut according to ut = -Kxt + σζt, where ζt ∼ N(0, Ik). As a consequence, the optimization problem defined in (4) under policy (6) can be reformulated as subject to Therefore, the closed-loop form of system (8) is given by where ξt = ϵt + σBζt ∼ N(0,Dσ) with Dσ = D0 + σ2BB⊤. Note that optimizing over the set of stochastic policies (6) will lead to the same optimal K∗ . From (9), a policy K is stabilizing if and only if ρ(A-BK) < 1, where ρ(·) denotes the spectral radius. It is well known that if K is stabilizing, the Markov chain in (9) yields a stationary state distribution ρK ∼ N(0,DK), where DK satisfies the following Lyapunov equation (by taking the variance of (9)) Similarly, we define PK as the unique positive definite solution to (Bellman equation under K) Based on DK and PK, the following lemma characterizes J(K) and its gradient ∇KJ(K). Lemma 1 ([Yang et al., 2019]). For any stabilizing policy K, the time-average cost J(K) and its gradient ∇KJ(K) take the following forms where EK := (R+B⊤PKB)K -B⊤PKA. Then, the natural gradient of J(K) can be calculated as [Fazel et al., 2018; Yang et al., 2019] which eliminates the burden of estimating DK. Note that we omit the constant coefficient since it can be absorbed by the stepsize. Calculating the natural gradient ∇NK J(K) requires estimating PK, which depends on A,B,Q,R. To estimate the gradient without the knowledge of the model, we instead directly utilize the Q-value. Lemma 2 ([Bradtke et al., 1994; Yang et al., 2019]). For any stabilizing policy K, the Q-value QK(x,u) takes the following form where Clearly, if we can estimate ΩK, then EK in (13) can be readily estimated by using Ω21 K and Ω22 K , which represent the bottom left corner block and bottom right corner block of matrix ΩK, respectively. ## 3 Single-sample Single-timescale Actor-Critic In this section, we describe the single-sample singletimescale AC algorithm for solving LQR. In view of the structure of the Q-value given in (14) and the fact that [Schacke, 2004] where and svec(·) denotes the vectorization of the upper triangular part of a symmetric matrix as defined in [Schacke, 2004]. We can then parameterize the Q-estimator (critic) by where ϕ(x,u) defined in (17) is the feature function and ω is the critic. Using the TD(0) learning, the critic update is followed by . where βt 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 ωt+1 in (18) with respect to the stationary distribution, conditioned on ωt, the expected subsequent critic can be written as Note that for ease of exposition, we denote (x′ ,u′ ) as the next state-action pair after (x,u) and abbreviate Ex∼ρK,u∼πK(·|x) as E(x,u). Assumption 1. We consider the policy class K such that ∀K ∈ K, K is norm bounded and the spectral radius satisfies ρ(A-BK) ≤ λ for some constant λ ∈ (0, 1). The above assumes the uniform boundedness of the policy (actor) parameter K, which is common in the literature of actor-critic algorithms [Karmakar and Bhatnagar, 2018; Barakat et al., 2022; Zhou and Lu, 2023]. One potential approach to address the boundedness assumption involves formulating a projection map capable of diminishing the magnitude of ∥K∥ when it exceeds the specified boundary [Konda and Tsitsiklis, 1999; Bhatnagar et al., 2009], which is deferred to future research endeavors. As previously discussed, a policy K is considered stabilizing if and only if ρ(A - BK) < 1. Therefore, Assumption 1 also implies the stability of policy K, which is equivalent to assuming the existence of AK due to the expectation being taken over the stationary distribution. Such assumption is standard in the literature [Wu et al., 2020; Chen et al., 2021; Olshevsky and Gharesifard, 2023]. Without loss of generality, we slightly strengthen the requirement to ρ(A - BK) ≤ λ for some constant λ ∈ (0, 1). This is made to avoid tedious computation of the probability of bounded learning trajectories. It is worth noting that one could alternatively assume ρ(A-BK) < 1 and deduce that the same results presented in the sequel with additional high probability characterization. We then provide the coercive property of cost function J(K), illustrating that J(K) tends towards infinity as ∥K∥ approaches infinity or when ρ(A-BK) approaches 1. Lemma 3 (Coercive Property). The cost function J(K) defined in (7) is coercive, that is, for any sequence {Ki}∞i=1 of stabilizing policies, we have J (Ki) → +∞, if ∥Ki∥ →+∞ or ρ(A-BKi) → 1. Lemma 3 demonstrates the safety of boundary cutting (∥Ki∥ → +∞, ρ(A-BKi) → 1), ensuring that the optimal K∗ that minimizes J(K) resides within the class K, thereby justifying Assumption 1. Additionally, we present some numerical examples in Section 5 to support this assumption. As the existence of AK and bK are ensured by Assumption 1, given a policy πK, it is not hard to show that if the update in (19) has converged to some limiting point ω∗K , i.e., limt→∞ ωt = ω∗K , ω∗K must be the solution of AKω = bK. Lemma 4. Suppose K ∈ K. Then the matrix AK defined in (20) is invertible and AKω = bK has a unique solution ω∗K that satisfies where ΩK is defined in (15). Since smat(·) represents the inverse of svec(·), it follows that ΩK can be expressed as smat(ω∗K ), thereby completing the estimation of ΩK. Combining (13), (15), and (21), we can express the natural gradient of J(K) using ω∗K : where smat(ω∗K )21 and smat(ω∗K )22 represent the bottom left corner block and bottom right corner block of matrix smat(ω∗K ), respectively. This allows us to estimate the natural policy gradient using the critic parameters ωt, and then update the actor in a modelfree manner where αt is the actor stepsize and ̂ ∇NKt J(Kt) is the natural gradient estimation depending on ωt: Furthermore, we introduce a cost estimator ηt to estimate the time-average cost J(Kt). Combining the critic update (18) and the actor update (22)-(23), the single-sample singletimescale AC for solving LQR is listed below. Algorithm 1 Single-Sample Single-timescale Actor-Critic for Linear Quadratic Regulator - 1: Input initialize actor parameter K0 ∈ K, critic parameter ω0, time-average cost η0, stepsizes αt for actor, βt for critic, and γt for cost estimator. - 2: for t = 0, 1, 2, · · · , T -1 do - 3: Sample xt from the stationary distribution ρKt . - 4: Take action ut ∼ πKt (·|xt) and receive cost ct = c(xt, ut) and the next state x′t . - 5: Obtain u′t ∼ πKt (·|x′t ). - 6: δt = ct - ηt +ϕ(x′t ,u′t )⊤ωt -ϕ(xt,ut)⊤ωt - 7: ηt+1 = projB¯ η (ηt + γt(ct - ηt)) - 8: ωt+1 = projB¯ω (ωt +βtδtϕ(xt,ut)) - 9: Kt+1 =Kt -αt(smat(ωt)22Kt - smat(ωt)21 ) - 10: end for Note that single-sample refers to the fact that only one sample is used to update the critic per actor step. Line 3 of Algorithm 1 samples from the stationary distribution induced by the policy πKt , which is a mild requirement in 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 and Recht, 2018], when K ∈ K, (9) is geometrically β-mixing and thus its distribution converges to the stationary distribution exponentially. In practice, one can run the Markov chain in (9) a sufficient number of steps and sample one state from the last step to approximate the stationary distribution. In addition, singletimescale refers to the fact that the stepsizes for the critic and the actor updates are constantly proportional. Since the update of the critic parameter in (18) requires the time-average cost J(Kt), Line 7 provides an estimation of it. Besides, on top of (18), we additionally introduce a projection in Line 8 and Line 9 to keep the critic norm-bounded. The projection follows the standard definition, i.e., projBy (x) means project x to the set By := {x|∥x∥ ≤ y}. This is common in the literature [Wu et al., 2020; Yang et al., 2019; Chen and Zhao, 2022]. In our analysis, the projection is relaxed using its nonexpansive property. ## 4 Main Theory In this section, we establish the global optimality and analyze the finite-time performance of Algorithm 1. All the proofs can be found in the Supplementary Material. Theorem 1. Suppose that Assumptions 1 hold and choose αt = c √T , βt = γt = 1 √T , where c is a small positive constant. It holds that The theorem shows that the cost estimator, the critic, and the actor all converge at a sub-linear rate of O(T - 12 ). The O notation hides the polynomials of the dependence parameters. Note that we have explicitly characterized all the necessary problem parameters in the proofs before the last step of the analysis of the interconnected system. One can easily keep all the problem parameters in the interconnected system analysis and get the order for all parameters. To focus on the key factors and for ease of comprehension, we only show the convergence rate in terms of the iteration number. Correspondingly, to obtain an ϵ-optimal policy, the required sample complexity is O(ϵ-2 ). This order is consistent with the existing results on single-sample single-timescale AC [Chen et al., 2021; Olshevsky and Gharesifard, 2023; Chen and Zhao, 2022]. Nevertheless, our result is the first finite-time analysis of the single-sample single-timescale AC with a global optimality guarantee and considers the challenging continuous state-action space. ## 4.1 Proof Sketch 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 1 in the following. The supporting lemmas and theorems mentioned below can be found in the Supplementary Material. We define three measures AT , BT , CT which denote average values of the cost estimation error, the critic error, and the square norm of natural policy gradient, respectively: where yt := ηt-J(Kt) is the cost estimation error and zt := ωt -ω∗ t with ω∗ t := ω∗Kt is the critic error. Note that EKt = ∇NKt J(Kt) is the natural policy gradient according to (13). We first derive implicit (coupled) upper bounds for the cost estimation error yt, the critic error zt, and the natural gradient EKt , respectively. After that, we solve an interconnected system of inequalities in terms of AT , BT , CT to establish the finite-time convergence. Step 1: Cost estimation error analysis. From the cost estimator update rule (Line 7 of Algorithm 1), we decompose the cost estimation error into (neglecting the projection for the time being): The second term on the right hand side of (24) is a noise term introduced by random sampling of state-action pairs, which reduces to 0 after taking the expectations. The third term is the variation of the moving targets J(Kt) tracked by cost estimator. It is bounded by yt, zt,EKt utilizing the Lipschitz continuity of J(Kt) (Lemma 9), the actor update rule (23), and the Cauchy-Schwartz inequality. The last term reflects the variance in cost estimation, which is bounded by O(γt). Step 2: Critic error analysis. By the critic update rule (Line 8 of Algorithm 1), we decompose the squared error by (neglecting the projection for the time being) where the definitions of h, ¯h,∆h,Λ, and Ot can be found in (28) in the Supplementary Material. The second term on the right hand side of (25) is bounded by -µ∥zt∥2 , where µ is a lower bound of σmin(AKt ) proved in Lemma 10. The third term is a 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 yt and zt. The fifth term tracks the difference between the drifting critic targets. We control it by the Lipschitz continuity of the critic target established in Lemma 11. The last term reflects the variances of various estimations, which is bounded by O(βt). Step 3: Natural gradient norm analysis. From the actor update rule (Line 9 of Algorithm 1) and the almost smoothness property of LQR (Lemma 12), we derive where ˆEKt denotes the estimation of the natural gradient EKt . The first term on the left hand side of (26) 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 consecutive 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 zt and the natural gradient EKt . The last term can be considered as the variance of the perturbed natural gradient update, which is bounded by O(αt). Step 4: Interconnected iteration system analysis. Taking expectation and summing (24), (25), (26) from 0 to T -1, we obtain the following interconnected iteration system: where h2, h4, h5, and h7 are positive constants defined in (47). By solving the above inequalities, we further prove that if h2h24 + h2h24h27 + 2h5h27 < 1, then AT , BT , CT converge at a rate of O(T - 1 2 ). This condition can be easily satisfied by choosing the stepsize ratio c to be smaller than a threshold defined in (51). Step 5: Global convergence analysis. To prove the global optimality, we utilize the gradient domination condition of LQR (Lemma 13): This property shows that the actor performance error can be bounded by the norm of the natural gradient (Tr(E⊤K EK)). Since we have proved the average natural gradient norm CT converges to zero, summation over both sides of the above inequality yields which is the convergence of the actor performance error. We thus complete the proof of Theorem 1. ## 5 Experiments While our main contribution lies in the theoretical analysis, we also present several examples to validate the efficiency of Algorithm 1. We provide two examples to illustrate our theoretical results. The first example (first column in Figure 1) (a) Learning results of Algorithm 1 ![Image](https://ijcai.org/proceedings/2024/fulltext/422/image_000000_109e09709d6e00170a45d09c36e9b5179ab0dd194dd78b54fa096739fcd6ca74.png) (b) Comparison of Algorithm 1 with two other algorithms ![Image](https://ijcai.org/proceedings/2024/fulltext/422/image_000001_0e7d10ff0502e34530d0b9e6a2fbf088e3b92c6fbf96cd0bc1786959a081ca0d.png) Figure 1: (a) Learning results of Algorithm 1. In the figure, the cost error refers to 1 T ∑T -1 t=0 (ηt - J(Kt))2 , Critic error refers to 1 T ∑T -1 t=0 ∥ωt - ω∗Kt ∥2 , and the Actor error refers to 1 T ∑T -1 t=0 [J(Kt) - J(K∗ )], corresponding to the conclusion in Theorem 1 empirically. (b) Comparison of Algorithm 1 with two other algorithms. The actor norm error refers to ∥K -K∗ ∥F . In this figure, the solid lines correspond to the mean and the shaded regions correspond to 95% confidence interval over 10 independent runs. is a two-dimensional system and the second example (second column in Figure 1) is a four-dimensional system. The detailed parameters are shown in Supplementary Material. The performance of Algorithm 1 is shown in Figure 1, where the left column corresponds to the two-dimensional system and the right column to the four-dimensional system. 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 1(a) shows that the cost estimation error, the critic error, and the actor performance error all diminish at a rate of at least O(T - 1 2 ). The convergence also suggests that the intermediate closed-loop linear systems during iteration are uniformly stable. We compare Algorithm 1 with the zeroth-order method [Fazel et al., 2018] and the double-loop AC algorithm [Yang et al., 2019] (listed in Algorithm 2 and Algorithm 3 respectively, in Supplementary Material). We plotted the relative errors of the actor parameters for all three methods in Figure 1(b). As it can be seen that Algorithm 1 demonstrates superior sample efficiency compared to the other two algorithms. ## 6 Conclusion and Discussion In this paper, we establish the finite-time analysis for the single-sample single-timescale AC method under the LQR setting. We for the first time show that this method can find a global optimal policy under the general continuous stateaction space, which contributes to understanding the limits of the AC on continuous control tasks. ## Acknowledgements This work was supported by the Singapore Ministry of Education Tier 1 Academic Research Fund (22-5460-A0001) and Tier 2 AcRF (T2EP20123-0037). (Corresponding author: Lin Zhao.) The work of J. Duan was supported in part by the NSF China under Grant 52202487 and in part by the Young Elite Scientists Sponsorship Program by CAST under Grant 2023QNRC001. ## References 1. [Anderson and Moore, 2007] Brian DO Anderson and John B Moore. Optimal control: linear quadratic methods. Courier Corporation, 2007. 2. [Barakat et al., 2022] Anas Barakat, Pascal Bianchi, and Julien Lehmann. Analysis of a target-based actor-critic algorithm with linear function approximation. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 991-1040. PMLR, 2022. 3. [Bhatnagar et al., 2009] Shalabh Bhatnagar, Richard S Sut- ton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(11):2471-2482, 2009. 4. [Bradtke et al., 1994] 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'94, volume 3, pages 3475-3479. IEEE, 1994. 5. [Castro and Meir, 2010] Dotan Di Castro and Ron Meir. A convergent online single time scale actor critic algorithm. The Journal of Machine Learning Research, 11:367-410, 2010. 6. [Chen and Zhao, 2022] Xuyang Chen and Lin Zhao. Finite- time analysis of single-timescale actor-critic. arXiv preprint arXiv:2210.09921, 2022. 7. [Chen et al., 2021] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternat- ing stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34:25294-25307, 2021. 8. [Cohen et al., 2019] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only √ T regret. In International Conference on Ma- chine Learning, pages 1300-1309. PMLR, 2019. 9. [Dean et al., 2018] 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. 10. [Dean et al., 2020] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample com- plexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-679, 2020. 11. [Duan et al., 2023] Jingliang Duan, Jie Li, Xuyang Chen, Kai Zhao, Shengbo Eben Li, and Lin Zhao. Optimiza- tion landscape of policy gradient methods for discrete-time static output feedback. IEEE Transactions on Cybernetics, 2023. 12. [Fazel et al., 2018] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gra- dient methods for the linear quadratic regulator. In Inter- national Conference on Machine Learning, pages 1467- 1476. PMLR, 2018. 13. [Joarder and Omar, 2011] Anwar H Joarder and M Hafidz Omar. On statistical characteristics of the product of two correlated chi-square variables. Journal of Applied Statis- tical Science, 19(4):89-101, 2011. 14. [Kakade, 2001] Sham M Kakade. A natural policy gradi- ent. Advances in neural information processing systems, 14, 2001. 15. [Karmakar and Bhatnagar, 2018] Prasenjit Karmakar and Shalabh Bhatnagar. Two time-scale stochastic approxima- tion with controlled markov noise and off-policy temporal- difference learning. Mathematics of Operations Research, 43(1):130-151, 2018. 16. [Konda and Tsitsiklis, 1999] Vijay Konda and John Tsitsik- lis. Actor-critic algorithms. Advances in neural informa- tion processing systems, 12, 1999. 17. [Krauth et al., 2019] Karl Krauth, Stephen Tu, and Benjamin Recht. Finite-time analysis of approximate policy iteration for the linear quadratic regulator. Advances in Neural In- formation Processing Systems, 32, 2019. 18. [Kumar et al., 2019] Harshat Kumar, Alec Koppel, and Ale- jandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approxi- mation. arXiv preprint arXiv:1910.08412, 2019. 19. [LeCun et al., 2015] Yann LeCun, Yoshua Bengio, and Ge- offrey Hinton. Deep learning. nature, 521(7553):436-444, 2015. 20. [Magnus, 1978] Jan R Magnus. The moments of products of quadratic forms in normal variables. Statistica Neer- landica, 32(4):201-210, 1978. 21. [Malik et al., 2019] Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Martin Wain- wright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2916-2925. PMLR, 2019. 22. [Mania et al., 2019] Horia Mania, Stephen Tu, and Ben- jamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Pro- cessing Systems, 32, 2019. 23. [Mnih et al., 2016] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asyn- chronous methods for deep reinforcement learning. In In- ternational conference on machine learning, pages 1928- 1937. PMLR, 2016. 24. [Nagar, 1959] Anirudh L Nagar. The bias and moment ma- trix of the general k-class estimators of the parameters in simultaneous equations. Econometrica: Journal of the Econometric Society, pages 575-595, 1959. 25. [Olshevsky and Gharesifard, 2023] Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 61(2):980-1007, 2023. 26. [Rencher and Schaalje, 2008] Alvin C Rencher and G Bruce Schaalje. Linear models in statistics. John Wiley & Sons, 2008. 27. [Schacke, 2004] Kathrin Schacke. On the kronecker product. Master's thesis, University of Waterloo, 2004. 28. [Schulman et al., 2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015. 29. [Silver et al., 2017] 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, 550(7676):354-359, 2017. 30. [Sutton and Barto, 2018] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. 31. [Sutton et al., 1999] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approx- imation. Advances in neural information processing sys- tems, 12, 1999. 32. [Tu and Recht, 2018] Stephen Tu and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. In International Conference on Ma- chine Learning, pages 5005-5014. PMLR, 2018. 33. [Wang et al., 2019] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150, 2019. 34. [Wu et al., 2020] 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 Pro- cessing Systems, 33:17617-17628, 2020. 35. [Xu et al., 2020] Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotic convergence analysis of two time- scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.03557, 2020. 36. [Yang et al., 2019] Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances in neural information processing systems, 32, 2019. 37. [Zhang et al., 2020] Shangtong Zhang, Bo Liu, Hengshuai Yao, and Shimon Whiteson. Provably convergent two- timescale off-policy actor-critic with function approxima- tion. In International Conference on Machine Learning, pages 11204-11213. PMLR, 2020. 38. [Zhou and Lu, 2023] Mo Zhou and Jianfeng Lu. Single timescale actor-critic method to solve the linear quadratic regulator with convergence guarantees. Journal of Ma- chine Learning Research, 24(222):1-34, 2023.