A Survey of Safe Reinforcement Learning and Constrained MDPs: A Technical Survey on Single-Agent and Multi-Agent Safety

1. Problem Definition

The paper addresses the critical challenge of deploying Reinforcement Learning (RL) agents in safety-critical real-world applications (e.g., autonomous driving, healthcare, robotics, power grids). Standard RL optimizes for cumulative reward but often ignores safety constraints, leading to catastrophic failures during training or deployment.

The core problem is formalized as Safe Reinforcement Learning (SafeRL): maximizing performance (cumulative reward) while strictly satisfying safety constraints during both the learning process and the final deployment. The paper focuses primarily on the Constrained Markov Decision Process (CMDP) framework, where safety is modeled as constraints on expected cumulative costs (or other risk measures) rather than just reward maximization. It also extends this to Multi-Agent Safe RL (SafeMARL), where multiple agents must learn and interact while adhering to individual or global safety constraints.

2. Methodology and Theoretical Foundations

The survey provides a rigorous mathematical overview of SafeRL, structured around the CMDP framework and its extensions.

A. Theoretical Foundations (CMDPs)

• Formulation: A CMDP is defined as an MDP tuple $(S, A, P, r, \{c^{(i)}\}, \gamma)$ where $c^{(i)}$ are cost functions. The objective is to maximize $J(\pi)$ subject to $J_c^{(i)}(\pi) \leq d_i$.
• Constraint Types: The paper categorizes safety specifications into:
  • Expected Cumulative Costs: The standard CMDP formulation (most common).
  • Instantaneous Constraints: Hard limits at every time step (e.g., torque limits, collision avoidance).
  • Probability of Failure: Constraints on the probability of entering a failure state (e.g., $Pr[\text{crash}] \leq \delta$).
  • Risk Measures: Constraints on higher-order statistics like Variance or Conditional Value-at-Risk (CVaR).
  • Temporal Logic: Safety defined via Linear Temporal Logic (LTL) formulas.
• Optimization Approaches:
  • Lagrangian Duality: Transforming the constrained problem into an unconstrained one using Lagrange multipliers ($\lambda$). The dual function is minimized to find optimal multipliers, while the primal (policy) is maximized.
  • Linear Programming (LP): For finite state spaces, CMDPs can be solved exactly via LP using occupancy measures.
  • Theoretical Guarantees: The paper cites Altman [1999] proving the existence of stationary optimal policies and strong duality under regularity conditions. It also reviews performance bounds (Achiam et al., 2017) that justify trust-region methods.

B. State-of-the-Art Algorithms (Single-Agent)

The survey classifies current methods into four main categories:

1. Lagrangian-based Policy Optimization:
   • Lagrangian Actor-Critic: Updates policy and Lagrange multipliers simultaneously (e.g., Tessler et al., 2019). Simple but may violate constraints during training.
   • Constrained Policy Optimization (CPO): A landmark trust-region method (Achiam et al., 2017) that solves a constrained subproblem at each step to guarantee near-constraint satisfaction.
   • Projected CPO (PCPO): Projects policy updates onto the feasible set to ensure safety.
2. Safety Shields and Action Correction:
   • External layers (e.g., Safety Layers, QP-based filters) that override unsafe actions proposed by the RL agent.
   • Formal Shielding: Uses model checking and temporal logic to pre-compute safe action sets.
3. Risk-Sensitive and Distributional Methods:
   • Optimizing for risk measures (e.g., CVaR) directly rather than using hard constraints.
   • Distributional RL to model the full return distribution and control tail risks.
4. Safe Multi-Agent RL (SafeMARL):
   • Centralized: Treating the multi-agent system as a single joint agent (e.g., MACPO).
   • Decentralized: Agents optimize local objectives with limited communication (e.g., $\kappa$-hop neighborhoods) to approximate global safety.
   • Game-Theoretic: Seeking constrained Nash equilibria in competitive settings.

3. Key Contributions

1. Comprehensive Taxonomy: The paper provides a structured taxonomy of SafeRL methods, distinguishing between single-agent and multi-agent approaches, and categorizing algorithms by their underlying mechanism (Lagrangian, Shielding, Risk-sensitive).
2. Mathematical Rigor: It offers a detailed derivation of CMDP theory, including Lagrangian duality, linear programming formulations, and policy gradient bounds, serving as a technical reference for researchers.
3. SafeMARL Focus: Unlike previous surveys that focused heavily on single-agent RL, this paper dedicates significant attention to the emerging field of SafeMARL, analyzing challenges in cooperative, competitive, and decentralized settings.
4. Identification of Open Problems: The authors propose five specific open research problems to guide future work:
   • P1: Zero-Violation Safe Exploration: Guaranteeing no constraint violations during the entire training process (not just asymptotically).
   • P2: Safety Under Partial Observability: Handling safety in POMDPs where the true state is unknown.
   • P3: Decentralized SafeMARL: Achieving global safety without a central controller or full state observability.
   • P4: Competitive SafeMARL: Finding safe equilibria (e.g., constrained Nash) in non-cooperative, general-sum games.
   • P5: Non-Stationary Multi-Agent Safety: Ensuring safety when the environment or agent population changes over time.
5. Resource Compilation: The paper includes a curated list of open-source libraries (e.g., OmniSafe, SafePO) and benchmark environments (e.g., Safety Gymnasium, SMARTS) to facilitate reproducibility.

4. Results and Findings

• Single-Agent Maturity: The field of single-agent SafeRL is relatively mature, with algorithms like CPO and Lagrangian methods providing strong theoretical guarantees and empirical success in benchmarks like Safety Gym.
• Multi-Agent Challenges: SafeMARL is identified as a nascent field. While centralized approaches (like MACPO) show promise, scalable decentralized solutions and robust methods for competitive settings remain largely unsolved.
• Trade-offs: The survey highlights a fundamental trade-off between safety guarantees and sample efficiency. Methods with strong theoretical guarantees (like CPO) are often computationally expensive, while simpler penalty-based methods are efficient but may violate constraints during training.
• Constraint Types Matter: The choice of constraint formulation (instantaneous vs. cumulative, risk-sensitive vs. expected) significantly impacts algorithm design and applicability to specific domains (e.g., robotics requires instantaneous constraints, while finance may prefer CVaR).

5. Significance

This survey is significant for several reasons:

• Unification: It bridges the gap between theoretical control theory (CMDPs) and modern deep RL, providing a unified language for safety.
• Roadmap for Deployment: By identifying open problems like "Zero-Violation" learning and "Decentralized Safety," it outlines the path required to move SafeRL from simulation to real-world deployment in high-stakes domains.
• Community Resource: The compilation of libraries and benchmarks serves as a vital toolkit for researchers to compare algorithms and reproduce results, accelerating progress in the field.
• Future Direction: The proposed research problems (P1–P5) set a clear agenda for the next generation of SafeRL research, emphasizing the need for robustness in partial observability, decentralization, and dynamic environments.

In conclusion, the paper establishes that while SafeRL has made significant strides, particularly in single-agent settings, the transition to complex, multi-agent, and real-world scenarios requires solving fundamental challenges in exploration, decentralization, and equilibrium computation.