Improved Bound for Robust Causal Bandits with Linear Models
Not on the map. Why?
Abstract (arXiv)
This paper investigates the robustness of causal bandits (CBs) in the face of temporal model fluctuations. This setting deviates from the existing literature's widely-adopted assumption of constant causal models. The focus is on causal systems with linear structural equation models (SEMs). The SEMs and the time-varying pre- and post-interventional statistical models are all unknown and subject to variations over time. The goal is to design a sequence of interventions that incur the smallest cumulative regret compared to an oracle aware of the entire causal model and its fluctuations. A robust CB algorithm is proposed, and its cumulative regret is analyzed by establishing both upper and lower bounds on the regret. It is shown that in a graph with maximum in-degree d, length of the largest causal path L, and an aggregate model deviation C, the regret is upper bounded by tildeO(d^L-frac12(√T + C)) and lower bounded by Omega(d^fracL2-2max√T; ,; d2C). The proposed algorithm achieves nearly optimal tildeO(√T) regret when C is o(√T), maintaining sub-linear regret for a broad range of C.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 30 of its 39 references that are in the map. First posted on arXiv 13 May 2024.
Builds on
30 of 39 references.
References · 30
- 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
- 2016Causal Bandits: Learning Good Interventions via Causal Inferencecited by 100
- 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
- 2021Adapting to Misspecification in Contextual Banditscited by 81
- 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
- 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
- 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
- 2018Causal Discovery in the Presence of Missing Datacited by 46
- 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
- 2017Learning Graph-Level Representation for Drug Discoverycited by 43
- 2017Misspecified Linear Banditscited by 41
- 2017Identifying Best Interventions through Online Importance Samplingcited by 39
18 more
- 2020Budgeted and Non-budgeted Causal Banditscited by 38
- 2021Causal Bandits with Unknown Graph Structurecited by 37
- 2022Model-based Causal Bayesian Optimizationcited by 26
- 2018Causal Bandits with Propagating Inferencecited by 23
- 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
- 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
- 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
- 2022Causal Bandits for Linear Structural Equation Modelscited by 19
- 2022Adaptively Exploiting d-Separators with Causal Banditscited by 18
- 2020Causal Bandits without prior knowledge using separating setscited by 17
- 2022Combinatorial Causal Banditscited by 16
- 2021A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounderscited by 15
- 2023Causal Bandits without Graph Learningcited by 10
- 2023Additive Causal Bandits with Unknown Graphcited by 10
- 2017Causal Discovery in the Presence of Measurement Error: Identifiability Conditionscited by 9
- 2023Combinatorial Causal Bandits without Graph Skeletoncited by 7
- 2023Learning Good Interventions in Causal Graphs via Coveringcited by 5
- 2023Robust Causal Bandits for Linear Modelscited by 4
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.