Finding Safe Zones of Markov Decision Processes Policies
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. For this reason, we concentrate on finding approximate SafeZones. Our main result is a bi-criteria approximation learning algorithm with a factor of almost $2$ approximation for both the escape probability and \newprob size, using a polynomial size sample complexity.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Finding Safe Zones of policies Markov Decision Processes
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 o…
Efficient and Safe Exploration in Deterministic Markov Decision Processes with Unknown Transition Models
We propose a safe exploration algorithm for deterministic Markov Decision Processes with unknown transition models. Our algorithm guarantees safety by leveraging Lipschitz-continuity to ensure that no unsafe states are v…
Safe ExplorationRegular Decision Processes for Grid Worlds
Markov decision processes are typically used for sequential decision making under uncertainty. For many aspects however, ranging from constrained or safe specifications to various kinds of temporal (non-Markovian) depend…
Decision MakingDecision Making Under UncertaintyIncremental LearningSequential Decision MakingDistributionally Robust Safety Verification for Markov Decision Processes
In this paper, we propose a distributionally robust safety verification method for Markov decision processes where only an ambiguous transition kernel is available instead of the precise transition kernel. We define the …
Safe Reinforcement Learning in Constrained Markov Decision Processes
Safe reinforcement learning has been a promising approach for optimizing the policy of an agent that operates in safety-critical applications. In this paper, we propose an algorithm, SNO-MDP, that explores and optimizes …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Safe Reinforcement Learning