Research map / Bandits and online learning / RL theory and MDPs
An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes OMDPD, an optimistic online mirror descent primal-dual algorithm for episodic CMDPs with anytime adversarial constraints, claiming O~(sqrt K) regret and strong (no-cancellation) constraint violation without Slater's condition or a known safe policy.
Problem
Online safe RL in unknown episodic CMDPs where cost constraints may be adversarial and time-varying; prior work gives sublinear regret/violation only for stochastic costs or with weak (cancellation-permitting) violation notions and often requires Slater's condition.
Approach
Combines optimistic transition/reward/cost estimates (UCB-type confidence set over occupancy measures) with optimistic online mirror descent on a surrogate objective that uses an exponential Lyapunov potential on a dual variable tracking positive constraint violations, so that cumulative positive violations are controlled without cancellation.
Key results
- Theorem claims regret and strong violation of O~(sqrt K) in both stochastic and adversarial cost settings, without Slater's condition or known safe policy.
- With a generative model/perfect simulator and fixed known reward, regret bound claimed to improve to O(1).
- Simulation on a synthetic CMDP with K=3000 shows cumulative violation curves consistent with sublinear O(sqrt K) growth; no baseline comparison reported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use OMDPD for online CMDPs with stochastic costs | Online CMDP · Stochastic costs | regret | Helped |
| use OMDPD for online CMDPs with stochastic costs | Online CMDP · Stochastic costs | strong constraint violation | Helped |
| use OMDPD for online CMDPs with adversarial costs | Online CMDP · Adversarial costs | regret | Helped |
| use OMDPD for online CMDPs with adversarial costs | Online CMDP · Adversarial costs | strong constraint violation | Helped |
| use accurate estimates of rewards and transitions | OMDPD · CMDP with generative model or perfect simulator and fixed reward | regret: replaced by a constant; \mathcal{O}(1) | Helped |
Surprising findings
- Claims O(1) regret when reward is fixed and accurately estimated, which is stronger than the sqrt(K) rate in the general case.
Limitations
- Regret and violation bounds carry dependence on S^2 A H^3 and on a constant C that requires smoothing when KL divergence is used.
- Simulation is a small synthetic tabular environment with no baseline comparison.
- Theoretical analysis in the adversarial setting relies on full cost revelation after each episode, while reward remains bandit feedback.
Experimental setup
Datasets: synthetic finite-horizon CMDP (5 states, 3 actions, horizon 5)
Benchmarks: synthetic tabular CMDP simulation (K=3000)
Metrics: cumulative constraint violation regret (theoretical)
Baselines: CMDP primal-dual policy optimization (CPD-PO) augmented Lagrangian safe RL method optimistic primal-dual CMDP methods with last-iterate convergence
Builds on: optimistic online mirror descent drift-plus-penalty framework occupancy-measure LP formulation of CMDPs
Closest papers by meaning
- Learning Adversarial MDPs with Stochastic Hard Constraints (ICML 2025 · similarity 0.92)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.91)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.91)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.91)
- Truly No-Regret Learning in Constrained MDPs (ICML 2024 · similarity 0.90)
- Online Learning in Risk Sensitive constrained MDP (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.