跳转至

Target-Aware Sequential Inference: Pooled versus Stratified Anytime-Valid Designs

作者: Subir Hait
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2609.37873


一、领域脉络与小综述

这个方向是什么:本文属于"任意有效推断"(anytime-valid inference)与"自适应实验设计"的交叉地带。根本问题是:当数据不是独立同分布地一次性收集,而是由某个(可能自适应的)采样协议逐条产生、且研究者可以随时停下并做出结论时,如何构造在任意停止时间下都保持覆盖概率的置信区间或检验。这类方法以置信序列(confidence sequences)、e-values、赌式检验(betting)为核心工具,近年在大规模 A/B 测试、多臂老虎机、以及大语言模型评估等场景中迅速成为方法论热点。该子方向目前处于"工具已成熟、设计原则仍在整合"的阶段:单参数均值/处理效应的 anytime-valid 推断已有较完整的理论(Hoeffding 型、empirical-Bernstein 型、正态混合型边界),但"分层结构 + 目标加权 + 自适应分配"三者叠加时的最优设计问题,仍缺乏统一框架。

发展脉络:

  • 奠基工作:任意有效推断的根源可追溯到 Darling and Robbins (1967) 与 Robbins (1970) 的置信序列思想——利用鞅不等式构造对任意停止时间均匀有效的区间。这一思想在半个世纪后由 Howard et al. (2021) 系统化为非参数、非渐近的置信序列理论,给出基于 sub-Gaussian 与 empirical-Bernstein 条件的显式边界。本文的边界构造直接建立在这条线上。
  • e-values 与赌式检验:Shafer (2021) 的"testing by betting"将任意有效推断重新表述为赌徒与零假设之间的博弈,Vovk and Wang (2021) 进一步建立了 e-values 的合并与校准理论。这条线为本文提供了"为什么可以持续监测而不付多重比较代价"的底层逻辑——e-process 的乘积/鞅结构天然允许任意停止。
  • 自适应实验中的推断:Hadad et al. (2021) 处理了自适应策略下策略评估的置信区间问题,指出朴素估计量在数据依赖分配下会有偏差,需要用逆概率加权或 WLS 修正。本文的 Lemma 6.1(可预测采样下局部置信序列仍然有效)正是这一问题的任意有效版本——只要分配只依赖过去、不依赖当前结果,局部 e-process 在全局时间轴上仍是鞅。
  • 分层采样与分配:经典分层抽样理论(Neyman 1934; Kish 1965)给出了固定预算下方差最优的 Neyman 分配 n_j ∝ q_j σ_j。Étoré and Jourdain (2010) 将这一思想推广到自适应分层蒙特卡洛,用估计的层方差驱动分配比例收敛到最优。本文的 Theorem 6.1 是这条线在任意有效推断下的对应物,但目标函数从"估计方差"换成了"置信序列宽度"。
  • LLM 评估作为应用场景:Hendricks et al. (2021) 的 MMLU 建立了多任务基准的评估范式;Polo et al. (2024) 的 PromptEval 进一步引入多 prompt 模板的评估成本问题。本文把"学科"当作分层、"prompt-题目对"当作采样单元,将 LLM 评估重新表述为一个目标加权的序贯推断问题——这是该应用方向首次与任意有效推断框架直接对接。

子线索聚类:

  1. 置信序列的构造理论(Darling-Robbins 1967; Robbins 1970; Howard et al. 2021; Waudby-Smith and Ramdas 2024; Wang and Ramdas 2025):关注如何在最弱假设下获得最紧的任意有效边界。本文的 PrPl-BE 构造属于这一簇,其特点是利用可预测方差估计自适应地收紧边界。
  2. 自适应分配与 off-policy 推断(Hadad et al. 2021; Karampatziakis et al. 2021; Étoré and Jourdain 2010):关注数据收集机制与目标分布不一致时的修正。本文的 pooled 架构(重要性加权)和 stratified 架构(局部 CS 聚合)分别对应这一簇的两种极端策略。
  3. 多重性与同时推断(Bonferroni、union bound、家族误差控制):本文的 Section 7 用 Bonferroni 在 H 对系统上做家族误差控制,属于经典多重比较在任意有效框架下的直接移植。
  4. 排序与选择(ranking and selection; Paulson 1964; Kim and Nelson 2001; Kaufmann et al. 2016; Garivier and Kaufmann 2016):本文的"最佳系统识别"问题与 best-arm identification 共享目标——以最少的样本识别最优选项,但本文的贡献在于把分层目标加权结构嵌入其中。

这个方向在追问的核心问题:

  1. 何时可以停止? 任意有效推断的核心承诺是:研究者可以随时偷看数据并决定是否停止,而不破坏推断的有效性。这要求构造在"所有停止时间"上均匀有效的边界,而非仅在预设样本量上有效。
  2. 目标分布与采样分布不一致时如何推断? 当分层权重 q_j 与采样比例 π_j 不同(例如为了降低方差而过度采样高波动层),如何构造仍然有效的置信区间?本文给出两条路径:重要性加权(pooled)或分层聚合(stratified)。
  3. 分层粒度与推断效率的权衡? 分层越细,局部信息越丰富(支持事后重加权、局部报告),但多重性代价越大。本文的核心定量结果(Proposition 3.1)就是刻画这一权衡:在对称根号 n 边界下,分层架构的宽度是 pooled 的 √J 倍。
  4. 自适应分配能否在保持有效性的同时逼近最优? Theorem 6.1 回答:可以,只要分配比例是"可预测的"(只依赖过去),且探索概率不消失得太快。

⚠️ 作者的 framing(这是作者的说法):作者把问题拆成三个"设计层"——目标分布(target distribution)、推断架构(inference architecture)、采样策略(sampling policy)。他声称这三者经常被混淆,而本文的贡献是"解耦"它们:先定目标,再选架构,最后优化采样。他特别强调,架构选择可以主导采样策略的收益:在 PromptEval 回放中,pooled 架构比最优 stratified 分配节省约 99% 的采样成本,这个差距远大于任何采样策略微调能带来的改进。作者还刻意淡化了一个竞争路径——直接对分层目标估计量构造一个单独的置信序列(而非聚合 J 个局部 CS),理由是这会失去局部报告和事后重加权的能力。

张力:被引文献之间未见直接对立的结论,但存在一个值得注意的目标错位。经典 Neyman 分配(Étoré and Jourdain 2010; Neyman 1934)优化的是固定预算下的估计方差,而本文的边界率分配优化的是置信序列宽度的收敛指数。当边界是根号 n 型时,两者给出不同的分配律(n_j ∝ q_j σ_j vs n_j ∝ (q_j σ_j)^{2/3})。这不是矛盾,而是目标函数不同导致的真实差异——但读者需要注意,本文的 2/3 律并不否定 Neyman 分配在纯估计任务中的最优性。另一个潜在张力是:Karampatziakis et al. (2021) 的 off-policy 置信序列在理论上可以处理任意已知的采样比例,而本文的 pooled 架构在 π 与 q 差异过大时会因重要性权重范围膨胀而失效——作者用"可预测采样 + 探索下限"回避了这个问题,但没有给出最优的探索-利用权衡。

什么明显该被引 / 该存在、却没出现在 intro 里(值得去查的问题,不是答案):本文没有讨论多重比较的现代替代方案(如 closed testing、graphical approaches)在任意有效框架下的表现;没有引用 Waudby-Smith et al. (2024) 关于渐近任意有效推断的最新进展(虽然引了其 2021 年的 Annals 论文);没有提及 conformal prediction 的任意有效版本(如 Vovk 的 conformal e-prediction),尽管这与 LLM 评估的不确定性量化直接相关;也没有讨论贝叶斯任意有效推断(如公开贝叶斯 e-values)。这些缺口可能是作者有意为之(保持频率学派框架的纯粹性),也可能是领域整合尚未完成。


二、最核心、最简单的例子 / 数学内核

第一步:符号、模型、可观测数据

先建立全文的记号地基,后面所有技术细节都建立在这套记号上:

  • 分层:\(j \in \{1, \dots, J\}\) 是预先定义的互斥分层(如 MMLU 的 57 个学科)。每个分层有一个层内均值差 \(\delta_j = \mathbb{E}[D_{j,r}]\),其中 \(D_{j,r}\) 是第 \(j\) 层第 \(r\) 次观测到的配对结果差(如系统 A 与系统 B 在同一题目上的正确性差异)。
  • 目标分布:\(Q = (q_1, \dots, q_J)\),\(q_j \ge 0\),\(\sum_j q_j = 1\)。这是科学上关心的总体构成(如部署环境中各学科的出现频率),它定义了目标估计量
    \[\Delta_Q = \sum_{j=1}^J q_j \delta_j.\]
    \(Q\) 是已知且固定的——它是研究者在实验开始前就声明好的权重,不是要估计的对象。
  • 采样分布:\(\pi_t(j) = \mathbb{P}(A_t = j \mid \mathcal{H}_{t-1})\),其中 \(A_t\) 是第 \(t\) 个全局时间步选择的分层,\(\mathcal{H}_{t-1}\) 是截至 \(t-1\) 的全部历史。\(\pi_t\) 是可预测的(只依赖过去),但可以是自适应的(依赖过去的观测值)。这是全文有效性的关键假设。
  • 可观测数据:研究者实际看到的是序列 \(\{(A_t, D_t)\}_{t=1}^\infty\),其中 \(D_t\) 是第 \(A_t\) 层的一个新观测。层内观测是 i.i.d. 的,但全局序列不是——因为 \(A_t\) 的分布随时间变化。每个分层 \(j\) 有一个局部时间 \(N_j(t) = \sum_{s=1}^t \mathbb{1}\{A_s = j\}\),即到全局时间 \(t\) 为止第 \(j\) 层被访问的次数。
  • 层内估计量:\(\bar{D}_{j,n} = \frac{1}{n} \sum_{r=1}^n D_{j,r}\) 是第 \(j\) 层基于 \(n\) 个局部观测的样本均值。
  • 置信序列(CS):一族置信区间 \(\{C_n\}_{n \ge 1}\),满足对任意停止时间 \(\tau\),\(\mathbb{P}(\theta \in C_\tau) \ge 1 - \alpha\)。与固定样本置信区间不同,CS 允许数据依赖的停止规则而不破坏覆盖。
  • 半宽函数:\(b_j(n)\) 表示第 \(j\) 层基于 \(n\) 个观测的 CS 半宽。本文考虑两类:范围型(range-only,只利用 \(D_j \in [-1,1]\) 的有界性)和方差自适应型(empirical-Bernstein,利用可预测方差估计收紧边界)。关键假设是 \(b_j(n) = r_j L(n) n^{-\beta}\),其中 \(\beta > 0\) 是边界衰减指数,\(L\) 是慢变化函数。根号 \(n\) 边界对应 \(\beta = 1/2\)。

第二步:最小内核——J=2 的对称例子

把论文的所有一般性假设剥掉,留下最核心的决策问题。假设只有 \(J=2\) 个分层,目标权重 \(Q = (1/2, 1/2)\),两个分层有相同的方差 \(\sigma^2\) 和相同的 CS 半宽函数 \(b(n) = r n^{-1/2}\)(根号 \(n\) 边界)。目标是以任意有效的方式判断 \(\Delta_Q = (\delta_1 + \delta_2)/2\) 是否大于 0。

Pooled 架构:每个时间步以概率 \(1/2\) 从分层 1 或分层 2 采样,记录 \(D_t\),然后对序列 \(\{D_t\}\) 直接构造一个 CS。因为 \(\mathbb{E}[D_t] = \Delta_Q\),且 \(D_t \in [-1,1]\),所以可以用标准的 Hoeffding 型 CS。经过 \(N\) 个全局观测后,半宽约为 \(r / \sqrt{N}\)。

Stratified 架构:每个分层分别维护自己的 CS。如果均匀分配,每层得到 \(N/2\) 个观测,每层 CS 半宽为 \(r / \sqrt{N/2} = \sqrt{2} r / \sqrt{N}\)。聚合后的目标 CS 半宽为

\[\frac{1}{2} \cdot \frac{\sqrt{2} r}{\sqrt{N}} + \frac{1}{2} \cdot \frac{\sqrt{2} r}{\sqrt{N}} = \frac{\sqrt{2} r}{\sqrt{N}}.\]
与 pooled 的 \(r / \sqrt{N}\) 相比,分层架构的宽度是 pooled 的 \(\sqrt{2}\) 倍。这就是 Proposition 3.1 在 \(J=2\) 时的退化情形:分层架构为局部保证付出的代价是 \(\sqrt{J}\) 的宽度膨胀。

为什么 2/3 指数会出现:现在假设分层数 \(J\) 很大,且各层方差不同。在分层架构中,目标 CS 半宽是 \(\sum_j q_j b_j(n_j)\)。给定总预算 \(N\),最优分配问题是

\[\min_{n_j \ge 0, \sum_j n_j = N} \sum_j q_j r_j n_j^{-\beta}.\]
拉格朗日乘子法给出 \(n_j \propto (q_j r_j)^{1/(1+\beta)}\)。当 \(\beta = 1/2\)(根号 \(n\) 边界)时,\(n_j \propto (q_j r_j)^{2/3}\)——这就是论文标题中"2/3 法则"的由来。注意它与经典 Neyman 分配 \(n_j \propto q_j \sigma_j\)(对应 \(\beta = 1\),即方差以 \(n^{-1}\) 衰减)不同。核心洞察是:置信序列的宽度优化与估计方差的优化是两个不同的目标函数,它们给出不同的分配律。

这个例子揭示了全文的核心张力:pooled 架构通过重要性加权把问题压缩为"单均值推断",避免了多重性代价,但要求 \(\pi_t\) 与 \(q\) 的比值有界(否则重要性权重爆炸);stratified 架构天然支持局部报告和事后重加权,但付出 \(\sqrt{J}\) 的宽度代价。论文的结论是:如果科学问题只需要一个目标加权答案,pooled 架构在效率上几乎总是占优;只有当局部保证本身是科学目标时,分层架构才值得。


三、这篇论文做了什么

三句话:① 论文研究在异质性分层下、目标为加权总体均值差 \(\Delta_Q\) 的序贯推断问题,比较"直接对目标采样并构建单一 pooled 置信序列"与"各层分别构建置信序列再聚合"两种架构的统计效率;② 核心工具是任意有效置信序列(empirical-Bernstein 型)与可预测自适应采样协议,推导出分层架构下宽度最优的分配律 \(n_j \propto (q_j r_j)^{1/(1+\beta)}\),在根号 \(n\) 边界下即 2/3 指数;③ 主要结论是 pooled 架构在仅需目标级推断时显著优于分层架构(PromptEval 回放中节省约 99% 采样),且方差自适应边界比分配策略的精细调优更重要。

关键设定与假设:

  1. 配对观测与有界性:每个观测 \(D_t\) 是配对比较结果(如两个系统在同一题目上的正确性差异),取值于 \([-1,1]\)。这个有界性假设是 Hoeffding 引理和 empirical-Bernstein 边界的前提。相比更一般的 sub-Gaussian 假设,有界性更强但允许完全非参数的处理。
  2. 可预测采样:\(\pi_t\) 只依赖 \(\mathcal{H}_{t-1}\),不依赖当前未观测的 \(D_t\)。这是 Lemma 6.1 成立的充分条件——它保证局部 e-process 在全局时间轴上仍是鞅。这个假设比"固定比例采样"宽松得多,但比"完全自适应(依赖当前结果)"严格。论文没有处理后者,因为那需要额外的鞅修正。
  3. 层内 i.i.d.:每个分层内部的观测独立同分布。这排除了层内时间趋势或相关性。对于 LLM 评估场景,这意味着同一学科内的题目- prompt 对被假设为可交换的——这是一个理想化假设,因为题目之间可能存在内容泄漏或难度聚类。
  4. 目标分布已知:\(Q\) 是预先指定的,不是从数据中估计的。如果 \(Q\) 本身有不确定性,需要进入 Section 5 的鲁棒框架。
  5. 正性条件:\(\pi_t(j) > 0\) 当 \(q_j > 0\),且重要性权重 \(q_j/\pi_t(j)\) 有界。后者是 pooled 架构有效性的关键——如果某个分层被极度欠采样,权重会爆炸,CS 宽度也会爆炸。

主要结果:

  • Proposition 3.1(架构权衡):在对称根号 \(n\) 基准下,分层架构的最优宽度是 pooled 架构的 \(\sqrt{J}\) 倍。这个结果是构造性的:它给出了分层架构的宽度下界(通过 Cauchy-Schwarz 或 Jensen),并指出 pooled 架构可以达到更紧的宽度。直觉:分层架构必须同时维持 \(J\) 个局部 CS,每个都需要足够的样本才能收窄;而 pooled 架构把所有样本都用于一个目标估计量。这个 \(\sqrt{J}\) 因子是"局部保证"的入场券。
  • Proposition 4.2(边界率分配律):在分层架构中,若局部 CS 半宽为 \(b_j(n) = r_j L(n) n^{-\beta}\),则宽度最优的分配是 \(n_j \propto (q_j r_j / c_j)^{1/(1+\beta)}\)。证明路线:拉格朗日乘子法 + 凸性验证。关键点:指数 \(1/(1+\beta)\) 是边界形状的直接推论——边界越陡(\(\beta\) 越大),最优分配越接近均匀;边界越平,越应该把样本集中在高权重或高方差的层。当 \(\beta = 1/2\) 时得到 \(2/3\) 指数,这是全文最常被引用的公式。
  • Theorem 6.1(自适应追踪):在可预测采样下,若每层观测 i.i.d. 且有界,则按估计的 \((q_j \hat{\sigma}_j)^{2/3}\) 比例分配样本(带探索项 \(\varepsilon_t\)),实际分配比例几乎必然收敛到最优比例。证明路线:鞅大数定律 + Borel-Cantelli + 强一致性。关键点:探索项 \(\varepsilon_t\) 必须满足 \(\sum_t \varepsilon_t = \infty\)(保证每层被访问无穷多次)且 \(\varepsilon_t \to 0\)(保证不偏离最优比例)。这个结果把 Section 4 的静态最优分配推广到在线学习场景。
  • Theorem 6.2(任意有效目标区间):在 Lemma 6.1 的条件下,聚合后的目标区间 \([\sum_j q_j L_{j,t}, \sum_j q_j U_{j,t}]\) 是 \(\Delta_Q\) 的任意有效置信区间。证明:直接来自局部 CS 的联合覆盖事件——如果每个局部 CS 以概率 \(1 - \alpha/J\) 覆盖 \(\delta_j\),则联合覆盖概率至少 \(1 - \alpha\)(Bonferroni)。注意:这里用的是局部 CS 的同时覆盖,而非逐点覆盖,因此不需要对时间做额外修正。
  • Section 7(家族误差控制):将上述框架扩展到 \(K\) 个系统的两两比较,用 Bonferroni 在 \(H = \binom{K}{2}\) 对上做修正,得到家族级任意有效的最佳系统识别规则。证明:直接并集界。这个结果本身不新,但论文将其嵌入目标感知框架,使得采样分配可以针对"识别最佳系统"这一目标优化。

证明路线与技术技巧:

  1. 时间变换(time-changing):Lemma 6.1 的核心技巧是把局部时间 \(N_j(t)\) 视为全局时间 \(t\) 的一个随机时间变换。因为 \(\pi_t\) 可预测,\(N_j(t)\) 是停时,局部 e-process 在停时处的期望仍然受控。这个论证是"可选停时 + 鞅"的经典组合,但论文将其用于自适应采样协议,而非固定采样。
  2. 可预测方差估计:PrPl-BE 构造的关键是使用 \(\hat{\sigma}_{i-1}^2\)(基于过去数据的方差估计)作为 betting 分数。由于 \(\hat{\sigma}_{i-1}^2\) 可预测,整个 betting 过程仍是鞅,不需要额外的覆盖修正。这是 Waudby-Smith and Ramdas (2024) 的贡献,本文将其嫁接到分层结构上。
  3. 正则变化边界:论文假设边界半宽 \(b_j(n) = r_j L(n) n^{-\beta}\) 是正则变化函数。这个假设允许统一处理 Hoeffding(\(\beta = 1/2\),\(L\) 含 \(\sqrt{\log}\) 项)、empirical-Bernstein(\(\beta = 1/2\),\(L\) 含方差估计)和正态混合边界。分配律的推导只依赖 \(\beta\),不依赖 \(L\) 的具体形式,这使结果具有跨边界的普适性。
  4. 凸优化/KKT:Section 5 的鲁棒分配问题通过引入最小不利混合 \(\bar{Q}\) 转化为凸优化,KKT 条件给出闭式解。技巧:将 minimax 问题转化为对偶问题,利用强对偶性保证解的存在性。

真实例子与应用:

  • 合成数据实验(Section 8):\(J=4\) 个分层,目标权重 \(Q = (0.55, 0.20, 0.15, 0.10)\),层内均值差 \(\delta = (0.08, 0.04, 0.12, 0.03)\),方差从 0.14 到 0.95 不等。实验验证了三个结论:(1) 方差自适应边界(PrPl-BE)比范围型边界节省约 40% 的样本;(2) 最优分配 \(q^{2/3}\) 比 \(Q\)-比例分配节省约 10-15% 的样本;(3) 边界选择比分配策略的精细调优影响更大。
  • PromptEval 回放(Section 10):使用 MMLU 的 57 个学科作为分层,15 个 LLM 在 100 个 prompt 模板下的正确率数据。固定领先对(Llama-3-70B-Instruct vs Mixtral-8x7B-Instruct-v0.1)后,pooled 架构中位停止时间为 305 个评估单元,而最佳 stratified 分配需要 23,985 个单元(表 9 与表 10 对比),节省 98.7-99.0%。这个例子说明架构选择可以比采样策略优化带来大得多的效率提升——这是论文最有力的实证卖点。但论文也谨慎指出,这是"固定领先对"后的条件比较,不是完整的排名推断。

🔎 结论是否比证明窄:论文的证明严格覆盖了:(a) 可预测采样下局部 CS 的任意有效性(Lemma 6.1);(b) 对称根号 \(n\) 基准下分层架构的 \(\sqrt{J}\) 宽度惩罚(Proposition 3.1);(c) 正则变差边界下的最优分配律(Proposition 4.2);(d) 自适应分配的几乎必然收敛(Theorem 6.1)。但论文的表述有时超出证明范围:例如,Section 10 的"99% 节省"是特定数据集、特定边界构造、特定领先对下的观测值,不是一般性定理;论文在 Section 12.1 也承认了这一点。另一个值得注意的窄化是:Theorem 6.1 的收敛性依赖于每层 i.i.d. 和方差估计的一致性,如果层内分布随时间漂移(如 LLM 评估中题目难度随测试进度变化),收敛性可能失效。论文没有给出漂移情形下的鲁棒性保证。


四、开放问题

  1. 有限样本最优分配:Proposition 4.2 的 2/3 法则是渐近最优的(在正则变差边界下)。但有限样本下,边界中的对数项和慢变化函数 \(L(n)\) 会改变最优分配。论文 Remark 4.1 建议用数值优化求解精确有限样本问题,但没有给出可操作的算法或误差界。要确认这是否是真 gap,去读近期关于"有限样本最优分配"的文献(如最优赌徒分数设计)——如果已有数值方法,则本文的贡献只是渐近启发式;如果文献中只有启发式,则这是一个可做的方向。

  2. 依赖结构下的任意有效性:论文假设层内观测 i.i.d.,但 LLM 评估中同一 prompt 模板在不同题目上的表现可能相关(prompt 效应),同一题目在不同 prompt 下的表现也可能相关(题目效应)。将 Lemma 6.1 推广到弱依赖(如 \(\alpha\)-混合或 \(\phi\)-混合)情形,需要新的鞅不等式。扎根点:Section 12.2 明确承认"依赖结构需要单独发展"。

  3. 自适应停止与事后选择的交互:论文的 Section 7 用 Bonferroni 控制家族误差,但停止规则本身可以依赖所有历史数据(包括未选中的系统)。在"先看数据再选系统"的设定下,Bonferroni 是否仍然 tight?扎根点:Section 12.4 提到"更紧的逐步方法"是未来工作。这个问题与 best-arm identification 的文献直接相关——那里的 lower bound 通常假设停止规则是"数据依赖的",但本文的构造没有利用这一结构。

  4. 目标不确定性的更一般模型:Section 5 假设目标集合是有限个点的凸包。如果目标集合是无穷维的(如所有 Lipschitz 连续的目标函数),minimax 最优分配是否仍然存在?扎根点:Proposition 5.1 的证明依赖有限维凸优化的 KKT 条件,推广到无穷维需要泛函分析工具(如 minimax 定理的无穷维版本)。

  5. 重要性权重的方差控制:Pooled 架构在 \(\pi_t\) 与 \(q\) 差异大时,重要性权重 \(q_j/\pi_t(j)\) 的方差会膨胀。论文用探索项 \(\varepsilon_t\) 保证 \(\pi_t\) 有下界,但没有给出最优的探索-利用权衡。扎根点:Section 6.3 的 \(\varepsilon_t\) 选择是启发式的(\(\varepsilon_t = \min\{1, t^{-0.25}\}\)),没有理论指导。这个问题与 bandit 文献中的"探索-利用困境"直接相关,但目标函数是 CS 宽度而非遗憾。

提醒:要确认上述哪条是真 gap,去读同子领域近期约 5 篇的 intro——都指向它 = 共识(真 gap),互相打架 = 机会。特别是第 1 条(有限样本最优分配)和第 4 条(无穷维目标集合),前者在 bandit 文献中已有大量工作,后者在 robust optimization 文献中也有平行发展,需要仔细定位本文的独特贡献点。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论