Research map / Bandits and online learning / RL theory and MDPs

Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints

ICML 2024 · Bandits and online learning › RL theory and MDPs · approach: Adversarial MDPs with bandit feedback

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 PDGD-OPS, a primal-dual best-of-both-worlds algorithm for episodic CMDPs with long-term stochastic or adversarial constraints and rewards, without knowing the Slater parameter rho.

Problem

Online learning in episodic constrained MDPs with long-term constraints that may be selected stochastically or adversarially, with unknown transitions and no knowledge of the Slater-like feasibility margin rho.

Approach

A primal-dual scheme where the primal player is a new UC-O-GDPS (upper-confidence online gradient descent policy search) regret minimizer for adversarial MDPs and the dual player is OGD over a shrunk dual space; the weak no-interval regret property of both players automatically bounds the dual variables, removing the need to know rho and giving best-of-both-worlds regret and violation bounds.

Key results

• PDGD-OPS achieves Õ(√T) regret and constraint violation under stochastic constraints when Slater-like Condition 2.5 holds, and Õ(T^3/4) otherwise.
• Under adversarial constraints, the algorithm achieves no-α-regret with α = ρ/(1+ρ) while keeping cumulative constraint violation Õ(ζ√T), with ζ = 20mL²/ρ².
• The algorithm does not need to know ρ and works even when ρ is arbitrarily small, unlike prior primal-dual CMDP methods.

Measured effects reported in the paper

Surprising findings

• Under stochastic constraints, the bound for adversarial rewards is better than for stochastic rewards, due to the different optimization baseline used.

Limitations

• Regret and violation guarantees hold only under Condition 2.5 (rho at least order T^-1/8); otherwise bounds degrade to Õ(T^3/4) or linear.
• Under adversarial constraints, sublinear regret and sublinear violation cannot be achieved simultaneously, so only no-α-regret with α=ρ/(1+ρ) is obtained.

Experimental setup

Metrics: regret cumulative constraint violation

Baselines: Efroni et al. 2020 Qiu et al. 2020 Castiglioni et al. 2022b Wei et al. 2023

Builds on: UC-O-REPS best-of-both-worlds constrained online learning (Balseiro et al. 2023) Lagrangian primal-dual CMDP methods

Closest papers by meaning

• Learning Adversarial MDPs with Stochastic Hard Constraints (ICML 2025 · similarity 0.95)
• Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.94)
• An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints (ICML 2025 · similarity 0.91)
• Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.91)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.90)
• Online Learning in Risk Sensitive constrained MDP (ICML 2025 · similarity 0.90)