Finite-time bounds arrive for importance-corrected momentum actor-critic on a single Markovian trajectory, with normalized steps converging faster and Muon pushing the rank factor into noise
Synopsis
Finite-time analyses of importance-corrected momentum (ICM) actor-critic previously relied on unbiased i.i.d. gradients or restarted episodes, whereas reinforcement learning samples along a single Markovian trajectory whose gradients are biased and correlated. This analysis pairs a ridge-regularized pathwise least-squares temporal-difference critic with ICM actors that average policy gradients over frames of T transitions, giving finite-time bounds along one trajectory: the averaged gradient norm decays as O(K-1/3+1/T) for normalized steps and O(K-1/4+1/T) for unnormalized steps. The bounds retain a constant floor from the stationary-to-discounted distribution mismatch, while the remaining error terms fall at least as 1/T with frame length.
Interpretation
Actor-critic learning along a single Markovian trajectory now has explicit finite-time convergence bounds, and both normalized and orthogonalized steps enter the same analysis. Earlier finite-time analyses covered only unnormalized steps, while analyses of normalized and orthogonalized momentum assumed unbiased i.i.d. gradients or relied on restarted episodes. With the critic, policy-gradient estimator and ICM held fixed, the averaged gradient norm after K updates is bounded by O(K-1/3+1/T) for normalized steps and O(K-1/4+1/T) for unnormalized steps, where T is the number of transitions per frame.
The critic needs no stepsize, no mixing time and no rank condition, solving a ridge-regularized system per frame. The usual approach takes one semi-gradient temporal-difference step per transition, requiring stepsize tuning and suffering the slow transient of stochastic updates. The critic approximates the ridge-regularized pathwise least-squares solution with Newton-Schulz iterations built only from matrix multiplications; the Newton-Schulz error falls superlinearly with the number P1 of recursions, and the Markovian sampling error is of order τmix/T.
Four concrete actor updates are compared in one framework, and Muon's rank factor appears only in the noise and correction terms. Muon-type methods in reinforcement learning had only been studied empirically, without finite-time guarantees along a single trajectory. With a dimension-free stepsize constant, Muon confines the min{m,n}1/2 factor to the noise and correction terms; orthogonalization guarantees a larger noiseless ascent than normalization exactly when the gradient's nuclear rank exceeds the ratio of spectral to Frobenius curvature constants.
Perspective
The analysis targets discounted Markov decision processes with a linear value-function critic and K updates along a single continuous trajectory, each frame containing T transitions; the conclusions are stated as theorems and include no experimental validation.
The bounds retain a constant floor caused by the mismatch between the stationary and discounted state-visitation distributions, and that floor does not vanish with frame length or update count; the authors note that removing it requires a different sampling protocol. The unnormalized-step bound also requires the stepsize constant to tighten as 1/T.
