找到最优条件干预的最小节点集，加速因果强化学习
The Minimal Search Space for Conditional Causal Bandits
- 基于因果图识别最优干预所需最小节点集
- 算法时间复杂度仅O(|V|+|E|)，显著缩小搜索空间
- 适合需高效决策的因果强化学习场景
因果知识可用于支持决策问题。在因果老虎机文献中，因果（多臂）老虎机由因果图模型和目标变量定义，动作是作用于因果模型的干预，奖励是目标变量的样本。传统研究聚焦于硬干预，本文则关注条件干预，即干预变量的取值可依据其他变量的观测值动态选择，更贴近现实决策问题。本文提出一种图形化表征，精确刻画出包含最优条件干预的最小节点集合，该干预能最大化期望奖励。同时，提出一个时间复杂度为O(|V| + |E|)的高效算法来识别该最小节点集，并证明其正确性。实验表明，将该算法集成至标准多臂老虎机算法中，可显著压缩搜索空间，大幅提升收敛速度。
原文摘要 · Abstract (English)
Causal knowledge can be used to support decision-making problems. This has been recognized in the causal bandits literature, where a causal (multi-armed) bandit is characterized by a causal graphical model and a target variable. The arms are then interventions on the causal model, and rewards are samples of the target variable. Causal bandits were originally studied with a focus on hard interventions. We focus instead on cases where the arms are conditional interventions, which more accurately model many real-world decision-making problems by allowing the value of the intervened variable to be chosen based on the observed values of other variables. This paper presents a graphical characterization of the minimal set of nodes guaranteed to contain the optimal conditional intervention, which maximizes the expected reward. We then propose an efficient algorithm with a time complexity of $O(|V| + |E|)$ to identify this minimal set of nodes. We prove that the graphical characterization and the proposed algorithm are correct. Finally, we empirically demonstrate that our algorithm significantly prunes the search space and substantially accelerates convergence rates when integrated into standard multi-armed bandit algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。