Anytime-valid Optimal Policy Identification

技术摘要：随时有效（Anytime-Valid）的最优策略识别

1. 问题陈述

本文探讨了利用日志上下文多臂老虎机（contexted bandit）数据，从有限候选类 $\Pi = \{\pi_1, \dots, \pi_m\}$ 中识别最优策略 $\pi^\star$ 的挑战。在许多实际场景中，数据是由外部确定的日志策略（logging policy, $h_t$）生成的，而分析师无法控制该策略。该日志策略可能是一个固定的随机化过程，也可能是一个为了实现其他目标（例如，最大化用户参与度而非最小化虚假信息）而调优的自适应算法。

核心难点在于两个约束条件：

1. 离策设置（Off-Policy Setting）： 分析师必须利用在不同策略 $h_t$ 下收集的数据来推断目标策略 $\nu(\pi)$ 的价值，而无法通过干预数据收集过程来引导识别目标。
2. 序列监测（Sequential Monitoring）： 从业者通常希望能够持续监测证据、随着数据的累积剔除明显次优的策略，并在最优策略被识别后停止数据收集，而不是预先设定一个固定的样本量（$N$）。

现有的最优策略识别文献通常假设分析师可以控制数据收集（自适应采样），或者仅在预先指定的固定样本量下提供推断保证。本文旨在通过为离策最优策略识别提供**随时有效（anytime-valid）**的保证，来填补这一空白。

2. 方法论

所提框架构建了一个随数据到达而演化的时变候选最优策略集合 $S_t$。该方法依赖于三个核心组件：

A. 双重稳健伪结果（Doubly Robust Pseudo-Outcomes）
为了从日志数据中估计策略价值 $\nu(\pi)$，该方法利用重要性权重 $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$。为了提高效率和稳定性，这些权重与奖励模型 $b_{rt}(x,a)$ 相结合，以构建双重稳健（DR）伪结果。具体而言，定义了下界和上界伪结果（$\phi^{DRL}_t$ 和 $\phi^{DRU}_t$），使得它们的条件期望分别等于真实的策略价值 $\nu(\pi)$ 和 $1-\nu(\pi)$。至关重要的是，其有效性并不依赖于奖励模型是否被正确指定，仅取决于已知的日志概率。

B. 随时有效置信序列（Confidence Sequences, CS）
基于 Waudby-Smith 等人 (2024) 的工作，本文为策略价值构建了置信序列。如果一个序列区间 $[L_t(\pi), U_t(\pi)]$ 在所有 $t \geq 1$ 时以至少 $1-\alpha$ 的概率使真实的 $\nu(\pi)$ 保持在区间内，则称其为 $(1-\alpha)$-CS。这些区间是利用 DR 伪结果和考虑了证据积累的方差过程 $V_t(\pi)$ 构建的。其区间宽度以 $O(\sqrt{(\log \log t + \log m)/t})$ 的速率收缩。

C. 序列消除与停止规则
利用对策略类 $\Pi$ 的联合界（union bound），该方法构建了所有策略的同步置信序列。候选集 $S_t$ 定义为：
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
当某个策略的上置信界低于任何竞争策略的最大下置信界时，该策略会从 $S_t$ 中被消除。当 $S_\tau$ 变为单元素集合（仅包含一个策略）时，程序在数据依赖的时间 $\tau$ 处停止。

3. 核心贡献

本文做出了两个主要的理论贡献：

1. 随时有效覆盖保证： 作者证明了构建的集合 $S_t$ 满足统一覆盖保证：
   $$P(\Pi^\star \subseteq S_t \text{ 对于所有 } t \geq 1) \geq 1 - \alpha$$
   其中 $\Pi^\star$ 是真实最优策略的集合。这确保了以高概率而言，无论分析师何时选择停止，都不会误删任何最优策略。

2. 样本复杂度界限： 当最优策略 $\pi^\star$ 是唯一的时候，本文定义了其识别的停止时间 $\tau$。在满足线性方差增长的正则性条件（假设 1）下，样本复杂度推导为：
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   其中 $\Delta_{\min}$ 是最优策略与次优策略之间的差距。该界限表明，所需样本量与策略类规模呈对数关系，并与次优差距的平方成反比。

4. 实验结果

本文通过三个实验演示验证了该框架：

• 合成模拟： 在一个包含六个策略的模拟上下文多臂老虎机设置中，该框架成功地在数据流早期就剔除了明显的次优策略，同时保留了最优策略直至其被唯一识别。策略价值的置信序列如预期般向真实值收敛。
• 样本效率： 通过将随时有效程序与固定-$N$设计（其中 $N$ 基于目标差距计算）进行比较，作者发现当真实差距大于目标差距时，存在显著的样本节省。例如，如果真实差距是目标差距的两倍，该随时有效方法平均可节省 60–80% 的计划样本量。
• 现实应用： 该方法被应用于一项涉及肯尼亚和尼日利亚 15,292 名用户的大型自适应实验（Offer-Westort et al., 2024），旨在减少虚假信息传播。该框架重现了原始研究的结论（识别出“准确性提示”和“Facebook 技巧”为表现最佳的策略），同时提供了证据积累的动态视图。它显示，在仅使用一小部分最终数据时即可消除表现最差的策略，而顶尖候选策略在整个过程中始终保留在候选集中。

5. 意义与局限性

意义：
本文为离策设置下的序列监测提供了一个严谨的推断框架。它允许分析师在不破坏统计保证的前提下做出数据依赖的停止决策，解决了固定-$N$方法的一个关键局限。这在数据收集受限于外部日志策略且资源有限的实际应用中具有极高的价值。

局限性：
作者明确指出了两个局限性：

1. 时不变性： 该框架假设策略价值随时间保持不变。目前无法处理非平稳环境（即处理效应随时间演变的情况，例如由于新颖性或疲劳效应导致的演变）。
2. 重叠要求： 该方法要求每个目标策略相对于日志策略是绝对连续的（严格重叠）。这排除了目标策略会采取、但日志策略确定性地分配零概率的场景，这种情况可能出现在高度集中的自适应算法（如 UCB 类算法）中。

本文总结道，尽管存在这些局限性，但该框架为实践中常见的广泛类别的随机日志策略提供了一个鲁棒的解决方案。