Towards Achieving Optimal Strong Regret and Constraint Violation via Computationally Efficient Model-free RL

We study episodic constrained Markov decision processes (CMDPs) with linear function approximation, where the goal is to achieve strong regret and constraint violation guarantees without allowing error cancellations. Unlike the existing work, which focuses on either tabular CMDP or model-based reinforcement learning methods. We propose a model-free policy APMPO that achieves near-optimal $\widetilde{O}(\sqrt{K})$ strong regret and strong constraint violation with Slater's condition (or strict feasibility assumption), where $K$ is the total number of episodes. It matches the best-known rates without requiring any prior knowledge of the feasibility gap reported in prior model-based work for tabular CMDPs. Besides, APMPO achieves $\widetilde{O}(K^{\frac{3}{4}})$ strong regret and $\widetilde{O}(K^\frac{3}{4})$ strong constraint violation without Slater's condition. To the best of our knowledge, this is the first sublinear result of CMDP w.r.t. the strong metrics without Slater's condition. APMPO achieves these results by a novel and adaptive design of a violation-aware penalty and learning rates to balance the strong regret and constraint violation, which is quite different from the (regularized) primal-dual methods imposing constraints via dual penalty in the literature. The experiments show APMPO significantly outperforms the strong baselines, which justify our design and theoretical performance.

In many real-world uses of reinforcement learning, such as robotics, online platforms, and advertising, an AI system must learn to earn high rewards while also respecting safety, budget, or service constraints. Existing methods often measure performance in a way that lets failures cancel each other out: a very safe episode can cover an unsafe one, even though the unsafe episode may be still harmful. We study how to prevent this masking effect during learning. We develop APMPO, a learning algorithm that does not need to build a full model of the environment and can handle large state spaces using compact features. We prove that APMPO nearly matches the best possible learning rate when a safety margin exists, and still provides the first sublinear guarantees of this kind when such a margin is not assumed. This work brings practical reinforcement learning methods closer to reliable use in settings where repeated constraint violations cannot be averaged away.