带赌博机反馈的强化学习中良好策略的纯探索

# 在强化学习中基于Bandit反馈寻找好策略的纯探索  
**来源**: https://arxiv.org/html/2605.23182  

**李自天**  
新加坡国立大学工业系统工程与管理系  
Engineering Drive 2 Block E1A #06-25 新加坡 117576  
[email protected]  

**张旺志**  
新加坡国立大学工业系统工程与管理系  
Engineering Drive 2 Block E1A #06-25 新加坡 117576  
[email protected]  

###### 摘要  
在回合制强化学习中的纯探索主要集中于最优策略识别 (BPI)，即高置信度地识别出一个 (近乎) 最优的策略。受实际场景中“足够好”的策略即可满足需求的启发，我们研究了一个替代目标：好策略识别 (GPI)。对于给定的奖励阈值 μ₀，GPI 仅要求：如果存在这样的策略 (正实例)，则识别出一个期望回合奖励至少为 μ₀ 的策略；如果不存在这样的策略 (负实例)，则声明 None。我们在固定置信度设置下形式化 GPI。要求输出正确的概率 ≥ 1-δ，并最小化期望样本复杂度，即用于输出结果的期望探索回合数。我们提出了一种新颖的算法 BEE-GPI，并推导了其在正实例和负实例下样本复杂度的理论上限。值得注意的是，对于正实例，我们的上限中 log(1/δ) 的系数为 O(H²/(V* - μ₀)²)，其中 H 是回合长度，V* 是一个回合的最优期望奖励。该系数不依赖于动作空间和状态空间的大小，这与 BPI 中的样本复杂度形成鲜明对比。我们进一步建立了下界结果，以证明 BEE-GPI 的近乎最优性以及 1/(V* - μ)² 项的必然性。数值实验进一步验证了我们方法的效率。

## 1 引言  
纯探索是强化学习中的一个基本目标，学习智能体需要识别出满足特定性能标准的策略。与遗憾最小化框架不同，纯探索优先考虑正确识别的概率和样本效率，而非总回合数。迄今为止，该领域的大多数研究都集中在最优策略识别或 ε-最优策略识别上，而好策略识别问题在很大程度上未被探索。在具有未知转移动态的回合制马尔可夫决策过程中，GPI 要求智能体：如果存在值函数超过预设阈值 μ₀ 的策略，则将其识别出来；否则返回 None。许多现实应用需要找到“足够好”的策略，而非近乎最优的策略，尤其是当精确的两两比较在计算上或实践中困难时。例如，在医学信息学中，新治疗方案通常与已知的“护理标准”（具有已知效用 μ₀）进行比较。目标是确保找到一种治疗序列，使患者康复率或“寿命年数”的效用 ≥ μ₀。在这种情况下，高置信度 1-δ 地识别出绝对最佳治疗方案往往是不必要的，尤其是当顶级策略之间的性能差异很小时。类似地，在云计算中，服务提供商使用强化学习进行流量路由和资源分配。提供商标通常不是为了寻求绝对最优的路由规则，而是旨在确保可靠性和效率水平超过指定的服务等级协议。此外，机构投资者在部署新交易策略之前，经常评估其是否达到最低夏普比率或投资回报率基准。这个基准 μ₀ 通常来自具有大量历史数据的既定指数。在这些场景中，主要关注点是确定新替代方案相对于基准是否具有竞争力，而不是在所有可能策略中找到最佳策略。

**主要贡献**。我们提供三个主要贡献。首先，我们在固定置信度设置下形式化了好策略识别问题。给定一个失败概率容忍参数 δ∈(0,1)，学习智能体必须以概率 ≥ 1-δ 识别出一个期望奖励至少为阈值 μ₀ 的策略（或正确识别其不存在）。其次，我们开发了 BEE-GPI，一种新颖的 δ-PAC 算法，它利用早期停止的 BPI 子程序作为预言机来实现高效的样本复杂度。我们给出了其期望样本复杂度的严格上限，证明对于正实例，log(1/δ) 的系数随间隙 (V* - μ₀) 缩小，但独立于状态和动作空间的大小。第三，我们为 GPI 问题建立了下界。我们的上下界之间的差距仅限于 S、A 和 H 的多项式因子，表明 BEE-GPI 是近乎最优的。

**符号**。记 N、R 分别为正整数集和实数集。对于 n ∈ N，记 [n] = {1, ..., n}。我们将按概率分布 p 的随机变量 R 简写为 R ~ p。

**问题形式化**。好策略识别问题的一个实例由元组 ν = (S, A, μ₀, δ, H, R, P, p) 指定。集合 S 和 A 分别表示有限的状态空间和动作空间。我们分别用 S、A 表示 S、A 的基数。标量 μ₀ ∈ R 是奖励阈值，即学习智能体旨在一个回合中累积的期望总奖励。误差参数 δ ∈ (0,1) 是错误输出概率的容忍水平。整数 H 表示回合长度。转移核和奖励函数分别记为 P = {p_h(·|s,a)}_{h∈[H], s∈S, a∈A} 和 R = {r_h(s,a)}_{h∈[H], s∈S, a∈A}。在回合 h ∈ [H] 时，当智能体处于状态 s ∈ S 并采取动作 a ∈ A 时，智能体获得确定性奖励 r_h(s,a) ∈ [0,1]，并以概率 p_h(s′|s,a) 转移到状态 s′。初始状态 S₁ 按初始分布 p 分布。我们假设 S、A、μ₀、δ、H、R 对智能体是已知的，而 P、p 是未知的。为便于讨论 P、p，我们在每个回合前添加一个虚构的时间轮次 0。轮次 0 与一个虚构状态 s₀ 和单个虚构动作 a₀ 相关联，这些动作产生零奖励并产生状态转移 p₀(·|s₀,a₀) = p(·)。策略 π 表示为 (π_h)_{h=1}^H ∈ Π^H，其中 Π = {f | f : S → A} 由从当前状态到动作的映射组成。因此，Π^H 是所有确定性策略的空间，π_h 决定轮次 h ∈ [H] 中的动作。策略 π 从轮次 h 到回合结束的值函数为  
V_h^π(s_h) := E^π [∑_{ℓ=h}^H r_ℓ(s_ℓ, π_ℓ(s_ℓ)) ∣ s_h]，  
其中 s_{ℓ+1} ~ p_ℓ(·|s_ℓ, π_ℓ(s_ℓ))。令 π* ∈ Π^H 表示最优策略。根据贝尔曼最优性，对于任何策略 π 和 s∈S、h∈[H]，有 V_h^{π*}(s) ≥ V_h^π(s)。我们将 V_0^*(s₀) = V_0^{π*}(s₀) 简写为一次回合的最优期望总奖励，并偶尔附加实例 ν 以表示为 V_0^*(s₀ | ν)，以强调对 ν 的依赖。

**动态过程**。智能体的算法的特征在于抽样规则 {π^t}_{t=1}^∞、停止时间 τ 和推荐规则 π̂。当回合 t ∈ N 开始时，算法根据在回合 1,..., t-1 中收集的数据 D_{t-1} 选择一个策略 π^t = (π_h^t)_{h=1}^H ∈ Π^H。在实例上执行 π^t 生成轨迹 z_t = (s₀, a₀, S_{t,1}, A_{t,1}, r₁(S_{t,1},A_{t,1}), ..., S_{t,H}, A_{t,H}, r_H(S_{t,H},A_{t,H}))，其中 S_{t,h} ~ p_{h-1}(·|S_{t,h-1}, π_{h-1}^t(S_{t,h-1}))。此轨迹被添加到历史中，即 D_t = D_{t-1} ∪ {z_t}，其中我们初始化 D₀ = ∅。在回合结束时，智能体可以选择终止算法。我们将停止时间 τ 定义为终止回合的索引。终止后，智能体基于 D_τ 输出答案 π̂ ∈ Π^H ∪ {None}。智能体的目标是：如果 μ₀ 可以达到，则输出满足 V_0^{π̂}(s₀) ≥ μ₀ 的策略 π̂ ∈ Π^H；如果智能体断定 V_0^*(s₀) < μ₀，则输出 None。我们在固定置信度设置下形式化该目标，并借助一些有助于讨论的定义：

###### 定义 1 (正实例和负实例)。  
GPI 实例 ν 是正实例，如果 V_0^*(s₀ | ν) > μ₀；是负实例，如果 V_0^*(s₀ | ν) < μ₀。

###### 定义 2 (合格策略)。  
对于正实例 ν，我们说策略 π 对于 ν 是合格的，如果 V_0^π(s₀ | ν) ≥ μ₀。

输出的正确性由 δ-概率近似正确 (δ-PAC) 来限定：

###### 定义 3 (δ-PAC)。  
如果一个算法对于任何正或负的好策略识别实例 ν 能保证：  
- 如果 V_0^*(s₀ | ν) > μ₀，则 Pr(V_0^{π̂_τ}(s₀ | ν) ≥ μ₀, τ < +∞) ≥ 1-δ  
- 如果 V_0^*(s₀ | ν) < μ₀，则 Pr(π̂_τ = None, τ < +∞) ≥ 1-δ  
则该算法称为 δ-PAC。

Degenne and Koolen (2019) 已证明，在满足 V_0^*(s₀|ν) = μ₀ 的实例 ν 上，任何 δ-PAC 算法都有 E_ν[τ] = ∞，即使我们将 ν 限制到 |S| = H = 1 的情况。因此，本文仅考虑正实例或负实例。

**目标**。智能体的目标是设计一个 δ-PAC 算法 ({π^t}_{t=1}^∞, τ, π̂)，以最小化期望采样复杂度 E_ν[τ]。

## 2 文献综述  
强化学习中纯探索的一个流行目标是高置信度地识别最优或 ε-最优策略。这一研究方向通常称为最优策略识别，由 Fiechter (1994) 开创。后续的大量工作假设存在生成模型，允许智能体通过查询任意状态-动作对与环境交互 (Kearns and Singh, 1998; Gheshlaghi Azar et al., 2013; Sidford et al., 2018, 2023; Agarwal et al., 2020; Al Marjani et al., 2021; Li et al., 2024)。虽然生成模型设置在理论上很有见地，但 BPI 更实际且更具挑战性的分支关注在线 (非生成) 设置，其中智能体必须通过连续回合探索 MDP 来收集数据。在此背景下，Dann and Brunskill (2015) 基于不确定性下的乐观原则提出了 UCFH 算法。随后，Ménard et al. (2021) 提出了 BPI-UCBVI，通过适配极小极大最优遗憾算法，改进了对状态空间大小 S 的依赖。Al Marjani and Proutiere (2021) 研究非回合制 MDP 中的强化学习 BPI。最近，研究已转向实例相关的样本复杂度。尽管 Wagenmaker et al. (2022) 和 Narang et al. (2024) 的算法实现了最先进的非渐近界，但它们通常计算密集。为了弥合这一差距，Kaufmann et al. (2021)、Ménard et al. (2021) 和 Tirinzoni et al. (2023) 分析了计算高效但理论上次优的乐观抽样规则。

尽管关于 BPI 和 ε-PI 的文献丰富，但这些方法不能直接应用于好策略识别问题。回想一下，对于 ε-PI，目标是识别出一个期望奖励至少为 V_0^*(s₀) - ε 的策略。困难在于 V_0^*(s₀) 是未知的；因此，智能体无法预先确定一个合适的 ε 给 ε-PI 算法，以确保识别出的策略能达到阈值 μ₀。此外，为 ε-PI 建立的下界 (Domingues et al., 2021) 不适用于 GPI 基于阈值的要求。在简化情况 S=1 且 H=1 下，GPI 简化为多臂赌博机问题，特别是 Degenne and Koolen (2019)、Katz-Samuels and Jamieson (2020) 以及 Li and Cheung (2025, 2026) 研究的“1-识别”或“任意低(高)”问题，这些也在相关文献中有所覆盖，但不是主要焦点。