arXiv:2411.04054stat.MLcs.LG2024-11NeurIPS被引 11

无需完整因果图也能实现无后悔学习,关键在于发现必要潜变量。

Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits

  • 仅需识别必要潜变量与奖励节点祖先的子图,即可确定最优决策集。
  • 两阶段算法在样本有限下实现亚线性后悔率,优于传统方法。
  • 适合因果结构未知且存在隐藏混淆的强化学习场景。

在因果带宽问题中,若已知决策变量与回报变量间的因果关系,可加速最优决策的学习。现有工作通常假设因果图已知,但实际中该信息未必可得。本文研究因果图未知且可能存在潜混淆因子的情形。尽管在无潜混淆时干预奖励节点的父节点为最优,但一般情况下需考虑一系列可能最优的行动/干预,这些行动是奖励节点祖先的特殊子集,因此超越奖励节点父节点的因果发现至关重要。我们证明:为最小化后悔,无需发现完整因果结构;但此前缺乏必要且充分的因果图组件定义。本文首次形式化了必须检测或学习的必要和充分潜混淆因子集合。同时提出一种随机算法,在有限样本下学习因果图,并提供任意置信度下的样本复杂度保证。在因果带宽框架中,我们设计两阶段方法:第一阶段学习奖励节点祖先上的诱导子图及必要充分潜混淆因子子集,构建可能最优行动集,此阶段后悔随因果图节点数多项式增长;第二阶段应用标准带宽算法(如UCB)。我们还建立了该两阶段方法的后悔上界,其关于轮次数为亚线性。

原文摘要 · Abstract (English)

Causal knowledge about the relationships among decision variables and a reward variable in a bandit setting can accelerate the learning of an optimal decision. Current works often assume the causal graph is known, which may not always be available a priori. Motivated by this challenge, we focus on the causal bandit problem in scenarios where the underlying causal graph is unknown and may include latent confounders. While intervention on the parents of the reward node is optimal in the absence of latent confounders, this is not necessarily the case in general. Instead, one must consider a set of possibly optimal arms/interventions, each being a special subset of the ancestors of the reward node, making causal discovery beyond the parents of the reward node essential. For regret minimization, we identify that discovering the full causal structure is unnecessary; however, no existing work provides the necessary and sufficient components of the causal graph. We formally characterize the set of necessary and sufficient latent confounders one needs to detect or learn to ensure that all possibly optimal arms are identified correctly. We also propose a randomized algorithm for learning the causal graph with a limited number of samples, providing a sample complexity guarantee for any desired confidence level. In the causal bandit setup, we propose a two-stage approach. In the first stage, we learn the induced subgraph on ancestors of the reward, along with a necessary and sufficient subset of latent confounders, to construct the set of possibly optimal arms. The regret incurred during this phase scales polynomially with respect to the number of nodes in the causal graph. The second phase involves the application of a standard bandit algorithm, such as the UCB algorithm. We also establish a regret bound for our two-phase approach, which is sublinear in the number of rounds.

因果推理带宽学习潜变量后悔分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。