# Causal Bandits without Graph Learning

arXiv: https://arxiv.org/abs/2301.11401 · HTML: https://mlsanity.com/paper/2301.11401/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 26 Jan 2023.

## Builds on (most cited first, 9 of 9)

- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [Identifying Best Interventions through Online Importance Sampling](https://mlsanity.com/paper/1701.02789/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Budgeted and Non-budgeted Causal Bandits](https://mlsanity.com/paper/2012.07058/) (2020)
- [Causal Bandits with Unknown Graph Structure](https://mlsanity.com/paper/2106.02988/) (2021)
- [Contextual Multi-Armed Bandits for Causal Marketing](https://mlsanity.com/paper/1810.01859/) (2018)
- [Causal Bandits without prior knowledge using separating sets](https://mlsanity.com/paper/2009.07916/) (2020)
- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)

## Built on by (most cited first, 10 of 10)

- [Combinatorial Causal Bandits without Graph Skeleton](https://mlsanity.com/paper/2301.13392/) (2023)
- [Causal Bandits with General Causal Models and Interventions](https://mlsanity.com/paper/2403.00233/) (2024)
- [Linear Causal Bandits: Unknown Graph and Soft Interventions](https://mlsanity.com/paper/2411.02383/) (2024)
- [Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits](https://mlsanity.com/paper/2411.04054/) (2024)
- [Robust Causal Bandits for Linear Models](https://mlsanity.com/paper/2310.19794/) (2023)
- [Improved Bound for Robust Causal Bandits with Linear Models](https://mlsanity.com/paper/2405.07795/) (2024)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Graph Agnostic Causal Bayesian Optimisation](https://mlsanity.com/paper/2411.03028/) (2024)
- [Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment](https://mlsanity.com/paper/2502.02020/) (2025)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)

## Abstract (arXiv)

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.