Additive Causal Bandits with Unknown Graph
Alan Malek Virginia Aglietti Silvia Chiappa
We explore algorithms to select actions in the causal bandit setting where
the learner can choose to intervene on a set of random variables related by a
causal graph, and the learner sequentially chooses interventions and observes a
sample from the interventional distribution. The learner's goal is to quickly
find the intervention, among all interventions on observable variables, that
maximizes the expectation of an outcome variable. We depart from previous
literature by assuming no knowledge of the causal graph except that latent
confounders between the outcome and its ancestors are not present. We first
show that the unknown graph problem can be exponentially hard in the parents of
the outcome. To remedy this, we adopt an additional additive assumption on the
outcome which allows us to solve the problem by casting it as an additive
combinatorial linear bandit problem with full-bandit feedback. We propose a
novel action-elimination algorithm for this setting, show how to apply this
algorithm to the causal bandit problem, provide sample complexity bounds, and
empirically validate our findings on a suite of randomly generated causal
models, effectively showing that one does not need to explicitly learn the
parents of the outcome to identify the best intervention.