# Linear Causal Bandits: Unknown Graph and Soft Interventions

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

## Key facts

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

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

- [CausalWorld: A Robotic Manipulation Benchmark for Causal Structure and Transfer Learning](https://mlsanity.com/paper/2010.04296/) (2020)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Confidence Intervals and Hypothesis Testing for High-Dimensional Regression](https://mlsanity.com/paper/1306.3171/) (2013)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [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)
- [Model-based Causal Bayesian Optimization](https://mlsanity.com/paper/2211.10257/) (2022)
- [Causal Bandits with Propagating Inference](https://mlsanity.com/paper/1806.02252/) (2018)
- [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)
- [Causal Bandits without prior knowledge using separating sets](https://mlsanity.com/paper/2009.07916/) (2020)
- [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)
- [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023)
- [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 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)
- [Adversarial Causal Bayesian Optimization](https://mlsanity.com/paper/2307.16625/) (2023)
- [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)

## 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)
- [Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment](https://mlsanity.com/paper/2502.02020/) (2025)
- [Causal Bayesian Optimization with Unknown Graphs](https://mlsanity.com/paper/2503.19554/) (2025)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)

## Abstract (arXiv)

Designing causal bandit algorithms depends on two central categories of assumptions: (i) the extent of information about the underlying causal graphs and (ii) the extent of information about interventional statistical models. There have been extensive recent advances in dispensing with assumptions on either category. These include assuming known graphs but unknown interventional distributions, and the converse setting of assuming unknown graphs but access to restrictive hard/operatornamedo interventions, which removes the stochasticity and ancestral dependencies. Nevertheless, the problem in its general form, i.e., unknown graph and unknown stochastic intervention models, remains open. This paper addresses this problem and establishes that in a graph with N nodes, maximum in-degree d and maximum causal path length L, after T interaction rounds the regret upper bound scales as tildeO((cd)^L-frac12√T + d + RN) where c>1 is a constant and R is a measure of intervention power. A universal minimax lower bound is also established, which scales as Omega(d^L-frac32√T). Importantly, the graph size N has a diminishing effect on the regret as T grows. These bounds have matching behavior in T, exponential dependence on L, and polynomial dependence on d (with the gap d ). On the algorithmic aspect, the paper presents a novel way of designing a computationally efficient CB algorithm, addressing a challenge that the existing CB algorithms using soft interventions face.