Research map / Bandits and online learning / Multi-armed bandits
Adaptive Experimentation When You Can't Experiment
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.
Introduces confounded pure exploration transductive linear bandits (CPET-LB) and elimination algorithms (CPEG, CPEUG) that use experimental design with a novel finite-time confidence interval for a P-2SLS instrumental-variable estimator to find the best treatment under encouragement designs.
Problem
Identifying the best-performing treatment via adaptive experimentation when users cannot be directly assigned treatments and unobserved confounding makes naive comparisons biased; only randomized encouragements (instruments) can be assigned.
Approach
Extends pure exploration transductive linear bandits to a linear structural equation model with endogenous noise, using encouragements as instrumental variables; designs the encouragement distribution via experimental design on an IV (P-2SLS) estimator with new finite-time confidence bounds, and handles unknown Gamma by alternating estimation phases with a doubling trick.
Key results
- Algorithm CPEG with known Gamma is shown to be delta-PAC with sample complexity scaling with rho* and L_nu, nearly matching a lower bound (extra factor d^2 gap in general noise).
- UCB-IV retains a constant probability of error on the membership example while CPEG finds the best arm with significantly higher probability over 100 simulations.
- Unknown-Gamma algorithm CPEUG's sample complexity scales with rho* almost matching the known-Gamma bound, with experiments showing it beats baselines that use uniform sampling for either Gamma or theta estimation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CPEG instead of UCB-OLS | UCB treatment selection in the compliance instance · Compliance location model (d=6) | probability of identifying the best treatment | Helped |
| Use UCB-IV instead of UCB-OLS | UCB treatment selection in the compliance instance · Compliance location model (d=6) | probability of identifying the best treatment | Helped |
| Use UCB-OLS with OLS treatment estimates | UCB treatment selection in the compliance instance · Compliance location model (d=6) | identification of the best treatment | Hurt |
| Use CPEG instead of the passive and naive pure-exploration baselines | Known-Γ experiment · Jump-Around instance | sample efficiency | Helped |
| Use adaptive uniform sampling with elimination instead of CPEG | Known-Γ experiment · Interpolation instance | sample efficiency | No clear effect |
| Use CPEG instead of static XY and uniform designs | Known-Γ experiment · Interpolation instance | sample efficiency | Helped |
| Use experimental design to estimate both Γ and θ instead of replacing both designs with uniform sampling | Unknown-Γ methods · Interpolation instance (ε=0.99) | sample efficiency | Helped |
Surprising findings
- Naive UCB-OLS completely fails to identify the best arm under confounding, and even instrument-based UCB-IV keeps a constant error probability.
- When Gamma approaches a rank-one matrix (weak instruments), the sample complexity blows up, making deconfounding impossible.
Limitations
- Lower bound is non-adaptive and likely not tight; general-noise bound has an extra d^2 factor relative to standard linear bandits
- Requires known lower bound on smallest singular value of Gamma (or an efficient estimation procedure) and noise sub-Gaussian parameters
- Experiments are limited to small synthetic instances (d=4 and d=6)
Experimental setup
Benchmarks: synthetic jump-around instance synthetic interpolation instance
Metrics: sample complexity probability of identifying best arm
Baselines: UCB-OLS UCB-IV Static Oracle Static XY-Optimal Static Uniform Adaptive Uniform (SE)
Builds on: RAGE 2SLS transductive linear bandits
Closest papers by meaning
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.86)
- Simulation-Based Inference for Adaptive Experiments (NeurIPS 2025 · similarity 0.85)
- Efficient Adaptive Experimentation with Noncompliance (NeurIPS 2025 · similarity 0.85)
- Stronger Neyman Regret Guarantees for Adaptive Experimental Design (ICML 2025 · similarity 0.84)
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.84)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.84)
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.