Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism

📄 arXiv: 2410.10158v1 📥 PDF

作者: Kihyun Yu, Duksang Lee, William Overman, Dabeen Lee

分类: cs.LG, math.OC

发布日期: 2024-10-14

💡 一句话要点

提出基于更紧致的成本悲观和奖励乐观估计的安全强化学习算法，提升Regret上界。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 安全强化学习 约束马尔可夫决策过程 Regret上界 成本悲观 奖励乐观 模型学习 Bellman方程

📋 核心要点

  1. 现有安全强化学习算法在未知环境下的探索效率和性能提升方面存在挑战，尤其是在保证安全约束的同时。
  2. 论文提出了一种基于模型的安全强化学习算法，通过更紧致的成本悲观和奖励乐观估计来提高性能。
  3. 实验结果表明，该算法在保证安全约束的同时，实现了更好的Regret上界，并验证了其计算有效性。

📝 摘要（中文）

本文研究了安全强化学习问题，该问题被形式化为具有未知转移核以及随机奖励和成本函数的 episodic 有限水平表格约束马尔可夫决策过程。我们提出了一种基于模型的算法，该算法基于新颖的成本和奖励函数估计器，这些估计器提供了更紧密的成本悲观和奖励乐观。在保证每个 episode 中没有违反约束的情况下，我们的算法实现了 $\widetilde{\mathcal{O}}((\bar C - \bar C_b)^{-1}H^{2.5} S\sqrt{AK})$ 的 Regret 上界，其中 $\bar C$ 是一个 episode 的成本预算，$\bar C_b$ 是一个 episode 中安全基线策略下的预期成本，$H$ 是 horizon，$S$、$A$ 和 $K$ 分别是状态、动作和 episode 的数量。这改进了最著名的 Regret 上界，并且当 $\bar C-\bar C_b=\Omega(H)$ 时，它几乎与 $\Omega(H^{1.5}\sqrt{SAK})$ 的 Regret 下界相匹配。我们通过 Bellman 类型的总方差定律推导出我们的成本和奖励函数估计器，以获得对价值函数估计方差的预期总和的严格界限。这导致函数估计器中对 horizon 的更严格的依赖性。我们还展示了数值结果，以证明我们提出的框架的计算有效性。

🔬 方法详解

问题定义：论文旨在解决 episodic 有限水平表格约束马尔可夫决策过程中的安全强化学习问题，其中转移核未知，奖励和成本函数是随机的。现有方法在保证安全约束的同时，往往难以实现较好的探索效率和性能，导致较高的Regret。

核心思路：论文的核心思路是设计更紧致的成本悲观和奖励乐观估计器，从而在保证安全约束的前提下，更有效地进行探索和学习。通过更精确地估计成本和奖励，算法可以更好地权衡探索和利用，从而降低Regret。

技术框架：该算法是一个基于模型的框架，主要包括以下几个阶段：1) 使用新颖的成本和奖励函数估计器构建环境模型；2) 基于模型进行策略优化，同时保证满足安全约束；3) 执行策略并收集数据，用于更新模型。关键在于成本和奖励函数估计器的设计，以及如何利用这些估计器来保证策略的安全性。

关键创新：论文最重要的技术创新在于提出了新的成本和奖励函数估计器，这些估计器基于 Bellman 类型的总方差定律，能够获得对价值函数估计方差的预期总和的更严格界限。这使得估计器对 horizon 的依赖性更紧密，从而提高了估计的准确性。

关键设计：论文的关键设计包括：1) 基于 Bellman 类型的总方差定律推导成本和奖励函数估计器；2) 设计策略优化算法，确保在每个 episode 中都满足安全约束；3) 分析算法的 Regret 上界，并证明其优于现有算法。具体的参数设置和损失函数等细节在论文中进行了详细描述。

📊 实验亮点

论文提出的算法实现了 $\widetilde{\mathcal{O}}((\bar C - \bar C_b)^{-1}H^{2.5} S\sqrt{AK})$ 的 Regret 上界，改进了现有最著名的 Regret 上界。当 $\bar C-\bar C_b=\Omega(H)$ 时，该算法的 Regret 上界几乎与 $\Omega(H^{1.5}\sqrt{SAK})$ 的 Regret 下界相匹配。数值实验验证了该算法的计算有效性。

🎯 应用场景

该研究成果可应用于各种需要安全保障的强化学习任务中，例如机器人控制、自动驾驶、医疗决策等。在这些领域中，违反安全约束可能会导致严重的后果，因此安全强化学习算法具有重要的实际价值。该研究可以推动安全强化学习算法在实际应用中的部署和发展。

📄 摘要（原文）

This paper studies the safe reinforcement learning problem formulated as an episodic finite-horizon tabular constrained Markov decision process with an unknown transition kernel and stochastic reward and cost functions. We propose a model-based algorithm based on novel cost and reward function estimators that provide tighter cost pessimism and reward optimism. While guaranteeing no constraint violation in every episode, our algorithm achieves a regret upper bound of $\widetilde{\mathcal{O}}((\bar C - \bar C_b)^{-1}H^{2.5} S\sqrt{AK})$ where $\bar C$ is the cost budget for an episode, $\bar C_b$ is the expected cost under a safe baseline policy over an episode, $H$ is the horizon, and $S$, $A$ and $K$ are the number of states, actions, and episodes, respectively. This improves upon the best-known regret upper bound, and when $\bar C- \bar C_b=Ω(H)$, it nearly matches the regret lower bound of $Ω(H^{1.5}\sqrt{SAK})$. We deduce our cost and reward function estimators via a Bellman-type law of total variance to obtain tight bounds on the expected sum of the variances of value function estimates. This leads to a tighter dependence on the horizon in the function estimators. We also present numerical results to demonstrate the computational effectiveness of our proposed framework.