技术摘要：带 Bandit 反馈的强化学习中的好策略纯探索

1. 问题表述

本文在强化学习（RL）的纯探索框架内，解决了**好策略识别（GPI）问题。与传统的最佳策略识别（BPI）**目标（即以高置信度识别一个（近）最优策略）不同，GPI 专注于寻找满足特定性能阈值的策略。

形式化地，给定一个具有未知转移动力学 $P$ 和初始分布 $p$、有限状态空间 $S$、动作空间 $A$ 以及时间视界 $H$ 的回合制马尔可夫决策过程（MDP），智能体被提供一个奖励阈值 $\mu_0$。目标是设计一个 $\delta$-概率近似正确（$\delta$-PAC）算法，使得：

• 正例情况： 如果存在一个策略 $\pi$，其期望总奖励 $V^\pi_0(s_0) \ge \mu_0$，则算法必须以至少 $1-\delta$ 的概率输出这样一个策略。
• 负例情况： 如果最优策略的值 $V^*_0(s_0) < \mu_0$，则算法必须以至少 $1-\delta$ 的概率输出“无”。

性能指标是达到正确决策所需的期望样本复杂度（即探索的期望回合数，记为 $\tau$）。本文明确排除了 $V^*_0(s_0) = \mu_0$ 的情况，因为先前的工作（Degenne 和 Koolen [2019]）已证明，在此边界情况下，任何 $\delta$-PAC 算法都需要无限样本。

2. 方法论：BEE-GPI

作者提出了一种名为BEE-GPI（用于好策略识别的平衡探索 - 利用）的新算法。该算法在 $k=1, 2, \dots$ 阶段运行，每个阶段由一个自适应探索阶段和一个决策分支机制组成。

关键组件：

1. 探索阶段（ES-BPI-UCRL）：

   • 该阶段利用一个早停 BPI-UCRL 预言机。它采用类似于 BPI-UCRL 的乐观采样策略来估计转移核和值函数。
   • 关键在于引入了一种新颖的早停机制。预言机在每一步检查两个条件：
     • 条件 (3)： 当前乐观策略值的下置信界超过 $\mu_0$（经因子 $C$ 调整）。若满足，则识别出一个候选策略。
     • 条件 (4)： 最优值函数的上置信界低于 $\mu_0$。若满足，则声明该实例为负例。
   • 如果两个条件均未满足且未超出探索预算 $T^{ee}_k$，算法继续采样。

2. 决策分支：

   • 如果预言机返回“未完成”，算法进入下一阶段，采用更严格的误差容限 $\delta_k$ 并增加预算。
   • 如果预言机返回“无”但置信度不足（$\delta_k \ge \delta/10$），算法继续进入下一阶段以确保 $\delta$-PAC 保证。
   • 如果预言机返回候选策略 $\hat{\pi}_k$，算法进入利用阶段。

3. 利用与验证：

   • 在该阶段，候选策略 $\hat{\pi}_k$ 被重复执行以估计其真实值。
   • 算法构建经验平均奖励的置信区间。如果在特定样本预算内，下置信界超过 $\mu_0$，则将该策略输出为解。
   • 如果预算耗尽仍未通过验证，算法返回下一轮迭代的探索阶段。

3. 主要贡献

本文做出了三项主要的理论贡献：

1. GPI 的形式化： 作者在固定置信度设置下正式定义了好策略识别问题，将其与 $\epsilon$-BPI 区分开来。他们强调，标准的 $\epsilon$-BPI 归约对于 GPI 是次优的，因为差距 $V^*_0(s_0) - \mu_0$ 是先验未知的，这使得 $\epsilon$ 的选择变得困难。
2. 算法设计与上界： 他们提出了 BEE-GPI，并推导了其在正例和负例情况下的样本复杂度的理论依据上界。
   • 正例情况： 样本复杂度上界为 $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$。
   • 负例情况： 该界限包含与状态和动作空间大小耦合的项，具体为 $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$。
3. 下界与近最优性： 作者利用构造的“均匀实例”（针对正例情况）和“树实例”（针对负例情况）建立了 GPI 问题的下界。
   • 他们证明，对于正例情况，任何 $\delta$-PAC 算法必须承担 $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$ 的样本复杂度。
   • 对于负例情况，下界为 $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$。
   • 这些结果表明 BEE-GPI 是近最优的，上界与下界之间的差距仅限于 $S, A, H$ 的多项式因子。

4. 结果与分析

理论洞察

• 对数项的解耦： 一个重要的发现是，对于正例情况，样本复杂度中 $\log(1/\delta)$ 项的系数为 $O(H^2)$，并且独立于状态空间大小 $S$ 和动作空间大小 $A$。这与标准的 BPI 归约形成鲜明对比，后者的系数通常随 $S$ 和 $A$ 呈多项式增长。
• 不对称性： 正例和负例情况之间存在固有的不对称性。虽然正例情况允许在不探索整个状态 - 动作空间的情况下高效地识别一个好策略，但负例情况需要全局探索以证明没有任何策略满足阈值，因此 $\log(1/\delta)$ 项依赖于 $S$ 和 $A$。

数值实验

作者使用两个经典环境：单链和双链 MDP 验证了他们的方法。

• 设置： 他们将 BEE-GPI 与最先进的 BPI-UCRL 算法（Kaufmann 等人 [2021]）进行了比较。为了确保公平比较，BPI-UCRL 被提供了预言机参数 $\epsilon = V^*_0 - \mu_0$，这赋予了它显著的先验知识。
• 发现： 在各种阈值 $\mu_0$ 下，与 BPI-UCRL 相比，BEE-GPI 始终需要显著更少的回合来识别合格的策略。实证结果证实了将 $\log(1/\delta)$ 项与状态和动作空间大小解耦的理论优势。

5. 意义与主张

本文主张，BEE-GPI 为实际的 RL 场景提供了一种更高效的解决方案，在这些场景中，寻找绝对最优策略是不必要的或计算上不可行的，但寻找一个“足够好”的策略（超过基准）至关重要。

• 实际相关性： 作者引用了医疗信息学（识别超过标准护理的治疗方案）、云计算（满足服务等级协议）和金融（满足投资回报率基准）中的应用，在这些应用中，目标是满足阈值而非追求最优。
• 理论进展： 通过形式化 GPI 并提供近最优界限，这项工作弥合了理论纯探索与实际基于阈值的需求之间的差距。它表明，当目标从最优性放宽为阈值满足时，样本复杂度可以显著降低，特别是在正例情况中。
• 未来方向： 作者谦逊地建议，未来的工作可以涉及推导更紧的实例相关界限，并利用函数近似将该框架扩展到大规模 MDP。

总之，本文确立了识别满足奖励阈值的策略与识别最佳策略在根本上是不同的，并提出了一种利用这一区别来实现更优样本效率的算法，特别是当最优值与阈值之间的差距是主要困难驱动因素时。