Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic

Zhiqiang Tan

cs.LGAug 20, 2026

Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic

Authors: Zhiqiang Tan

Organizations: Department of Statistics, Rutgers University. Address: 110 Frelinghuysen Road, Piscataway, NJ 08854.

Abstract

While entropy regularization is widely used to stabilize and accelerate Natural Policy Gradient methods, its ability to yield faster convergence rates for the unregularized objective remains underexplored. Existing analyses often rely on double-loop architectures and invoke a linear entropy penalty. To bridge the gap between theory and practice, we analyze a single-loop, entropy-regularized Natural Actor-Critic algorithm under compatible linear function approximation. By training an uncentered critic, our critic tracking can remain stable even as the training policy approaches determinism and the Fisher information matrix degenerates. We focus on two primary regimes for the optimization landscape: a Stochastic Regime, where we fuse coupled actor-critic updates into a joint Lyapunov recurrence, and a Deterministic Regime, where we pivot to a Policy Mirror Descent framework to circumvent the collapse of Euclidean geometry. By exploiting a positive Minimal Action Gap in the unregularized Markov decision process, we introduce an Exponential Translation mechanism that maps the regularized gap to the unregularized one up to an exponentially decaying tail. By tuning the fixed temperature, our algorithm achieves accelerated unregularized convergence rates, up to approximation-error terms: $\tilde{\mathcal{O}}(T_{total}^{-1})$ in the Stochastic Regime, and $\tilde{\mathcal{O}}(T_{total}^{-2/3})$ for the average iterate alongside $\tilde{\mathcal{O}}(T_{total}^{-1/3})$ for the last iterate in the Deterministic Regime. Here, $T_{total}$ denotes the total number of stochastic critic updates (or Monte Carlo rollouts). Furthermore, in the tabular setting, our positive-action-gap analysis yields a $\tilde{\mathcal{O}}(T_{total}^{-2/3})$ average-iterate rate, surpassing the $\mathcal{O}(T_{total}^{-1/2})$ worst-case statistical barrier that applies without a positive action margin.

Figures & tables

Reference	Algorithm	Setting	Obj	Rate
Agarwal et al., (2021)	Double-loop	Discounted,	Unreg	Avg: $\mathcal{O}(T_{total}^{-1/4})+\mathcal{O}(\sqrt{\epsilon_{app}})$
(Corollary 26)	Q-NPG	indep. sampling
Liu et al., (2020)	Double-loop	Discounted,	Unreg	Avg: $\mathcal{O}(T_{total}^{-1/3})+\mathcal{O}(\sqrt{\epsilon_{app}})$
(Theorem 4.9)	NPG	indep. sampling
Yuan et al., (2023)	Double-loop	Discounted,	Unreg	Last: $\tilde{\mathcal{O}}(T_{total}^{-1/2})+\mathcal{O}(\sqrt{\epsilon_{app}})$
(Corollary 1)	Q-NPG	indep. sampling

Table 1: Comparison of sample-based NPG and NAC algorithms using linear function approximation (log-linear policies and linear compatible critics).

T_{total}=N\times T

denotes the total number of stochastic updates (or Monte Carlo rollouts) across

T

outer-loop iterations and

N

inner-loop steps, translating to the total number of environment interactions up to an additional

\mathcal{O}((1-\gamma)^{-1})

expected-horizon factor.

Reference	Algorithm	Unregularized Rate
Shani et al., (2020) (Thm. 5)	TRPO (with $\nu$ -sampling)	Avg: $\tilde{\mathcal{O}}(T_{total}^{-1/4})$
Cen et al., (2022) (Rem. 1)	SPI (Generative Model)	Last: $\tilde{\mathcal{O}}(T_{total}^{-1/2})$
Lan, (2023) (Prop. 2)	SPMD (Generative Model)	Avg: $\tilde{\mathcal{O}}(T_{total}^{-1/2})$
Ours (Theorem 10.3 )	ent-reg, unc NAC	Avg: $\tilde{\mathcal{O}}(T_{total}^{-2/3})$
	(with $\nu$ -sampling)	Last: $\tilde{\mathcal{O}}(T_{total}^{-1/3})$

Table 2: Comparison of sample-based NPG and PMD algorithms in the tabular unregularized setting, free of concentrability conditions.

T_{total}

denotes the total number of stochastic updates, translating to environment interactions up to an additional

\mathcal{O}((1-\gamma)^{-1})

expected-horizon factor.

\theta_{t+1}=\Pi_{R_{\theta}}\Big[\theta_{t}-\alpha_{t}g_{t}^{cr}(s_{t},a_{t})\Big].

Algorithm 1 Single-Loop, Entropy-Regularized, Uncentered Natural Actor-Critic

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

\theta_{t}^{(k+1)}=\theta_{t}^{(k)}+\alpha_{t}\big(\hat{Q}_{k}-\theta_{t}^{(k)\top}\phi(s_{k},a_{k})\big)\phi(s_{k},a_{k})

Appendix

Algorithm 2 Double-Loop Unregularized Q-NPG ( Agarwal et al.,, 2021 ; Yuan et al.,, 2023 )

\theta_{t}^{(k+1)}=\theta_{t}^{(k)}+\alpha\Big(\hat{A}_{k}-\theta_{t}^{(k)\top}\tilde{\phi}_{t}(s_{k},a_{k})\Big)\tilde{\phi}_{t}(s_{k},a_{k})

Appendix

Algorithm 3 Double-Loop Unregularized NPG ( Liu et al.,, 2020 )

\omega_{t+1}=\omega_{t}+\eta_{t}(\theta_{t+1}-\tau\omega_{t}).

Appendix

Algorithm 4 Sample-Based Entropy-Regularized NPG with Averaging ( Cayci et al.,, 2024 )

\theta_{t}^{(k+1)}=\Pi_{R_{\theta}}\Big[\theta_{t}^{(k)}-\alpha_{t}g_{t}^{cr}(s_{k},a_{k})\Big].

Appendix

Algorithm 5 Warm-Start Double-Loop, Entropy-Regularized, Uncentered Natural Actor-Critic

Policy Optimization

Policy optimization develops algorithms for improving decision rules in reinforcement learning, language models, and sequential decision systems.

See all 215 papers

May 23, 2026

Refined Analysis of Entropy-Regularized Actor-Critic

In this paper, we study the role of the critic in actor--critic for entropy-regularized, finite, discounted environments. We establish that, when the critic is exact, using the latter as a baseline is a variance-reduction method in a strong sense. In this case, actor--critic with stochastic gradients matches the sample complexity of deterministic policy gradient, reaching an

ε

-optimal regularized value with

\tilde{O}(\log(1/ε))

samples. In practice, the critic is learned alongside the actor: the variance of the actor update is then influenced by the critic's variance and bias. Specifically, when the critic has a sufficiently small error, the variance reduction and rapid convergence are preserved. This suggests to learn the critic first, keeping it up to date after each actor update, underscoring the crucial role of accurate critic estimation in actor--critic methods.

Safwan Labbi, Paul Mangold, Daniil Tiapkin +1

CMAP, CNRS, École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France · Université Paris-Saclay, CNRS, LMO, 91405, Orsay, France · Google DeepMind +2

Reinforcement Learning Maximum Entropy RL Policy Gradient Methods Actor-Critic Methods Sample-Efficient RL

Ask PDF

Oct 11, 2023

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

Regularization is a cornerstone of modern reinforcement learning. Regularized policy iteration (RPI) provides a fundamental scheme for solving regularized Markov decision processes (RMDPs), and the widely used soft actor-critic algorithm arises as a special case when the regularizer is Shannon entropy. Despite its empirical success, the theoretical underpinnings of RPI remain unclear. In this paper, we address this gap by proving that RPI is formally equivalent to the standard Newton-Raphson method applied to the Bellman equation smoothed by strongly convex regularizers. This equivalence enables a unified convergence analysis of existing methods and supports the development of accelerated algorithms. We show that RPI enjoys local quadratic convergence; notably, for Shannon entropy, the guarantee is dimension-free. We further study RPI with inexact policy evaluation, establishing its equivalence to an inexact Newton method in which each Newton step is solved via truncated iterations, and derive an asymptotic linear convergence rate of

γ^{M}

, where

M

denotes the number of operator steps used in policy evaluation. Finally, motivated by higher-order Newton schemes, we propose a new algorithm for RMDPs that achieves third-order local convergence. Numerical experiments corroborate our theory and demonstrate the practical advantages of the proposed algorithm. Overall, our results advance the theoretical understanding of regularization in reinforcement learning and suggest new directions for efficient algorithm design.

Zeyang Li, Chuxiong Hu, Yunan Wang +4

Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, United States · Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China · College of Artificial Intelligence and the School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China

Markov Decision Processes Reinforcement Learning Policy Optimization Policy Iteration Second-Order Optimization

Ask PDF

May 13, 2026

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

In this paper, we establish last-iterate convergence rates for off-policy actor--critic methods in reinforcement learning. In particular, under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods, we prove the first

\tilde{\mathcal{O}}(ε^{-2})

sample complexity guarantee for finding an

ε

-optimal policy under minimal assumptions, namely, the existence of a policy that induces an irreducible Markov chain. This stands in stark contrast to the existing literature, where an

\tilde{\mathcal{O}}(ε^{-2})

sample complexity is achieved only through nested-loop updates and/or under strong, algorithm-dependent assumptions on the policies, such as uniform mixing and uniform exploration. Technically, to address the challenges posed by the coupled update equations arising from the single-loop implementation, as well as the potentially unbounded iterates induced by off-policy learning, our analysis is based on a coupled Lyapunov drift framework. Specifically, we establish a geometric convergence rate for the actor and an

\tilde{\mathcal{O}}(1/T)

convergence rate for the critic, and combine the two Lyapunov drift inequalities through a cross-domination property. We believe this analytical framework is of independent interest and may be applicable to other coupled iterative algorithms with unbounded

Ishaq Hamza, Zaiwei Chen

IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE

Policy Gradient Last-Iterate Convergence Natural Policy Gradient Actor-Critic Methods Policy Learning Sample-Efficient RL+1

Ask PDF

Abstract

Policy Optimization

Explore similar work

Refined Analysis of Entropy-Regularized Actor-Critic

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

Achieving ε−2ε^{-2}ε−2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions