Research map / Bandits and online learning / Online convex optimization and games
Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and 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 PDB-PS, a primal-dual policy optimization algorithm for episodic CMDPs with bandit feedback that achieves best-of-both-worlds guarantees for stochastic and adversarial constraints without knowing the Slater parameter.
Problem
Online learning in episodic constrained MDPs where rewards and constraints can be stochastic or adversarial, under bandit feedback and unknown Slater parameter, with prior best-of-both-worlds work requiring full feedback and convex occupancy-measure optimization.
Approach
A primal-dual method where the primal is policy optimization with a fixed-share update (giving no-interval regret under bandit feedback), and the dual is projected OGD; the no-interval regret of both players automatically bounds the Lagrange multipliers without knowing the Slater parameter, and a dynamic learning rate scales with the observed loss range.
Key results
- With stochastic constraints, the algorithm achieves Õ(√T) regret and constraint violation when Slater's parameter satisfies the stated condition, matching full-feedback results.
- With adversarial constraints, it attains Õ(√T) constraint violation and a Ω(ρ/(ρ+H)) fraction of the optimal reward.
- Without the Slater condition, bounds degrade to Õ(T^{3/4}) for both regret and violation in the stochastic setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use bandit-feedback primal-dual policy optimization for stochastic constraints when Condition 2.5 holds | PDB-PS · Stochastic constraints; rewards stochastic or adversarial | regret: eO(Λ√T) | Helped |
| use bandit-feedback primal-dual policy optimization for stochastic constraints when Condition 2.5 holds | PDB-PS · Stochastic constraints; rewards stochastic or adversarial | constraint violation: eO(Λ√T) | Helped |
| use bandit-feedback primal-dual policy optimization when Condition 2.5 does not hold | PDB-PS · Stochastic constraints; rewards stochastic or adversarial | regret: eO(T^{3/4}) | Helped |
| use bandit-feedback primal-dual policy optimization when Condition 2.5 does not hold | PDB-PS · Stochastic constraints; rewards stochastic or adversarial | constraint violation: eO(T^{3/4}) | Helped |
| use PDB-PS with the average-feasible baseline for adversarial constraints | PDB-PS · Adversarial constraints; Condition 2.5 holds | reward: Ω(ρ/(ρ + H) · OPTr,G) | Helped |
| use the per-episode-feasible weaker baseline for adversarial constraints | PDB-PS · Adversarial constraints; Condition 2.5 holds | regret: eO(Λ√T) | Helped |
| use the per-episode-feasible weaker baseline for adversarial constraints | PDB-PS · Adversarial constraints; Condition 2.5 does not hold | regret: eO(T^{3/4}) | Helped |
Limitations
- Guarantees with weaker baseline; the stronger baseline gives only a fraction of optimal reward in adversarial setting.
- Degrades to Õ(T^{3/4}) when Slater condition is weak or absent.
- Purely theoretical; no empirical evaluation reported.
Experimental setup
Metrics: regret constraint violation
Baselines: Stradi et al. (2024b)
Builds on: Stradi et al. (2024b) best-of-both-worlds CMDP Luo et al. (2021) policy optimization for adversarial MDPs Cesa-Bianchi et al. (2012) fixed share Jin et al. (2020) Efroni et al. (2020)
Closest papers by meaning
- Learning Adversarial MDPs with Stochastic Hard Constraints (ICML 2025 · similarity 0.95)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.94)
- An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints (ICML 2025 · similarity 0.91)
- 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.91)
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.91)
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.