Causal Bandits: Learning Good Interventions via Causal Inference
We study the problem of using causal models to improve the rate at which good interventions can be learned online in a stochastic environment. Our formalism combines multi-arm bandits and causal inference to model a novel type of bandit feedback that is not exploited by existing approaches. We propose a new algorithm that exploits the causal feedback and prove a bound on its simple regret that is strictly better (in all quantities) than algorithms that do not use the additional causal information.
I have read the author feedback, and stand by my recommendation for accepting the submission as a poster. The paper studies a novel problem formulation that can apply to several real world problems (e.g., many applications that are currently modeled as contextual bandits). After reading the author feedback, I am suitably convinced that this formulation is not trivially solved by partial monitoring or Bareinboim et al, 2015 etc.  I can see several follow-ups that study the connections between graph properties of the underlying causal graph and simple/cumulative regret and jointly learning causal structure online, etc. more thoroughly. Alg2 and its assumptions are unfortunately too limiting, but the basic ideas can spur further research.   --Earlier review follows below--  The paper studies best arm identification in multi-armed bandits, where on each round, a reward as well as a bunch of covariates are revealed to the learner (like in partial monitoring games). These covariates influence the reward through a known causal model, and this additional information is used to develop an algorithm with minimax optimal simple regret (up to log factors) for "parallel" causal graphs (covariates independently influence reward). Moreover, an algorithm that requires additional information about conditional intervention distributions (to estimate a quantity m < #actions) provably achieves \tilde{O}(sqrt(m/T)) simple regret. Simulations show that these methods can indeed perform better than the Successive Reject algorithm by knowing the correct causal model.
I have read the author feedback, and stand by my recommendation for accepting the submission as a poster. The paper studies a novel problem formulation that can apply to several real world problems (e.g., many applications that are currently modeled as contextual bandits). After reading the author feedback, I am suitably convinced that this formulation is not trivially solved by partial monitoring or Bareinboim et al, 2015 etc.  I can see several follow-ups that study the connections between graph properties of the underlying causal graph and simple/cumulative regret and jointly learning causal structure online, etc. more thoroughly. Alg2 and its assumptions are unfortunately too limiting, but the basic ideas can spur further research.   --Earlier review follows below--  The paper was clear to follow and introduces a novel model in multi-armed bandit problems with well-analyzed algorithms. I appreciate that code implementing the experiment was available in the supplementary. My comments below focus only on the weaknesses.  The paper motivates a nice model of reward-feedback in the multi-armed bandit problem. However, please elaborate on the differences between this model and combinatorial partial monitoring (e.g. Tian Lin et al, Combinatorial Partial Monitoring Game with Linear Feedback and Its Applications, ICML 2014). In particular, are there suitable choices of encoding the outcome vector, action matrices etc. in CombPM that recovers every causal model instance? Or the other way around? Or are the two incomparable (with a counter-example in each direction)?  The simulated experiment was a weak point of the paper. First I don't understand why lil'UCB was not simulated (rather than/in addition to Successive Reject). Secondly, I do not understand the comment about Alon et al's algorithms for adversarial bandits with feedback graphs. Yes a malicious adversary can set q = 0 but I don't see why Algorithm 1 or 2 (or their variant) do any better than their algorithm in that case (m(q)=N then). Thirdly, the terrible performance of Alg 1 and 2 in Fig 2(a) only convinces me that the asymptotic regret analysis is giving us an incomplete picture of these algorithms' performance (for instance, being reward oblivious is nearly minimax optimal simple regret!) I would like to see a discussion on how better to characterize their performance (e.g. would cumulative regret be the right thing to tell these algorithms apart? Would the idea sketched in Section 6 then be nearly minimax-optimal too)?  Assuming that conditional intervention distributions is known is, as the paper admits, quite limiting. I can also intuitively see that we need some way to link the action we take to how it affects the outcomes for the parents of Y in the causal graph (as also the reward outcome Y). Is this assumption equivalent to saying, the results provably work only for causal models where all non-Y nodes are parents of Y (so, a parallel graph with additional edges between X_i) and intervening on some subset of the non-Y nodes are the allowed actions? If so, I find the chain graph example distracting (yes, multiple intervention rewards can be observed there, but we cannot really exploit that without additional knowledge).  Interesting choice of truncation, and I found the comment about empirical results when B_a is set higher intriguing. Am I correctly understanding that clipping as Y_t min{B_a, R_a(X_t)} rather than Y_t R_a(X_t) I{R_a(X_t) < B_a} will introduce less bias and could work better (although worst-case analysis does not change)? On line 280: no truncation was performed for Algorithm 2, so could it also be unbounded variance hurting Alg 2?  Minor comments:  201: P{X_1 = 1} = 0. 321: "reach round" -> each