Truly No-Regret Learning in Constrained MDPs
This solves a safety-critical problem for reinforcement learning practitioners by providing the first provably safe online learning method in CMDPs, though it is incremental as it builds on existing primal-dual frameworks.
The paper tackles the problem of ensuring safety during online learning in constrained Markov decision processes (CMDPs) by addressing the issue of error cancellations in primal-dual algorithms, and it proves that their proposed model-based primal-dual algorithm achieves sublinear regret without allowing such cancellations.
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.