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

Mathematical methods of reinforcement learning
Jul 8, 2026Denis Belomestny, Alexander Gasnikov, Egor Gladin +5Markov Decision Processes Reinforcement Learning
Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1
Policy Gradient for Continuous-Time Robust Markov Decision Processes
Jun 3, 2026Tanya Veeravalli, David M. Bossens, Atsushi NitandaRobust Markov Decision Processes Markov Decision Processes
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
Sample-Efficient Reinforcement Learning with General Utilities via Neural Dual Critics
Oct 17, 2026Ankur Naskar, Vaneet AggarwalReinforcement Learning Sample-Efficient RL
Indian Institute of Science, India · Purdue University, USA

Jul 8, 2026J/K move · Enter open · S save

Mathematical methods of reinforcement learning

Denis Belomestny, Alexander Gasnikov, Egor Gladin, Alexey Naumov+4

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

Markov Decision Processes Reinforcement Learning Function Approximation in RL

Open paper AskPDF arXiv

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.

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