# Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 6 Nov 2024.

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

- [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)
- [A Survey on Causal Discovery: Theory and Practice](https://mlsanity.com/paper/2305.10032/) (2023)
- [Identifying Best Interventions through Online Importance Sampling](https://mlsanity.com/paper/1701.02789/) (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)
- [Active Bayesian Causal Inference](https://mlsanity.com/paper/2206.02063/) (2022)
- [Causal Bandits without prior knowledge using separating sets](https://mlsanity.com/paper/2009.07916/) (2020)
- [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)

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

- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Epistemic Regret Minimization: Label-Free Causal Critique Beyond Outcome Reward](https://mlsanity.com/paper/2602.11675/) (2026)
- [On Transportability for Structural Causal Bandits](https://mlsanity.com/paper/2511.17953/) (2025)
- [Causal Bayesian Optimization with Unknown Graphs](https://mlsanity.com/paper/2503.19554/) (2025)
- [Information-Directed Sampling for Causal Bandits](https://mlsanity.com/paper/2607.15577/) (2026)

## Abstract (arXiv)

Causal knowledge about the relationships among decision variables and a reward variable in a bandit setting can accelerate the learning of an optimal decision. Current works often assume the causal graph is known, which may not always be available a priori. Motivated by this challenge, we focus on the causal bandit problem in scenarios where the underlying causal graph is unknown and may include latent confounders. While intervention on the parents of the reward node is optimal in the absence of latent confounders, this is not necessarily the case in general. Instead, one must consider a set of possibly optimal arms/interventions, each being a special subset of the ancestors of the reward node, making causal discovery beyond the parents of the reward node essential. For regret minimization, we identify that discovering the full causal structure is unnecessary; however, no existing work provides the necessary and sufficient components of the causal graph. We formally characterize the set of necessary and sufficient latent confounders one needs to detect or learn to ensure that all possibly optimal arms are identified correctly. We also propose a randomized algorithm for learning the causal graph with a limited number of samples, providing a sample complexity guarantee for any desired confidence level. In the causal bandit setup, we propose a two-stage approach. In the first stage, we learn the induced subgraph on ancestors of the reward, along with a necessary and sufficient subset of latent confounders, to construct the set of possibly optimal arms. The regret incurred during this phase scales polynomially with respect to the number of nodes in the causal graph. The second phase involves the application of a standard bandit algorithm, such as the UCB algorithm. We also establish a regret bound for our two-phase approach, which is sublinear in the number of rounds.