Causal Bandits without Graph Learning

Mikhail Konobeev, Jalal Etesami, Negar Kiyavash
Proceedings of the Fourth Conference on Causal Learning and Reasoning, PMLR 275:31-63, 2025.

Abstract

We study the causal bandit problem when the causal graph is unknown and develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We derive the exact equation for the expected number of interventions performed by the algorithm and show that under certain graphical conditions it could perform either logarithmically fast or, under more general assumptions, slower but still sublinearly in the number of variables. We formally show that our algorithm is optimal as it meets the universal lower bound we establish for any algorithm that performs atomic interventions. Finally, we extend our algorithm to the case when the reward node has multiple parents. Using this algorithm together with a standard algorithm from bandit literature leads to improved regret bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v275-konobeev25a, title = {Causal Bandits without Graph Learning}, author = {Konobeev, Mikhail and Etesami, Jalal and Kiyavash, Negar}, booktitle = {Proceedings of the Fourth Conference on Causal Learning and Reasoning}, pages = {31--63}, year = {2025}, editor = {Huang, Biwei and Drton, Mathias}, volume = {275}, series = {Proceedings of Machine Learning Research}, month = {07--09 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v275/main/assets/konobeev25a/konobeev25a.pdf}, url = {https://proceedings.mlr.press/v275/konobeev25a.html}, abstract = {We study the causal bandit problem when the causal graph is unknown and develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We derive the exact equation for the expected number of interventions performed by the algorithm and show that under certain graphical conditions it could perform either logarithmically fast or, under more general assumptions, slower but still sublinearly in the number of variables. We formally show that our algorithm is optimal as it meets the universal lower bound we establish for any algorithm that performs atomic interventions. Finally, we extend our algorithm to the case when the reward node has multiple parents. Using this algorithm together with a standard algorithm from bandit literature leads to improved regret bounds.} }
Endnote
%0 Conference Paper %T Causal Bandits without Graph Learning %A Mikhail Konobeev %A Jalal Etesami %A Negar Kiyavash %B Proceedings of the Fourth Conference on Causal Learning and Reasoning %C Proceedings of Machine Learning Research %D 2025 %E Biwei Huang %E Mathias Drton %F pmlr-v275-konobeev25a %I PMLR %P 31--63 %U https://proceedings.mlr.press/v275/konobeev25a.html %V 275 %X We study the causal bandit problem when the causal graph is unknown and develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We derive the exact equation for the expected number of interventions performed by the algorithm and show that under certain graphical conditions it could perform either logarithmically fast or, under more general assumptions, slower but still sublinearly in the number of variables. We formally show that our algorithm is optimal as it meets the universal lower bound we establish for any algorithm that performs atomic interventions. Finally, we extend our algorithm to the case when the reward node has multiple parents. Using this algorithm together with a standard algorithm from bandit literature leads to improved regret bounds.
APA
Konobeev, M., Etesami, J. & Kiyavash, N.. (2025). Causal Bandits without Graph Learning. Proceedings of the Fourth Conference on Causal Learning and Reasoning, in Proceedings of Machine Learning Research 275:31-63 Available from https://proceedings.mlr.press/v275/konobeev25a.html.

Related Material