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

Truly No-Regret Learning in Constrained MDPs

ICML 2024 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs · 0 citations (OpenAlex)

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.

Shows that a regularized primal-dual algorithm with optimistic exploration achieves sublinear strong regret (no error cancellations) for learning unknown tabular finite-horizon CMDPs, with O(K^0.93) bounds.

Problem

Primal-dual algorithms for CMDPs only guarantee sublinear weak regret, which allows error cancellations between constraint violations and strict satisfaction, so the online learner can remain unsafe during learning; it was open whether primal-dual methods achieve sublinear strong regret in unknown C

Approach

Adds entropy regularization to the Lagrangian (regularized primal-dual scheme with closed-form mirror-descent primal updates and a larger dual domain), proves last-iterate convergence for multiple constraints, and combines it with optimistic model-based exploration to get strong regret bounds.

Key results

• Main theorem: with tau=K^{-1/7}, eta=(H^2 I)^{-1} Xi K^{-5/7}, lambda_max=H Xi^{-1} K^{1/14}, strong regret for objective and constraints is O~(K^{0.93}), versus O~(K^{1/2}) for weak regret of vanilla primal-dual.
• Last-iterate convergence of the regularized primal-dual scheme to an eps-optimal feasible policy with k=O~(eps^{-10}) episodes given a value oracle, for arbitrary number of constraints.
• In simulation, vanilla primal-dual and dual algorithms show oscillations and linear strong regret, while the regularized algorithms achieve sublinear strong regret.

Measured effects reported in the paper

Surprising findings

• Vanilla primal-dual algorithms can achieve zero weak regret while being unsafe in every other episode, showing weak regret is uninformative about safety during learning.
• Theoretically derived hyperparameters are overly pessimistic; empirically tuned choices give much better regret.

Limitations

• Strong regret exponent 0.93 is far from the optimal K^{1/2} achieved by LP-based methods.
• Last-iterate convergence rate is slow (eps^{-10}) and depends on the Slater gap; theory-chosen parameters are pessimistic.
• Safety holds only in most episodes, not every episode, since exploration in unknown CMDPs necessarily risks violations.

Experimental setup

Datasets: randomly generated tabular CMDP (S=A=H=5, deterministic rewards, unknown transitions)

Benchmarks: randomly generated tabular CMDP simulation

Metrics: strong regret weak regret constraint violation per episode suboptimality per episode

Baselines: vanilla primal-dual (OptPrimalDual) vanilla dual algorithm (OptDual) regularized dual algorithm (own variant)

Builds on: optimistic model-based CMDP learning (OptPrimalDual, Efroni et al. 2020) regularized primal-dual last-iterate analysis (Ding et al.) mirror descent / multiplicative weights policy update

Closest papers by meaning

• Online Learning in Risk Sensitive constrained MDP (ICML 2025 · similarity 0.91)
• Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.91)
• Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.90)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.90)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)
• Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization (ICLR 2025 · similarity 0.90)