Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals
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.
Characterizes the Pareto optimal frontier of regret for causal bandits adapting between conditionally benign and arbitrary environments, gives a reduction to linear bandits enabling instance-dependent bounds, and shows approximate marginals are needed for better-than-worst-case rates.
Problem
Adapting multi-armed bandit learners to whether post-action context d-separates actions from rewards (conditionally benign structure), without knowing which holds, while keeping minimax regret guarantees; also how marginal knowledge affects achievable rates.
Approach
Establishes matching upper and lower bounds on the Pareto frontier of regret rates for benign vs arbitrary environments, achieved by dynamic balancing over C-UCB and UCB base learners; reduces causal bandits with post-action context to linear bandits with conditionally sub-Gaussian noise so phased elimination yields instance-dependent O(log T) regret.
Key results
- Dynamic balancing achieves regret O~(sqrt(|Z|T)) on conditionally benign instances and O~(sqrt(|A|/|Z|)·sqrt(|A|T)) on arbitrary ones, matching a lower bound that implies the price of adaptivity is a factor sqrt(|A|/|Z|).
- Phased elimination with G-optimal design gives instance-dependent regret O(dim(span{nu_a})·log(|A|T)/Delta_min) in conditionally benign environments, the first such bound for causal bandits.
- No algorithm agnostic to marginals can beat the minimax rate sqrt(|A|T) on arbitrary environments; approximate marginals with epsilon = O~(1/sqrt(T)) suffice for O~(sqrt(T)) regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Balance a benign learner and a robust arbitrary-environment learner instead of using HAC-UCB | Causal bandit adaptation · Arbitrary environments, while retaining the benign-environment rate | regret: \tilde O(T^{3/4}) -> \tilde O(\sqrt{|\mathcal A|/|\mathcal Z|}\cdot\sqrt{|\mathcal A|T}) | Helped |
| Use phased elimination rather than C-UCB as the benign base learner | Dynamic Balancing · Conditionally benign environments | worst-case regret: \tilde O(\sqrt{|\mathcal Z|T}) -> O\lr{\sqrt{\dimspan{\nu}T\log(|\mathcal A|T)}} | Helped |
| Use phased elimination with known marginals | Causal bandits · Conditionally benign environments with a positive minimum gap | instance-dependent expected regret: O\lr{\frac{\dimspan{\nu}\log(|\mathcal A|T)}{\Delta_{\min}(\nu)}} | Helped |
| Remove all knowledge of the context marginals | Algorithms for causal bandits · Conditionally benign environments | expected regret: \Omega(\sqrt{|\mathcal A|T}) | Hurt |
| Use ε-close approximate marginals instead of exact marginals | Phased Elimination · Conditionally benign environments | regret: C\lr{\sqrt{\dimspan{\tilde\nu} \log\lr{\frac{|\mathcal A|\log T}{\delta}}t}+\varepsilon t\sqrt{\dimspan{\tilde\nu}}\log | Hurt |
| Set ε=0 by using exact marginals rather than approximate marginals | Phased Elimination · Conditionally benign environments | regret: C\lr{\sqrt{\dimspan{\tilde\nu} \log\lr{\frac{|\mathcal A|\log T}{\delta}}t}+\varepsilon t\sqrt{\dimspan{\tilde\nu}}\log | Helped |
| Use Dynamic Balancing rather than persistently running the optimistic learner before switching | Causal bandit adaptation · Arbitrary environments | regret: \tilde O(T^{3/4}) -> \tilde O(\sqrt{|\mathcal A|/|\mathcal Z|}\cdot\sqrt{|\mathcal A|T}) | Helped |
Surprising findings
- Strict adaptivity (minimax in both benign and arbitrary classes simultaneously) is impossible, but a Pareto trade-off is achievable with a price of adaptivity factor sqrt(|A|/|Z|).
- Without accurate marginal knowledge, an algorithm cannot beat the non-causal minimax rate even in conditionally benign environments.
Limitations
- Dynamic balancing is cumbersome to implement compared to simpler algorithms.
- Adaptive O(log T) instance-dependent regret across both environment classes remains open; model-selection-based approaches do not always achieve it.
- Finite action and context spaces are assumed.
Experimental setup
Metrics: expected pseudo-regret
Baselines: C-UCB HAC-UCB UCB
Builds on: C-UCB HAC-UCB dynamic balancing phased elimination UCB
Closest papers by meaning
- Multi-Objective Causal Bandits: Minimal Intervention Space and Policy-Level Learning (NeurIPS 2026 · similarity 0.93)
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.92)
- Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.92)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
- Factored-Reward Bandits with Intermediate Observations (ICML 2024 · similarity 0.90)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.90)
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.