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

Zhaojun Peng

cs.LGSep 29, 2026

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

Authors: Zhaojun Peng

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.

Figures & tables

Ref.	Method	Data	Structural assumption	Stability / analysis device	Guarantee	RL meaning
[ 16 ]	ADMM	Det.	Nonconvex consensus / sharing; large penalty	Consensus / sharing structure + AL descent	Stationary-set convergence	–
[ 34 ]	MEAL	Det.	Weakly convex nonsmooth, linear constraints	Moreau envelope of AL	$o(\varepsilon^{-2})$ FOSP complexity	–
[ 6 ]	ADMM	Det.	Nonsmooth nonconvex under RSC	Restricted strong convexity	Convergence without differentiability	–
[ 33 ]	Prox-ADMM	Det.	Multi-block; one continuous block; BI / SU operator	Increasing penalty + decreasing smoothing	$O(\varepsilon^{-3})$ critical-point complexity	–
[ 36 ]	Stoch. ADMM	Finite sum	Nonconvex nonsmooth linear constraint	SVRG + momentum + potential	$O(1/T)$ stationarity; linear under KL	–
[ 30 ]	1st-order opt.	Markov	Smooth nonconvex gradient oracle	Markov-oracle lower-bound construction	$\Omega(\varepsilon^{-4})$ countable; $\Omega(\varepsilon^{-2})$ finite chain	RL-relevant oracle

Table 1: Structural positioning across neighboring theories. Rates are reported in each paper’s native stationarity or performance metric.

Panel of Figure 1 — Figure 1: Numerical validation of the operator-stability mechanism. (a) A shared empirical Bellman operator yields substantially smaller true squared KKT residuals than an equal-budget split-operator construction. (b) Sharing the operator preserves the empirical value–dual identity to numerical precision, whereas inconsistent blockwise operators break this identity. (c) With $m_{k}=T$ and $N=T^{2}$ , the companion squared KKT residual exhibits slope $-0.87$ , close to the $T^{-1}$ scaling predicted by Theorem 5.2 .

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Batch-size sensitivity. Mean companion squared KKT residual at fixed

T=240

as the Markov batch size increases. The dashed line shows an

m^{-1}

reference slope.

Figure 3: Residual–Jacobian product scaling. Magnitude of the empirical product term

\beta G^{\top}e

as the batch size increases. The same-batch construction follows approximately the predicted

m^{-1}

scale. Independent batches reduce the correlation but require separate samples.

Figure 4: KKT residual and policy performance. Policy suboptimality versus the true KKT scale

\sqrt{G}

. The dashed line denotes the empirical 95th-percentile

C\sqrt{G}

envelope.

Figure 5: Penalty sensitivity. Trailing true squared KKT residual as a function of the ADMM penalty parameter

\beta

Construction	Value	Dual	Total steps
All shared	0	0	$m$
Value–dual shared	1	1	$2m$
All separate	1	2	$3m$

Appendix

Table 2: Empirical-model assignments. Distinct indices denote separately sampled models. Under an equal per-model batch size

m

, the last column gives the total number of reset-controlled sampling steps per iteration.

Figure 6: Identity preservation and estimator precision. Left: trailing identity defect under equal per-model batches and adaptive behavior. All-shared and value–dual-shared curves overlap at numerical precision. Right: empirical-model squared error under fixed uniform behavior and 320 steps per model. Circles denote policy models and squares denote value models. Model error is measured as the sum of squared Frobenius transition error and squared Euclidean reward error. Error intervals resample MDP means.

Budget	Construction	Steps	$G$	$\Delta_{\lambda}$	$\Delta_{J}$
Equal total	All shared	320	0.5028	1.0452	0.01425
	Value–dual shared	320	1.3813	2.2538	0.05144
	All separate	320	13.1920	12.8006	0.17656
Equal per model	All shared	320	0.5028	1.0452	0.01425
	Value–dual shared	640	0.6390	1.1283	0.02419
	All separate	960	4.1585	4.0575	0.04168

Appendix

Table 3: Batch-320 comparison. Entries average the last 30 of 180 iterations and then the eight MDP means.

G

is the true squared KKT residual,

\Delta_{\lambda}

is the squared multiplier increment, and

\Delta_{J}=J^{\star}-J(\pi)

is the return gap. Total cost includes reset steps.

Figure 7: Consistency and sampling-budget controls. Top: equal total steps per iteration. Bottom: equal steps per empirical model, with total costs

m

2m

, and

3m

for all shared, value–dual shared, and all separate. Columns show the true squared KKT residual, squared multiplier increment, and return gap. Curves average the last 30 of 180 iterations. Shading denotes 95% bootstrap intervals over MDP means.

Metric	Contrast	Mean difference	95% interval
$G$	Value–dual shared $-$ all shared	0.1361	$[0.0463,0.2260]$
	All separate $-$ all shared	3.6557	$[2.6170,4.6944]$
	All separate $-$ value–dual shared	3.5196	$[2.5340,4.5052]$
$\Delta_{\lambda}$	Value–dual shared $-$ all shared	0.0831	$[0.0205,0.1457]$
	All separate $-$ all shared	3.0123	$[2.2128,3.8118]$
	All separate $-$ value–dual shared	2.9293	$[2.1526,3.7060]$

Appendix

Table 4: Paired contrasts at equal per-model batch size 320. Each contrast subtracts the second construction from the first. Intervals are based on eight paired MDP means.

Construction	$G$	$\Delta_{\lambda}$	$\Delta_{J}$
All shared	0.8505	1.7776	0.02818
Value–dual shared	1.1477	1.8908	0.04018
All separate	7.0014	6.7681	0.07335

Appendix

Table 5: Uniform-behavior control at 320 steps per model. Total costs are 320, 640, and 960 steps, respectively. The notation and aggregation match Table 3 .

Figure 8: Discount sensitivity with fixed policy and transition error. One empirical transition model per run is reused across all discounts. Panels show the true resolvent norm and the absolute and relative errors in the stationary dual representation. Shading denotes 95% bootstrap intervals over MDP means.

Figure 9: Dynamic discount sweep. Uniform behavior and 320 steps per model, with all other algorithmic parameters fixed. The reset probability changes with the discount. Outcomes average the last 30 of 180 iterations, and shaded intervals resample MDP means.

Construction	$G$	$\Delta_{\lambda}$	$\Delta_{J}$	$D$
All shared	$6.735$	$76.779$	$2.034$	$2.22\times 10^{-11}$
Value–dual shared	$266.470$	$1813.805$	$2.177$	$3.13\times 10^{-11}$
All separate	$5.12\times 10^{8}$	$8.33\times 10^{8}$	$2.210$	$1.82\times 10^{4}$

Appendix

Table 6: Large-penalty check. Uniform behavior, 320 steps per model, and

\beta=97777.778

. All quantities use the same trailing aggregation as the other controls.

D

denotes the identity defect.

Alternating Direction Method of Multipliers

Alternating Direction Method of Multipliers (ADMM) splits structured optimization problems into simpler updates coordinated by dual variables.

See all 32 papers

Jul 8, 2026

Mathematical methods of reinforcement learning

Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates for value and policy iteration, and temporal-difference schemes. We then develop the optimization perspective: stochastic approximation and martingale methods, convex duality and the role of regularization linking mirror/proximal methods. Function approximation is treated through linear and non-linear settings, covering stabilization, error decomposition, and sample-complexity via concentration inequalities for dependent data and mixing processes. We further cover off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs). Throughout we unify algorithmic templates under common operator and variational lenses, highlighting both finite-sample bounds and asymptotic results. Our presentation is intended to provide a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning.

Denis Belomestny, Alexander Gasnikov, Egor Gladin +5

Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1

Markov Decision Processes Reinforcement Learning Function Approximation in RL

Ask PDF

Jun 3, 2026

Policy Gradient for Continuous-Time Robust Markov Decision Processes

The framework of robust Markov decision processes (RMDPs) allows the design of reinforcement learning agents that satisfy performance guarantees under worst-case transition dynamics. Traditional RMDPs consider discrete-time dynamics and recently, sample-efficient policy gradient algorithms have been considered in this context. This paper investigates policy gradient algorithms within a continuous-time RMDP framework. Policy gradients and adversarial gradients are derived using pathwise and adjoint-based formulas for stochastic and ordinary differential equations. We propose double-loop optimisers to obtain linear convergence in the oracle-based setting and an

\tilde{\mathcal{O}}(\frac{1}{ε^2})

sample complexity in the sample-based setting in an analysis which also derives novel tools for the framework of undiscounted total cost MDPs. Additionally, we propose mean-field optimisers as distributional optimisers with an

\tilde{\mathcal{O}}(\frac{1}{K})

oracle-based convergence rate and an

\tilde{\mathcal{O}}(\frac{N^2}ε)

sample complexity under

N

-particle approximation. The effectiveness of continuous-time policy gradient algorithms is confirmed for both optimisers on continuous-time RMDPs with neural ordinary differential equation dynamics.

Tanya Veeravalli, David M. Bossens, Atsushi Nitanda

Centre for Frontier AI Research, Agency for Science, Technology and Research (A*STAR) · Institute of High Performance Computing, Agency for Science, Technology and Research (A*STAR) · College of Computing and Data Science, Nanyang Technological University

Robust Markov Decision Processes Markov Decision Processes Continuous-Time RL Policy Gradient Methods Robust RL Policy Learning

Ask PDF

Oct 17, 2026

Sample-Efficient Reinforcement Learning with General Utilities via Neural Dual Critics

Reinforcement learning with general utilities optimizes nonlinear functionals of policy-induced occupancy measures. We develop a natural actor-critic method for concave RLGU objectives admitting an exact variational dual representation, with explicit constructions for a broad class of separable occupancy utilities. Rather than estimating the occupancy measure and then forming the policy-gradient pseudo-reward, our method learns this pseudo-reward directly as a function of the state-action pair using a neural critic. The critic is trained by projected stochastic updates, while multilevel Monte Carlo combines outputs across training horizons to control its bias at logarithmic expected cost. Our analysis separates conditional actor bias from estimator second moments and accounts explicitly for dual optimization, critic approximation, and neural linearization errors. Under policy-transfer, dual-stability, and local critic-regularity conditions, the method achieves

\widetilde{O}(T^{-1/2})

global convergence above policy, critic-class, and finite-width approximation errors using

\widetilde{O}(T)

expected environment transitions and reference samples. For a fixed critic representation, this yields

\widetilde{O}(ε^{-2})

sampling complexity above the approximation floor, covering infinite state-action spaces and occupancy utilities beyond fixed finite vectors of returns.

Ankur Naskar, Vaneet Aggarwal

Indian Institute of Science, India · Purdue University, USA

Reinforcement Learning Sample-Efficient RL Actor-Critic Methods Function Approximation in RL

Ask PDF

Abstract

Alternating Direction Method of Multipliers

Explore similar work

Mathematical methods of reinforcement learning

Policy Gradient for Continuous-Time Robust Markov Decision Processes

Sample-Efficient Reinforcement Learning with General Utilities via Neural Dual Critics