Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs
Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs
复制标题
DOI：
10.1609/aaai.v35i9.16937
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Aria HasanzadeZonuzy;D. Kalathil;S. Shakkottai
中科院分区：
文献类型：
--
作者：
Aria HasanzadeZonuzy;D. Kalathil;S. Shakkottai
许多物理系统都有潜在的安全考虑，要求所采用的策略确保满足一组约束。分析公式通常采用约束马尔可夫决策过程（CMDP）的形式。我们专注于CMDP是未知的情况下，RL算法获得的样本，发现模型和计算的最优约束策略。我们的目标是描述安全约束和样本数量之间的关系，以确保所需的准确性水平-目标最大化和约束满足-在PAC的意义。我们探索了两类RL算法，即（i）基于生成模型的方法，其中最初采用样本来估计模型，以及（ii）在线方法，其中模型随着样本的获得而更新。我们的主要发现是，相比于最好的已知的无约束制度的界限，约束RL算法的样本复杂度增加了一个因素，是对数的限制，这表明该方法可以很容易地利用在真实的系统。
Many physical systems have underlying safety considerations that require that the policy employed ensures the satisfaction of a set of constraints. The analytical formulation usually takes the form of a Constrained Markov Decision Process (CMDP). We focus on the case where the CMDP is unknown, and RL algorithms obtain samples to discover the model and compute an optimal constrained policy. Our goal is to characterize the relationship between safety constraints and the number of samples needed to ensure a desired level of accuracy---both objective maximization and constraint satisfaction---in a PAC sense. We explore two classes of RL algorithms, namely, (i) a generative model based approach, wherein samples are taken initially to estimate a model, and (ii) an online approach, wherein the model is updated as samples are obtained. Our main finding is that compared to the best known bounds of the unconstrained regime, the sample complexity of constrained RL algorithms are increased by a factor that is logarithmic in the number of constraints, which suggests that the approach may be easily utilized in real systems.