Explicit Explore, Exploit, or Escape ($E^4$): near-optimal safety-constrained reinforcement learning in polynomial time

Abstract

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 ($E^4$), which extends the Explicit Explore or Exploit ($E^3$) algorithm to a robust CMDP setting. $E^4$ 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. $E^4$ 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 $E^4$ finds a near-optimal constraint-satisfying policy in polynomial time whilst satisfying safety constraints throughout the learning process. We then discuss $E^4$ 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.

Accepted at Machine Learning

References in corpus (12)

• First return, then explore
• Safe Reinforcement Learning via Curriculum Induction
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• Leave no Trace: Learning to Reset for Safe and Autonomous Reinforcement Learning
• Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs
• Chernoff-Hoeffding Inequality and Applications
• Explicit Explore-Exploit Algorithms in Continuous State Spaces
• Conservative Exploration in Reinforcement Learning
• Decoupling Exploration and Exploitation for Meta-Reinforcement Learning without Sacrifices
• Jelly Bean World: A Testbed for Never-Ending Learning
• Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty
• Lyapunov Robust Constrained-MDPs: Soft-Constrained Robustly Stable Policy Optimization under Model Uncertainty

Cited by in corpus (1)

• AI Safety for Everyone