# Causal Bandits with Unknown Graph Structure

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 48 references that are in the map.
- First posted on arXiv 5 Jun 2021.

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

- [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)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [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)
- [Experimental Design for Cost-Aware Learning of Causal Graphs](https://mlsanity.com/paper/1810.11867/) (2018)
- [Regret Analysis of Bandit Problems with Causal Background Knowledge](https://mlsanity.com/paper/1910.04938/) (2019)

## Built on by (most cited first, 30 of 37)

- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [A Survey on Causal Reinforcement Learning](https://mlsanity.com/paper/2302.05209/) (2023)
- [Active Learning for Optimal Intervention Design in Causal Models](https://mlsanity.com/paper/2209.04744/) (2022)
- [Causal Reinforcement Learning: A Survey](https://mlsanity.com/paper/2307.01452/) (2023)
- [Causal Deep Learning](https://mlsanity.com/paper/2303.02186/) (2023)
- [Causal Bandits for Linear Structural Equation Models](https://mlsanity.com/paper/2208.12764/) (2022)
- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [Combinatorial Causal Bandits](https://mlsanity.com/paper/2206.01995/) (2022)
- [A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounders](https://mlsanity.com/paper/2107.02772/) (2021)
- [Achieving Counterfactual Fairness for Causal Bandit](https://mlsanity.com/paper/2109.10458/) (2021)
- [Causal Entropy Optimization](https://mlsanity.com/paper/2208.10981/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Causal Bandits without Graph Learning](https://mlsanity.com/paper/2301.11401/) (2023)
- [Additive Causal Bandits with Unknown Graph](https://mlsanity.com/paper/2306.07858/) (2023)
- [Combinatorial Pure Exploration of Causal Bandits](https://mlsanity.com/paper/2206.07883/) (2022)
- [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)
- [Learning Good Interventions in Causal Graphs via Covering](https://mlsanity.com/paper/2305.04638/) (2023)
- [Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2310.07518/) (2023)
- [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)
- [Transfer Learning in Latent Contextual Bandits with Covariate Shift Through Causal Transportability](https://mlsanity.com/paper/2502.20153/) (2025)
- [Uplifting Bandits](https://mlsanity.com/paper/2206.04091/) (2022)
- [Improved Bound for Robust Causal Bandits with Linear Models](https://mlsanity.com/paper/2405.07795/) (2024)
- [Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals](https://mlsanity.com/paper/2407.00950/) (2024)
- [Asymmetric Graph Error Control with Low Complexity in Causal Bandits](https://mlsanity.com/paper/2408.11240/) (2024)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Intervention Efficient Algorithm for Two-Stage Causal MDPs](https://mlsanity.com/paper/2111.00886/) (2021)
- [Causal Contextual Bandits with Adaptive Context](https://mlsanity.com/paper/2405.18626/) (2024)

## Abstract (arXiv)

In causal bandit problems, the action set consists of interventions on variables of a causal graph. Several researchers have recently studied such bandit problems and pointed out their practical applications. However, all existing works rely on a restrictive and impractical assumption that the learner is given full knowledge of the causal graph structure upfront. In this paper, we develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and a general class of causal graphs. The regret guarantees of our algorithms greatly improve upon those of standard multi-armed bandit (MAB) algorithms under mild conditions. Lastly, we prove our mild conditions are necessary: without them one cannot do better than standard MAB algorithms.