Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Fast and Sample Efficient Multi-Task Representation Learning in Stochastic 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 LRRL-AltGDMin, an alternating projected gradient descent and minimization estimator with spectral initialization for multi-task representation learning in linear contextual bandits, with regret guarantees and simulations on synthetic data and MNIST.
Problem
Multi-task linear contextual bandits where T tasks share a common r-dimensional linear representation (r much smaller than d); the joint low-rank estimation is non-convex and prior bandit methods either assume an oracle or use convex relaxations without guarantees.
Approach
Adapts alternating gradient descent and minimization (AltGDmin) to sequential bandit learning with noisy rewards, using epoch-wise doubling, truncated spectral initialization with sample splitting, and greedy action selection, yielding a GD-based estimator with sample and time guarantees and an O(sqrt(rNT)) regret bound.
Key results
- Regret bound of 2 mu sigma_max sqrt(rNT log(1/delta)) (1+log log N) with probability 1-delta-Ld^-10 under sample-size conditions.
- Sample complexity per epoch scales as r^3 (ignoring logs and constants) when d≈T, versus at least d for per-task inversion.
- In simulations, LRRL-AltGDMin outperforms MoM, trace-norm relaxation, and per-task Thompson Sampling in cumulative regret and estimation error, with advantage growing with number of tasks; estimation error saturates near the noise level (1e-6).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LRRL-AltGDMin instead of the benchmark algorithms | Multi-task linear contextual bandits · Synthetic and MNIST simulations | cumulative regret | Helped |
| Increase the number of tasks | LRRL-AltGDMin relative to the benchmark algorithms · Synthetic and MNIST simulations | cumulative regret | Helped |
| Vary the feature-matrix rank | Thompson Sampling · Synthetic and MNIST simulations | cumulative regret | No clear effect |
| Use LRRL-AltGDMin instead of LRRL-AltGD or trace-norm relaxation | Low-rank representation estimation · Synthetic data | relative Frobenius estimation error | Helped |
| Continue trace-norm relaxation iterations | Trace-norm relaxation estimator · Synthetic data | relative Frobenius estimation error | Helped |
| Increase the GD iteration count | LRRL-AltGDMin estimator · Synthetic data | relative Frobenius estimation error: 10^{-6} | Helped |
Surprising findings
- The trace-norm relaxation baseline improves only minimally over iterations in the reported experiments.
Limitations
- Analysis assumes i.i.d. standard Gaussian features, which is restrictive for greedy epochs after the first.
- Regret analysis uses a noise and sample-size regime with constants and assumes incoherence of right singular vectors.
- Current algorithm is greedy with no confidence intervals (not UCB-based).
Experimental setup
Datasets: MNIST synthetic Gaussian data
Benchmarks: synthetic linear bandit simulations MNIST pairwise bandit tasks
Metrics: cumulative regret estimation error ||Theta-Theta*||_F/||Theta*||_F
Baselines: Method-of-Moments (MoM) bandit estimator trace-norm convex relaxation Thompson Sampling per task LRRL-AltGD
Builds on: AltGDmin OFUL Method-of-Moments representation learning for bandits trace-norm relaxation for multi-task bandits
Closest papers by meaning
- Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees (NeurIPS 2022 · similarity 0.92)
- Leveraging Good Representations in Linear Contextual Bandits (ICML 2021 · similarity 0.91)
- Impact of Representation Learning in Linear Bandits (ICLR 2021 · similarity 0.91)
- Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations (NeurIPS 2025 · similarity 0.90)
- Beyond task diversity: provable representation transfer for sequential multitask linear bandits (NeurIPS 2024 · similarity 0.90)
- An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction (NeurIPS 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.