# Causal Bandits with Propagating Inference

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2018.

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

- [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 Bandits for Linear Structural Equation Models](https://mlsanity.com/paper/2208.12764/) (2022)
- [Invariant Policy Learning: A Causal Perspective](https://mlsanity.com/paper/2106.00808/) (2021)
- [Matching a Desired Causal State via Shift Interventions](https://mlsanity.com/paper/2107.01850/) (2021)
- [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)
- [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)
- [Linear Causal Bandits: Unknown Graph and Soft Interventions](https://mlsanity.com/paper/2411.02383/) (2024)
- [Improved Bound for Robust Causal Bandits with Linear Models](https://mlsanity.com/paper/2405.07795/) (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)
- [Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment](https://mlsanity.com/paper/2502.02020/) (2025)
- [The Minimal Search Space for Conditional Causal Bandits](https://mlsanity.com/paper/2502.06577/) (2025)
- [Generator-Mediated Bandits: Thompson Sampling for GenAI-Powered Adaptive Interventions](https://mlsanity.com/paper/2505.16311/) (2025)
- [Hierarchical Causal Bandit](https://mlsanity.com/paper/2103.04215/) (2021)
- [Identifying Best Fair Intervention](https://mlsanity.com/paper/2111.04272/) (2021)
- [Information-Directed Sampling for Causal Bandits](https://mlsanity.com/paper/2607.15577/) (2026)

## Abstract (arXiv)

Bandit is a framework for designing sequential experiments. In each experiment, a learner selects an arm A ∈ A and obtains an observation corresponding to A. Theoretically, the tight regret lower-bound for the general bandit is polynomial with respect to the number of arms |A|. This makes bandit incapable of handling an exponentially large number of arms, hence the bandit problem with side-information is often considered to overcome this lower bound. Recently, a bandit framework over a causal graph was introduced, where the structure of the causal graph is available as side-information. A causal graph is a fundamental model that is frequently used with a variety of real problems. In this setting, the arms are identified with interventions on a given causal graph, and the effect of an intervention propagates throughout all over the causal graph. The task is to find the best intervention that maximizes the expected value on a target node. Existing algorithms for causal bandit overcame the Omega(√|A|/T) simple-regret lower-bound; however, their algorithms work only when the interventions A are localized around a single node (i.e., an intervention propagates only to its neighbors). We propose a novel causal bandit algorithm for an arbitrary set of interventions, which can propagate throughout the causal graph. We also show that it achieves O(√ γ^*log(|A|T) / T) regret bound, where γ^* is determined by using a causal graph structure. In particular, if the in-degree of the causal graph is bounded, then γ^* = O(N2), where N is the number N of nodes.