# Combinatorial Pure Exploration of Causal Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 16 Jun 2022.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Identifying Best Interventions through Online Importance Sampling](https://mlsanity.com/paper/1701.02789/) (2017)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [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)
- [Causal Bandits with Propagating Inference](https://mlsanity.com/paper/1806.02252/) (2018)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Separators and Adjustment Sets in Causal Graphs: Complete Criteria and an Algorithmic Framework](https://mlsanity.com/paper/1803.00116/) (2018)
- [Combinatorial Causal Bandits](https://mlsanity.com/paper/2206.01995/) (2022)
- [Matrix anti-concentration inequalities with applications](https://mlsanity.com/paper/2111.05553/) (2021)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)

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

- [Additive Causal Bandits with Unknown Graph](https://mlsanity.com/paper/2306.07858/) (2023)
- [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)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [A Correction of Pseudo Log-Likelihood Method](https://mlsanity.com/paper/2403.18127/) (2024)
- [Causal Contextual Bandits with Adaptive Context](https://mlsanity.com/paper/2405.18626/) (2024)
- [Generator-Mediated Bandits: Thompson Sampling for GenAI-Powered Adaptive Interventions](https://mlsanity.com/paper/2505.16311/) (2025)

## Abstract (arXiv)

The combinatorial pure exploration of causal bandits is the following online learning task: given a causal graph with unknown causal inference distributions, in each round we choose a subset of variables to intervene or do no intervention, and observe the random outcomes of all random variables, with the goal that using as few rounds as possible, we can output an intervention that gives the best (or almost best) expected outcome on the reward variable Y with probability at least 1-δ, where δ is a given confidence level. We provide the first gap-dependent and fully adaptive pure exploration algorithms on two types of causal models -- the binary generalized linear model (BGLM) and general graphs. For BGLM, our algorithm is the first to be designed specifically for this setting and achieves polynomial sample complexity, while all existing algorithms for general graphs have either sample complexity exponential to the graph size or some unreasonable assumptions. For general graphs, our algorithm provides a significant improvement on sample complexity, and it nearly matches the lower bound we prove. Our algorithms achieve such improvement by a novel integration of prior causal bandit algorithms and prior adaptive pure exploration algorithms, the former of which utilize the rich observational feedback in causal bandits but are not adaptive to reward gaps, while the latter of which have the issue in reverse.