Research map / Bandits and online learning / RL theory and MDPs
Learning Adversarial MDPs with Stochastic Hard 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.
Studies online episodic CMDPs with adversarial losses, stochastic hard constraints and bandit feedback, giving three algorithms (sublinear positive violation, safe, constant violation) built on optimistic policy search with OMD and a lower bound showing Slater-parameter dependence.
Problem
Online learning in episodic constrained MDPs with adversarial losses, stochastic constraints, and bandit feedback, where constraints must be satisfied under hard (non-cancelling) criteria.
Approach
Optimistic projection of OMD iterates onto the set of occupancy measures that optimistically satisfy estimated constraints (SV-OPS); safety is obtained by randomizing with a known strictly feasible policy using pessimistic upper bounds (S-OPS); constant violation is obtained by estimating a strictly feasible policy and Slater parameter in a constant number of episodes (CV-OPS).
Key results
- SV-OPS attains regret and positive violation of order L|X|sqrt(|A|T ln(...)) with high probability, without any experiments.
- S-OPS is safe with high probability (at every episode) and attains sublinear regret with a Psi-dependent factor.
- CV-OPS attains constant positive violation (independent of T) and sublinear regret, with the number of estimation episodes bounded by a constant depending on the Slater parameter.
- Lower bound: any algorithm with o(sqrt(T)) violation suffers Omega(sqrt(T)/rho) regret on some instance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimistic constraint-satisfying occupancy measures with online updates | SV-OPS · General CMDPs, adversarial losses and stochastic constraints | cumulative positive constraints violation: V_T \leq \mathcal{O}\left( L|X|\sqrt{|A|T\ln\left(\nicefrac{T|X||A|m}{\delta}\right)}\right) | Helped |
| Use optimistic constraint-satisfying occupancy measures with online updates | SV-OPS · General CMDPs, adversarial losses and stochastic constraints | regret: R_T \leq \mathcal{O}\left( L|X|\sqrt{|A|T\ln\left(\nicefrac{T|X||A|}{\delta}\right)}\right) | Helped |
| Randomize the selected policy with a known strictly feasible policy using pessimistic cost bounds | S-OPS · CMDPs with known strictly feasible policy | safety: safe with probability at least 1-5\delta | Helped |
| Randomize the selected policy with a known strictly feasible policy using pessimistic cost bounds | S-OPS · CMDPs with known strictly feasible policy | regret: R_T \leq \mathcal{O} \left(\Psi L^3|X|\sqrt{|A|T\ln\left(\nicefrac{T|X||A|m}{\delta}\right)}\right) | Helped |
| Estimate a strictly feasible policy and its margin, then run S-OPS | CV-OPS · CMDPs with unknown strictly feasible policy | cumulative positive constraints violation: V_T \leq \mathcal{O}( \nicefrac{L}{\rho^4}(C_\mathcal{A}^P + L\sqrt{\ln\frac{1}{\delta}} + C_\mathcal{A}^D+L)^4) | Helped |
| Estimate a strictly feasible policy and its margin, then run S-OPS | CV-OPS · CMDPs with unknown strictly feasible policy | regret: R_T \leq \mathcal{O} (\Theta L^3|X|\sqrt{|A|T\ln\left(\nicefrac{T|X||A|m}{\delta}\right)}+ \nicefrac{L}{\rho^4}(C_\mathc | Helped |
| Require violation V_T = o(\sqrt{T}) | Any algorithm on the stated CMDP instances · Two CMDP instances, single state and one constraint | regret: R_T = \Omega( \frac{1}{\rho}\sqrt{T}) | Hurt |
Limitations
- Dependence on Slater parameter/violation gap is unavoidable for safe and constant-violation settings, and bounds scale with 1/rho or Psi
- Requires known strictly feasible policy for safety guarantees (S-OPS); CV-OPS relies on unknown Slater parameter estimation
- Projection step assumed efficiently solvable; no empirical evaluation
Experimental setup
Metrics: regret positive constraints violation
Builds on: online mirror descent for adversarial MDPs UOB-REPS safe bandit exploration
Closest papers by meaning
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.95)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.95)
- An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints (ICML 2025 · similarity 0.92)
- Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization (ICLR 2025 · similarity 0.91)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.90)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.90)
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.