Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
复制标题
DOI：
--
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Dongsheng Ding;Xiaohan Wei;Zhuoran Yang;Zhaoran Wang;M. Jovanovi'c
中科院分区：
文献类型：
--
作者：
Dongsheng Ding;Xiaohan Wei;Zhuoran Yang;Zhaoran Wang;M. Jovanovi'c
我们使用约束马尔可夫决策过程（CMDP）公式来研究安全强化学习（SRL）问题，在该公式中，智能体旨在在对一个准则函数（例如，效用）的期望总值有安全约束的条件下，最大化期望总奖励。我们关注具有函数逼近的情节设置，其中奖励和准则函数以及马尔可夫转移核都具有线性结构，但对采样模型没有施加任何额外假设。在这种设置下，设计具有可证明的计算和统计效率的SRL算法特别具有挑战性，因为需要将安全约束和函数逼近都纳入基本的利用/探索权衡中。为此，我们提出了一种乐观原始 - 对偶近端策略优化（OPDOP）算法，其中通过结合最小二乘策略评估和一个用于安全探索的额外奖励项来估计值函数。我们证明所提出的算法实现了$O(d^{1.5}H^{3.5}\sqrt{T})$的遗憾值和$O(d^{1.5}H^{3.5}\sqrt{T})$的约束违反，其中$d$是特征映射的维度，$H$是每个情节的范围，$T$是总步数。我们在以下两种设置下建立了这些界限：（i）奖励和准则函数都可能对抗性地变化，但在每个情节之后完全揭示。（ii）奖励/准则函数是固定的，但每个情节之后的反馈是随机的。我们的界限仅通过特征映射的维度依赖于状态空间的容量，因此即使状态数量趋于无穷，我们的结果仍然成立。据我们所知，我们为具有安全探索的CMDP提供了第一个可证明有效的策略优化算法。
We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation in which an agent aims to maximize the expected total reward subject to a safety constraint on the expected total value of a criterion function (e.g., utility). We focus on an episodic setting with the function approximation where the reward and criterion functions and the Markov transition kernels all have a linear structure but do not impose any additional assumptions on the sampling model. Designing SRL algorithms with provable computational and statistical efficiency is particularly challenging under this setting because of the need to incorporate both the safety constraint and the function approximation into the fundamental exploitation/exploration tradeoff. To this end, we present an {O}ptimistic {P}rimal-{D}ual Proximal Policy {OP}timization (OPDOP) algorithm where the value function is estimated by combining the least-squares policy evaluation and an additional bonus term for safe exploration. We prove that the proposed algorithm achieves an O(d^{1.5}H^{3.5}\sqrt{T}) regret and an O(d^{1.5}H^{3.5}\sqrt{T}) constraint violation, where d is the dimension of the feature mapping, H is the horizon of each episode, and T is the total number of steps. We establish these bounds under the following two settings: (i) Both the reward and criterion functions can change adversarially but are revealed entirely after each episode. (ii) The reward/criterion functions are fixed but the feedback after each episode is bandit. Our bounds depend on the capacity of the state space only through the dimension of the feature mapping and thus our results hold even when the number of states goes to infinity. To the best of our knowledge, we provide the first provably efficient policy optimization algorithm for CMDPs with safe exploration.