paper-with-me

홈 › Papers

Truly No-Regret Learning in Constrained MDPs

2024-02-24 · Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, Niao He

Constrained Markov decision processes (CMDPs) are a common way to model safety constraints in reinforcement learning. State-of-the-art methods for efficiently solving CMDPs are based on primal-dual algorithms. For these algorithms, all currently known regret bounds allow for error cancellations -- one can compensate for a constraint violation in one round with a strict constraint satisfaction in another. This makes the online learning process unsafe since it only guarantees safety for the final (mixture) policy but not during learning. As Efroni et al. (2020) pointed out, it is an open question whether primal-dual algorithms can provably achieve sublinear regret if we do not allow error cancellations. In this paper, we give the first affirmative answer. We first generalize a result on last-iterate convergence of regularized primal-dual schemes to CMDPs with multiple constraints. Building upon this insight, we propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.

📄 PDF Abstract BibTeX arXiv:2402.15776

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Regret Analysis in Deterministic Reinforcement Learning

2021-06-27 · Damianos Tranos, Alexandre Proutiere

We consider Markov Decision Processes (MDPs) with deterministic transitions and study the problem of regret minimization, which is central to the analysis and design of optimal learning algorithms. We present logarithmic…

reinforcement-learningReinforcement LearningReinforcement Learning (RL)

Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm

2024-02-03 · Qinbo Bai, Washim Uddin Mondal, Vaneet Aggarwal

This paper explores the realm of infinite horizon average reward Constrained Markov Decision Processes (CMDPs). To the best of our knowledge, this work is the first to delve into the regret and constraint violation analy…

Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization

2026-02-08 · Anirudh Satheesh, Vaneet Aggarwal arxiv

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the unichain assumption and general policy parameterizations. Existing regret analyses for constrained reinforcement learning l…

Reinforcement Learning

Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization

2024-10-03 · Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti

We study online learning in \emph{constrained MDPs} (CMDPs), focusing on the goal of attaining sublinear strong regret and strong cumulative constraint violation. Differently from their standard (weak) counterparts, thes…

Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret

2026-05-12 · Kihyun Yu, Beomhan Baek, Dabeen Lee arxiv

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Our contributions are twofold. First, we establish strong duality for weakly communicating…