Safe Reinforcement Learning in Constrained Markov Decision Processes

Akifumi Wachi, Yanan Sui

Introduction

Standard Reinforcement Learning (RL) agents learn by trial and error. In real-world, safety-critical applications—like a Mars rover navigating a cratered landscape or a drone learning to fly—"error" can mean catastrophic failure or loss of the robot.

Safe RL attempts to solve this by constraining the agent's exploration. However, when the environment's safety constraints and reward locations are both unknown a priori, existing algorithms struggle. They either focus entirely on mapping the safe space (ignoring reward optimization) or they guarantee safety but get stuck in sub-optimal areas, failing to maximize their cumulative reward. This paper introduces a safe reinforcement learning algorithm that guarantees near-optimal cumulative rewards without violating safety constraints in environments where both reward and safety functions are initially unknown.

Methods: The SNO-MDP Algorithm

The authors propose the Safe Near-Optimal Markov Decision Process (SNO-MDP) algorithm, which takes a stepwise approach to decouple safety and reward:

  1. Exploration of Safety: The agent first expands its "pessimistic safe space" (areas it is highly confident are safe) by targeting states on the frontier that can reveal more safe areas.
  2. Exploration and Exploitation of Reward: Once the safe region is expanded, the agent optimizes its policy within that certified safe zone using the "optimism in the face of uncertainty" principle.

To model the unknown reward and safety functions, the algorithm uses Gaussian Processes (GPs), which provide a mathematical way to quantify uncertainty and establish confidence intervals about unvisited states.

Pessimistic and optimistic safe spaces modeled via Gaussian Processes.

Early Stopping of Exploration of Safety (ES²)

Exhaustively mapping the entire safe space is highly inefficient. The authors introduce ES² to stop safety exploration early. It creates an "optimistic" MDP—assuming all unknown frontier states are safe and highly rewarding. If the optimal policy for this highly optimistic scenario still doesn't require the agent to leave its currently known safe zone, the agent stops exploring for safety and purely focuses on gathering rewards. You don't need to map the entire world to know you've found the best spot.

A practical variant, P-ES², uses virtual states and transition probabilities to improve empirical performance. It introduces a "virtual state" that acts as a penalty sink for low-probability safe states, smoothing out the agent's decision-making and preventing over-conservatism.

Datasets and Environments

The authors evaluate their approach on two environments:

  • GP-SAFETY-GYM: A newly introduced, open-source synthetic grid-world environment built on top of OpenAI Safety-Gym. It represents rewards via colors and safety via terrain height.
  • Simulated Mars Surface Exploration: A realistic environment built using actual Mars digital elevation model (DEM) data captured by the HiRISE camera. Safety is defined by the slope angle of the terrain (e.g., slopes > 25 degrees are unsafe).

Key Results

GP-SAFETY-GYM environment and performance comparisons showing SNO-MDP's superior reward optimization and the efficiency of ES².
  • Zero Unsafe Actions: Across all experiments, SNO-MDP and its variants never took a single unsafe action, successfully respecting the safety constraints 100% of the time.
  • Superior Reward Optimization: In the Mars rover simulation, SNO-MDP with P-ES² achieved a normalized cumulative reward of 0.81. This significantly outperformed existing safe RL baselines like SafeMDP (which scored 0.34) and SafeExpOpt-MDP (which scored 0.59).
  • Faster Convergence: The ES² and P-ES² algorithms demonstrated much faster convergence to optimal reward-gathering behavior compared to the vanilla SNO-MDP, proving that stopping safety exploration early saves massive amounts of time and sample complexity.

Limitations and Future Work

The primary limitation lies in the gap between theory and practice for the early stopping mechanism. The pure ES² algorithm provides strict mathematical guarantees for near-optimal rewards, but its assumption that all optimistic safe spaces are perfectly safe hurts its empirical performance. The practical version (P-ES²) performs much better in actual simulations but sacrifices the strict theoretical guarantee for reward near-optimality.

Additionally, the reliance on Gaussian Processes and discrete state spaces generally limits scalability to very high-dimensional or continuous control tasks, which presents a natural direction for future work.

Summary updated

Abstract

Safe reinforcement learning has been a promising approach for optimizing the policy of an agent that operates in safety-critical applications. In this paper, we propose an algorithm, SNO-MDP, that ...
BibTeX
@inproceedings{wachi2020safe,
  author = {Akifumi Wachi and Yanan Sui},
  title = {{Safe Reinforcement Learning in Constrained Markov Decision Processes}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=f9olQs5nnfo},
}
Figure