Learning good interventions in causal graphs via covering
Article No.: 171, Pages 1827 - 1836
Abstract
We study the causal bandit problem that entails identifying a near-optimal intervention from a specified set A of (possibly non-atomic) interventions over a given causal graph. Here, an optimal intervention in A is one that maximizes the expected value for a designated reward variable in the graph, and we use the standard notion of simple regret to quantify near optimality. Considering Bernoulli random variables and for causal graphs on N vertices with constant in-degree, prior work has achieved a worst case guarantee of Õ(N/√T) for simple regret. The current work utilizes the idea of covering interventions (which are not necessarily contained within A) and establishes a simple regret guarantee of Õ(√N/T). Notably, and in contrast to prior work, our simple regret bound depends only on explicit parameters of the problem instance. We also go beyond prior work and achieve a simple regret guarantee for causal graphs with unobserved variables. Further, we perform experiments to show improvements over baselines in this setting.
Supplementary Material
Supplemental material.
- Download
- 243.99 KB
References
[1]
Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. Learning and testing causal models with interventions. Advances in Neural Information Processing Systems, 31, 2018.
[2]
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[3]
Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counter-factual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
[4]
Pascal Caillet, Sarah Klemm, Michel Ducher, Alexandre Aussem, and Anne-Marie Schott. Hip fracture in the elderly: a re-analysis of the epidos study with causal bayesian networks. PLoS One, 10(3):e0120125, 2015.
[5]
Daniel Koch, Robert S Eisinger, and Alexander Gebharter. A causal bayesian network model of disease progression mechanisms in chronic myeloid leukemia. Journal of theoretical biology, 433:94-105, 2017.
[6]
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. Advances in Neural Information Processing Systems, 29, 2016.
[7]
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[8]
Sujee Lee, Sijie Wang, Philip A Bain, Christine Baker, Tammy Kundinger, Craig Sommers, and Jingshan Li. Reducing copd readmissions: A causal bayesian network model. IEEE Robotics and Automation Letters, 3(4): 4046-4053, 2018.
[9]
Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pages 141-150. PMLR, 2020.
[10]
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. Advances in Neural Information Processing Systems, 34:24817-24828, 2021.
[11]
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Efficient reinforcement learning with prior causal knowledge. In Conference on Causal Learning and Reasoning, pages 526-541. PMLR, 2022.
[12]
Aurghya Maiti, Vineet Nair, and Gaurav Sinha. A causal bandit approach to learning good atomic interventions in presence of unobserved confounders. In Uncertainty in Artificial Intelligence, pages 1328-1338. PMLR, 2022.
[13]
Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits. In International Conference on Artificial Intelligence and Statistics, pages 2017-2025. PMLR, 2021.
[14]
Judea Pearl. Causality: Models, reasoning and inference. Cambridge, UK: Cambridge University Press, 19(2), 2000.
[15]
Judea Pearl. Causality. Cambridge university press, 2009.
[16]
Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. In International Conference on Machine Learning, pages 3057-3066. PMLR, 2017a.
[17]
Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alex Dimakis, and Sanjay Shakkottai. Contextual bandits with latent confounders: An nmf approach. In Artificial Intelligence and Statistics, pages 518-527. PMLR, 2017b.
[18]
Jaime Sevilla. Explaining data using causal bayesian networks. In 2nd Workshop on Interactive Natural Language Technology for Explainable Artificial Intelligence, pages 34-38, 2020.
[19]
Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends® in Machine Learning, 12 (1-2):1-286, 2019.
[20]
Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. In Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pages 519-527, 2002.
[21]
Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. arXiv preprint arXiv:2208.12764, 2022.
[22]
Nuoya Xiong and Wei Chen. Combinatorial pure exploration of causal bandits. In International Conference on Learning Representations, 2023.
[23]
Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, and Ken-ichi Kawarabayashi. Causal bandits with propagating inference. In International Conference on Machine Learning, pages 5512-5520. PMLR, 2018.
[24]
Takami Yoshida and Kazuhiro Nakadai. Active audio-visual integration for voice activity detection based on a causal bayesian network. In 2012 12th IEEE-RAS International Conference on Humanoid Robots (Humanoids 2012), pages 370-375. IEEE, 2012.
Recommendations
Local Clique Covering of Claw-Free Graphs
A k-clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called the local clique cover number of ...
Learning causal graphs with small interventions
NIPS'15: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover ...
On edge covering colorings of graphs
An edge covering coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least one time. The maximum integer k such that G has an edge covering coloring with k colors is called the edge covering chromatic index of G ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 Association for Uncertainty in Artificial Intelligence.
Publisher
JMLR.org
Publication History
Published: 31 July 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025