CS Paper Radar

A Unified Analysis of Importance-Corrected Momentum Actor-Critic over a Markovian Trajectory

Yanjie Dong, Zhou Su, Wei Wang, Gang Wang

cs.LG cs.AI ·submitted 2026-10-24 06:03 UTC · v1

Abstract

We present a generic actor-critic method that combines a ridge-regularized pathwise least-squares temporal-difference (LSTD) critic with importance-corrected momentum (ICM) actors. The critic solves a ridge-regularized system per frame by Newton-Schulz inversion and needs no stepsize, no knowledge of the mixing time, and no rank condition. Averaging stochastic policy gradients over frames of $T$ consecutive transitions, the ICM actors incur a frame-dependent gradient bias of order $\frac{1}{T}$. To our knowledge, we establish the first finite-time bounds for ICM actor-critic methods with normalized and unnormalized steps along a single Markovian trajectory. Up to a stationary-to-discounted distribution mismatch, the averaged gradient norm over $K$ updates is bounded by ${\cal O}(K^{-1/3}+\frac{1}{T})$ for normalized steps and by ${\cal O}(K^{-1/4}+\frac{1}{T})$ for unnormalized steps. We specialize these bounds to Muon, normalized stochastic gradient descent (SGD) with momentum, SGD with momentum, and AdaNorm, and compare them in the nuclear norm. With a dimension-free stepsize, Muon confines the factor $\min\{m,n\}^{1/2}$ associated with an $m\times n$ actor parameter matrix to the noise and correction terms. The comparison also characterizes when orthogonalization guarantees a larger noiseless ascent than normalization: exactly when the gradient's nuclear rank exceeds the spectral-to-Frobenius curvature ratio.

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Regularized Policy Mirror Descent with One-Step TD Updates

cs.LG math.OC ·2026-09-30 ·Qipei Chen, Wenye Li, Yule Sun, Ke Wei
similarity 0.72
Abstract

Policy mirror descent (PMD) enjoys fast convergence in regularized Markov decision processes (MDPs), but existing guarantees often rely on exact or increasingly accurate policy evaluation. We analyze PMD coupled with a persistent critic advanced by one temporal-difference (TD) update. For finite discounted MDPs, we establish global linear convergence in value for exact coordinate-wise Bellman updates, with any positive constant actor stepsize and arbitrary finite critic initialization. The proof combines a resolvent-based auxiliary distribution with a decaying Bellman-violation correction and a potential weighted by inverse coordinate weights. We then study stochastic TD-PMD with general strongly convex mirror maps under a single off-policy Markov trajectory. With suitably chosen constant stepsizes and a finite-batch TD update, the method achieves an expected value gap of $ε$ after $\widetilde{O}(1/((1-γ)^5 \widetildeσ_b ε))$ transitions. The stochastic analysis relies on the trajectory-wise Lipschitz continuity of the regularizer, derived from uniform bounds on vertex Bregman divergences, together with a visitation-weighted resolvent estimate for signed critic-error propagation that yields an inverse-linear dependence on behavior coverage $\widetildeσ_b$. In contrast to many prior guarantees for regularized policy optimization, our sample-complexity guarantee holds without trajectory resets, generative-model access, or nested policy-evaluation loops. Numerical results are consistent with the theoretical convergence analysis.

0.44

Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs

cs.LG math.OC ·2026-10-02 ·Enes Arda, Atilla Eryilmaz
top venue similarity 0.69
Abstract · NeurIPS 2026 camera-ready version. 45 pages, 5 figures

Policy mirror descent (PMD) has a mature finite-time theory in discounted Markov decision processes (MDPs), but less is known in the average-reward setting, a more natural objective for many control applications. We give a finite-time, finite-sample analysis of PMD in ergodic average-reward MDPs built around a single master recursion that governs convergence for any critic, without external regularization. Its specializations yield linear rates for exact, inexact-tabular, and linear function approximation (LFA) updates. For exact PMD, the rate is tight in the worst case, and convergence can become superlinear. We complement these convergence results with critics whose end-to-end sample complexities improve the prior best policy-gradient dependence from $|S||A|\,t_{\mathrm{mix}}^3$ to $|S|\,t_{\mathrm{mix}}^3+|S||A|\,t_{\mathrm{mix}}^2$ in the tabular setting and from $|S||A|\,t_{\mathrm{mix}}^5$ to $d\,t_{\mathrm{mix}}^3$ under LFA. Matching information-theoretic lower bounds establish that both critics are optimal up to logarithmic factors.

0.37

Anatomy of Off-Policy Policy Gradient: Importance Sampling, KL Regularization, and Baselines

cs.LG cs.AI ·2026-10-19 ·Haoqun Cao, Yurun Yuan, Tengyang Xie
similarity 0.67
Abstract

Reinforcement learning has become a central tool for large language model (LLM) post-training, where policy gradient methods are routinely deployed off-policy, even though vanilla policy gradient assumes on-policy sampling. We study when such off-policy deployment is justified, and what roles its core ingredients, including importance sampling, KL regularization, and baselines, play in handling the resulting distribution shift. We show that for a general class of off-policy policy gradient updates, consistency, in the sense that the optimal policy remains a stationary point, requires one of two structures at the optimal policy: trajectory-level importance weighting, which suffers from the well-known curse of horizon, or KL regularization with a baseline equal to the optimal soft value, instantiated by the grouped mean. Focusing on the KL route, we identify it with the group-relative policy gradient (GRPG) update, establish an equivalence to a trajectory-level Bellman residual minimization objective, and obtain a finite-sample regret bound under all-policy coverage. This also gives a theoretical account of a variant of the empirically successful GRPO objective. We further uncover a hidden role of baselines in the off-policy setting: a constant shift in the baseline implements pessimism, the standard remedy in offline RL for partial data coverage. We instantiate this via the asymmetric REINFORCE objective, and connect it to the game-theoretic offline RL framework, showing a regret bound with single-policy coverage. Together, these results offer a unified theoretical view of off-policy policy gradient in LLM post-training and connect it to classical ideas in offline RL.

0.26

On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces

cs.LG math.OC ·2026-11-04 ·Jingyi Jin, Martha White, Hao Wang
similarity 0.66
Abstract · 66 pages, 1 figure. Submitted to the Journal of Machine Learning Research

Temporal-difference (TD) learning underlies many prediction and control algorithms, but can diverge when combined with off-policy learning, bootstrapping, and function approximation. TD with Regularized Corrections (TDRC) is theoretically sound and practically simple, but existing convergence theory covers only the one-step case under i.i.d. sampling, while the Huber Bellman-error formulation has not been extended to TDRC or eligibility traces. In this work, we establish convergence of constrained TDRC($λ$) with diminishing stepsizes and non-i.i.d. off-policy data, for state-dependent and history-dependent $λ$-parameters. We also propose TDRC($λ$)-Huber, which preserves the TDRC($λ$) fixed point while reducing sensitivity to large Bellman errors. For both algorithms, we apply an ODE-based weak-convergence method from stochastic approximation theory. For the nonlinear mean dynamics of TDRC($λ$)-Huber, we give an integral small-gain condition that guarantees uniqueness and global asymptotic stability of the target equilibrium. We then establish convergence of the constrained algorithm, derive computable sufficient conditions for convergence, and identify a regularization-based convergence mechanism shared by linear TDRC($λ$) and TDRC($λ$)-Huber. When the mean TD matrix is positive stable, both constrained algorithms converge under sufficiently strong regularization without requiring positive definiteness.

0.23

Neural Actor--Critic Learning with Minimax Critics and Reflected Langevin Sampling

cs.LG stat.ML ·2026-11-02 ·Kunqi Huang, Lican Kang, Hongrui Shu, Jincheng Ying
similarity 0.66
Abstract

Actor--critic methods rely on critic gradients to improve continuous-action policies, yet finite-sample guarantees must control both value and gradient errors and their propagation through the actor. We develop a neural actor-critic procedure that combines a regularized minimax Bellman estimator over sigmoid networks with a finite reflected Langevin sampler driven by the fitted critic gradient. Under uniform Bellman regularity and covered reset sampling, a positive high-order action-derivative penalty yields value and action-gradient risk bounds with classical nonparametric minimax exponents up to logarithmic factors. We propagate estimation, mixing, discretization, temperature, and policy-iteration errors to obtain return guarantees, with refinements for bounded multimodal potentials and strongly concave regimes. Empirical studies across controlled simulations, logged continuous-control data, and a simulated decision task show favorable performance relative to the considered baselines.

0.15

Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

cs.LG cs.GT ·2026-10-05 ·Yuheng Zhang
similarity 0.65
Abstract

We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a $\widetilde{\mathcal{O}}(t^{-1/4})$ duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the $\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al. (2023), for any fixed $ν>0$, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.

0.19

Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data

cs.LG stat.ML ·2026-09-30 ·Yang Peng
theory similarity 0.65
Abstract

We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy $b$ with an irreducible, possibly periodic state chain; a target policy $π$ covered by $b$ is evaluated with action importance ratios bounded by $\varrho$. Write $H=(1-γ)^{-1}$, with $μ_{\min}$ the minimum stationary probability and $\mathfrak h_\star$ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most $\varepsilon$ with high probability after $\widetilde O(\varrho H^3/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions for $0<\varepsilon\le1$. The statistical term retains the cubic effective-horizon dependence of synchronous TD, while the initialization cost is additive in $\mathfrak h_\star$. Setting $b=π$ and $\varrho=1$ recovers the on-policy rate. For aperiodic behavior chains, $\mathfrak h_\star=\widetilde O(t_{\rm mix}/μ_{\min})$ recovers a mixing-time bound. The proof combines an anchored local Poisson equation in reverse time to control fluctuations without a mixing-time factor, a compensation argument for successive hitting costs, and an expected cumulative propagation mass bound for decreasing step sizes. Given the policy ratios and their bound, an empirical state-count rule attains the same rate without prior knowledge of model parameters. The framework covers nonnegative affine importance-weighted prediction updates, including successor features, transition-dependent discounting, and coupled finite-mode predictions. A perturbation estimate yields a time-uniform guarantee for online return-variance estimation. A three-state, two-action construction gives matching minimax lower bounds for both terms up to logarithmic factors on the considered parameter classes.

0.47

Markovian Nonconvex ADMM for Reinforcement Learning: Bellman-Resolvent Stability Beyond Smooth Blocks

cs.LG ·2026-09-29 ·Zhaojun Peng
similarity 0.65
Abstract

We identify and study a structural mechanism for Markovian nonconvex ADMM in reinforcement learning. Using finite discounted MDPs as a canonical proving ground, we show that the discounted Bellman resolvent $(I-γP_π)^{-1}$ can provide the multiplier stability that classical nonconvex ADMM analyses often obtain from a designated smooth block. Starting from this mechanism, we establish convergence under controlled Markov sampling and then under stochastic observations using an empirical Bellman surrogate that jointly represents the random residual and its Jacobian. Markov mixing, initialization drift, observation noise, and decaying bias enter as one operator perturbation, avoiding unbiased product and double sampling requirements. When the perturbations are square summable, the true KKT residual converges almost surely to zero. Under a finite conditional fourth moment condition, a companion iterate satisfies $ \mathbb{E}[\widetilde G_{K+1}] \le A/T+(B/T)\sum_{k<T}m_k^{-1}, $ which becomes $O(T^{-1}+T/N)$ for total Markov sample budget $N$, giving $O(ε^{-1})$ iteration complexity and $O(ε^{-2})$ sample complexity for squared KKT accuracy $ε$. Beyond stationarity, discounted occupancy coverage yields $J^\star-J(π)=O(\sqrt G)$ for direct tabular policies, so covered exact KKT points are globally optimal, while a statewise quadratic Bellman-improvement condition sharpens the relation to $O(G)$. Finally, nonlinear policy, projected Bellman, and explicit occupancy formulations exhibit the same chain of operator invertibility, dual representation, and multiplier stability. This supports discounted operator invertibility as a reusable structural principle for primal-dual reinforcement learning.

0.26