We study the causal bandit problem when the causal graph is unknown and develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We derive the exact equation for the expected number of interventions performed by the algorithm and show that under certain graphical conditions it could perform either logarithmically fast or, under more general assumptions, slower but still sublinearly in the number of variables. We formally show that our algorithm is optimal as it meets the universal lower bound we establish for any algorithm that performs atomic interventions. Finally, we extend our algorithm to the case when the reward node has multiple parents. Using this algorithm together with a standard algorithm from bandit literature leads to improved regret bounds.
翻译:当因果图未知时,我们研究因果强盗问题,并开发一种有效的算法,用原子干预方法找到奖赏节点的母节点。我们得出算法的预期干预次数的精确方程式,并表明在某些图形条件下,算法既可以快速进行对数计算,也可以在更一般的假设下,在变量数量上进行慢但仍然是次线的计算。我们正式表明我们的算法是最佳的,因为它符合我们为任何进行原子干预的算法所确立的普遍较低约束值。最后,我们把算法扩大到奖励节点有多个父母时的情况。使用这个算法和土匪文学的标准算法可以改善遗憾界限。