acceptodds
Under review as a conference paper at ICLR 2027

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

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 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 which becomes for total Markov sample budget , giving iteration complexity and sample complexity for squared KKT accuracy . Beyond stationarity, discounted occupancy coverage yields for direct tabular policies, so covered exact KKT points are globally optimal, while a statewise quadratic Bellman-improvement condition sharpens the relation to . 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.

Primary area:
optimization
Keywords:
Nonconvex ADMM, Reinforcement Learning, Markovian Optimization, Bellman Equation, Policy Optimization, Primal-Dual Methods, Occupancy Measure, Function Approximation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_u1k2OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper gives the analysis of the Alternating Direction Method of Multipliers for non-convex minimization, applied to the problem of reinforcement learning. Specifically, it analyzes the tabular MDP setup and shows that the bellman resolvent provides the stability needed for convergence of the bellman constrained policy optimization, improving upon conventional analyses where such stability is assumed. The main focus of the analysis is the evolution of the block matrix entries of the value block as the policy evolves. The analysis involves accounting for the errors incurred due to estimation of the transition model shared across the primal and dual updates, converting the KKT residual gap into the gap on expected return as well extension of said result to general non-linear policy setup. The sample complexity results is obtained for the squared KKT residual and supporting results for the convergence and rates are provided.

Critical strengths
  1. The paper provides genuinely interesting analysis on how the multiplier stability of non-convex ADMM can be established for the tabular RL case. This analysis may be of interest to both the optimization and RL communities.
  2. The specific results regarding value-dual adjoint multiplier stability are quite general results and show promise in being applicable in other hierarchical RL setups such as bi-level RL and constrained MDP problems. 3.The analysis connecting the KKT residual to expected return is also quite interesting and may be applicable in futrure analyses of MDP setups.
  3. The work has empirical results to verify the rates of the established algorithm, something which is rare for theory focussed works and should be commended.
Critical weaknesses

The main issue with the result is the fact that, as it stands, it is presented as a sample complexity result for a policy optimization algorithm. In comparison to the existing literature, it thus exposes several critical weaknesses.

  1. The analysis here is for a tabular setup for the main rate. In contrast, their are several existing works which already analyze continuous state spaces with general non-linear policy optimization algorithm with last iterate sample complexity (such as Gaur et al. mentioned in the work itself).
  2. The obtained sample complexity is with respect to the KKT residual. When the sample complexity is evaluated for the final expected return, it converts to a sample complexity of \epsilon^{-4}. This is worse than established results both with respect to Gaur et al. as well as some other results where \epsilon^{-2} was obtained (Ganesh et al.).
  3. The empirical results do not compare performance to other existing RL algorithms. Thus it is hard to provide a comparative analysis in both a theoretical and analytical sense.

References:

Order-Optimal Global Convergence for Actor-Critic with General Policy and Neural Critic Parametrization, (UAI 2025); Swetha Ganesh, Jiayu Chen, Washim Uddin Mondal, Vaneet Aggarwal

Questions for authors
  1. In your analysis, you mention that the V block need not be smooth. But since you consider the smooth objective as linear, does the linearity not provide the smoothness? I may be wrong in this so would like some clarification.
  2. In the final rate constants, the dependence on the state and action space size, does not seem to be explicit. Can you state what the explicit dependence will be?
Reviewer_ZbUSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper presents a structural mechanism and formulation for reinforcement learning through nonconvex ADMM. The core idea of this paper is that the Bellman resolvent (I−γPπ)−1(I-\gamma P_\pi)^{-1} can provide multiplier stability for nonconvex ADMM, and the authors establish convergence of the KKT residual under controlled Markov sampling. They provide a finite-time complexity of the squared KKT residual O(T−1+T/N)O(T^{-1} + T/N) and extend it to a policy performance gap of O(G)O(\sqrt{G}). The authors further extend to nonlinear policies, projected Bellman equations and occupancy formulations, and test their claims on small tabular MDPs.

Critical strengths

This paper offers a structural viewpoint connecting nonconvex ADMM and Bellman policy optimization, where the invertibility of the discounted Bellman operator supplies multiplier stability. The authors maintain this viewpoint coherently throughout the paper, from the squared KKT residual analysis to the nonlinear-policy, projected Bellman, and occupancy formulations, and the policy-performance guarantee gives the optimization analysis a direct reinforcement learning meaning.

Critical weaknesses

Weakness1. Major concern regarding presentation, contribution and support for the central claim.

(1) The contribution of this paper is obscurely established, and the weak presentation reinforces it. The central point of this paper can be stated concisely: applying the discounted Bellman resolvent (I−γPπ)−1(I - \gamma P_\pi)^{-1} gives the multiplier stability that "classical nonconvex ADMM analyses often obtain from a designated smooth block." I consider this direction potentially valuable, but the paper does not clearly establish the following three points: (i) Which point was the central limitation of previous works. (ii) Which exact point is the direct breakthrough of this paper compared to previous works. (Points (i) and (ii) are detailed in (2).) (iii) From the breakthrough of this paper, what the RL community gains for informative knowledge. Furthermore, the presentation itself is weak, not well condensed and organized, which differs from what is expected of a theory paper at ICLR. Specifically, the paper does not develop its argument around its most important claim and main theorem. Sections 4 and 5 present a series of lemmas and theorems of similar weights, and Section 7 presents appendix numbering for the proofs. Hence, readers cannot identify the main claim directly from the paper, and must connect and infer it by themselves.

(2) The authors claim that the Bellman resolvent can replace the smooth block as the source of multiplier stability in the convergence analysis, but the paper does not support this claim, or supports it only vaguely. Specifically, the introduction states that existing nonconvex analyses obtain multiplier stability "from a designated smooth block and a suitable linear operator," and the authors position the Bellman resolvent as its replacement. However, the paper does not clearly explain which specific step of existing smooth-block-based analyses cannot be applied to the proposed formulation, or how the resolvent-based argument overcomes this limitation. As far as I understand, the authors appear not to replace smoothness through the resolvent, but instead address the dependency of MπM_\pi on the policy π\pi through Lemma A.1 and Lemma 4.3, unlike the fixed linear subblock of the multiaffine formulation in Gao et al. (2020).

Weakness 2. Motivation and significance of the ADMM formulation in reinforcement learning.

In section 6, the author sets ϕ≡0\phi \equiv 0 and c=−μc = -\mu without further justification. In such cases, the problem of equation (1) reduces to the standard policy optimization as the author mentioned in Section 3. However, this problem is known as an already solved problem through any of the methods following: value iteration, policy iteration, or linear programming. The paper does not justify why specific ADMM should be applied to solve this problem. Although Appendix C.9 explains specific cases when ϕ≢0\phi \not\equiv 0, this is a technical example but not a justification why RL requires this method. As far as I understand, the ADMM formulation is required under which the previous method was impossible to solve, for example the general case when ϕ≢0\phi \not\equiv 0. However, the paper demonstrates neither that the proposed nonconvex ADMM analysis solves RL problems that classical methods cannot solve, nor that it provides improved bound or sample complexity fairly compared to existing methods in RL.

Given weaknesses, it is difficult to assess the contribution of this paper. In its current state, I recommend 2 (weak reject), unless the authors can clearly justify their claims and address weaknesses.

Questions for authors

Q1. In Appendix C.2, the authors describe Lemma 4.3 as the replacement for the classical smooth-block multiplier estimate. However, the problem formulation in equation (1) already gives a linear smooth block c⊤Vc^\top V and an invertible matrix MπM_\pi. Could the authors further clarify which assumption or step in the classical smooth-block analysis cannot be applied to problem (1), and how Lemma 4.3 overcomes this limitation?

Q2. Why should ADMM be applied to the problem in equation (1)? When ϕ≡0\phi \equiv 0, the problem reduces to standard policy optimization, which existing methods already solve. Could the authors justify why the Bellman-ADMM structure is required under a specific case, for example ϕ≢0\phi \not\equiv 0? Alternatively, when the problem reduces to standard policy optimization with ϕ≡0\phi \equiv 0, does the Bellman-ADMM analysis provide an improved bound or sample complexity in a fair comparison with existing methods?

1 comment

I thank the authors for the response.

Resolved. The answer to Q1 is precise. The authors confirm that the key difficulty is the policy dependence of the Bellman operator, and that Lemma A.1 and Lemma 4.3 control the changing-operator term. The answers to W1 (i)-(iii) also state the limitation of previous work and the contribution more clearly than the submission.

Not resolved. The response confirms my concern on the central claim instead of resolving it. The title and the abstract state that the Bellman resolvent replaces the smooth-block mechanism. However, according to the response, the value block is linear and smooth, and the assumption that is replaced is the fixed constraint operator, not smoothness. The central claim and the actual contribution are therefore different.

On W2, the authors agree that the formulation has no advantage when the regularizer is zero, and state that the value appears with a nonsmooth or nonconvex regularizer. However, the paper still contains no instance or experiment in this regime, so the motivation remains unsupported.

Rating. I maintain my rating at 2 (weak reject). I consider the mechanism itself potentially valuable. In my view, the claim and the proof would be consistent if the contribution were stated as multiplier stability under a policy-dependent operator.

Reviewer_dcQUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies ADMM for discounted reinforcement learning formulated with Bellman equality constraints and a possibly nonsmooth, nonconvex policy penalty. Its main contribution is to use stability of the policy-dependent Bellman operator to control multiplier updates. Under controlled Markov sampling, a shared empirical model preserves this structure and supports convergence to first-order stationary conditions, together with a sublinear bound on the expected squared stationarity residual. Additional results connect these residuals to policy performance under coverage assumptions and extend the analysis to nonlinear policies, projected Bellman equations, and occupancy formulations.

Validation uses small finite MDPs with five states and two actions. The experiments compare shared and separately estimated models across ADMM updates, supporting the proposed consistency mechanism. All experiments use no policy penalty and include no comparison with established planning or RL algorithms.

Critical strengths
  1. A substantive convergence argument for policy-dependent Bellman constraints. The paper uses stability of the inverse Bellman operator to control ADMM multiplier updates, addressing a structural distinction from analyses requiring a fixed linear constraint block. This provides a potentially reusable analytical mechanism beyond a direct application of existing ADMM results.

  2. Careful treatment of empirical-model errors. The analysis handles dependence between estimated Bellman residuals and their Jacobians by using a shared empirical model across updates. The experiments include meaningful consistency and sampling-budget controls that support this mechanism. This strengthens confidence in the technical analysis, although the validation remains limited to small unregularized MDPs.

Critical weaknesses
  1. The significance for solving RL problems is insufficiently demonstrated. All experiments use small, unregularized MDPs and compare variants of the proposed ADMM procedure. They support the empirical-model consistency mechanism, but do not establish a benefit over classical planning methods using the same samples. Since ordinary finite discounted MDPs already admit established solution approaches, the paper needs a clearer explanation of what useful capability or sufficiently broad theoretical advance this alternative formulation provides.

  2. The general nonconvex-penalty setting lacks convincing motivation and computational validation. The main theory assumes global solution of each policy subproblem, while excluding its internal computational cost from the complexity bounds. The proximal-gradient extensions mitigate this requirement but still need tractable proximal updates for the chosen penalty. The support-count example in Appendix C.9 is not experimentally tested and already admits an ordinary optimal deterministic policy as a global solution. Consequently, the paper does not demonstrate a practically relevant nonconvex setting in which its broader theory provides a meaningful advantage.

Questions for authors
  1. Clarification of significance: What is the most consequential new theoretical insight provided by the changing-operator analysis, beyond convergence of this particular ADMM splitting? Which useful problem class or broader analytical consequence distinguishes it from existing approaches?

  2. Clarification of computational scope: Beyond the support-count example, what practically motivated nonconvex policy penalty changes the optimal decision problem and admits tractable exact or proximal updates? What computational costs are excluded from the stated complexity bounds?

  3. Clarification of theory and experiments: Do the sufficient conditions admit substantially tighter instance-dependent bounds for the tested MDPs? The large-penalty experiment is acknowledged; the unresolved issue is how informative the guarantees are for the parameter regime exhibiting favorable finite-budget behavior.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.