因果赌博机的信息导向采样

# 面向因果老虎机的信息导向采样
来源：https://arxiv.org/html/2607.15577
Murat Kocaoglu², Mahsa Ghasemi¹
¹ 普渡大学电气与计算机工程学院
² 约翰霍普金斯大学计算机科学学院
elahi0@purdue\.edu, mkocaoglu@jhu\.edu, mahsa@purdue\.edu

###### 摘要

因果老虎机利用变量间的结构关系来跨干预共享信息，从而加速高回报决策的识别。然而，在许多应用中，某些变量即使影响回报并提供有关底层因果系统的有用信息，也无法直接进行操作。我们研究带有不可操作变量的上下文因果老虎机，其中上下文变量在动作选择前被观测到，而额外变量则在每次干预后观测到。假设因果图已知且无潜在混杂，我们采用贝叶斯公式，将观测分布的条件概率表视为未知参数。这种表示允许在一次干预下收集的观测数据，通过共享的因果机制来更新其他干预的回报估计。我们针对该场景开发了汤普森采样和信息导向采样（IDS）的因果变体。对于汤普森采样，我们建立了一个依赖于熵的次线性贝叶斯遗憾界。对于IDS，我们推导出一个依赖熵的遗憾界，该界明确量化了蒙特卡洛近似预期遗憾和信息增益所引入的额外误差；当这些量可精确计算时，该界恢复了标准的次线性IDS速率。我们进一步为算法使用的蒙特卡洛估计提供了高概率置信界。在多个合成因果老虎机任务上的实验表明，所提方法通过更有效地利用跨干预共享的信息，优于因果和非因果基线。

## 1 引言

在经典的多臂老虎机问题中，决策者从有限集合中重复选择动作，并观察由此产生的回报。由于回报分布初始未知，学习者必须平衡*探索*（收集关于不确定动作的信息）和*利用*（倾向于被认为能产生高回报的动作）Lattimore 和 Szepesvári (2020 (https://arxiv.org/html/2607.15577#bib.bib55)); Slivkins 等人 (2019 (https://arxiv.org/html/2607.15577#bib.bib56)); Vermorel 和 Mohri (2005 (https://arxiv.org/html/2607.15577#bib.bib57))。在没有额外结构的情况下，观察一个动作的回报通常不直接提供关于其他动作回报的信息。因此，有效的算法必须足够频繁地探索可用动作Garivier 和 Cappé (2011 (https://arxiv.org/html/2607.15577#bib.bib44)); Jamieson 和 Nowak (2014 (https://arxiv.org/html/2607.15577#bib.bib58)); Jamieson 等人 (2014 (https://arxiv.org/html/2607.15577#bib.bib39))。

然而，在许多决策问题中，动作通过共同的底层机制相互关联。因此，在一个动作后收集的观测可能提供关于其他几个动作的信息。结构化老虎机方法利用这种关系来提高统计效率并减少不必要的探索Schulz 等人 (2020 (https://arxiv.org/html/2607.15577#bib.bib38)); Jun 和 Zhang (2020 (https://arxiv.org/html/2607.15577#bib.bib37)); Tirinzoni 等人 (2020 (https://arxiv.org/html/2607.15577#bib.bib36)); Van Parys 和 Golrezaei (2024 (https://arxiv.org/html/2607.15577#bib.bib60)); Wan 等人 (2023 (https://arxiv.org/html/2607.15577#bib.bib61)); Mersereau 等人 (2009 (https://arxiv.org/html/2607.15577#bib.bib62))。核心挑战在于表征并利用相关的信息共享结构，同时继续平衡探索和利用。

当环境受底层结构因果模型支配时，因果老虎机为结构化决策提供了一个原则性框架Lattimore 等人 (2016 (https://arxiv.org/html/2607.15577#bib.bib25)); Sen 等人 (2017 (https://arxiv.org/html/2607.15577#bib.bib46)); Lee 和 Bareinboim (2018 (https://arxiv.org/html/2607.15577#bib.bib26)); Wei 等人 (2024 (https://arxiv.org/html/2607.15577#bib.bib50)); Qasim Elahi 等人 (2024 (https://arxiv.org/html/2607.15577#bib.bib43))。在这种设置下，每个动作对应于对因果系统的干预，产生的观测根据共享的因果模型生成Pearl (2009 (https://arxiv.org/html/2607.15577#bib.bib33))。与非结构化老虎机模型不同，不同干预相关的回报分布通过共同的因果机制耦合。因此，在一次干预下获得的观测可以潜在地改进学习者对其他干预相关回报的估计Lattimore 等人 (2016 (https://arxiv.org/html/2607.15577#bib.bib25)); Sen 等人 (2017 (https://arxiv.org/html/2607.15577#bib.bib46)); Yabe 等人 (2018 (https://arxiv.org/html/2607.15577#bib.bib49)); Lee 和 Bareinboim (2018 (https://arxiv.org/html/2607.15577#bib.bib26))。

许多现有的因果老虎机公式允许对大量观测变量进行干预。然而，在实践中，某些变量无法直接操作。例如，医疗保健中的遗传特征、公共政策应用中的人口统计属性以及经济决策中的宏观经济条件。尽管这些变量不可操作，但它们可能强烈影响回报以及可行干预的效果。因此，它们的存在改变了候选干预集，并为跨动作高效共享信息创造了额外挑战。

Lee 和 Bareinboim (2019 (https://arxiv.org/html/2607.15577#bib.bib52)) 研究了包含不可操作变量的因果老虎机，且图可能包含潜在混杂。他们描述了在可操作性约束下可能最优的干预，并使用广义的 z² 识别过程推导了干预回报分布的多个估计量。这些估计量通过基于自举的最小方差加权平均进行组合，并融入到汤普森采样和 KL-UCB 的变体中。他们的结果展示了利用因果信息的实证价值，但未提供所得算法的遗憾保证。

我们研究带有不可操作变量的上下文因果老虎机，假设因果图已知且无潜在混杂。在每一轮中，学习者在选择干预之前观察到上下文变量。学习者随后观察到回报以及因果图中剩余的观测变量。例如，在医疗保健应用中，患者特征和病史可能在治疗选择前可用，而无法直接操作的生理测量可能在治疗后观察到。学习者的目标是选择最大化上下文相关期望回报的可行干预。

遵循Russo 和 Van Roy (2016 (https://arxiv.org/html/2607.15577#bib.bib54), 2014 (https://arxiv.org/html/2607.15577#bib.bib59)) 的贝叶斯信息论框架，我们使用随机参数 θ 表示关于因果系统的不确定性。由于图不包含潜在混杂，相关的干预分布通过截断因式分解公式从观测分布中识别。因此，我们让 θ 收集与因果图相关的条件概率表。每一轮的观测更新这些共享参数上的后验分布，使得在一次干预下收集的样本能够改进其他干预的估计回报和信息增益。

基于此公式，我们开发了汤普森采样和信息导向采样的因果变体。汤普森采样根据在观测上下文下最优的后验概率选择干预。IDS 则通过平衡干预的预期即时遗憾与其提供的关于上下文相关最优决策的信息来选择干预上的分布。由于 IDS 所需的后验期望通常无法以封闭形式获得，我们使用蒙特卡洛样本来估计它们，并明确考虑由此产生的近似误差。

我们的主要贡献总结如下：

- • 我们以贝叶斯框架形式化带有不可操作变量的上下文因果老虎机，其中观测分布的条件概率表被视为未知参数。这种公式使得一次干预下收集的观测能够通过共享的因果机制更新与其他干预相关的估计。
- • 我们针对该场景提出了因果汤普森采样和信息导向采样算法。我们为汤普森采样建立了一个依赖于熵的次线性贝叶斯遗憾界。对于 IDS，我们推导了一个遗憾界，将标准信息论项与蒙特卡洛近似引起的额外误差分离开来；当信息比率精确计算时，达到标准次线性 IDS 保证。
- • 我们推导了预期即时遗憾和上下文信息增益的蒙特卡洛估计的高概率集中界。这些结果提供了可计算的置信集，并量化了后验采样误差对 IDS 遗憾保证的影响。
- • 我们在多个合成因果老虎机任务上评估了所提方法，包括结构化示例和随机生成的因果图。结果表明，所提算法通过更有效地利用跨干预共享的信息，优于因果和非因果基线。

## 2 预备知识

我们采用结构因果模型（SCM）框架Pearl (2009 (https://arxiv.org/html/2607.15577#bib.bib33))。一个 SCM，记作 M，被定义为一个四元组 ⟨U, V, F, P(U)⟩，其中 U 表示由模型外部因素决定的外生（未观测）变量集合，V 表示通过结构函数 F 由 U∪V 中的变量决定的内生（观测）变量集合。在我们的设置中，内生变量 V 取值于有限域，由回报变量 Y、可操作（可操纵）变量、不可操作（不可操纵）变量以及上下文变量组成。为了进一步简化，我们在本文中假设它们为二值变量。对于任何节点子集 X ⊆ V，令 Ω(X) 表示 X 中所有变量的状态空间的笛卡尔积。然而，我们提出的方法和结果在观测节点是离散且可能取多于两个值时同样成立。结构函数 F 指定了每个 Vi 如何根据其父变量 PAⁱ ⊆ V 和外生变量 Uⁱ ⊆ U 被赋予一个值，记作 vᵢ = fᵢ(PAⁱ, Uⁱ)。最后，P(U) 是外生变量 U 上的概率分布。

每个 SCM 关联一个因果图 G = ⟨V, E⟩，其中边集 E 包括两种类型：有向边，如 Vi → Vj，表示直接函数依赖（即 Vi 被用于定义 F 中的 fj）；以及双向边，如 Vi ↔ Vj，表示存在影响 Vi 和 Vj 两者的未观测（潜在）混杂。我们使用符号 pa、ch、an 和 de 分别指代变量的父节点、子节点、祖先和后代。大写形式如 Pa、Ch、An 和 De 包含变量本身（例如，An(W) = an(W) ∪ {W}）。对于变量集合，其关系定义为各个输出结果的并集，例如，An(W) = ⋃_{W∈W} An(W)。注意 pa(Vi) = PAⁱ。G 的一个子图，记作 Gₓ̄，是通过移除指向 X 中变量的边得到的。有向无环图 G 中包含顶点 Vi 的连通分量（c 分量）记作 CC_G(Vi)，它是 G 中所有与 Vi 存在仅由双向边组成的路径的顶点的最大集合Tian 和 Pearl (2002 (https://arxiv.org/html/2607.15577#bib.bib4))。

在 K 臂老虎机问题中，有 K 个具有不同回报分布的臂可用，目标是在 T 轮上最小化累积遗憾。遗憾定义为总是选择最优臂所能达到的最大期望累积回报与给定算法获得的期望累积回报之间的差。在 SCM-MAB 设置中，每个臂对应于对变量子集的一次干预。给定因果图 G 和回报 Y，臂定义为 {do(X=x) ∣ X ⊆ V \ {Y}}，其中在干预 do(X=x) 下回报变量的分布，记作 P(Yₓ)，与干预分布 Pₓ(Y) 一致。与干预相关的期望回报为 μₓ = E[Y | do(x)]。当在干预前观察到额外的上下文变量 C 时，目标变为优化基于上下文的条件期望回报，即 μₓ(C=c) = E[Y | do(x), C=c]。此外，我们假设 C 在祖先关系下封闭，即 An(C) = C，这样上下文变量只有其他上下文变量作为祖先，因此不受干预影响，从而保持了其作为干预前信息的解释并避免了时间顺序问题。

## 3 因果老虎机中可能最优的臂

在本节中，我们回顾 Lee 和 Bareinboim (2019 (https://arxiv.org/html/2607.15577#bib.bib52)) 的结果，该结果刻画了当因果图中某些节点不可操作时，因果老虎机中可能最优的臂。令 N ⊆ V \ {Y} 表示不可操作变量集合，注意回报变量 Y 本身也是固有不可操作的。

###### 定义 1.
（未观测混杂（UC）领土Lee 和 Bareinboim (2018 (https://arxiv.org/html/2607.15577#bib.bib26))）考虑因果图 G(V, E) 和回报节点 Y，