Budgeted and Non-budgeted Causal Bandits
  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.
