Regret Analysis of Bandit Problems with Causal Background Knowledge
Regret Analysis of Bandit Problems with Causal Background Knowledge
复制标题
带有因果背景知识的土匪问题的遗憾分析
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zhenyu Yan
中科院分区：
文献类型：
--
作者：
Yangyi Lu;A. Meisami;Ambuj Tewari;Zhenyu Yan
我们研究如何在给出以因果图表示的因果信息以及相关的条件分布的情况下顺序学习最佳干预措施。因果模型对于现实世界的问题非常有用，例如在线广告，其中复杂的因果机制是干预措施和结果之间关系的基础。我们提出了两种算法，因果置信上限（C-UCB）和因果汤普森采样（C-TS），与不使用因果信息的算法相比，它们具有改进的累积遗憾界限。因此，我们解决了 cite{lattimore2016causal} 提出的一个开放问题。此外，我们将 C-UCB 和 C-TS 扩展到线性老虎机设置，并提出因果线性 UCB (CL-UCB) 和因果线性 TS (CL-TS) 算法。这些算法具有累积遗憾界限，仅与特征维度成比例。我们的实验证明了使用因果信息的好处。例如，我们观察到，即使进行数百次迭代，因果算法的遗憾也比标准算法少三倍。我们还表明，在某些因果结构下，随着干预次数的增加，我们的算法比标准老虎机算法具有更好的扩展性。
We study how to learn optimal interventions sequentially given causal information represented as a causal graph along with associated conditional distributions. Causal modeling is useful in real world problems like online advertisement where complex causal mechanisms underlie the relationship between interventions and outcomes. We propose two algorithms, causal upper confidence bound (C-UCB) and causal Thompson Sampling (C-TS), that enjoy improved cumulative regret bounds compared with algorithms that do not use causal information. We thus resolve an open problem posed by cite{lattimore2016causal}. Further, we extend C-UCB and C-TS to the linear bandit setting and propose causal linear UCB (CL-UCB) and causal linear TS (CL-TS) algorithms. These algorithms enjoy a cumulative regret bound that only scales with the feature dimension. Our experiments show the benefit of using causal information. For example, we observe that even with a few hundreds of iterations, the regret of causal algorithms is less than that of standard algorithms by a factor of three. We also show that under certain causal structures, our algorithms scale better than the standard bandit algorithms as the number of interventions increases.
结构性因果强盗：在哪里干预？
DOI：
--
发表时间：
2018
期刊：
Advances in Neural Information Processing Systems 31
影响因子：
--
作者：
Lee, Sanghack;Bareinboim, Elias
通讯作者：
Bareinboim, Elias