REVIEW 3 major objections 4 minor 15 references
A single constrained-RL algorithm achieves ~sqrt(T) regret and violation with no Slater point, and sublinear violation against adversarial constraints.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
A new algorithm achieves Õ(√T) regret and constraint violation in online CMDPs without Slater's condition, plus sublinear α-regret against the unconstrained optimum under adversarial constraints.
T0 review reviewed 2026-08-04 challenge →
load-bearing objection Stochastic no-Slater sqrt(T) result is a real advance, but the adversarial alpha-regret proof has a load-bearing gap: unvisited support pairs break the containment argument. the 3 major comments →
Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Core claim
The paper's discovery is that the Slater-free guarantee comes from replacing the usual primal-dual, Lagrangian machinery with a moving optimistic decision space. At each episode, the algorithm plays the occupancy measure induced by an online mirror descent update over the set of occupancies that look feasible after subtracting an optimistic bonus from the empirical constraint estimates. Because the true safe set is contained in this optimistic set with high probability, the no-regret update automatically approaches the best safe policy; the same framework, with adaptively weighted constraint estimators, extends to adversarially chosen constraints. The result is ~sqrt(T) regret and violation
What carries the argument
The load-bearing object is the per-episode 'moving' feasible set, written roughly as Δ̂_t(P_t) = {q in Δ(P_t) : (ĝ_{t,i} - b_t)^T q ≤ 0 for all i}. Here Δ(P_t) is the set of occupancy measures compatible with the transition confidence set, ĝ_{t,i} is a weighted estimate of the i-th constraint, and b_t is an optimistic UCB-style bonus. The constraint estimator uses adaptive learning rates: under stochastic constraints the weights collapse to the empirical mean, so the bonus alone handles feasibility; under adversarial constraints the weights respond to accumulated violation. WC-OPS runs online mirror descent with the unnormalized KL divergence over this moving feasible set, and this construct
Load-bearing premise
For the adversarial constraint guarantee to be non-vacuous, there must exist an occupancy that clears every constraint by a strictly positive margin in every episode and on every state-action pair it uses (rho > 0); the stochastic guarantee additionally assumes the feasible set is non-empty, otherwise the optimum is undefined.
What would settle it
Build a single-state, two-action CMDP in which the only safe occupancy has expected constraint cost exactly zero (the feasible set lies on the boundary, with no interior point), run WC-OPS with stochastic constraints, and measure regret and positive violation. The theorem predicts both grow roughly as sqrt(T); observing linear growth in either would contradict the central claim.
If this is right
- Stochastic CMDPs need no strictly feasible solution: as long as the feasible set is non-empty, regret and violation both grow as ~sqrt(T) with high probability.
- Positive violation is also ~sqrt(T), so an agent cannot hide early constraint violations by later playing very safe policies.
- Adversarial constraints are handled without Slater's condition: cumulative violation stays sublinear, and alpha-regret relative to the unconstrained optimum is sublinear, with alpha = rho/(1+rho).
- The violation bounds have no explicit 1/rho^2 dependence, removing a known source of poor performance in nearly-infeasible problems.
- The same algorithm and parameter choices behave well whether constraints are stochastic or adversarial, so the learner need not know the regime in advance.
Where Pith is reading between the lines
- Editorial extension: because the regret argument relies on optimism in the constraint estimate rather than on a dual variable, the same moving-feasible-set schedule is a natural template for partial-feedback or bandit versions of the problem, which the paper does not analyze.
- Editorial extension: the adversarial guarantee is only as strong as the uniform margin rho; allowing the margin to vary per episode or per state-action would clarify how the alpha-regret degrades as rho approaches zero.
- Editorial extension: the positive-violation control makes WC-OPS a natural candidate for safety-critical deployments where early violations cannot be cancelled; simulation benchmarks with per-episode violation budgets would test that practical value.
- Editorial extension: substituting a variance-adaptive confidence width for the worst-case bonus could preserve the sqrt(T) rate while improving constants on easy stochastic instances; this is a direct testable variation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online episodic loop-free CMDPs with adversarial rewards and constraints that are either stochastic i.i.d. or fully adversarial. It proposes WC-OPS (Algorithm 1), an optimistic OMD-based method that maintains transition-function confidence sets, weight-based constraint estimators with adaptive learning rates, and an optimistically constrained occupancy set. The main claims are: (i) in the stochastic-constraint regime, Õ(√T) regret, cumulative violation, and positive violation without any Slater-like condition; (ii) in the adversarial-constraint regime, Õ(√T) violation and Õ(√T) α-regret with respect to the unconstrained optimum, with α = ρ/(1+ρ) under a per-state-action uniform margin condition. Proofs are given in a detailed appendix, and synthetic experiments are reported.
Significance. If correct, the stochastic results would be a genuine improvement over the earlier best-of-both-worlds CMDP algorithms: they remove Slater's condition and extend the guarantees to positive violation at the optimal rate. The adversarial α-regret claim, relative to the unconstrained optimum, would also be notable. The paper is clearly written and the proof strategy is interesting, with a useful alternative to primal-dual methods. However, the adversarial α-regret theorem rests on a containment proof that contains a demonstrable error. Since that result is one of the two headline contributions, the manuscript cannot be accepted without substantive revision. I also flag an internal inconsistency in the definition of the constraint learning rate and a missing proof of an imported concentration lemma.
major comments (3)
- [Section 4.2 / Appendix B.2, Theorem 4.5] The proof asserts that for every t and i, max_{(x,a)∈Q(q⋄)} ĝ_{t,i}(x,a)q⋄(x,a) ≤ -ρ. This is false when N_t(x,a)=0: ĝ_{t,i}(x,a) is the weighted average over the observed visits T_{t,x,a} (Algorithm 1, Line 8; Eq. (2)), so an empty sum gives ĝ_{t,i}(x,a)=0 > -ρ. No event in the high-probability analysis forces all support pairs of q⋄ to be visited by episode t; the OMD update gives only positive, possibly exponentially small, sampling probabilities. Consequently ĝ_{t,i}^T q⋄ need not be ≤ -ρ' = -Lρ, and the interpolated point q̃ = (L q⋄ + ρ' q)/(L+ρ') can violate (ĝ_t - b_t)^T q̃ ≤ 0. Thus Δ⋄ ⊆ Δ̂_t(P_t) is not established as written, and Theorem 4.6's α-regret bound is not proven. I note that Algorithm 1 already includes b_t in the definition of Δ̂_t(P_t); a repair could prove (ĝ_t - b_t)^T q⋄ ≤ -ρ' using b_t ≥ ρ on unvisited pairs, but that is not what the manuscript proves and requir
- [Section 3.2 / Appendix B.5, β definition] The definition of the constraint learning rate β_{t,i}(x,a) is inconsistent between the main text and the appendix. The main text as typeset gives β_{t,i}(x,a)=1/(N_t(x,a)(1+Γ_{t,i})), while the proof of Theorem B.7 (and Corollary B.5) uses β_{t,i}(x,a)=(1+Γ_{t,i})/N_t(x,a). These differ by a factor (1+Γ_{t,i})^2. The lower bound in the proof of Theorem B.7, β_{t,i}(x,a) ≥ 21L|X|√(2|A|ln(···))/N_t(x,a), is valid only for the second form. If the intended algorithm is β=(1+Γ)/N, the main-text formula must be corrected; if β=1/(N(1+Γ)), the violation proof is invalid. This is load-bearing for the violation bound claimed in both settings.
- [Appendix C, Lemma C.2] Lemma C.2, the concentration inequality for transition functions used in Lemma C.5 and ultimately in Theorem B.2, is imported as 'Lemma J.6 of [Stradi et al., 2025d]' with no proof. This is a load-bearing step in the regret analysis. The manuscript should either provide a proof or state the result with a precise, self-contained derivation; a journal version should not rely on an unproved lemma from a companion paper for a central bound.
minor comments (4)
- [Eq. (4)] The bonus b_t(x,a) is undefined when N_t(x,a)=0. A convention such as b_t(x,a)=∞ or b_t(x,a)=c for N_t=0 (or max{1,N_t} in the denominator) is needed for Corollary 4.2 and for any repair of Theorem 4.5.
- [Proof of Theorem 4.6] The final sentence says 'ρ/(1+ρ') = ρ'/(L+ρ)', which is algebraically false. The correct identity is ρ'/(L+ρ') = ρ/(1+ρ). This appears to be a typo, but it should be corrected.
- [Section 2.3] When ρ=0, α=0 and the α-regret bound is vacuous (or trivially non-positive). The paper should state explicitly that Theorem 4.6 assumes ρ>0, or explain the degenerate case.
- [Appendices D / Figures] The experimental figures lack sufficient detail in the main text (axis labels, number of runs, problem sizes, confidence intervals are only mentioned in the appendix). This is a presentation issue and does not affect the theoretical claims.
Circularity Check
No significant circularity: the central regret/violation proofs reduce to external OMD/concentration lemmas, not to the paper's own conclusions.
full rationale
The derivation chain is self-contained with respect to circularity. The stochastic no-Slater result (Theorem 4.3) follows from Corollary 4.2 (true feasible set contained in the optimistic set via Hoeffding + bonus) combined with a standard OMD regret bound (Theorem B.2) whose proof explicitly invokes external lemmas: Lemma 6 of Jin et al. (2020), Lemma B.3 of Rosenberg and Mansour (2019b), and Lemma 12 of Jin et al. (2020). The only self-cited item, Lemma C.2 (Lemma J.6 of Stradi et al. 2025d), is a parameter-free transition-occupancy concentration inequality; it does not assume Slater's condition nor any of the paper's target guarantees, so it is independent support rather than a circular premise. The adversarial α-regret result (Theorem 4.6) uses the explicit definition ρ := max_q min_{(x,a)∈Q(q)} min_t min_i −g_{t,i}(x,a) and α := ρ/(1+ρ); these are problem-dependent constants defined in Section 2.3, not parameters fitted to the algorithm's output, and the theorem is stated in terms of them. No step renames a known result or smuggles an ansatz via self-citation. A possible gap in the adversarial containment proof (Theorem 4.5) regarding unvisited support pairs of q⋄, where bg_{t,i}=0 rather than ≤−ρ, is a correctness/coverage issue, not an equivalence by construction; likewise the vacuity when ρ=0 is a weakness of the guarantee rather than circularity.
Axiom & Free-Parameter Ledger
axioms (6)
- domain assumption Finite loop-free episodic MDP with unknown transition function P and bandit feedback
- domain assumption Rewards in [0,1], constraint costs in [-1,1] per state-action pair, m constraints
- domain assumption In the stochastic setting, the feasible set Δ⋆ is non-empty
- domain assumption In the adversarial setting, there exists q⋄ with uniform margin ρ>0 over all episodes and all pairs in its support for the α-regret result
- standard math Hoeffding, Azuma, and union bound concentration results
- standard math Lemma C.2 (transition concentration) imported from Stradi et al. [2025d]
Cite this review
Pith. "Pith review of Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints." pith.science (2026). https://pith.science/paper/GT7CELZM
@misc{pith2026250920114,
author = {Pith},
title = {Pith review of: Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/GT7CELZM}},
note = {Machine review of arXiv:2509.20114}
}
abstract
We study \emph{online episodic Constrained Markov Decision Processes} (CMDPs) under both stochastic and adversarial constraints. We provide a novel algorithm whose guarantees greatly improve those of the state-of-the-art best-of-both-worlds algorithm introduced by Stradi et al. (2025). In the stochastic regime, \emph{i.e.}, when the constraints are sampled from fixed but unknown distributions, our method achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation without relying on Slater's condition, thereby handling settings where no strictly feasible solution exists. Moreover, we provide guarantees on the stronger notion of \emph{positive} constraint violation, which does not allow to recover from large violation in the early episodes by playing strictly safe policies. In the adversarial regime, \emph{i.e.}, when the constraints may change arbitrarily between episodes, our algorithm ensures sublinear constraint violation without Slater's condition, and achieves sublinear $\alpha$-regret with respect to the \emph{unconstrained} optimum, where $\alpha$ is a suitably defined multiplicative approximation factor. We further validate our results through synthetic experiments, showing the practical effectiveness of our algorithm.
Figures
Reference graph
Works this paper leans on
-
[1]
Lemma B.1.For anyδ∈(0,1)and for anyq∈ T t∈[T] b∆t(Pt), Algorithm 1 attains: TX t=1 bℓ⊤ t (bqt −q)≤L ln |X| 2|A| η +η|X||A|T+ ηLln L δ γ , with probability at least1−δ
We start with the following lemma. Lemma B.1.For anyδ∈(0,1)and for anyq∈ T t∈[T] b∆t(Pt), Algorithm 1 attains: TX t=1 bℓ⊤ t (bqt −q)≤L ln |X| 2|A| η +η|X||A|T+ ηLln L δ γ , with probability at least1−δ. Proof.The result follows from Lemma 12 of [Jin et al., 2020], considering a generalq∈ T t∈[T] b∆t(Pt). We conclude by showing the following performance bo...
2020
-
[7]
Aviv Rosenberg and Yishay Mansour
URLhttps://proceedings.neurips.cc/paper/2020/ file/ae95296e27d7f695f891cd26b4f37078-Paper.pdf. Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alch´ e- Buc, E. Fox, and R. Garnett, editors,Advances in Neural Information Processing Sy...
2020
-
[9]
Online learning in CMDPs: Handling stochastic and adversarial constraints
Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in CMDPs: Handling stochastic and adversarial constraints. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Proceedings of the 41st Intern...
-
[12]
The authors analyze two approaches, both providing sub- linear regret and cumulative constraint violation
deals with finite-horizon CMDPs, with stochastic losses and constraints, unknown transition function and bandit feedback. The authors analyze two approaches, both providing sub- linear regret and cumulative constraint violation. Stradi et al. [2025b] propose the first primal-dual algorithm capable of attaining sublinear positive violation in the stochasti...
2024
-
[13]
This algorithm achieves eO(T 3 4 ) regret and guarantees that the cumulative constraint violation remains below a certain threshold with a given probability
studies episodic CMDPs with stochastic losses and constraints, known transition function and bandit feedback. This algorithm achieves eO(T 3 4 ) regret and guarantees that the cumulative constraint violation remains below a certain threshold with a given probability. [Qiu et al., 2020] achieves sublinear regret and violation in episodic CMDPs with adversa...
2020
-
[14]
The first best-of-both- worlds algorithm for online learning in episodic CMDPs was proposed by Stradi et al
prove (for the easier single state setting) the impossibility of attaining both sublinear regret and constraint violation with respect to a policy that satisfies the constraints on average. The first best-of-both- worlds algorithm for online learning in episodic CMDPs was proposed by Stradi et al. [2024a], which employs a primal-dual approach providing eO...
2023
-
[16]
In the stochastic setting, Algorithm 1 guarantees with probability at least 1−16δ: Vt ≤18L|X| r 2t|A|ln 2mT|X||A| δ ∀t∈[T]
Theorem 4.4.Letδ∈(0,1). In the stochastic setting, Algorithm 1 guarantees with probability at least 1−16δ: Vt ≤18L|X| r 2t|A|ln 2mT|X||A| δ ∀t∈[T]. Proof.Define for eachi∈[m] andt∈[T] the following quantity: Vt,i := tX τ=1 ¯g⊤ i qτ + . 28 Given ani∈[m] and at∈[T] we have: Vt,i = tX τ=1 ¯g⊤ i qτ + = tX τ=1 (¯gi −bgτ−1,i +bgτ−1,i )⊤qτ + = tX τ=1 (¯gi −bgτ−1...
2020
-
[32]
URLhttps://proceedings.neurips.cc/paper/2019/file/ a0872cc5b5ca4cc25076f3d868e1bdf8-Paper.pdf
Curran Associates, Inc., 2019a. URLhttps://proceedings.neurips.cc/paper/2019/file/ a0872cc5b5ca4cc25076f3d868e1bdf8-Paper.pdf. Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,Proceedings of the 36th International Con- ference on Machine Learning...
2019
-
[2008]
Mohammad Gheshlaghi Azar, Ian Osband, and R´ emi Munos
URLhttps://proceedings.neurips.cc/paper/ 2008/file/e4a6222cdb5b34375400904f03d8e6a5-Paper.pdf. Mohammad Gheshlaghi Azar, Ian Osband, and R´ emi Munos. Minimax regret bounds for reinforcement learning. InInternational Conference on Machine Learning, pages 263–272. PMLR,
2008
-
[2009]
the algorithm receives the complete loss/reward information
and Rosenberg and Mansour [2019b] consider a full-information feedback, i.e. the algorithm receives the complete loss/reward information. Most of the first works on MDPs are set in a stochastic environment, i.e. the loss is assumed to be generated according to a certain (unknown) distribution (see Auer et al. [2008], Azar et al. [2017]). Other works, such...
2008
-
[2013]
13 Contents 1 Introduction 1 1.1 Original Contributions
URLhttps://proceedings.neurips.cc/paper_files/paper/2013/file/ 68053af2923e00204c3ca7c6a3150cf7-Paper.pdf. 13 Contents 1 Introduction 1 1.1 Original Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Preliminaries 2 2.1 Constrained Markov Decision Processes . . . . . . . . . . . . . . . . . . . . . . . . . . ...
2013
-
[2015]
Gergely Neu, Andras Antos, Andr´ as Gy¨ orgy, and Csaba Szepesv´ ari
URLhttps://proceedings.neurips.cc/ paper_files/paper/2015/file/e5a4d6bf330f23a8707bb0d6001dfbe8-Paper.pdf. Gergely Neu, Andras Antos, Andr´ as Gy¨ orgy, and Csaba Szepesv´ ari. Online markov decision processes under bandit feedback.Advances in Neural Information Processing Systems, 23,
2015
-
[2019]
Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang
URLhttp: //arxiv.org/abs/1912.13213. Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. InInternational conference on artificial intelligence and statistics, pages 2827–2835. PMLR,
Pith/arXiv arXiv 1912
-
[2020]
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour
URLhttps://arxiv.org/abs/2003.02189. Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes.Mathematics of Operations Research, 34(3):726–736,
Pith/arXiv arXiv 2003
-
[2021]
Safe reinforcement learning on autonomous vehicles
David Isele, Alireza Nakhaei, and Kikuo Fujimura. Safe reinforcement learning on autonomous vehicles. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1–6. IEEE,
2018
This paper was first reviewed by deepseek-v4-flash on August 4, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.