- 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
- 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.
- 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.
- 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.
- 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).
- 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.).
- 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
- 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.
- 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?
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.