mlsanityData to 7 Oct 2026

Adaptively Exploiting d-Separators with Causal Bandits

arXiv 2202.05100 ↗First posted 10 Feb 2022stat.ML cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

Multi-armed bandit problems provide a framework to identify the optimal intervention over a sequence of repeated experiments. Without additional assumptions, minimax optimal performance (measured by cumulative regret) is well-understood. With access to additional observed variables that d-separate the intervention from the outcome (i.e., they are a d-separator), recent "causal bandit" algorithms provably incur less regret. However, in practice it is desirable to be agnostic to whether observed variables are a d-separator. Ideally, an algorithm should be adaptive; that is, perform nearly as well as an algorithm with oracle knowledge of the presence or absence of a d-separator. In this work, we formalize and study this notion of adaptivity, and provide a novel algorithm that simultaneously achieves (a) optimal regret when a d-separator is observed, improving on classical minimax algorithms, and (b) significantly smaller regret than recent causal bandit algorithms when the observed variables are not a d-separator. Crucially, our algorithm does not require any oracle knowledge of whether a d-separator is observed. We also generalize this adaptivity to other conditions, such as the front-door criterion.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 15 of its 41 references that are in the map. First posted on arXiv 10 Feb 2022.

Builds on

15 of 41 references.

References · 15

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2016Causal Bandits: Learning Good Interventions via Causal Inferencecited by 100
  4. 2016Corralling a Band of Bandit Algorithmscited by 99
  5. 2017Cost-Optimal Learning of Causal Graphscited by 44
  6. 2017Identifying Best Interventions through Online Importance Samplingcited by 39
  7. 2020Budgeted and Non-budgeted Causal Banditscited by 38
  8. 2021Causal Bandits with Unknown Graph Structurecited by 37
  9. 2016Contextual Bandits with Latent Confounders: An NMF Approachcited by 26
  10. 2018Experimental Design for Cost-Aware Learning of Causal Graphscited by 25
  11. 2020Corralling Stochastic Bandit Algorithmscited by 23
  12. 2020Causal Bandits without prior knowledge using separating setscited by 17
3 more
  1. 2015The Pareto Regret Frontier for Banditscited by 13
  2. 2020Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularizationcited by 8
  3. 2018Adaptation to Easy Data in Prediction with Limited Advicecited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 6; 2025: 4; 2026: 1.

18 papers.

Sort:

  1. 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
  2. 2023Causal Reinforcement Learning: A Surveycited by 22
  3. 2023Causal Deep Learningcited by 20
  4. 2022Causal Bandits for Linear Structural Equation Modelscited by 19
  5. 2023Additive Causal Bandits with Unknown Graphcited by 10
  6. 2023Intervention Generalization: A View from Factor Graph Modelscited by 7
  7. 2024Causal Bandits with General Causal Models and Interventionscited by 7
  8. 2024Causally Abstracted Multi-armed Banditscited by 5
  9. 2024Linear Causal Bandits: Unknown Graph and Soft Interventionscited by 5
  10. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directionscited by 5
  11. 2023Robust Causal Bandits for Linear Modelscited by 4
  12. 2025Transfer Learning in Latent Contextual Bandits with Covariate Shift Through Causal Transportabilitycited by 4
6 more
  1. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  2. 2024Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginalscited by 2
  3. 2024Asymmetric Graph Error Control with Low Complexity in Causal Banditscited by 2
  4. 2025Graph Learning Is Suboptimal in Causal Banditscited by 2
  5. 2025Using causal abstractions to accelerate decision-making in complex bandit problemscited by 1
  6. 2025On Transportability for Structural Causal Banditscited by 1