# Additive Causal Bandits with Unknown Graph

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 13 Jun 2023.

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

- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (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)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [Causal Bandits without prior knowledge using separating sets](https://mlsanity.com/paper/2009.07916/) (2020)
- [A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounders](https://mlsanity.com/paper/2107.02772/) (2021)
- [Combinatorial Pure Exploration of Causal Bandits](https://mlsanity.com/paper/2206.07883/) (2022)
- [Extended Conditional Independence and Applications in Causal Inference](https://mlsanity.com/paper/1512.00245/) (2015)

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

- [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)
- [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)
- [Causal Contextual Bandits with Adaptive Context](https://mlsanity.com/paper/2405.18626/) (2024)
- [Graph Agnostic Causal Bayesian Optimisation](https://mlsanity.com/paper/2411.03028/) (2024)
- [Causal Bayesian Optimization with Unknown Graphs](https://mlsanity.com/paper/2503.19554/) (2025)

## Abstract (arXiv)

We explore algorithms to select actions in the causal bandit setting where the learner can choose to intervene on a set of random variables related by a causal graph, and the learner sequentially chooses interventions and observes a sample from the interventional distribution. The learner's goal is to quickly find the intervention, among all interventions on observable variables, that maximizes the expectation of an outcome variable. We depart from previous literature by assuming no knowledge of the causal graph except that latent confounders between the outcome and its ancestors are not present. We first show that the unknown graph problem can be exponentially hard in the parents of the outcome. To remedy this, we adopt an additional additive assumption on the outcome which allows us to solve the problem by casting it as an additive combinatorial linear bandit problem with full-bandit feedback. We propose a novel action-elimination algorithm for this setting, show how to apply this algorithm to the causal bandit problem, provide sample complexity bounds, and empirically validate our findings on a suite of randomly generated causal models, effectively showing that one does not need to explicitly learn the parents of the outcome to identify the best intervention.