An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints

Dabeen Lee; Honghao Wei; Jiahui Zhu; Kihyun Yu; Xin Liu

REVIEW 2 major objections 5 minor 39 references

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An optimistic mirror descent primal-dual algorithm for online constrained MDPs claims the first optimal-order regret and strong-violation bounds under anytime adversarial constraints.

desk verdict The anytime-adversarial CMDP setting is genuinely new, but the main theorem is unproven as written: the surrogate function is concave where the proof needs strong convexity. read the letter →

arxiv 2505.21841 v1 pith:AXFLYWSA submitted 2025-05-28 cs.LG cs.AI

Jiahui Zhu , Kihyun Yu , Dabeen Lee , Xin Liu , Honghao Wei This is my paper

classification cs.LGcs.AI

keywords onlineconstrainedMDPadversarialconstraintsoptimisticmirrordescentprimal-dualmethodstrongconstraintviolationregretboundsafereinforcementlearninganytime

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes OMDPD, an optimistic mirror descent primal-dual algorithm for episodic constrained MDPs where cost functions may be chosen adversarially at each episode. It claims to achieve O~(√K) regret and O~(√K) strong constraint violation simultaneously, matching the optimal order in the number of episodes K, under both stochastic and adversarial costs. These are the first such guarantees for anytime adversarial constraints, and the algorithm avoids needing Slater's condition or a known strictly safe policy. The result rests on a Lyapunov-drift surrogate objective and an optimistic mirror descent update whose per-episode regret is controlled by the cumulative variation of gradients.

What carries the argument

The engine is the surrogate objective f_k(q) = α(−r̃_kᵀ q + Φ′(λ_k)[d̃_kᵀ q]₊) − (1/2)‖q − q_k‖², with Φ(x) = exp(βx) − 1, and the dual variable λ_k updated by λ_k = λ_{k−1} + α[d̃_kᵀ q_k]₊. The exponential potential converts cumulative positive violations into an increasing penalty, and the drift-plus-penalty argument (Eq. 23) reduces regret and violation to bounding the term (Regret_alg) — the sum of f_k(q_k) − f_k(q*) over episodes. That term is controlled by optimistic mirror descent (an alternating prediction/refinement step using Bregman divergence) through Lemma 5.8, which bounds Regret_alg by the square root of the cumulative variation of consecutive gradients; Lemma 5.9 then bounds that variation by O~(√K) plus a term in Φ′(λ_K). The proof's validity depends on f_k being 1-strongly convex for the Bregman telescoping in Lemma 5.8, a property the written formula for f_k does not have because of the minus sign on the quadratic term.

What would settle it

Take the Hessian of f_k in Eq. (20) with respect to q: the term −(1/2)‖q − q_k‖² contributes −I, so the Hessian is not positive definite (in fact f_k is concave), contradicting the 1-strong convexity that Lemma 5.8 needs to telescope the Bregman divergences; a reader can verify this directly from the printed equation without running any experiment.

Watch

Extended reading notes

Core claim

Theorem 5.1 asserts that with probability at least 1−2δ, OMDPD achieves Regret(K) ≤ O~(√(N S A H³ K) + S² A H³ + √C √(S A H K) + S A H) and Violation(K) ≤ O~(√(N S A H³ K) + S² A H³ + √C √(S A H K)) for both stochastic and adversarial constraint settings, where C is a uniform bound on the Bregman divergence over the occupancy-measure polytope Q. The violation notion is 'strong': only positive per-episode constraint violations accumulate, with no cancellation between safe and unsafe episodes. If correct, this is the first O~(√K) strong-violation guarantee for online CMDPs with anytime adversarial constraints, and it holds without Slater's condition and without access to a known safe policy.

Load-bearing premise

The proof of the key regret bound (Lemma 5.8) requires the surrogate function f_k to be 1-strongly convex, but in the formula as written the quadratic term is negative, making f_k concave rather than convex; the bound only survives if that minus sign is a typo and the intended term is positive.

Editorial extensions

If this is right

If Theorem 5.1 is correct, an online safe-RL agent can face adversarially changing cost functions and still keep cumulative strong violation at O~(√K) without any prior safe policy.
The guarantees apply without Slater's condition, so they hold even when the feasible region has empty interior, which is exactly the regime an adversary can force.
With a generative model that supplies accurate reward and transition estimates, the regret bound improves to O(1) when rewards are fixed (Remark 5.2), meaning the learning cost is paid only through constraint exploration.
The algorithm achieves the same O~(√K) order in both stochastic and adversarial cost settings, so an agent does not need to know which regime it is in.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the sign in Eq. (20) is a typo and the intended quadratic term is +1/2‖q − q_k‖², the same proof structure would likely extend to other strongly convex regularizers, and the reliance on a uniform bound C would simplify; this is an editorial reading, not a claim of the paper.
The analysis suggests an unexplored middle regime: when rewards drift slowly rather than staying fixed, the gradient-variation bound in Lemma 5.9 interpolates between the O(1) and O~(√K) cases, so a problem-dependent regret of O~(√T) where T is the total variation may be achievable.
Because the algorithm only needs bandit feedback on rewards and full-information feedback on adversarial costs, it could be adapted to non-episodic settings by treating blocks of steps as pseudo-episodes; the paper does not discuss this.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The setting is genuinely new: first explicit O~(√K) regret and strong-violation bounds for episodic CMDPs under anytime adversarial constraints, without Slater's condition or a known safe policy. That is a real gap in the literature, and the paper's comparison to Efroni, Müller, Stradi, and Kitamura is fair. The estimation-error analysis in Lemma 5.10 claims a √H improvement over prior work, and the appendix gives a real proof attempt rather than a hand-wave.

The soft spots are load-bearing. Equation (20) defines f_k(q) = α(-r̃_k^T q + Φ'(λ_k)[d̃_k^T q]_+) - (1/2)||q - q_k||^2. That quadratic term is concave, so f_k is not convex, let alone 1-strongly convex. But Appendix C.1 opens Lemma 5.8 with "f_k is 1-strongly convex" and then uses the subgradient inequality for convex functions plus the strong-convexity lower bound on the Bregman divergence. Both steps are invalid for the function actually written. Since Lemma 5.8 drives Lemmas 5.9, 5.11, and 5.13, Theorem 5.1 is unproven as submitted. A sign change to +1/2||q-q_k||^2 might restore convexity, but the drift argument in Section 5.1 and Appendix C.3 would need to be reworked—this is not a typo you can fix in one line.

Two more concerns, smaller but real. Remark 5.2 promises O(1) regret with accurate estimates, but Appendix D.2 proves it only under the assumption that both reward and constraint are fixed, which is exactly what the adversarial setting denies. The adversarial benchmark in Eq. (3) also requires a single policy that satisfies all d_k constraints simultaneously; the paper never states the feasibility condition that such a policy exists, so the regret definition can be empty. Finally, the Azuma-Hoeffding application in Lemma 5.12 looks off: r̄ - r̂_{k-1} is not a martingale difference, so that bound needs a different concentration argument.

Bottom line: this paper is for people working on online constrained RL. The idea is plausible and worth repairing, but the current proof does not establish the main claims. I would send it to review rather than desk-reject, because the setting is new and the flaws are identifiable and likely fixable. The authors need to correct the strong-convexity error, state the feasibility assumption, and re-derive Lemma 5.12. As it stands, don't cite the main theorem.

Referee Report

2 major / 5 minor

Summary. This paper studies finite-horizon episodic constrained MDPs (CMDPs) with unknown transition kernels and unknown rewards/costs, covering both stochastic and anytime adversarial constraint sequences. It proposes the OMDPD algorithm, which combines optimistic (UCB-style) model estimates, an exponential Lyapunov function Φ(λ) = exp(βλ) - 1 over a dual variable that accumulates positive constraint violations, and an optimistic online mirror descent (OMD) update over occupancy measures, with learning rates tuned by the cumulative gradient variation. Theorem 5.1 claims that with probability at least 1 - 2δ, OMDPD achieves regret Õ(√(NSAH³K) + S²AH³ + √C√(SAHK) + SAH) and strong constraint violation Õ(√(NSAH³K) + S²AH³ + √C√(SAHK)) for both settings, without Slater's condition or a known safe policy; Remark 5.2 claims an O(1) regret bound when a generative model provides accurate reward/transition estimates and the reward is fixed, even if costs are adversarial. The proof is modular: Lemma 5.8 bounds the surrogate 'algorithm regret' by the cumulative gradient variation, Lemmas 5.9, 5.11, and 5.13 convert this into the regret/violation bounds, and Lemma 5.10 bounds estimation errors; a short simulation with K = 3000 episodes illustrates sublinear cumulative violation.

Significance. If Theorem 5.1 were correct, the paper would be a meaningful advance: it would give the first Õ(√K) strong (non-cancelling) violation guarantee for online CMDPs under anytime adversarial constraints, unify the stochastic and adversarial settings, and remove Slater's condition and the known-safe-policy assumption; the modular lemma structure, the explicit constants, and the proof roadmap in Figure 1 are assets, and the estimation-error machinery in Appendix C.2 follows established UCB techniques. The O(1) generative-model claim would also be notable. However, the central proof is not valid as submitted: the proof of Lemma 5.8 relies on a false convexity assertion (Major Comment 1), and the proof of the O(1) claim contradicts the claim itself (Major Comment 2). Because the load-bearing step of the main theorem fails, the advertised guarantees are not established by this manuscript, so the significance is conditional on a substantially corrected analysis.

major comments (2)

[Eq. (20); Algorithm 1; Appendix C.1 (Lemma 5.8); Appendix C.3] The proof of Lemma 5.8 asserts 'we know f_k(q) is 1-strong convex' and then uses the linearization f_k(q_k) - f_k(q*) ≤ ⟨∇f_k(q_k), q_k - q*⟩. This is false for the function actually defined in Eq. (20): wherever [d̃_k^T q]_+ is differentiable, the Hessian of f_k is -I, so f_k is concave rather than convex. The claimed inequality fails even for a feasible q*: take α = Φ'(λ_k) = 1, r̃_k = 0, d̃_k = 1, q_k = 1, q* = 0 (so d̃_k^T q* = 0, i.e., q* satisfies the feasibility condition of Lemma 5.7); then f_k(q_k) - f_k(q*) = 1 - (-1/2) = 3/2, while ⟨∇f_k(q_k), q_k - q*⟩ = 1, so the inequality 3/2 ≤ 1 is violated. Since Lemma 5.8 is the engine for Lemmas 5.9, 5.11, and 5.13, Theorem 5.1 is not established as written. This is not a typo-level sign issue: Appendix C.3 deliberately uses the same minus sign in deriving Eq. (23) via f_k(q*) = -α r̃_k^T q* - (1/2)||q* - q_k||², and flipping the sign would introduce an additional (1/2)Σ_k ||q* - q_k||² term on the right-hand side of Eq. (23), which is only bounded by O(SAH·K) and would destroy the sublinear bound. A correct analysis of Lemma 5.8 for the actual non-convex surrogate is needed and is not supplied.
[Remark 5.2; Appendix D.2] The claimed O(1) regret bound for a generative model with fixed reward and adversarial costs is not supported by its proof. Appendix D.2 begins by fixing both reward and constraint ('If we fix the reward and constraint, where r̃_k = r̃_{k-1}, d̃_k = d̃_{k-1}'), and the subsequent gradient-variation bound relies on both sequences being constant. In the adversarial-constraint setting claimed in Remark 5.2 and in the contribution bullet of Section 1 ('cost function is also not known and can be adversarial'), d̃_k = d_k is time-varying and chosen adversarially, so the gradient differences Φ'(λ_k)d_k - Φ'(λ_{k-1})d_{k-1} need not vanish and the O(1) conclusion does not follow. The claim and its proof must be aligned: either the claim should be restricted to fixed or stochastic constraints, or a separate argument for adversarially varying d_k must be provided.

minor comments (5)

[Lemma 5.12] The statement of Lemma 5.12 in Section 5.4 gives SAH√((K-1)/2 ln(2/δ)) + SAH, the statement in Appendix C.5 gives SAH√(K/2 ln(2/δ)), and the proof concludes SAH√((K-1)/2 ln(2/δ)) + SAH; these versions should be reconciled.
[Theorem 5.1; Lemma 5.10; Lemma E.6] The bounds contain the parameter N (e.g., Õ(√(NSAH³K))) which is never defined in the paper; the main-rate claims are uninterpretable until N is defined or replaced by an explicit expression in S, A, H, and log factors.
[Abstract; Section 1] The abstract and the contribution list describe the O(√K) rate as 'optimal,' but the manuscript states no matching lower bound for the CMDP model considered; the optimality claim should cite a lower bound or be stated with appropriate qualification.
[Section 6] The simulation section asserts qualitative agreement with the O(√K) violation growth from a single set of cumulative-violation curves with no error bars, no multiple seeds, and no baseline comparison, so the claimed agreement is not quantitatively supported.
[Throughout] There are several typos and notation slips, including 'in the beverage sense' (Section 1), 'forbidding algorithms' (contribution bullet, Section 1), and a switch from cost notation d to c in Section 6; these should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret/violation bounds are derived in-paper from OMD, concentration, and drift arguments; the only overlapping-author citations are for standard tools and are not load-bearing.

full rationale

Walking the derivation chain of Theorem 5.1, all load-bearing inequalities are proved in the paper from the optimistic OMD update, the exponential-potential drift argument, and external concentration lemmas (Lemmas 5.6, 5.10, E.2, E.6). The regret/violation decomposition in Eqs. (24)-(25) separates estimation error from optimization error, and each term is bounded by independent arguments rather than by reinserting the claim. The parameters α, β, η_k are explicit analytic choices, and C is a problem-defined diameter; no parameter is fitted to the regret or violation quantity, so there is no fitted-input-called-prediction step. The citations to overlapping-author work (Guo et al. 2022 for the exponential-potential surrogate; Wei et al. 2020 for entropy smoothing) are for standard techniques and are not used to import the main theorem; the drift bound and gradient-variation bound are proved in Appendices C.1-C.6. The possible sign error in Eq. (20), where the term -1/2||q-q_k||^2 is concave while Lemma 5.8 asserts 1-strong convexity, is a mathematical correctness defect and not a circularity: it does not make any bound identical to an input by construction. Appendix A's admission that Lekeufack & Jordan (2024) attain comparable bounds is a novelty/positioning concern, not a circular reduction. Hence no circular step is present.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or model entities. The ledger instead records three analytic hyperparameters and four unstated or background assumptions; the feasibility of q* and the convexity of f_k are the ones that most affect the validity of the main theorem.

free parameters (3)

alpha = 1/(2(1+sqrt(L_delta)) S A H)
Dual update step size chosen in Theorem 5.1 to cancel factors in Lemma 5.9; analytic, not fitted to data.
beta = S A H / (8 sqrt(C) sqrt(6 S A H K))
Lyapunov exponent; chosen small enough that the exponential drift term vanishes in the regret bound and to keep the denominator in Lemma 5.13 positive. It depends on K, so it must be fixed with knowledge of the horizon.
eta_k = sqrt(C) * min{1 / sqrt(sum_{i<k}||grad_i - grad_{i-1}||^2) + ... , 1}
Adaptive OMD learning rate based on cumulative gradient variation; analytic, not a fitted parameter.

assumptions (4)

standard math The CMDP is equivalent to an LP over occupancy measures, and any occupancy measure can be converted to a policy via Eq. (11).
Invoked in Eq. (8)-(10) and throughout; standard result (Altman 1999), not proved.
domain assumption In the adversarial cost setting, there exists a policy q* satisfying d_k^T q* <= 0 for every episode k simultaneously.
Eq. (3) defines q* as the solution to the adversarial problem. If the adversary makes constraints mutually inconsistent, q* does not exist. The paper never states this feasibility condition.
domain assumption The Bregman divergence D is bounded above by C over the feasible occupancy set Q.
C = sup D(q1,q2) is used throughout Lemma 5.8 and Theorem 5.1. For KL divergence the bound requires a smoothing trick mentioned in Remark 5.3; the paper does not provide the smoothing construction.
ad hoc to paper The surrogate function f_k in Eq. (20) is 1-strongly convex.
Assumed in Appendix C.1 to run the optimistic OMD regret argument, but the printed definition has a negative quadratic term, making it concave. This is a red flag as much as an axiom.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints." pith.science (2026). https://pith.science/paper/AXFLYWSA

@misc{pith2026250521841,
  author       = {Pith},
  title        = {Pith review of: An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AXFLYWSA}},
  note         = {Machine review of arXiv:2505.21841}
}

read the original abstract

Online safe reinforcement learning (RL) plays a key role in dynamic environments, with applications in autonomous driving, robotics, and cybersecurity. The objective is to learn optimal policies that maximize rewards while satisfying safety constraints modeled by constrained Markov decision processes (CMDPs). Existing methods achieve sublinear regret under stochastic constraints but often fail in adversarial settings, where constraints are unknown, time-varying, and potentially adversarially designed. In this paper, we propose the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, the first to address online CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret O(sqrt(K)) and strong constraint violation O(sqrt(K)) without relying on Slater's condition or the existence of a strictly known safe policy. We further show that access to accurate estimates of rewards and transitions can further improve these bounds. Our results offer practical guarantees for safe decision-making in adversarial environments.

Figures

Figures reproduced from arXiv: 2505.21841 by the authors.

**Figure 1.** Proof Roadmap of the Theorem 5.1 1, consider: ÿ K k“1 ” V π ˚ pr, p ¯ q ´ V πk pr˜k, p˜kq ı “ ÿ K k“1 “ Err¯ Jq ˚ s ´ Err˜ J k qks ‰ “ ÿ K k“1 “ Err¯ Jq ˚ s ´ Err˜ J k q ˚ s ‰ looooooooooooooomooooooooooooooon Term 1 ` ÿ K k“1 “ Err˜ J k q ˚ s ´ Err˜ J k qks ‰ looooooooooooooomooooooooooooooon Term 2 . (26) Notably, Term 2 corresponds to the violation-regret relationship in Eq. (23), providing a critical link to ou… view at source ↗

**Figure 2.** Cumulative Violation over Learning Episodes 7. Conclusion In this work, we addressed the challenge of online safe reinforcement learning in dynamic environments with adversarial constraints by proposing the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm. Our approach is the first to provide optimal guarantees in terms of both regret and strong constraint violation under anytime adversarial cost functions,… view at source ↗

**Figure 3.** Proof Roadmap of Theorem 5.1 D.1.1. REGRET BOUND PROOF Recall the definition of Regret: RegretpKq “ ÿ K k“1 ” V π ˚ pr, p ¯ q ´ V πk pr, p ¯ q ı “ ÿ K k“1 rV πk pr˜k, p˜kq ´ V πk pr, p ¯ qs loooooooooooooooooomoooooooooooooooooon Estimation Error ` ÿ K k“1 ” V π ˚ pr, p ¯ q ´ V πk pr˜k, p˜kq ı loooooooooooooooooomoooooooooooooooooon Optimization Error We can bound the “Estimation Error” term by using Lemma 5.10. Now… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 31 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

Constrained policy optimization

Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In Int. Conf. Machine Learning (ICML), volume 70, pp.\ 22--31. JMLR, 2017

work page 2017
[3]

Constrained Markov decision processes, volume 7

Altman, E. Constrained Markov decision processes, volume 7. CRC Press, 1999

work page 1999
[4]

Near-optimal regret bounds for reinforcement learning

Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. NeurIPS, 21, 2008

work page 2008
[5]

G., Osband, I., and Munos, R

Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International conference on machine learning, pp.\ 263--272. PMLR, 2017

2017
[6]

S., Agarwal, M., Koppel, A., and Aggarwal, V

Bai, Q., Bedi, A. S., Agarwal, M., Koppel, A., and Aggarwal, V. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In AAAI Conf. Artificial Intelligence, volume 36, pp.\ 3682--3689, 2022

work page 2022
[7]

DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning

Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F. Safe exploration for constrained reinforcement learning with provable guarantees. arXiv preprint arXiv:2112.00885, 2021

work page Pith review arXiv 2021
[8]

Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case

Chen, L. and Luo, H. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case, 2021. URL https://arxiv.org/abs/2102.05284

work page Pith review arXiv 2021

Show all 39 references

[9]

Learning infinite-horizon average-reward markov decision process with constraints

Chen, L., Jain, R., and Luo, H. Learning infinite-horizon average-reward markov decision process with constraints. In Int. Conf. Machine Learning (ICML), pp.\ 3246--3270. PMLR, 2022

2022
[10]

Risk-constrained reinforcement learning with percentile risk criteria

Chow, Y., Ghavamzadeh, M., Janson, L., and Pavone, M. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18 0 (1): 0 6070--6120, 2017

2017
[11]

Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning

Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017

2017
[12]

Provably efficient safe exploration via primal-dual policy optimization

Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In Int. Conf. Artificial Intelligence and Statistics (AISTATS), volume 130, pp.\ 3304--3312. PMLR, 2021

2021
[13]

and Lavaei, J

Ding, Y. and Lavaei, J. Provably efficient primal-dual reinforcement learning for cmdps with non-stationary objectives and constraints. arXiv preprint arXiv:2201.11965, 2022

2022 arXiv
[14]

Exploration-exploitation in constrained MDP s

Efroni, Y., Mannor, S., and Pirotta, M. Exploration-exploitation in constrained MDP s. arXiv preprint arXiv:2003.02189, 2020

2003 arXiv
[15]

E., Genalti, G., Castiglioni, M., Marchesi, A., and Gatti, N

Germano, J., Stradi, F. E., Genalti, G., Castiglioni, M., Marchesi, A., and Gatti, N. A best-of-both-worlds algorithm for constrained mdps with long-term constraints. arXiv preprint arXiv:2304.14326, 2023

2023 arXiv
[16]

Provably efficient model-free constrained rl with linear function approximation

Ghosh, A., Zhou, X., and Shroff, N. Provably efficient model-free constrained rl with linear function approximation. In NeurIPS, 2022

2022
[17]

Online convex optimization with hard constraints: Towards the best of two worlds and beyond

Guo, H., Liu, X., Wei, H., and Ying, L. Online convex optimization with hard constraints: Towards the best of two worlds and beyond. In Advances Neural Information Processing Systems (NeurIPS), 2022

2022
[18]

Safe reinforcement learning on autonomous vehicles

Isele, D., Nakhaei, A., and Fujimura, K. Safe reinforcement learning on autonomous vehicles. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.\ 1--6. IEEE, 2018

2018
[19]

Learning adversarial markov decision processes with bandit feedback and unknown transition

Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp.\ 4860--4869. PMLR, 2020

2020
[20]

Asymptotically optimal information-directed sampling

Kirschner, J., Lattimore, T., Vernade, C., and Szepesvári, C. Asymptotically optimal information-directed sampling. Arxiv preprint arXiv:2011.05944, 2021

2011 arXiv
[21]

A policy gradient primal-dual algorithm for constrained mdps with uniform pac guarantees

Kitamura, T., Kozuno, T., Kato, M., Ichihara, Y., Nishimori, S., Sannai, A., Sonoda, S., Kumagai, W., and Matsuo, Y. A policy gradient primal-dual algorithm for constrained mdps with uniform pac guarantees. arXiv preprint arXiv:2401.17780, 2024

2024 arXiv
[22]

and Jordan, M

Lekeufack, J. and Jordan, M. I. An optimistic algorithm for online convex optimization with adversarial constraints. arXiv preprint arXiv:2412.08060, 2024

2024 arXiv
[23]

Learning policies with zero or bounded constraint violation for constrained MDPs

Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero or bounded constraint violation for constrained MDPs . In Advances Neural Information Processing Systems (NeurIPS), volume 34, 2021 a

2021
[24]

Learning policies with zero or bounded constraint violation for constrained mdps

Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34: 0 17183--17193, 2021 b

2021
[25]

Policy optimization in adversarial mdps: Improved exploration via dilated bonuses

Luo, H., Wei, C.-Y., and Lee, C.-W. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34: 0 22931--22942, 2021

2021
[26]

Cancellation-free regret bounds for lagrangian approaches in constrained markov decision processes

M \"u ller, A., Alatur, P., Ramponi, G., and He, N. Cancellation-free regret bounds for lagrangian approaches in constrained markov decision processes. arXiv preprint arXiv:2306.07001, 2023

2023 arXiv
[27]

Truly no-regret learning in constrained mdps

M \"u ller, A., Alatur, P., Cevher, V., Ramponi, G., and He, N. Truly no-regret learning in constrained mdps. arXiv preprint arXiv:2402.15776, 2024

2024 arXiv
[28]

Neely, M. J. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3 0 (1): 0 1--211, 2010

2010
[29]

Upper confidence primal-dual reinforcement learning for CMDP with adversarial loss

Qiu, S., Wei, X., Yang, Z., Ye, J., and Wang, Z. Upper confidence primal-dual reinforcement learning for CMDP with adversarial loss. In Advances Neural Information Processing Systems (NeurIPS), volume 33, pp.\ 15277--15287. Curran Associates, Inc., 2020

2020
[30]

and Sridharan, K

Rakhlin, S. and Sridharan, K. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013

2013
[31]

Singh, R., Gupta, A., and Shroff, N. B. Learning in markov decision processes under constraints. arXiv preprint arXiv:2002.12435, 2020

2002 arXiv
[32]

and Vaze, R

Sinha, A. and Vaze, R. Optimal algorithms for online convex optimization with adversarial constraints, 2024. URL https://arxiv.org/abs/2310.18955

2024 arXiv
[34]

E., Castiglioni, M., Marchesi, A., and Gatti, N

Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Learning adversarial mdps with stochastic hard constraints. arXiv preprint arXiv:2403.03672, 2024 b

2024 arXiv
[35]

E., Castiglioni, M., Marchesi, A., and Gatti, N

Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Optimal strong regret and violation in constrained mdps via policy optimization. arXiv preprint arXiv:2410.02275, 2024 c

2024 arXiv
[36]

Triple-Q: a model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation

Wei, H., Liu, X., and Ying, L. Triple-Q: a model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2022 a

2022
[37]

A provably-efficient model-free algorithm for infinite-horizon average-reward constrained markov decision processes

Wei, H., Liu, X., and Ying, L. A provably-efficient model-free algorithm for infinite-horizon average-reward constrained markov decision processes. In AAAI Conf. Artificial Intelligence, February 2022 b

2022
[38]

Provably efficient model-free algorithms for non-stationary CMDP s

Wei, H., Ghosh, A., Shroff, N., Ying, L., and Zhou, X. Provably efficient model-free algorithms for non-stationary CMDP s. In Int. Conf. Artificial Intelligence and Statistics (AISTATS), pp.\ 6527--6570. PMLR, 2023

2023
[39]

Wei, X., Yu, H., and Neely, M. J. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4 0 (2): 0 1--36, 2020

2020
[40]

and Ugot, O.-A

Yinka-Banjo, C. and Ugot, O.-A. A review of generative adversarial networks and its application in cybersecurity. Artificial Intelligence Review, 53: 0 1721--1736, 2020

2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

Constrained policy optimization

Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In Int. Conf. Machine Learning (ICML), volume 70, pp.\ 22--31. JMLR, 2017

work page 2017

[3] [3]

Constrained Markov decision processes, volume 7

Altman, E. Constrained Markov decision processes, volume 7. CRC Press, 1999

work page 1999

[4] [4]

Near-optimal regret bounds for reinforcement learning

Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. NeurIPS, 21, 2008

work page 2008

[5] [5]

G., Osband, I., and Munos, R

Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International conference on machine learning, pp.\ 263--272. PMLR, 2017

2017

[6] [6]

S., Agarwal, M., Koppel, A., and Aggarwal, V

Bai, Q., Bedi, A. S., Agarwal, M., Koppel, A., and Aggarwal, V. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In AAAI Conf. Artificial Intelligence, volume 36, pp.\ 3682--3689, 2022

work page 2022

[7] [7]

DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning

Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F. Safe exploration for constrained reinforcement learning with provable guarantees. arXiv preprint arXiv:2112.00885, 2021

work page Pith review arXiv 2021

[8] [8]

Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case

Chen, L. and Luo, H. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case, 2021. URL https://arxiv.org/abs/2102.05284

work page Pith review arXiv 2021