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 co…