ICLR 23 Submission (7.33)｜ 因果Bandits的组合纯探索

简介：因果Bandits的组合纯探索是以下的在线学习任务：给定一个具有未知因果推理分布的因果图，在每一轮中我们选择一个变量子集进行干预或不做干预，并观察所有随机变量的随机结果，目标是使用尽可能少的几轮，我们可以输出一个干预，在奖励变量Y上给出最好（或几乎最好）的预期结果，概率至少为1-$\delta$，其中$\delta$是一个给定的置信度。我们在两类因果模型--二元广义线性模型（BGLM）和广义图上提供了第一个依赖差距和完全自适应的纯探索算法。对于BGLM，我们的算法是第一个专门为这一设置而设计的算法，并实现了多项式的样本复杂度，而所有现有的通用图的算法要么样本复杂度与图的大小成指数关系，要么是一些不合理的假设。对于一般的图，我们的算法在样本复杂度上有很大的改进，它几乎与我们证明的下限相匹配。我们的算法通过对先前的因果Bandits算法和先前的自适应纯探索算法的新的整合来实现这种改进，前者利用了因果Bandits中丰富的观察反馈，但对奖励差距没有适应性，而后者的问题正好相反。