Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Abstract

We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ over $K$ episodes, where $H$ is the horizon of a single episode, while $S$ and $A$ are the numbers of states and actions, respectively. Here, $\mathrm{Var}^{\star}$ is the maximum return variance among safe policies, $\mathbb{V}_Σ$ is the variance accumulated before the first unsafe action is encountered, and $\mathcal{C}$ captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in $K$. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 1 October 2026

  Geometric Similarity in VLM Low-Level Vision Representations

  Shao-Jun Xia, Huixin Zhang, Zhen Lei and 3 others
• arXiv preprint · 2 October 2026

  Time Series Forecasting Benchmarks Need Scenario-Grounded Stress Testing

  Yuyang Zhao, Lian Xu and Hao Xue
• arXiv preprint · 1 October 2026

  Learning Multiple Timescales for Goal-Conditioned Reinforcement Learning

  Pedro Robles Dutenhefner, Dikshant Shehmar, Wagner Meira and 1 other
• arXiv preprint · 2 October 2026

  VERSE: Verified Self-Evolving Optimizer for Agent Harnesses

  Zekai Wang, Yingqiang Ge, Zekun Wang and 6 others
• arXiv preprint · 1 October 2026

  Don't Waste the Noise: Importance-Guided Perturbation Allocation under Joint Global and Local Constraints

  Melika Shirian and Kianoosh Vadaei

All new papers in Machine Learning