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 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 o…
Reinforcement Learning with Almost Sure Constraints
In this work we address the problem of finding feasible policies for Constrained Markov Decision Processes under probability one constraints. We argue that stationary policies are not sufficient for solving this problem,…
Navigatereinforcement-learningReinforcement LearningReinforcement Learning (RL)Learning Safe Policies with Cost-sensitive Advantage Estimation
Reinforcement Learning (RL) with safety guarantee is critical for agents performing tasks in risky environments. Recent safe RL algorithms, developed based on Constrained Markov Decision Process (CMDP), mostly take the s…
Reinforcement Learning (RL)Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
Constrained Markov decision processes (CMDPs), in which the agent optimizes expected payoffs while keeping the expected cost below a given threshold, are the leading framework for safe sequential decision making under st…
Decision MakingSequential Decision MakingRobust Asymmetric Learning in POMDPs
Policies for partially observed Markov decision processes can be efficiently learned by imitating policies for the corresponding fully observed Markov decision processes. Unfortunately, existing approaches for this kind …
Imitation Learning