A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes

Honghao Wei, Xin Liu, Lei Ying

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:

  1. Discounted Approximation: It solves the average-reward problem by approximating it with a discounted reward problem where the discount factor $\gamma$ is near 1.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Comparison of Triple-QA against existing model-based and known-model algorithms.

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.

Average reward and average cost of Triple-QA (Ours) compared to Optimistic Q-learning.

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

Abstract

This paper presents a model-free reinforcement learning (RL) algorithm for infinite-horizon average-reward Constrained Markov Decision Processes (CMDPs). Considering a learning horizon K, which is sufficiently large, the proposed algorithm achieves sublinear regret and zero constraint violation. The bounds depend on the number of states S, the number of actions A, and two constants which are independent of the learning horizon K.
BibTeX
@inproceedings{wei2022provably,
  author = {Honghao Wei and Xin Liu and Lei Ying},
  title = {{A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20302},
}
Figure