Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Mixed-Effects Contextual 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.
Proposes a contextual bandit with vector rewards modeled by a linear mixed-effects model and the ME-CUCB algorithms (known or estimated covariance) with weighted least-squares, achieving near-optimal regret.
Problem
Contextual bandits where each pull returns a vector of correlated outcomes whose correlation stems from shared random effects; standard linear bandit methods ignore this correlation.
Approach
Models multi-dimensional rewards with a linear mixed-effects model and uses a weighted least-squares estimator with inverse covariance weights inside a UCB rule; because estimated weights depend on future data, the error is non-martingale and is bounded via covering numbers.
Key results
- ME-CUCB achieves Õ(d√(mT)) regret, matched by a lower bound Ω(d√(mΛT)) up to logarithmic factors.
- On synthetic data with correlated rewards, ME-CUCB1 and ME-CUCB2 have significantly lower cumulative regret than C2UCB over T=1000.
- On MovieLens 10M bundle simulation (K=50, m=5), ME-CUCB2 achieves significantly smaller regret than C2UCB and LinUCB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ME-CUCB1 to account for correlated outcomes | C2UCB · Random intercept, D>0 | cumulative regret | Helped |
| Estimate D and σ² instead of using their true values (ablation) | ME-CUCB1 · Random intercept, D>0 | cumulative regret | No clear effect |
| Estimate D and σ² instead of using their true values (ablation) | ME-CUCB1 · Random intercept, D=0 | cumulative regret | No clear effect |
| Use ME-CUCB1 or ME-CUCB2 to account for correlated outcomes | C2UCB · Random coefficient model | cumulative regret | Helped |
| Estimate the covariance structure with ME-CUCB2 | C2UCB and LinUCB · MovieLens 10M | cumulative regret | Helped |
Limitations
- Theory for unknown covariance requires consistent estimators of D and sigma^2 with rate assumptions (condition (7)) and adds a non-dominant O(dmT^{1/4}) term.
- Experiments are limited to simulations and one MovieLens-based setup with 10 repeated runs.
- Covariance-estimation procedure for the random coefficient model is only described via EM; theory covers random intercept models for closed-form estimators.
Experimental setup
Datasets: MovieLens 10M synthetic data from random intercept and random coefficient models
Benchmarks: synthetic bandit simulations (d=10, K=100, m=10) MovieLens 10M bundle recommendation simulation
Metrics: cumulative regret
Baselines: C2UCB LinUCB
Builds on: LinUCB C2UCB SupLinUCB Laird and Ware mixed-effects model
Closest papers by meaning
- How Does Variance Shape the Regret in Contextual Bandits? (NeurIPS 2024 · similarity 0.90)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.90)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.90)
- High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions (ICML 2025 · similarity 0.90)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.90)
- Linear Contextual Bandits With Interference (ICML 2025 · similarity 0.89)
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.