技术摘要：图学习在因果多臂老虎机中并非最优

问题陈述

本文研究了在因果充分性（无未观测混杂因素）假设下，当代理方未知底层因果图结构时，因果多臂老虎机中的遗憾最小化问题。在此设定中，代理方按顺序选择定义在变量子集（大小至多为 $m$）上的干预动作，以最大化累积奖励。奖励由有向无环图（DAG）中 $n$ 个变量上的特定节点 $Y$ 决定。

先前的文献大多基于以下假设：识别奖励节点的父节点集（$Pa_Y$）是有效学习的前提。策略通常涉及两阶段方法：首先发现父节点集（通常通过结构学习或顺序搜索），然后应用标准老虎机算法（如 UCB），但仅限于对这些父节点进行干预。或者，一些工作尝试同时学习父节点并最小化遗憾。

本文解决的核心问题是：识别奖励节点的父节点集是否是减少累积遗憾的必要或最优策略？

方法论与理论框架

1. 识别与遗憾之间的权衡

作者首先确立了父节点识别与遗憾最小化目标之间的根本理论冲突。

• 反例构建：他们构建了一个特定的实例子类（$\mathcal{E}_0$），其中高奖励动作的集合与提供关于父节点集信息的动作集合是不相交的。
• 定理 3.2（识别 - 遗憾权衡）：论文证明，对于任何在识别父节点集方面实现指数级低错误率（即 $\delta_T \in O(\exp(-T^\alpha))$）的策略，其累积遗憾必须增长为 $\Omega(T^\alpha)$。反之，实现最优遗憾率则排除了以高概率识别父节点集的可能性。
• 推论：在最坏情况下，代理方无法同时高效地学习因果结构并最小化遗憾。区分真实父节点集所需的“信息性”动作往往会产生高遗憾，而“最优”动作则不提供任何结构信息。

2. 遗憾下界

作者推导了关于最坏情况遗憾的新颖信息论下界，即使代理方完全知晓非奖励变量上的因果图（$G$），这些界限依然成立。这表明，对图结构（不包括奖励节点的具体父节点集）的知识并不能改善最坏情况下的遗憾保证。

• 已知父节点大小（$k$）：
  • 情况 $m \ge k$：下界为 $\Omega\left(\sqrt{T \max\left(\frac{(\ell-1)^k \binom{n}{k}}{\binom{m}{k}}, \ell^k\right)}\right)$。
  • 情况 $m < k$：下界为 $\Omega\left(\sqrt{T \max\left((\ell-1)^m \binom{n}{m}, \ell^m\right)}\right)$。
  • 这些界限捕捉了动作空间的组合复杂性，并表明困难源于哪个大小为 $k$ 的子集构成父节点的不确定性，而非图拓扑本身。
• 未知父节点大小（$k$）：
  • 论文建立了不同父节点大小（$k_1$ 和 $k_2$）的遗憾乘积的下界，证明没有任何单一算法能对所有可能的 $k$ 值统一实现最优遗憾率。这需要在不同问题实例的性能之间进行权衡。

3. 提出的算法

通过绕过显式图恢复的需求，作者提出了两种算法，实现了近最优的遗憾界限：

• 算法 1（已知 $k$）：

  • 机制：该算法不学习图，而是从所有大小为 $m$ 的干预动作空间中随机采样一个动作子集（$A'$）。该子集的大小经过精心选择，以确保以高概率包含至少一个最优动作。
  • 执行：随后，它仅在这个缩减后的子集 $A'$ 上运行标准的置信上限（UCB）算法。
  • 性能：其实现的遗憾与推导出的下界相匹配（对数因子范围内），无需知晓图 $G$ 或具体的父节点集。

• 算法 2（未知 $k$）：

  • 机制：旨在适应未知数量的父节点，该算法分阶段运行。在每个阶段中，它采样一个随机动作子集，运行 UCB，并构建一个“混合臂”（基于该阶段经验分布的随机化动作）。
  • 适应性：阶段长度和样本量会动态调整（样本量减半，阶段长度加倍），以平衡不同潜在父节点集大小之间的探索。
  • 性能：该算法被证明是速率帕累托最优的。这意味着其遗憾向量（在所有可能的 $k$ 上的性能）不能被任何其他策略严格占优；它在处理小 $k$ 和大 $k$ 实例的性能之间实现了最佳可能的权衡。

主要结果与贡献

1. 图学习的次优性：论文严格证明，在最坏情况设定下，学习父节点集对于遗憾最小化是次优的。存在一些实例，其中结构学习与遗憾最小化的目标从根本上是冲突的。
2. 新颖的下界：作者提供了针对未知图因果多臂老虎机的首个下界，明确考虑了动作空间的组合结构。关键在于，这些界限甚至适用于代理方知晓完整图 $G$（除奖励节点的父节点外）的情况，证明仅凭结构知识不足以绕过问题的难度。
3. 近最优算法：
   • 对于已知 $k$，所提出的算法实现了 $\tilde{O}\left(\sqrt{T \ell^k \binom{n}{k} / \binom{m}{k}}\right)$ 的遗憾，与下界相匹配。
   • 对于未知 $k$，自适应算法实现了帕累托最优的遗憾向量，有效地处理了 $k$ 的不确定性，而无需先验知识。
4. 实证验证：在合成 Erdős–Rényi 图上的实验表明，所提出的方法（EmpKnownUCB+ 和 EmpUnknownUCB+）显著优于现有基线，包括：
   • RAPS：一种在最小化遗憾之前显式学习父节点的先进方法。
   • 标准 UCB：应用于完整动作空间。
   • 与基线相比，所提出的方法将遗憾降低了高达 20 倍，特别是在 RAPS 的父节点识别阶段会消耗过多资源的设定中。

意义与主张

本文主张在未知结构因果多臂老虎机的方法上发生范式转变。它认为，为了实现最优遗憾率，显式的因果发现是不必要的。通过证明结构学习与遗憾最小化可能是冲突的目标，该工作表明算法应直接关注奖励景观，而不是试图重建底层因果图。

作者强调，他们的结果在无分布假设（例如线性）下成立，并且适用于硬干预。他们指出，虽然结构信息（图 $G$）并不能改善最坏情况下的遗憾界限，但所提出的算法在无需此类信息的情况下实现了这些界限。该工作得出结论：对于最坏情况下的遗憾最小化，“绕过图和父节点恢复”不仅是可行的，而且优于传统的两阶段方法。

正如作者所建议的，未来的工作涉及刻画这些目标可能一致的设定，或研究可能允许同时优化结构学习和遗憾的特定分布假设。