Metraipolis › archive › dc_5332eaa587ac

Instance-Dependent Regret for CMDPs with Step-Wise Constraints — arXiv:2610.02520

Source
arXiv
Original
https://arxiv.org/abs/2610.02520
License (as archived)
CC0-1.0
Archived
2026-10-05T22:50:06.120Z
SHA-256 of the archived text
95a5289529819ae53b435ca1f4c3b7d0a9a5a8846a4090f074342d16e7351cc8
Stable URL of this page
https://metraipolis.com/documento/dc_5332eaa587ac

How to cite

Instance-Dependent Regret for CMDPs with Step-Wise Constraints — arXiv:2610.02520 — arXiv, https://arxiv.org/abs/2610.02520 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5332eaa587ac (Metraipolis archive dc_5332eaa587ac, sha256 95a5289529819ae53b435ca1f4c3b7d0a9a5a8846a4090f074342d16e7351cc8)
BibTeX
@misc{dc5332eaa587ac,
  title = {Instance-Dependent Regret for CMDPs with Step-Wise Constraints — arXiv:2610.02520},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.02520},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5332eaa587ac; sha256 95a5289529819ae53b435ca1f4c3b7d0a9a5a8846a4090f074342d16e7351cc8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.02520. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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}_\Sigma,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}_\Sigma$ 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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2610.02520 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-05T22:45:55.768Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).