Search papers, labs, and topics across Lattice.
This paper investigates the convergence rates of a single-loop, entropy-regularized Natural Actor-Critic algorithm, addressing the gap between theoretical expectations and practical performance. By employing an uncentered critic and analyzing both stochastic and deterministic optimization regimes, the authors introduce an Exponential Translation mechanism that effectively links regularized and unregularized convergence rates. The results demonstrate accelerated convergence rates, achieving $\tilde{\mathcal{O}}(T_{total}^{-1})$ in the Stochastic Regime and $\tilde{\mathcal{O}}(T_{total}^{-2/3})$ for average iterates in the Deterministic Regime, significantly improving upon existing benchmarks.
Achieving up to $\tilde{\mathcal{O}}(T_{total}^{-1})$ convergence rates without regularization challenges conventional wisdom about the necessity of entropy in policy gradient methods.
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.
