Budgeted and Non-budgeted Causal Bandits
This work is significant for researchers and practitioners working with causal inference and bandit problems, particularly in settings where interventions are costly and resources are limited, providing methods to optimize intervention strategies.
This paper addresses the problem of learning optimal interventions in causal graphs under budget constraints, where interventions are more costly than observations. The authors propose algorithms that minimize simple regret by optimally trading off observations and interventions, and minimize expected cumulative regret while staying within a budget, outperforming standard algorithms. For unbudgeted scenarios, they present an algorithm that achieves constant expected cumulative regret when parent distributions are known.
Learning good interventions in a causal graph can be modelled as a stochastic multi-armed bandit problem with side-information. First, we study this problem when interventions are more expensive than observations and a budget is specified. If there are no backdoor paths from an intervenable node to the reward node then we propose an algorithm to minimize simple regret that optimally trades-off observations and interventions based on the cost of intervention. We also propose an algorithm that accounts for the cost of interventions, utilizes causal side-information, and minimizes the expected cumulative regret without exceeding the budget. Our cumulative-regret minimization algorithm performs better than standard algorithms that do not take side-information into account. Finally, we study the problem of learning best interventions without budget constraint in general graphs and give an algorithm that achieves constant expected cumulative regret in terms of the instance parameters when the parent distribution of the reward variable for each intervention is known. Our results are experimentally validated and compared to the best-known bounds in the current literature.