# Finding Safe Zones of policies Markov Decision Processes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 23 Feb 2022.

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

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Unsolved Problems in ML Safety](https://mlsanity.com/paper/2109.13916/) (2021)
- [Constrained Variational Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/2201.11927/) (2022)
- [Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentation](https://mlsanity.com/paper/2202.06558/) (2022)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Provably Efficient Reinforcement Learning with Aggregated States](https://mlsanity.com/paper/1912.06366/) (2019)
- [Safe Reinforcement Learning with Chance-constrained Model Predictive Control](https://mlsanity.com/paper/2112.13941/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [A Learning Theoretic Perspective on Local Explainability](https://mlsanity.com/paper/2011.01205/) (2020)

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

- [Learning When to Advise Human Decision Makers](https://mlsanity.com/paper/2209.13578/) (2022)

## Abstract (arXiv)

Given a policy of a Markov Decision Process, we define a SafeZone as a subset of states, such that most of the policy's trajectories are confined to this subset. The quality of a SafeZone is parameterized by the number of states and the escape probability, i.e., the probability that a random trajectory will leave the subset. SafeZones are especially interesting when they have a small number of states and low escape probability. We study the complexity of finding optimal SafeZones, and show that in general, the problem is computationally hard. Our main result is a bi-criteria approximation learning algorithm with a factor of almost 2 approximation for both the escape probability and SafeZone size, using a polynomial size sample complexity.