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

• URL: http://arxiv.org/abs/2608.19587v1
• Date: Thu, 20 Aug 2026 03:08:33 GMT
• Title: Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic
• Abstract summary: entropy regularization is widely used to stabilize and accelerate Natural Policy Gradient methods.<n>We analyze a single-loop, entropy-regularized Natural Actor-Critic.<n>By training an uncentered critic, our critic tracking can remain stable even as the training policy approaches determinism.
• Score: 3.756550107432323
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Stability and Generalization of Straight-Through Estimators for Training Two-Layer Quantized Neural Networks [16.84694273405234]
  We study the identity straight-through estimator (STE) for training a two-layer binary-activation network with hinge loss.<n>Our central question is whether algorithmic stability can explain the statistical generalization of the estimator produced by the discontinuous STE training rule.
  arXiv  Detail & Related papers  (2026-09-06T07:12:16Z)
• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element.<n>Our main result bounds the regret by $widetildeObig(sqrtT, d_*(),log|X|big)$, where $d_*()$ is a widely-adopted notion of effective dimension.
  arXiv  Detail & Related papers  (2026-05-26T06:10:24Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms [8.636513507553504]
  We analyze two classical algorithms for solving additively composite convex optimization problems.<n>We focus on the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates.<n>Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.
  arXiv  Detail & Related papers  (2026-02-05T09:50:06Z)
• Optimal Rates in Continual Linear Regression via Increasing Regularization [39.30412893918111]
  We study realizable continual linear regression under random task orderings.<n>In this setup, the worst-case expected loss after $k$ learning admits a lower bound of $Omega (1/k)$.<n>We use two frequently used regularization schemes: explicit isotropic $ell$ regularization, and implicit regularization via finite step budgets.
  arXiv  Detail & Related papers  (2025-06-06T19:51:14Z)
• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  We address the problem of solving strongly convex and smooth problems using gradient descent (SGD) with a constant step size.<n>We provide an expansion of the mean-squared error of the resulting estimator with respect to the number of iterations $n$.<n>Our analysis relies on the properties of the SGDs viewed as a time-homogeneous Markov chain.
  arXiv  Detail & Related papers  (2024-10-07T15:02:48Z)
• Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization [26.218670461973705]
  We propose methods for solving problems coordinate non-asymptotic gradient norm guarantees. Our results demonstrate the efficacy of the proposed cyclic-reduced scheme in training deep neural nets.
  arXiv  Detail & Related papers  (2022-12-09T19:17:39Z)
• Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
  We revisit the classical entropy regularized policy gradient methods with the soft-max policy parametrization. We establish a global optimality convergence result and a sample complexity of $widetildemathcalO(frac1epsilon2)$ for the proposed algorithm.
  arXiv  Detail & Related papers  (2021-10-19T17:21:09Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.