Identifying Best Interventions through Online Importance Sampling

Abstract

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.

30 pages, 11 figures

References in corpus (11)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• "Why Should I Trust You?": Explaining the Predictions of Any Classifier
• Distinguishing cause from effect using observational data: methods and benchmarks
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Two Optimal Strategies for Active Learning of Causal Models from Interventional Data
• Causal Bandits: Learning Good Interventions via Causal Inference
• Cyclic Causal Discovery from Continuous Equilibrium Data
• Learning Causal Graphs with Small Interventions
• Dynamic Ad Allocation: Bandits with Budgets

Cited by in corpus (9)

• Causal Confusion in Imitation Learning
• Causal Bandits with Unknown Graph Structure
• Causal Markov Decision Processes: Learning Good Interventions Efficiently
• Regret Analysis of Bandit Problems with Causal Background Knowledge
• Bandit Algorithms for Precision Medicine
• Contextual Bandits with Stochastic Experts
• Budgeted and Non-budgeted Causal Bandits
• Identifying Best Fair Intervention
• A Guiding Principle for Causal Decision Problems