The Role of Contextual Information in Best Arm Identification¶
作者: Masahiro Kato, Kaito Ariu
来源: JMLR
主题: 数理统计 / 假设检验
相关性: 4/10
机构绿灯: University of Tokyo(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文研究的核心问题是带固定置信度的最优臂识别(Best Arm Identification, BAI),这是多臂老虎机(Multi-Armed Bandit, MAB)问题中的一个纯探索(pure exploration)任务。与经典的遗憾最小化(regret minimization)不同,BAI 的目标不是在整个过程中最大化累积奖励,而是以尽可能少的样本(即最小的期望停止时间)以至少 1−δ 的概率找出平均奖励最大的那个臂。本文的特殊之处在于引入了上下文(contextual)信息:每一轮在决策前可以观测到一个协变量 X_t,但最终要识别的目标并不是"给定上下文条件下的最优臂",而是在上下文分布上边际化后的平均奖励最大的臂。这个设定介于传统的无上下文 BAI 与完全条件化的上下文 Bandit 之间,其核心统计问题是:如何利用与目标参数(边际均值)相关的辅助信息(上下文)来加速序贯假设检验/决策过程。
发展脉络¶
-
奠基工作:BAI 的统计复杂度刻画。本文的直接理论基石是 Garivier 和 Kaufmann (2016) 的工作,该工作首次在单参数指数族框架下给出了 BAI 问题实例相关的样本复杂度下界,并提出了 Track-and-Stop (TS) 策略,证明其渐近最优性。这是无上下文 BAI 的黄金标准,本文的所有结果都是以此为参照系展开的。
-
主要进展:从无上下文到有上下文。本文的贡献在于将上述框架推广到有上下文的情形。作者指出,尽管已有一些工作(如 Tekin and van der Schaar 2015; Guan and Jiang 2018; Deshmukh et al. 2018)考虑了带上下文的 BAI,但它们都没有讨论实例特定的最优性——即没有回答"给定一个具体的问题实例,最少需要多少样本"这个核心问题。本文填补了这一空白。
-
当前 frontier:线性模型与更一般的结构。与本文最接近的后续工作是 Qin and Russo (2022),以及在线性 Bandit 框架下的工作(Soare et al. 2014; Xu et al. 2018; Tao et al. 2018; Fiez et al. 2019; Jedra and Proutiere 2020)。这些工作考虑了利用线性结构来提升 BAI 效率,但本文的设定(边际化目标 + 一般上下文分布)与它们不同,且本文明确指出了其下界推导和最优策略的独特性。
-
因果推断的视角。本文在引言中明确将问题与实验设计(experimental design)联系起来,特别是与 van der Laan (2008)、Hahn et al. (2011)、Tabord-Meehan (2018) 等关于利用协变量提高平均处理效应(ATE)估计效率的工作相关联。这是一个重要的 framing:BAI 可以被看作是一个特殊的序贯实验设计问题,而上下文信息的作用类似于因果推断中的协变量调整(covariate adjustment)——它不改变目标参数,但可以降低估计的方差,从而加速决策。
子线索聚类¶
- 线索一:BAI 的信息论下界与最优策略。核心文献是 Kaufmann et al. (2016)、Garivier and Kaufmann (2016) 以及 Kaufmann and Koolen (2021)。这条线索关注如何用 change-of-measure 参数和 KL 散度来刻画问题的固有难度,并设计匹配下界的采样策略。本文的 Theorem 2 和 Theorem 5 属于此线索。
- 线索二:利用结构(上下文/线性)加速探索。核心文献是 Soare et al. (2014)、Xu et al. (2018)、Tao et al. (2018)、Fiez et al. (2019)、Jedra and Proutiere (2020) 以及 Qin and Russo (2022)。这条线索关注如何利用协变量或线性假设来降低样本复杂度。本文的 CTS 算法属于此线索,但其目标(边际化均值)和策略(在上下文-臂对层面分配样本)是独特的。
- 线索三:因果推断中的自适应实验设计。核心文献是 van der Laan (2008)、Hahn et al. (2011)、Tabord-Meehan (2018)、Kato et al. (2020, 2024a)。这条线索关注如何通过依协变量调整的随机化来高效估计 ATE。本文将其作为应用背景,但并未深入探讨估计量的性质,而是聚焦于序贯决策的停止时间。
这个方向在追问的核心问题¶
- 如何定义并计算有上下文时的实例相关复杂度? 即,给定上下文分布 ζ 和条件均值函数 (μ_{a,x}),最优的样本分配比例 w* 是什么?本文通过一个 minimax 问题(式 3)给出了答案。
- 如何设计一个能自适应地追踪最优分配的算法? 由于 μ 和 ζ 未知,算法必须在不完全信息下逐步逼近最优分配。本文的 CTS 算法通过"估计-优化-采样"的循环来解决这一问题。
- 上下文信息何时有用,何时无用? 本文的定理 3 和实验表明,当上下文与奖励相关时(ρ 较大),利用上下文可以显著降低样本复杂度;当上下文与奖励无关时,CTS 退化为标准的 TS 算法。这回答了"上下文信息在 BAI 中的价值"这一根本问题。
⚠️ 作者的 framing¶
作者将本文的贡献定位为:首次在带上下文的 BAI 中建立了实例相关的下界,并给出了渐近最优的算法。作者在引言中强调,尽管已有上下文 BAI 的工作,但"their instance-specific optimality has never been discussed"(它们的实例特定最优性从未被讨论过)。作者将这一 gap 归因于上下文带来的技术困难:最优分配不再是简单的常数,而是依赖于上下文分布的复杂函数。作者还特别指出,与 Russac et al. (2021) 的 A/B/n 测试(有对照组)不同,本文处理的是无对照组的纯 BAI 问题,且需要处理多个最优分配候选的问题。
张力¶
- 未见明显对立引用。本文引用的工作之间没有直接的矛盾。不过,一个值得注意的张力存在于"利用上下文"与"模型鲁棒性"之间:本文的 CTS 算法(以及其最优性证明)依赖于对条件均值函数 (μ_{a,x}) 的准确估计(在指数族假设下)。如果模型被错误设定(例如,真实条件均值不是线性的),CTS 的最优性是否还能保证?本文在引言中提到了模型误设的风险,但并未给出理论分析。这是一个潜在的、值得研究者去查证的 gap。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
在展开论文的技术细节之前,我们先建立一个最小的记号框架。这是理解全文的基础。
- 时间与样本:\(t = 1, 2, \ldots\) 表示离散的时间轮次。\(T\) 为总轮数(可能随机)。
- 上下文(可观测):\(X_t \in \mathcal{X}\) 是第 \(t\) 轮观测到的上下文,服从分布 \(\zeta\)。在有限上下文情形下,\(\mathcal{X} = \{1, \ldots, M\}\),\(\zeta_x = P(X_t = x)\)。这是可观测的随机变量。
- 臂(动作):\(A_t \in [K] = \{1, \ldots, K\}\) 是第 \(t\) 轮选择的臂。这是由算法决定的决策变量。
- 潜在结果(不可观测):\(R_{t,a}\) 是第 \(t\) 轮选择臂 \(a\) 会得到的奖励。这是潜在(counterfactual)量,我们只能观测到被选中臂的奖励 \(R_t = \sum_{a=1}^K \mathbf{1}\{A_t = a\} R_{t,a}\)。这对应因果推断中的 SUTVA 假设(无干扰、无隐藏版本)。
- 条件均值(参数):\(\mu_{a,x} = E[R_{t,a} | X_t = x]\) 是给定上下文 \(x\) 时臂 \(a\) 的条件平均奖励。在指数族设定下,条件分布 \(P_{a,x}\) 完全由 \(\mu_{a,x}\) 决定。这是要估计的未知参数。
- 边际均值(目标 estimand):\(\mu_a = E[R_{t,a}] = \sum_{x \in \mathcal{X}} \zeta_x \mu_{a,x}\) 是臂 \(a\) 在上下文分布上边际化的平均奖励。这是我们要识别的目标参数。最优臂定义为 \(a^* = \arg\max_a \mu_a\)。
- 分配比例(决策变量):\(w_{a,x} \in [0,1]\) 表示在上下文 \(x\) 出现时,将样本分配给臂 \(a\) 的比例。\(\sum_{a=1}^K w_{a,x} = 1\) 对所有 \(x\) 成立。\(W\) 是所有可行分配的集合。
- 停止时间:\(\tau_\delta\) 是算法在置信水平 \(1-\delta\) 下停止并做出决策的随机时间。
- KL 散度:\(KL(P_{a,x}, Q_{a,x})\) 表示在上下文 \(x\) 下,臂 \(a\) 的真实分布与备择分布之间的 KL 散度。在指数族中,它可写成关于均值 \(\mu_{a,x}\) 和 \(\lambda_{a,x}\) 的函数 \(kl(\mu_{a,x}, \lambda_{a,x})\)。
数据生成机制(模型): 1. 每一轮 \(t\),环境从 \(\zeta\) 中抽取上下文 \(X_t\)。 2. 算法根据历史观测(包括 \(X_t\))选择臂 \(A_t\)。 3. 环境从条件分布 \(P_{A_t, X_t}\) 中抽取奖励 \(R_t\)。 4. 算法观测到 \((X_t, A_t, R_t)\),更新内部状态。
可观测数据:\(\{(X_t, A_t, R_t)\}_{t=1}^{\tau_\delta}\)。注意,我们观测不到未选择臂的潜在结果 \(R_{t,a}\)(\(a eq A_t\)),也不知道真实的 \(\zeta\) 和 \(\mu_{a,x}\)。
第二步:最小内核¶
现在,我们剥离所有技术细节,聚焦于支撑整篇论文的那个最小内核。这个内核可以概括为一个带约束的优化问题,它同时回答了两个问题:"最优分配是什么?"和"最少需要多少样本?"
核心思想:BAI 的本质是一个假设检验问题。我们需要区分"臂 1 是最优的"这个原假设和"某个其他臂是最优的"备择假设。样本复杂度的下界来自于区分两个相似的概率模型所需的最小信息量。
最小内核(两臂、单上下文、高斯且已知方差):
考虑最简单的情形:\(K=2\) 个臂,\(\mathcal{X} = \{x_0\}\) 是单点(即无上下文),奖励服从高斯分布 \(N(\mu_a, 1)\),方差已知。真实模型为 \(\nu\),其中 \(\mu_1 > \mu_2\),最优臂为 1。
-
备择模型:考虑一个备择模型 \(\nu'\),其中臂 2 是最优的(即 \(\mu'_2 > \mu'_1\)),但其他方面与 \(\nu\) 尽可能接近。为了区分 \(\nu\) 和 \(\nu'\),我们需要收集足够的证据。
-
Change-of-measure 参数:任何 \(\delta\)-PAC 算法在停止时,其决策错误的概率不超过 \(\delta\)。利用 change-of-measure 参数(或 Neyman-Pearson 引理),可以证明:在 \(\nu\) 下,算法停止时,观测到的对数似然比必须足够大。这导致一个下界:
\[E_\nu[\tau] \geq \frac{d(\delta, 1-\delta)}{\inf_{\nu' \in Alt(\nu)} \sum_{a=1}^2 E_\nu[N_a(\tau)] KL(P_a, P'_a)}\]其中 \(N_a(\tau)\) 是臂 \(a\) 被拉动的次数,\(Alt(\nu)\) 是备择模型集合。 -
最优分配:为了最大化区分效率(即最小化分母),我们需要选择每个臂的拉动比例 \(w_a = E[N_a(\tau)]/E[\tau]\),使得在"最坏情况"备择模型下,总 KL 散度最大。这导致一个minimax 问题:
\[\frac{1}{T^*(\nu)} = \max_{w \in \Delta_K} \min_{\nu' \in Alt(\nu)} \sum_{a=1}^2 w_a KL(P_a, P'_a)\]其中 \(\Delta_K\) 是概率单纯形。这个问题的解 \(w^*\) 就是最优分配比例,而 \(T^*(\nu)\) 就是特征时间(characteristic time)。 -
为什么这个内核是核心? 因为本文的所有结果——无论是下界(Theorem 2, 5)还是上界(CTS 算法)——都是围绕这个 minimax 问题展开的。在无上下文时,\(w^*\) 是一个常数向量;在引入上下文后,\(w^*\) 变成了一个依赖于上下文 \(x\) 的函数 \(w^*_{a,x}\),并且目标函数中的 KL 散度需要按上下文分布 \(\zeta\) 加权。上下文的作用是增加了分配的"自由度":我们可以在信息量更大的上下文状态下,更多地采样那些有助于区分最优臂的臂,从而降低总样本数。
这个最小内核的数学本质:它揭示了 BAI 的样本复杂度由一个凸优化问题决定,其目标函数是 KL 散度的加权和,约束是分配比例的可行域。本文的主要技术贡献在于: 1. 在连续上下文(高斯)情形下,证明了最优分配可以通过一个半定规划(SDP)求解(Theorem 3)。 2. 在有限上下文(指数族)情形下,证明了最优分配是非唯一的,并给出了一个凸集的描述(Theorem 5, Lemma 13)。 3. 设计了 CTS 算法,其核心是一个在线估计-优化的循环,能够渐近地追踪最优分配集合中的某个点。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在带上下文的随机 Bandit 中,如何以固定置信度、最小化期望样本数来识别边际平均奖励最大的臂(而非条件最优臂),并刻画该问题的实例相关样本复杂度。
- 核心工具/方法:基于 change-of-measure 参数的信息论下界;将最优分配问题转化为一个minimax 优化问题;设计了 Contextual Track-and-Stop (CTS) 算法,其采样规则通过求解一个经验估计的优化问题来追踪最优分配,停止规则基于广义似然比检验(GLRT)。
- 主要结论:推导了上下文 BAI 的实例相关下界(Theorem 2, 5);在两类特殊情形下(两臂高斯连续上下文、有限上下文指数族)给出了最优分配的显式或可计算刻画;证明了 CTS 算法的渐近最优性(Theorem 4, 19),即其期望停止时间与下界之比趋于 1。
关键设定与假设¶
- 设定:每轮先观测上下文 \(X_t \sim \zeta\),再选择臂 \(A_t\),观测奖励 \(R_t\)。目标是识别 \(\arg\max_a \mu_a = \arg\max_a E[R_{t,a}]\)。
- 假设 1(指数族):在有限上下文情形(Section 4-6),给定上下文 \(x\) 和臂 \(a\),奖励分布属于单参数指数族(式 1),其均值 \(\mu_{a,x}\) 是唯一参数。这保证了 KL 散度可写成 \(kl(\mu_{a,x}, \lambda_{a,x})\) 的形式,且 \(kl\) 是凸的。相比 Garivier and Kaufmann (2016) 的假设,这里允许不同上下文下均值不同,但要求分布形式已知。
- 假设 2(高斯性):在连续上下文情形(Section 3),假设 \((R_{t,1}, R_{t,2}, X_t)\) 联合服从多元高斯分布,且协方差结构已知(均值未知)。这是一个很强的参数假设,它使得条件分布 \(R_{t,a}|X_t=x\) 仍是高斯,且方差为常数 \(\sigma'^2_a\)。这个假设是获得显式解(Theorem 3)的关键。
- 假设 3(唯一最优):\(\Omega\) 要求最优臂唯一(\(\mu_{a^*} > \mu_a\) for all \(a eq a^*\))。这是 BAI 问题的标准假设,避免平局。
- 假设 4(上下文分布已知或可估计):在有限上下文情形,\(\zeta\) 可以是未知的,但 CTS 算法需要估计它(通过 \(\hat{\zeta}_x(t) = N_x(t)/t\))。在连续情形,\(\zeta\) 是标准高斯(或已知参数)。
- 相比已有工作的放宽/强化:相比无上下文 BAI(Garivier and Kaufmann 2016),本文放宽了"无上下文"的限制,允许利用协变量信息;相比线性 Bandit BAI(Jedra and Proutiere 2020),本文强化了目标(识别边际最优而非条件最优),但弱化了模型(不要求线性结构,但要求指数族/高斯)。
主要结果¶
- Theorem 2 (一般下界):对于任何 \(\delta\)-PAC 策略,期望停止时间满足 \(E_\nu[\tau_\delta] \geq T^*(\nu) d(\delta, 1-\delta)\),其中 \(T^*(\nu)\) 由式 (2) 定义。这是对 Garivier and Kaufmann (2016) 的直接推广,关键区别在于下界中的 KL 散度项是按上下文加权的,且最优分配 \(w^*\) 是上下文相关的。
- Theorem 3 (两臂高斯下界):在多元高斯设定下,下界简化为 \(T^*(\nu)^{-1} = \frac{(\mu_1 - \mu_2)^2}{2(\sigma'_1 + \sigma'_2)^2}\)。这个结果非常简洁:上下文的影响完全通过残差标准差 \(\sigma'_a\) 体现。当 \(\rho_{aX} eq 0\) 时,\(\sigma'_a < \sigma_a\),因此 \(T^*(\nu)\) 比无上下文时更小。这定量地回答了"上下文何时有帮助"的问题。
- Theorem 4 (两臂高斯上界):\(\alpha\)-elimination 算法(使用上下文修正的估计量)是渐近最优的,即 \(E_\nu[\tau_\delta] \leq (1+\epsilon) T^*(\nu) \log(1/\delta) + o(\log(1/\delta))\)。证明的关键在于构造了一个方差为 \(\sigma'^2_a\) 的无偏估计量(通过控制变量法),使得检验统计量的方差与下界匹配。
- Theorem 5 (有限上下文下界):对于有限上下文和指数族,下界由式 (4) 给出,其中最优分配 \(w^*\) 是以下 minimax 问题的解:
\[T^*(\nu)^{-1} = \max_{w \in W} \min_{a eq 1} \sum_{x} \zeta_x \left[ w_{1,x} kl(\mu_{1,x}, \lambda_{1,x}) + w_{a,x} kl(\mu_{a,x}, \lambda_{a,x}) \right]\]这个问题的关键特征是:最优分配不是唯一的,其解集 \(\Phi(\nu)\) 是一个凸集(Lemma 13)。
- Theorem 19 (有限上下文上界):CTS 算法是渐近最优的。其采样规则(式 5)通过"强制探索"(forced exploration)保证每个上下文-臂对都有足够的样本,然后通过求解经验 minimax 问题来更新分配比例,使其收敛到 \(\Phi(\nu)\)。
证明路线与技术技巧¶
整体路线(以 Theorem 5 和 19 为例):
- 下界(Theorem 5):
- Step 1: Change-of-measure。构造备择模型 \(\nu'\),其中最优臂变为 \(a eq 1\)。利用 change-of-measure 参数,将错误概率与似然比联系起来。
- Step 2: 数据过程不等式。利用 Wald 引理和可选停时定理,将期望停止时间与每个上下文-臂对的期望样本数 \(E[N_{a,x}(\tau)]\) 联系起来。
-
Step 3: 优化问题。将下界转化为一个关于 \(E[N_{a,x}(\tau)]\) 的约束优化问题,并证明其最优值等于 \(T^*(\nu)\)。关键技巧是引入分配比例 \(w_{a,x}\),并利用 KL 散度的凸性将问题转化为一个凸优化问题。
-
上界(Theorem 19):
- Step 1: 估计。在每个时刻 \(t\),用经验均值 \(\hat{\mu}_{a,x}(t)\) 估计 \(\mu_{a,x}\),用 \(\hat{\zeta}_x(t)\) 估计 \(\zeta_x\)。
- Step 2: 优化。求解经验 minimax 问题,得到当前的"最优分配" \(\hat{w}(t)\)。
- Step 3: 采样。根据 \(\hat{w}(t)\) 和强制探索项,决定当前上下文 \(X_t\) 下选择哪个臂。
- Step 4: 停止。使用 GLRT 统计量 \(Z(t)\),当 \(Z(t) > \beta(t, \delta)\) 时停止。
- Step 5: 分析。证明在事件 \(\mathcal{E}\)(所有估计量都接近真实值)上,\(Z(t)\) 的增长速率至少为 \(t/T^*(\nu)\),从而停止时间有上界。同时证明 \(\mathcal{E}\) 的概率至少为 \(1-\delta\)。
关键技术技巧: - Change-of-measure 参数:这是整个下界证明的核心,直接继承了 Kaufmann et al. (2016) 的技术。 - 凸优化与 minimax 定理:将最优分配问题转化为凸优化问题,并利用 minimax 定理(或 Sion 定理)交换 \(\max\) 和 \(\min\) 的顺序,从而得到可计算的下界。 - 强制探索(Forced Exploration):为了保证估计量的一致性,CTS 算法强制每个上下文-臂对至少被采样 \(\sqrt{t}\) 次。这是处理未知 \(\zeta\) 和 \(\mu\) 的关键技巧。 - GLRT 停止规则:使用广义似然比检验作为停止准则,并利用 Kaufmann and Koolen (2021) 的精细大偏差不等式来设定阈值 \(\beta(t, \delta)\)。 - 控制变量法(Control Variates):在高斯情形下,利用 \(R_{t,a}\) 与 \(X_t\) 的相关性构造方差更小的估计量,从而降低停止时间。
真实例子与应用¶
- 模拟实验(Section 7):作者在 Bernoulli Bandit 设定下比较了 CTS 与 TS 算法。实验表明,当上下文与奖励相关时(例如,条件均值在不同上下文下差异很大),CTS 的停止时间显著小于 TS;当上下文与奖励无关时,两者性能接近。这验证了理论预测的"上下文增益"。
- 应用场景:本文在引言中提到的应用包括在线广告(根据用户特征选择广告,目标是找到总体点击率最高的广告)和临床试验(根据病人特征分配治疗,目标是找到总体疗效最好的治疗)。在这些场景中,决策者关心的是边际平均效果,而非针对每个子群体的条件效果。
🔎 结论是否比证明窄¶
- 是的,存在明显的"证明窄于结论"之处。作者在摘要和引言中声称 CTS 算法是"渐近最优的",但这一结论仅在以下条件下被严格证明:
- 有限上下文(Theorem 19):要求 \(\mathcal{X}\) 是有限集,且奖励属于单参数指数族。
- 两臂高斯(Theorem 4):要求 \(K=2\),且协方差结构已知。
- 对于一般连续上下文(如 \(\mathcal{X} = \mathbb{R}^d\))或多臂非指数族情形,作者并未给出严格的证明,只是在 Section 6.5 中通过"上下文聚合"(context aggregation)提供了一个启发式扩展,并证明了一个较弱的单调性结果(Lemma 22)。作者在结论部分也承认,对于连续上下文的一般情形,"developing a fully adaptive algorithm that achieves the lower bound remains an open problem"(开发一个达到下界的完全自适应算法仍然是一个开放问题)。
- 此外,下界本身(Theorem 2, 5)的证明依赖于对 \(\zeta\) 的已知性。如果 \(\zeta\) 未知且需要估计,下界的形式可能需要修正。作者在文中假设 \(\zeta\) 已知(或通过 \(\hat{\zeta}\) 一致估计),但并未讨论估计误差对最优性的影响。
四、开放问题¶
-
连续上下文的一般情形:本文的 CTS 算法仅对有限上下文或两臂高斯情形有严格的最优性保证。对于一般连续上下文(如 \(\mathcal{X} = \mathbb{R}^d\)),如何设计一个计算可行且渐近最优的算法?作者在 Section 6.5 提出的"上下文聚合"方法虽然简单,但其最优性损失(相对于连续下界)未被量化。扎根于:Section 6.5 和 Conclusion 中的 "developing a fully adaptive algorithm ... remains an open problem"。
-
未知上下文分布的自适应估计:本文的下界和算法都假设 \(\zeta\) 已知或可一致估计。当 \(\zeta\) 完全未知且需要在线估计时,估计误差会如何影响样本复杂度的常数项?是否存在一个"自适应"的下界,将估计 \(\zeta\) 的代价纳入其中?扎根于:Theorem 2 和 5 中对 \(\zeta\) 的假设,以及 Appendix C 中证明对 \(\zeta\) 的依赖。
-
非参数/半参数奖励分布:本文假设奖励属于单参数指数族(或高斯),这保证了 KL 散度的解析形式。对于更一般的奖励分布(如重尾分布或半参数模型),下界的形式会如何变化?是否仍能通过一个凸优化问题来刻画最优分配?扎根于:式 (1) 的指数族假设,以及作者在 Conclusion 中提到的 "extension to general reward distributions"。
-
与因果推断中自适应实验设计的联系:本文在引言中提到了与 ATE 估计的联系,但并未深入。一个潜在的研究方向是:将 CTS 算法与高效 ATE 估计(如 van der Laan 2008 的 targeted maximum likelihood)相结合,在序贯决策中同时实现"识别最优臂"和"高效估计处理效应"的双重目标。扎根于:Introduction 中关于 causal inference 的讨论,以及参考文献 [4] 和 [7]。
-
计算-统计权衡:CTS 算法需要每轮求解一个 minimax 优化问题(式 3)。当上下文空间和臂的数量很大时,这个优化问题的计算成本可能很高。是否存在计算上更廉价但统计效率损失可控的近似算法?扎根于:Section 6.1 中关于"直接应用优化求解器"的描述,以及 Appendix J.1 中关于计算成本的讨论。
提醒:要确认上述问题是否真的是领域内的 gap,建议去读近 5 年(2021-2026)关于 contextual bandits 和 pure exploration 的论文(如 ICML、NeurIPS、COLT 上的相关文章),看是否有工作已经解决了这些问题。如果多篇论文的引言都指向同一个未解决问题,那它大概率是共识性的 gap;如果各论文的结论互相矛盾,那可能是一个更有意思的机会。
Maintained by 陈星宇 · Homepage · Source on GitHub