This paper puts forward the concept that learning to take safe actions in unknown environments, even with probability one guarantees, can be achieved without the need for an unbounded number of exploratory trials. This is indeed possible, provided that one is willing to navigate trade-offs between optimality, level of exposure to unsafe events, and the maximum detection time of unsafe actions. We illustrate this concept in two complementary settings. We first focus on the canonical multi-armed bandit problem and study the intrinsic trade-offs of learning safety in the presence of uncertainty. Under mild assumptions on sufficient exploration, we provide an algorithm that provably detects all unsafe machines in an (expected) finite number of rounds. The analysis also unveils a trade-off between the number of rounds needed to secure the environment and the probability of discarding safe machines. We then consider the problem of finding optimal policies for a Markov Decision Process (MDP) with almost sure constraints. We show that the action-value function satisfies a barrier-based decomposition which allows for the identification of feasible policies independently of the reward process. Using this decomposition, we develop a Barrier-learning algorithm, that identifies such unsafe state-action pairs in a finite expected number of steps. Our analysis further highlights a trade-off between the time lag for the underlying MDP necessary to detect unsafe actions, and the level of exposure to unsafe events. Simulations corroborate our theoretical findings, further illustrating the aforementioned trade-offs, and suggesting that safety constraints can speed up the learning process.
翻译:本文提出一个概念,即学会在未知环境中采取安全行动,即使有可能有一个保障,也可以在未知环境中学会安全行动,即使有可能有一个保障,在不需要大量无限制的试探性试验的情况下实现。这的确有可能。只要人们愿意在最佳性、不安全事件暴露的程度和不安全行动的最大探测时间之间权衡取舍,就有可能实现。我们在两个互补的场合中说明了这一概念。我们首先关注卡通性的多武装匪徒问题,并研究在存在不确定性的情况下学习安全的内在权衡取舍。在充分探索的温和假设下,我们提供一种算法,在(预期的)有限回合中可以发现所有不安全机器。分析还揭示了确保环境所需的轮数和抛弃安全机器的可能性之间的权衡取舍。然后我们考虑在几乎肯定限制的情况下为马尔科夫决策过程找到最佳政策的问题。我们表明,行动价值功能能够满足基于障碍的进一步分解,从而可以独立地确定可行的奖赏政策。我们利用这个分数,我们开发了一种障碍学习算法,我们又提出了一种时间,用以确定我们安全性贸易选择的极限分析,从而确定我们的安全性接触的进度。