🤖 machine learning

Information-Directed Sampling for Causal Bandits

本文针对具有不可操纵变量的上下文因果多臂老虎机问题，提出了贝叶斯汤普森采样和信息导向采样算法，建立了依赖于熵的次线性遗憾界限，并通过有效利用共享因果机制来加速高回报决策的识别，证明了其相对于基准算法的优越性能。

原作者： Muhammad Qasim Elahi, Murat Kocaoglu, Mahsa Ghasemi

发布于 2026-07-20

📖 1 分钟阅读☕ 轻松阅读

原作者： Muhammad Qasim Elahi, Murat Kocaoglu, Mahsa Ghasemi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名试图破解谜团的侦探，但你不能随心所欲地询问嫌疑人任何问题。有些线索被锁在玻璃后面——你能看到它们，却无法触碰它们。这就是“因果多臂老虎机”（causal bandits）的世界，它是人工智能的一个分支，其中计算机通过实验来学习如何做出最佳决策。在标准游戏中，如果你尝试一个动作并获得奖励，你只能学到关于那个特定动作的信息。但在现实世界中，行动像多米诺骨牌一样相互连接；推倒其中一个可能会撞倒好几个其他的。因果多臂老虎机利用这些隐藏的联系来更快地学习：如果你学会了一个多米诺骨牌是如何倒下的，你就可以在甚至不去触碰它的情况下，预判下一个多米诺骨牌会如何倒下。然而，当其中一些多米诺骨牌是“不可操纵的”时，一个重大问题就出现了。你可能可以推动一个杠杆（一个动作），但你无法改变患者的年龄或天气（不可操纵的变量），尽管这些因素极大地影响着结果。挑战在于，当最重要的线索中有一些是你无法控制的时候，如何找出最佳策略来进行学习。

这篇论文通过引入两种更聪明的、让 AI 玩这场游戏的方法，解决了这个精确的难题。作者们在已知事物如何连接的“地图”这一理念基础上，提出了一种方法，让 AI 将系统中未知的部分视为一个充满概率的神秘盒子。AI 不仅仅是瞎猜，而是使用了一种叫做“信息导向采样”（Information-Directed Sampling, IDS）的技术。把 IDS 想象成这样一位侦探：他不仅会挑选那个他认为现在就能破案的线索，还会挑选那个能让他对整个谜团了解得最深刻的线索，即便这个线索现在还不能直接破案。论文表明，通过使用这种方法，AI 可以比旧方法更好地在不同的实验之间共享信息。

研究人员开发了两种具体的策略。第一种是“汤普森采样”（Thompson Sampling）的一种变体，这就像是通过抛一枚加权硬币来决定下一步进行哪项实验，而硬币的权重是基于该实验成为最佳选择的可能性。他们从数学上证明了这种方法会随着时间的推移变得越来越好，其犯下的“错误”增长得非常缓慢。第二种是更复杂、也是他们提出的新版 IDS 策略。由于在计算机上完美解决 IDS 的数学计算极其困难，他们不得不使用一种“蒙特卡洛”（Monte Carlo）方法——基本上，是在脑海中运行数千次模拟场景，以获得一个良好的估算。论文的大发现是，即使使用了这些估算，该方法仍然表现得极其出色。他们证明了这些模拟所引入的误差是微小且可控的。在针对虚构场景的测试中，这些新方法击败了既有的因果方法和非因果方法，这表明当你无法触及一切时，最好的学习方式是仔细选择哪些实验能让你对全局有最深刻的理解。

技术摘要：用于因果多臂老虎机的信息导向采样

问题表述

本文研究了包含不可操纵变量的环境中的**上下文因果老虎机（contextual causal bandits）**问题。在标准的多臂老虎机问题中，动作的选择旨在最大化具有未知分布的奖励。在因果老虎机中，动作对应于对结构因果模型（SCM）的干预（$do(X=x)$），其中奖励通过共享的因果机制相互耦合。

本文解决的具体挑战源于某些变量虽然会影响奖励，但无法被直接操纵（例如人口统计属性、遗传特征或宏观经济条件）。虽然这些变量无法被干预，但它们作为上下文变量在动作选择前被观测到，并在干预后作为观测变量出现。目标是从候选动作集中选择一个可行的干预措施，以最大化上下文相关的期望奖励 $\mu_x(c) = E[Y | do(x), C=c]$ ，同时在不同干预之间高效地共享信息。

作者假设：

存在一个已知的因果图 $G$ ，且不存在潜变量混杂因素（latent confounders）。
存在一组不可操纵变量 $N \subseteq V \setminus \{Y\}$ 。
上下文变量 $C$ 在动作选择前被观测到，且对祖先封闭（即 $An(C)=C$）。
观测分布是未知的，由条件概率表（CPTs）参数化。

方法论

1. 贝叶斯公式化与参数化

作者采用了贝叶斯框架，其中未知参数 $\theta$ 由观测分布的条件概率表组成。在无潜变量混杂因素的假设下，干预分布可以通过截断分解公式（truncated factorization formula）从观测分布中识别。

参数独立性： 参数向量 $\theta$ 被分解为局部向量 $\theta_{ij}$ ，对应于每个变量在其父节点配置下的 CPT。
后验更新： 假设使用共轭狄利克雷先验（Dirichlet priors），可以基于观测数据对 $\theta$ 的后验分布进行解析更新。这使得在一种干预下收集的样本可以通过精炼共享的 CPT 来更新其他干预的估计。

2. 候选动作的识别

为了处理不可操纵变量，本文利用了从 Lee 和 Bareinboim [2019] 导出的**可能最优最小干预集（POMISs）**的概念。

投影： 将原始图投影到仅包含可操纵变量的图 $H$ 上。由不可操纵变量引起的潜在混杂作用在 $H$ 中由双向边表示。
动作选择： 通过枚举投影图 $H$ 的 POMISs 来生成候选动作集 $\mathcal{A}$ 。这确保了算法仅考虑在操纵性约束下理论上最优的干预。

3. 提出的算法

本文提出了两种标准老虎机的因果变体算法：

A. 因果汤普森采样 (Causal Thompson Sampling, TS)

机制： 在每一轮 $t$ ，给定上下文 $C_t=c_t$ ，算法从上下文条件后验分布 $P(\theta | F_t, C_t=c_t)$ 中采样一个参数 $\theta_t$ 。然后，它选择在采样参数下使期望奖励最大的动作 $a_t$ ： $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$ 。
遗憾分析： 作者建立了取决于最优动作映射熵 $H(\Pi^*)$ 的次线性贝叶斯遗憾界限。该界限的规模为 $O(\sqrt{T |A| |C| \log |A|})$ 。

B. 因果信息导向采样 (Causal Information-Directed Sampling, IDS)

机制： IDS 选择一个动作分布，以最小化信息比（information ratio），该比率定义为平方期望瞬时遗憾与关于最优动作的期望信息增益之比。
- 遗憾项： $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$ 。
- 信息增益项： $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$ 。
蒙特卡洛近似： 由于计算信息比所需的后验期望在连续参数空间中在解析上是难以处理的，算法使用来自后验分布的 $N$ 个蒙特卡洛样本进行近似。
误差控制： 作者为用于计算期望遗憾和信息增益的蒙特卡洛估计值的两个高概率集中不等式（引理 3 和 4）进行了推导。这些不等式明确量化了近似引入的额外误差。

核心贡献

针对不可操纵变量的贝叶斯框架： 本文通过将观测 CPTs 视为未知参数，构建了包含不可操纵变量的上下文因果老虎机。这种形式化使得即使在某些变量无法被干预的情况下，也能通过共享的因果机制实现不同干预之间的信息共享。
具有遗憾保证的因果汤普森采样： 作者提出了一种因果 TS 算法，并证明了其具有依赖于熵的次线性贝叶斯遗憾界限。这将 TS 的保证扩展到了具有结构约束和上下文的情景。
具有近似分析的因果 IDS： 本文开发了一种因果 IDS 算法，平衡了遗憾最小化与信息获取。至关重要的是，作者推导出了一个遗憾界限，该界限明确地将标准的信息论项与蒙特卡洛近似引入的误差分离开来。当使用精确计算信息比（Oracle 版本）时，可以恢复标准的次线性 IDS 速率。
蒙特卡洛估计的集中不等式： 作者提供了关于期望瞬时遗憾和上下文信息增益的蒙特卡洛估计的高概率置信界限。这些结果量化了后验采样误差对算法性能保证的影响。

结果与评估

所提方法在多个合成因果老虎机任务（包括结构化示例和随机生成的因果图）上进行了评估。

性能： 实验表明，所提出的 Causal TS 和 Causal IDS 算法优于因果和非因果基准算法。
机制： 这种卓越性能归功于算法能够更有效地利用通过共享因果结构在不同干预之间共享的信息，特别是在存在不可操纵变量的情况下。

意义

本文声称其意义在于为在无法完全控制变量的因果环境中进行决策提供了一个原则性的框架。通过将不可操纵变量整合进因果老虎机框架，并提供具有严格遗憾界限（包括近似误差分析）的算法，这项工作弥合了理论因果推断与实际序列决策之间的鸿盟。对 IDS 中蒙特卡洛近似误差的显式处理被强调为一项关键的理论进展，确保了即使在精确计算不可行时，信息导向采样的优势仍能得以保持。