Introduction
Reinforcement Learning (RL) has achieved remarkable success in simulated environments, but its application to real-world safety-critical systems—such as autonomous driving or surgical robotics—remains limited. In these domains, the standard "trial and error" approach is insufficient; agents must maximize rewards while strictly adhering to safety constraints.
Constrained Markov Decision Processes (CMDPs) provide a formal framework for this challenge. While many existing algorithms offer safety guarantees, they are predominantly model-based, requiring the agent to learn and store the entire transition physics of the environment. This is often computationally prohibitive and memory-intensive. This paper introduces Triple-QA, the first model-free RL algorithm for infinite-horizon average-reward CMDPs that provides rigorous theoretical guarantees for both efficiency and safety.
The Triple-QA Algorithm
The authors propose Triple-QA (Primal-Dual-Based, Two-Time-Scale Optimistic SARSA), which avoids the memory overhead of model-based methods by learning value functions directly. The algorithm incorporates several key mechanisms:
- Discounted Approximation: It solves the average-reward problem by approximating it with a discounted reward problem where the discount factor $\gamma$ is near 1.
- Primal-Dual Framework: Safety constraints are managed via a "virtual queue" ($Z$) that acts as a Lagrange multiplier. This queue increases when constraints are violated, effectively penalizing unsafe actions.
- Two-Time-Scale Updates: To ensure stability, reward and utility Q-functions are updated at a "fast" scale, while the safety penalty (virtual queue) is updated at a "slow" scale.
- Optimistic SARSA: Unlike standard Q-learning, Triple-QA uses a SARSA-type update with an "optimism bonus" to better handle the stochastic optimal policies common in CMDPs.
- Constraint Tightening: By solving a slightly stricter version of the safety requirement, the algorithm ensures zero cumulative violations over the long term.
Theoretical Contributions
Triple-QA represents a significant milestone in model-free RL. As shown in the comparison table below, it is the first model-free approach to achieve sublinear regret while maintaining zero constraint violations in the infinite-horizon setting.
The algorithm achieves a regret bound of $\tilde{O}(K^{5/6})$. While this is wider than the $\tilde{O}(\sqrt{K})$ typically found in model-based approaches, it proves that the agent will eventually converge to an optimal policy without ever exceeding the safety budget.
Empirical Evaluation
The algorithm was tested in a 2D Safety Grid-World (a 10x10 grid) where an agent must reach a goal while avoiding obstacles. The environment is stochastic, with a 3% chance of random movement, making safety management challenging.
In these simulations, Triple-QA successfully learned to reach the goal while keeping the average cost strictly below the threshold (0.15). In contrast, standard Optimistic Q-learning—which does not account for constraints—achieved higher rewards but failed significantly on the safety metric, consistently exceeding the allowed cost threshold.
Conclusion and Future Work
Triple-QA bridges a critical gap in RL literature by providing a provably efficient, model-free method for safe, long-term learning. While the current work focuses on tabular MDPs, it lays the groundwork for scaling these safety guarantees to deep RL. Future research aims to close the theoretical regret gap between model-free and model-based methods and to reduce the algorithm's sensitivity to hyperparameters.
Summary updated