Metraipolis › archive › dc_81bb84ba13e6

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation — arXiv:2609.39093

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.39093
License (as archived)
CC0-1.0
Archived
2026-10-07T13:45:49.342Z
SHA-256 of the archived text
d10cd367194b80a5a712c0c2263c6a1233c19eace6dbcc4caf1e88834abf2397
Stable URL of this page
https://metraipolis.com/documento/dc_81bb84ba13e6

How to cite

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation — arXiv:2609.39093 — arXiv (en), https://arxiv.org/abs/2609.39093 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_81bb84ba13e6 (Metraipolis archive dc_81bb84ba13e6, sha256 d10cd367194b80a5a712c0c2263c6a1233c19eace6dbcc4caf1e88834abf2397)
BibTeX
@misc{dc81bb84ba13e6,
  title = {Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation — arXiv:2609.39093},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39093},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_81bb84ba13e6; sha256 d10cd367194b80a5a712c0c2263c6a1233c19eace6dbcc4caf1e88834abf2397},
  year = {2026}
}

Archived text

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

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and cumulative constraint violation with high probability in the tabular setting. The $\sqrt{T}$ dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in $T$.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.39093 — 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-07T13:18:10.319Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).