Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Linear Contextual Bandits With Interference
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 linear contextual bandits with interference (LinEGWI, LinUCBWI, LinTSWI) that model neighbor-driven reward spillovers, with regret, finite-sample, and asymptotic inference theory plus simulations and a MovieLens-based synthetic study.
Problem
Contextual bandits with multiple units per round ignore interference (one unit's action affecting others' rewards), which biases reward estimation and decisions; the theory of interference in online contextual bandits is underexplored.
Approach
Extends linear contextual bandits to a linear interference model where reward is a weighted sum of neighbors' payoffs via a known interference matrix W_t; the optimal action depends only on each unit's covariates and an interference weight omega_ti, and OLS is run on transformed covariates. A clipping rate on exploration ensures estimation consistency and valid asymptotic inference.
Key results
- Coverage of beta and V^pi* confidence intervals hovers around 95% across LinEGWI, LinUCBWI, and LinTSWI in simulations (B=1000).
- Proposed interference-aware algorithms yield significantly smaller average regret than classical linear contextual bandits under interference; reduce to comparable performance without interference.
- Theoretical regret bound O(N_T^{1/2} log N_T) stated for LinEGWI, LinUCBWI, and LinTSWI.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Account for the known interference structure using LinEGWI, LinUCBWI, or LinTSWI instead of classical linear contextual bandits | Linear contextual bandits · Simulation with interference | average regret | Helped |
| Account for the known interference structure using LinEGWI, LinUCBWI, or LinTSWI instead of classical contextual bandits | MovieLens 1M synthetic data · Reward-generating Model I | average reward | Helped |
| Account for the known interference structure using LinEGWI, LinUCBWI, or LinTSWI instead of classical contextual bandits | MovieLens 1M synthetic data · Reward-generating Model II | average reward | Helped |
| Replace the interference matrix with the identity matrix | LinEGWI, LinUCBWI, and LinTSWI · Simulation without interference | average regret | No clear effect |
Surprising findings
- Without interference, the proposed methods perform comparably to classical LinCB, so the gains come specifically from modeling interference.
Limitations
- Assumes the interference matrix W_t is known
- Extension to K>2 arms is only sketched, with detailed theory deferred
- Linear reward model may be misspecified (noted as explaining gap to oracle in MovieLens Model I)
Experimental setup
Datasets: MovieLens 1M (synthetic reward generation)
Benchmarks: simulation coverage probability (B=1000) simulated average regret vs LinCB (B=100) MovieLens-based synthetic data (T=200)
Metrics: coverage probability average regret average rating
Baselines: classical LinCB (no interference) oracle policy
Builds on: LinUCB linear Thompson sampling SUTVA-violation causal inference literature Kalman-type online inference for bandits
Closest papers by meaning
- Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits (ICML 2025 · similarity 0.91)
- Mutli-Armed Bandits with Network Interference (NeurIPS 2024 · similarity 0.91)
- Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference (NeurIPS 2025 · similarity 0.90)
- Mixed-Effects Contextual Bandits (AAAI 2024 · similarity 0.89)
- Learning to target with network interference (NeurIPS 2026 · similarity 0.89)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 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.