Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits
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.
Shows that causal bandits with unknown graphs and latent confounders need only learn a partial structure (ancestral subgraph plus necessary confounders) to identify all possibly optimal arms, and proposes a two-phase discover-then-UCB algorithm with sublinear regret.
Problem
Causal bandits where the causal graph is unknown and may contain latent confounders; the optimal intervention may be a subset of the reward's ancestors rather than its parents, so full causal discovery is costly.
Approach
Characterizes the necessary and sufficient latent confounders between the reward and its ancestors (and certain ancestor pairs) needed to recover all POMISs, then learns only that partial structure via a randomized, interventional-data-based discovery procedure before running UCB over the reduced arm set.
Key results
- Partial discovery requires fewer interventional samples than learning the full induced graph with all confounders across 10, 15 and 20-node random graphs, with the advantage shrinking as confounder density rho_L grows.
- Regret bound for the two-phase algorithm is sublinear in T, with discovery-phase cost polynomial in the number of graph nodes and the UCB term scaling with the number of POMISs.
- Discovery reduces the action space from (K+1)^n arms to the POMIS set before running UCB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn only the subgraph and confounders needed to identify POMISs, rather than learning all confounders | Causal bandits with unknown graphs · Randomly generated causal graphs | interventional samples | Helped |
| Increase confounder density while holding graph density fixed | Proposed partial-discovery algorithm versus full graph discovery · Randomly generated causal graphs | interventional samples | Mixed |
| Use partial discovery to reduce the action set to POMISs before running UCB | Causal bandits with unknown graphs · Causal bandits, graphs with 10, 15, and 20 nodes | interventional samples | Helped |
| Run UCB on the learned POMIS set after discovery | Proposed causal bandit algorithm · Randomly sampled causal graphs | cumulative regret | Helped |
Limitations
- Worst-case number of POMISs can still be exponential in the number of ancestors of the reward.
- Requires gap assumptions (epsilon, gamma, eta) and a bound on maximum degree d_max for guarantees.
- Learning confounders requires many more samples than ancestral tests, since conditional causal effects must be estimated.
Experimental setup
Datasets: synthetic random causal graphs (10, 15, 20 nodes, binary variables)
Benchmarks: synthetic random causal graphs
Metrics: interventional sample count cumulative regret
Baselines: full graph discovery with latent confounders UCB over all interventions
Builds on: POMIS enumeration (Lee and Bareinboim) UCB randomized causal discovery with interventions (Kocaoglu-style) Do-see test
Closest papers by meaning
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.92)
- Linear Causal Bandits: Unknown Graph and Soft Interventions (NeurIPS 2024 · similarity 0.91)
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.90)
- Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.89)
- Sample Efficient Bayesian Learning of Causal Graphs from Interventions (NeurIPS 2024 · similarity 0.88)
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.88)
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.