mlsanityData to 7 Oct 2026

Finding Safe Zones of policies Markov Decision Processes

arXiv 2202.11593 ↗First posted 23 Feb 2022cs.LG cs.AI cs.DScited by 1

Not on the map. Why?

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.

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

Builds on

11 of 32 references.

References · 11

  1. 2017Understanding Black-box Predictions via Influence Functionscited by 1,714
  2. 2016Concrete Problems in AI Safetycited by 1,582
  3. 2021Unsolved Problems in ML Safetycited by 291
  4. 2022Constrained Variational Policy Optimization for Safe Reinforcement Learningcited by 69
  5. 2022Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentationcited by 63
  6. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  7. 2021Provably efficient, succinct, and precise explanationscited by 32
  8. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  9. 2021Safe Reinforcement Learning with Chance-constrained Model Predictive Controlcited by 18
  10. 2021Connecting Interpretability and Robustness in Decision Trees through Separationcited by 16
  11. 2020A Learning Theoretic Perspective on Local Explainabilitycited by 11

Built on by

Cited by year

Citing papers per year: 2022: 1.

1 paper.

  1. 2022Learning When to Advise Human Decision Makerscited by 18