Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Linear Causal Bandits: Unknown Graph and Soft Interventions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GA-LCB, a causal bandit algorithm for unknown DAG structure and unknown stochastic soft interventions in linear SEMs, achieving sqrt(T) regret with a graph-learning phase and a scalable successive-elimination intervention design.
Problem
Causal bandits where both the causal graph and the pre/post-intervention (soft, stochastic) statistical models are unknown, with linear SEMs; prior soft-intervention methods assume known graphs and their UCB optimization is intractable.
Approach
Learns the skeleton via causal-bandit exploration (descendant/ancestor estimation from interventional mean differences, then Lasso for parents), then avoids the non-convex joint UCB optimization by computing UCB widths recursively through causal depth and using successive elimination over interventions.
Key results
- Regret upper bound of order (kappa d)^(L-1/2) sqrt(T) + d + RN under unknown graph; known-skeleton bound d^(L-1/2) sqrt(T), improving on the best known d^(2L-1) sqrt(T).
- Minimax lower bound Omega(d^(L-3/2) sqrt(T)), so upper and lower bounds match up to a factor of d in d and constant kappa^(L-1/2) in L.
- Experiments on hierarchical graphs show GA-LCB's running time is significantly lower than LinSEM-UCB and GCB-UCB at L=2 and better at L=4, though its regret is slightly higher than the baselines at L=2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GA-LCB instead of LinSEM-UCB | linear causal bandits with known graph and soft interventions · Known graph | cumulative regret upper bound: \tilde\mcO\left(d^{2L-\frac{3}{2}}\sqrt{NT}\right) -> \tilde\mcO\left( d^{L-\frac{1}{2}}\sqrt{T}\right) | Helped |
| Use GA-LCB instead of GCB-UCB | linear causal bandits with known graph and soft interventions · Known graph | cumulative regret upper bound: \tilde\mcO\left(d^{2L-1} \sqrt{T}\right) -> \tilde\mcO\left( d^{L-\frac{1}{2}}\sqrt{T}\right) | Helped |
| Use the graph-dependent intervention search over reward ancestors | GA-LCB · Graph-dependent setting | cumulative regret upper bound: (\kappa d)^{L-\frac{1}{2}} -> (\kappa d_e)^{L_e-\frac{1}{2}} | Helped |
| Learn the graph skeleton rather than assume it is known | GA-LCB · Unknown graph versus known skeleton | cumulative regret upper bound: \tilde \mcO\big(d^{L-\frac{1}{2}} \sqrt{T} \big) -> \tilde \mcO\big( (\kappa d)^{L-\frac{1}{2}} \sqrt{T} + d + R N \big) | Hurt |
| Use GA-LCB with known graph instead of LinSEM-UCB or GCB-UCB | hierarchical graph, d=3 and L=2 · Empirical cumulative regret | cumulative regret | Hurt |
| Add the structure-learning phase | GA-LCB · Hierarchical graph, d=3 and L=2 | cumulative regret | Hurt |
| Use phased elimination with GA-LCB | GA-LCB with known graph · Empirical cumulative regret | cumulative regret | Hurt |
| Use GA-LCB rather than LinSEM-UCB or GCB-UCB | hierarchical graph with L=2 · Computational time | running time | Helped |
| Increase causal depth L | GA-LCB on hierarchical graphs with d=2 · Regret scaling with L | cumulative regret | Hurt |
| Increase maximum in-degree d | GA-LCB on hierarchical graphs with L=2 · Regret scaling with d | cumulative regret | Hurt |
| Use the unknown-graph setting instead of the known-graph setting | GA-LCB on hierarchical graphs with L=4 and L=6 · Empirical cumulative regret | cumulative regret | Hurt |
Surprising findings
- On the small hierarchical graph (L=2, d=3), LinSEM-UCB and GCB-UCB achieve lower regret than GA-LCB, which is slightly worse despite the better theory.
Limitations
- Upper bound is looser than the lower bound by a factor of d and a constant kappa^(L-1/2).
- Requires known number of nodes, in-degree bound, and bounded weights/noise with known expected noise.
- Empirical regret is slightly higher than the existing baselines on small graphs, and structure learning adds regret.
Experimental setup
Datasets: synthetic hierarchical linear SEM graphs
Benchmarks: synthetic hierarchical graphs
Metrics: cumulative regret computational time
Baselines: LinSEM-UCB GCB-UCB
Builds on: LinSEM-UCB GCB-UCB C-UCB CN-UCB
Closest papers by meaning
- Causal Bandits with Propagating Inference (ICML 2018 · similarity 0.92)
- Additive Causal Bandits with Unknown Graph (ICML 2023 · similarity 0.92)
- Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.91)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.89)
- Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.87)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.