Inference for Batched Bandits¶
讲者: Susan Murphy
讨论人: Stefan Wager
来源: OCIS (Online Causal Inference Seminar)
日期: 2020-05-19
主题: 因果推断
视频: https://www.youtube.com/watch?v=iLJ1hC5k-IQ · 幻灯片
本页据讲座录音的自动转写（ASR）生成。人名 / 术语 / 公式 / 具体的率与界可能被听错，关键处请对照视频或讲者论文核对。
相关论文¶
- 2002.03217 （尚未精读 —
talks read --id … --read-papers可补）
一、这场报告在讲哪条工作线¶
这场报告属于 「自适应数据收集 (adaptive data collection) 后的统计推断」 这一子方向。具体而言，它聚焦于批处理 (batched) 情境——赌博机算法不是逐个体地更新，而是在每收到一批 (batch) 大小为 n 的数据后才更新一次行动选择策略——并回答：当数据是由一个赌博机算法（如 Thompson sampling）收集时，我们还能不能用标准的「批内 OLS + 正态近似」来做假设检验和置信区间？如果不能，又该怎么做？
方向背景：
- 奠基与主流路线：经典结果如 Lai & Wei (1982) 给出了在线性回归中回归系数的渐近正态性，但那些结果依赖「设计矩阵的某个随机比例收敛到一个非随机极限」这一条件。在赌博机设置中，当处理效应为零或很小时，这个条件往往不成立（见报告 [0:25:38] 附近），导致 OLS 估计量的渐近分布不为正态。之前的文献（Villar et al., 2015; Deshpande et al., 2018; Nie et al., 2018; Shin et al., 2019）已经观察到这种非均匀收敛问题。
- 当前 frontier：近期工作有两条进路：
（1）自适应加权方案（如 Hadad et al., 2019 的 AW-AIPW）——通过数据依赖的权重调整，使聚合后的估计量重新满足 CLT；
（2）批内单独推断 + 聚合——即本报告的核心思路：不试图对全部数据做整体 OLS，而是每批各自算 OLS，并证明每批内的标准化统计量是渐近正态的，再将它们按批组合（为检验统计量或联合估计）。
- 本报告立足点：报告对应论文 arXiv 2002.03217 (Zhang, Janson, Murphy, 2020)。它直接应对上述非均匀收敛问题，提出了 Batched OLS (BOLS) 估计量，并证明其在弱条件下（包括批次内动作选择概率被截断）是渐近正态的，且对基线非平稳性 (non-stationarity in baseline reward) 具有鲁棒性。报告还通过模拟对比了 BOLS、OLS、W-decorrelated (Deshpande et al., 2018) 和 AW-AIPW (Hadad et al., 2019) 的表现。
领域内的关键工作（按转写 + 幻灯片提及）： - Lai & Wei (1982)：线性回归自适应性数据的渐近正态性所需条件。 - Deshpande et al. (2018)：W-decorrelated 估计量，一种调整版 OLS，需选择调参。 - Hadad et al. (2019)：Adaptively-Weighted AIPW (AW-AIPW)，通过自适应权重稳定方差。 - 本报告：Zhang, Janson, Murphy (2020)，批内分治推断。
二、最小内核 / 一个最简例子¶
2.1 符号与模型（固定于报告的两臂赌博机，批处理设置）¶
可观测数据： - 时间索引 \(t = 1, \dots, T\)（T 固定，批次数量），每个批次内有 \(i = 1, \dots, n\) 个独立个体（用户 / 试验对象），n 为批次大小（大样本渐近中取 \(n \to \infty\)）。 - 对每个 (t,i)：动作 \(A_{t,i} \in \{0,1\}\)（二值），由赌博机算法按概率 \(\pi_t^{(n)}\) 选择（\(\pi_t^{(n)}\) 是算法基于历史 \(H_{t-1}\) 计算出的概率；条件于历史，各 \(A_{t,i}\) 在该批次内 i.i.d. Bernoulli(\(\pi_t^{(n)}\))）。 - 潜在结果：\(Y_{t,i}(0), Y_{t,i}(1)\)（独立于所有批次间），但只观察到 \(R_{t,i} = Y_{t,i}(A_{t,i})\)（奖励）。 - 假设：\(Y_{t,i}(a) \overset{\text{i.i.d.}}{\sim} (\beta_a, \sigma^2)\)，即均值 \(\beta_a\)，方差 \(\sigma^2\)（可异方差，但报告假设同方差简化）。
参数 / 目标： - 处理效应 (treatment effect)：\(\Delta = \beta_1 - \beta_0\)。 - 我们想要做关于 \(\Delta\) 的假设检验或构造置信区间。
潜在不可观测 / 关键概念： - 概率 \(\pi_t^{(n)}\) 是条件于历史的随机变量，不会（在 \(\Delta = 0\) 或很小的情况下）随 \(n \to \infty\) 集中于一个非随机极限——这是 OLS 出问题的根源。
2.2 最简特例（d=1 无协变量，T=2 批，二值动作）¶
情形： - 批 1（\(t=1\)）：均匀随机化，\(\pi_1^{(n)} = 1/2\) 固定。 - 批 2（\(t=2\)）：算法不截断，直接用后验概率 \(\pi_2^{(n)} = P(\beta_1 > \beta_0 \mid H_1)\)。 - 设真实 \(\Delta = 0\)（零处理效应）。
发生了什么 [0:20:02–0:21:24]： - 因为 \(\Delta = 0\)，后验概率 \(\pi_2^{(n)}\) 在批 1 数据足够大时收敛到一个非退化的分布（均匀分布）。也就是说，不同模拟路径下，有的 \(\pi_2^{(n)} \to 0.9\)，有的 \(\to 0.1\)，有的停在 0.5——完全不集中。 - 此时，整个样本中动作 1 的比例 \(n^{-1} \sum_{t,i} A_{t,i}\) 无法被一个非随机常数标准化（这将导致 OLS 检验统计量的渐近分布不是正态）。 - 若我们坚持用「把两批数据合起来做 OLS + 用 CLT 近似」，检验会过度拒绝（Type-1 error inflation）[0:26:29–0:27:57]。
BOLS 思路 [0:31:40–0:33:30]： - 对每个批次单独计算 OLS（即分别估计 \(\hat{\beta}_{t,0}, \hat{\beta}_{t,1}\)）。 - 在每批内部，条件于历史，\(A_{t,i}\) 是 i.i.d. Bernoulli(\(\pi_t^{(n)}\))，所以该批内的 OLS 估计量是条件无偏的，且其方差可被该批内动作选择比例的样本矩一致估计。 - 即使 \(\pi_t^{(n)}\) 不集中到常数，每批内的样本比例除以概率的比也会收敛到 1（即 \( \frac{\frac{1}{n}\sum_i A_{t,i}}{\pi_t^{(n)}} \overset{P}{\to} 1\)），这是 BOLS 渐近正态性的关键。 - 最后，对 T 个批次的正态统计量做加权合并（如取简单平均）即可得到关于 \(\Delta\) 的全局检验。
直觉：把赌博机数据视为 T 个独立的、带有历史条件随机化的实验，逐个处理每个实验，再用它们自身内部的正态近似，就能绕开跨批次的不均匀收敛问题。
三、报告主体：讲者讲了什么¶
开场与动机 [0:00:05–0:01:30]
- 介绍合作者 Kelly Zhang 和 Lucas Janson，并启动 Q&A 流程。
1. 赌博机与 Thompson sampling 简介 [0:01:51–0:08:25]
- 用广告、数字健康、在线教育三个例子说明赌博机在现实中的应用。
- 给出两臂赌博机的符号：\(\beta_0, \beta_1\) 为两臂的均值，\(\pi_t\) 为时间 t 选择动作 1 的概率（由历史决定）。
- 演示 Thompson sampling：用高斯先验 + 高斯似然，每一步计算后验概率 \(P(\beta_1 > \beta_0 \mid \text{history})\) 并以此概率做出动作选择。
2. 为什么 after-study 推断不简单 [0:08:20–0:11:10]
- 潜在结果缺失机制是 MAR，似然可分解，但实际推断困难（Villar, Deshpande, Nie, Shin 等已指出）。
- 原因：赌博机算法为了最大化累积奖励，必然在好臂上投入更多样本，导致另一个臂样本不足 → 有偏估计。
3. 批处理赌博机与问题定义 [0:11:38–0:17:20]
- 情境：每个时间 t，做一批大小为 n 的试验，算法只在每批结束时更新（T 固定，n → ∞ 为渐近框架）。
- 符号：\(\pi_t^{(n)}\) 是条件于历史的选择概率（该批次内 i.i.d. 条件于历史）。
- 报告强调：即使截断 \(\pi_t^{(n)}\) 在 \([\pi_{\min}, \pi_{\max}]\) 内（常见于数字健康中），当 \(\Delta\) 很小时，\(\pi_t^{(n)}\) 仍不集中 [0:19:32–0:21:24]。
4. OLS 的非均匀收敛与非正态性 [0:23:14–0:27:20]
- 引述 Lai & Wei (1982) 的 CLT 要求：存在非随机常数序列 \(a_n\) 使得 \(\frac{\sum_{t,i} A_{t,i}}{a_n} \overset{P}{\to} 1\)。
- 当 \(\Delta = 0\) 时，这个要求不成立（Kelly 证明）。
- 通过模拟（T=25 批，不同 n 与信噪比）：OLS 的 95% CI 实际覆盖在信号弱时会严重低于名义水平（无论 n 多大，总存在某个小的 Δ 导致欠覆盖）[0:26:29–0:27:57]。
5. BOLS：核心思想与理论 [0:31:40–0:34:43]
- 关键观察：对每批内部，\(\frac{\frac{1}{n}\sum_i A_{t,i}}{\pi_t^{(n)}} \overset{P}{\to} 1\) (as n→∞)，即使 \(\pi_t^{(n)}\) 本身不集中到常数 [0:31:55–0:33:05]。
- BOLS 估计量：对每批 t，用该批内数据分别做 OLS，得到 \(\hat{\Delta}_t = \hat{\beta}_{t,1} - \hat{\beta}_{t,0}\)。
- 定理（简单固定截断版）[0:33:10–0:34:00]：在截断 + 矩条件下，
6. 模拟对比 [0:35:56–0:40:00]
- 对比方法：OLS（聚焦批内 CLT 近似）、W-decorrelated (Deshpande et al., 2018)、AW-AIPW (Hadad et al., 2019) 以及 BOLS。
- 平稳设置 [0:35:56–0:37:45]：
- OLS 的 Type-1 error 过高（未校正）。
- W-decorrelated 和 BOLS 的 Type-1 error 都很好（≤ 0.05），但 BOLS 的功率高于 W-decorrelated。
- AW-AIPW 在批数少时 Type-1 error 偏高。
- 非平稳基线（baseline 均值随时间变化，但处理效应固定） [0:38:15–0:39:45]：
- 只有 BOLS 保持了良好的 Type-1 error 控制（其他方法未针对非平稳设计）。
- 功率上 BOLS 依然不错。
7. 讨论与开放问题 [0:40:01–0:42:20]
- 再次强调非均匀收敛的根源——后验概率当作“非平滑函数”对待。
- 提出更广的问题：当团队想在赌博机数据上做中介分析、矩法估计等多种事后分析时，如何利用 BOLS 的渐近联合正态为这些更复杂的估计提供推断？[0:42:08–0:42:20]
8. 讨论者 Stefan Wager 的评论 [0:43:03–0:55:24]
- 用「两阶段自适应样本量设计」的简例说明了自适应停止如何破坏合并估计的正态性。
- 总结已有进路：置信序列、自适应加权（Hadad et al.）与批内推断（本报告），指出两者在深层思想（对每批单独标准化再聚合）上是相通的。
- 提出一个有意思的统一视角：BOLS 的聚合测试统计量是对 确定性权重（等权）的批内 z-值的平均；而优化功率则导向类似 Hadad 等人的方差稳定策略。
四、对应论文与开放问题¶
对应论文
- Zhang, K. W., Janson, L., & Murphy, S. A. (2020). Inference for Batched Bandits. arXiv:2002.03217.
（报告唯一明确引用的论文，转写 [0:01:30] 和讲者简介中匹配。）
报告中提及的其它文献
- Deshpande et al. (2018)：W-decorrelated 估计量（幻灯片第 25 页提到，但未给出 arXiv ID；转写 [0:35:18] 提到 "Deshpande et al."）。
- Hadad et al. (2019)：AW-AIPW（幻灯片第 25 页；转写 [0:35:18] 提到 "Hadad et al."）。
- Lai & Wei (1982)：作为 CLT 背景被引（幻灯片第 15 页）。
开放问题（每条来自转写/讨论的具体时间点）
-
研究更一般的「矩法事后分析」框架 [0:42:08–0:42:20]：
讲者指出，研究者事后还想做中介分析等多种矩类型统计推断；能否把 BOLS 的“批内独立正态”思路推广到更一般的估计方程或 M-估计？
（对用户：这刚好对接你熟悉的半参数理论与高阶影响函数——批内独立的联合正态性能否让跨批聚合高阶 U-统计量的推断变得可行？） -
BOLS vs. 自适应加权方法的统一与功率优化 [0:53:00–0:53:55]（Stefan 讨论）：
等权批内 z-检验与 Hadad 等人的方差稳定检验在深层有联系；一个有系统性的 功率优化（在给定 Type-1 error 约束下） 框架是什么？最优权重的形式是什么，如何依数据估计？
（用户：这涉及非渐近与渐近准则的权衡，可能用你的 minimax 与效率理论背景来切入。） -
处理效应本身也随时间变化的非平稳性 [0:38:50–0:38:58]：
讲者提到论文中考虑了基线非平稳，但还有“处理效应本身变化”的更一般情形——在这种情境下，BOLS 是否仍能提供有效的推断？如何定义检验假设的恰当目标？
（用户：动态处理效应的因果推断正是你的领域。） -
不截断赌博机概率的场景：
报告的大部分分析建立在概率截断假设上。如果实际算法不做截断（如标准 Thompson sampling），BOLS 的 CLT 是否仍然成立？需要何种新的正则性条件？
（转写 [0:20:02] 中非截断例子的非集中行为暗示了风险。）
Maintained by 陈星宇 · Homepage · Source on GitHub