Identifying Best Interventions through Online Importance Sampling

By Rajat Sen, Karthikeyan Shanmugam, A. Dimakis, Sanjay Shakkottai. 2017

82 citations recorded by the source corpus.

Motivated by applications in computational advertising and systems biology, we consider the problem of identifying the best out of several possible soft interventions at a source node V in an acyclic causal directed graph, to maximize the expected value of a target node Y (located downstream of V). Our setting imposes a fixed total budget for sampling under various interventions, along with cost constraints on different types of interventions. We pose this as a best arm identification bandit problem with K arms where each arm is a soft intervention at V, and leverage the information leakage among the arms to provide the first gap dependent error and simple regret bounds for this problem. Our results are a significant improvement over the traditional best arm identification results. We empirically show that our algorithms outperform the state of the art in the Flow Cytometry data-set, and also apply our algorithm for model interpretation of the Inception-v3 deep net that classifies images.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Causal Reasoning from Meta-reinforcement Learning (2019, background): “Despite advances in both (Or-tega and Stocker, 2015; Lattimore et al., 2016; Bramley et al., 2017; Forney et al., 2017; Sen et al., 2017; Parida et al., 2018), inducing models is expensive and typically requires simplifying assumptions.”
Causal Confusion in Imitation Learning (2019, methodology): “We operate in the interventional regime [55, 11, 49, 48] where a user may “experiment” to discover causal structures by assigning values to some subset of the variables of interest and observing the effects on the rest of the system.”
Counterfactual Data-Fusion for Online Reinforcement Learners (2017, unknown): “w (a form of information leakage, (15)).”