# Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial time

arXiv: https://arxiv.org/abs/2111.07395 · HTML: https://mlsanity.com/paper/2111.07395/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 49 references that are in the map.
- First posted on arXiv 14 Nov 2021.

## Builds on (most cited first, 20 of 20)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Leave no Trace: Learning to Reset for Safe and Autonomous Reinforcement Learning](https://mlsanity.com/paper/1711.06782/) (2017)
- [Safe Reinforcement Learning via Curriculum Induction](https://mlsanity.com/paper/2006.12136/) (2020)
- [Decoupling Exploration and Exploitation for Meta-Reinforcement Learning without Sacrifices](https://mlsanity.com/paper/2008.02790/) (2020)
- [Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs](https://mlsanity.com/paper/1902.07605/) (2019)
- [Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version](https://mlsanity.com/paper/1904.10090/) (2019)
- [AGI Safety Literature Review](https://mlsanity.com/paper/1805.01109/) (2018)
- [Robust Markov Decision Process: Beyond Rectangularity](https://mlsanity.com/paper/1811.00215/) (2018)
- [Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty](https://mlsanity.com/paper/2010.04870/) (2020)
- [Conservative Exploration in Reinforcement Learning](https://mlsanity.com/paper/2002.03218/) (2020)
- [Explicit Explore-Exploit Algorithms in Continuous State Spaces](https://mlsanity.com/paper/1911.00617/) (2019)
- [Jelly Bean World: A Testbed for Never-Ending Learning](https://mlsanity.com/paper/2002.06306/) (2020)
- [Characterization of Gradient Dominance and Regularity Conditions for Neural Networks](https://mlsanity.com/paper/1710.06910/) (2017)
- [Lyapunov Robust Constrained-MDPs: Soft-Constrained Robustly Stable Policy Optimization under Model Uncertainty](https://mlsanity.com/paper/2108.02701/) (2021)

## Built on by (most cited first, 6 of 6)

- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)
- [From Intelligent Agents to Trustworthy Human-Centred Multiagent Systems](https://mlsanity.com/paper/2210.02260/) (2022)
- [Robust Lagrangian and Adversarial Policy Gradient for Robust Constrained Markov Decision Processes](https://mlsanity.com/paper/2308.11267/) (2023)
- [Trust in Language Grounding: a new AI challenge for human-robot teams](https://mlsanity.com/paper/2209.02066/) (2022)
- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Polynomial-Time Approximability of Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.07764/) (2025)

## Abstract (arXiv)

In reinforcement learning (RL), an agent must explore an initially unknown environment in order to learn a desired behaviour. When RL agents are deployed in real world environments, safety is of primary concern. Constrained Markov decision processes (CMDPs) can provide long-term safety constraints; however, the agent may violate the constraints in an effort to explore its environment. This paper proposes a model-based RL algorithm called Explicit Explore, Exploit, or Escape (E4), which extends the Explicit Explore or Exploit (E3) algorithm to a robust CMDP setting. E4 explicitly separates exploitation, exploration, and escape CMDPs, allowing targeted policies for policy improvement across known states, discovery of unknown states, as well as safe return to known states. E4 robustly optimises these policies on the worst-case CMDP from a set of CMDP models consistent with the empirical observations of the deployment environment. Theoretical results show that E4 finds a near-optimal constraint-satisfying policy in polynomial time whilst satisfying safety constraints throughout the learning process. We then discuss E4 as a practical algorithmic framework, including robust-constrained offline optimisation algorithms, the design of uncertainty sets for the transition dynamics of unknown states, and how to further leverage empirical observations and prior knowledge to relax some of the worst-case assumptions underlying the theory.