Finding Safe Zones of Markov Decision Processes Policies

Dec 2, 2022



Given a policy, 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 the 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. For this reason, we concentrate on computing approximate SafeZones Our main result is a bi-criteria approximation algorithm which gives a factor of almost 2 approximation for both the escape probability and SafeZone size, using a polynomial size sample complexity. We conclude the paper with an empirical demonstration of our algorithm.


Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%


Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow NeurIPS 2022