Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Beyond task diversity: provable representation transfer for sequential multitask linear 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 BOSS, a bandit online subspace selection algorithm for sequential multi-task linear bandits that achieves meta-regret without task diversity assumptions, using exponential weights over an expert cover of subspaces and randomized meta-exploration.
Problem
Lifelong/sequential multi-task linear bandits where task parameters lie in an unknown m-dimensional subspace; prior sequential regret guarantees require a task diversity assumption that is hard to verify and may fail in practice.
Approach
Bi-level algorithm: at each task randomly chooses meta-exploration (PEGE over full space, to learn the subspace) or meta-exploitation (estimate within a chosen subspace), and selects subspaces online via exponential weights over an epsilon-cover of the Grassmannian with importance-weighted surrogate costs, avoiding any task diversity assumption.
Key results
- Theoretical meta-regret of BOSS is Otilde(Nm sqrt(tau) + N^{2/3} tau^{2/3} d m^{1/3} + N d^2 + tau m d) without task diversity, improving on the Otilde(N d sqrt(tau)) single-task baseline when tau >> d^2 and N >> m sqrt(tau).
- On synthetic experiments, BOSS and BOSS-no-oracle achieve lower cumulative regret than independent PEGE and SeqRepL baselines in the setting (N, tau, d, m) = (4000, 500, 10, 3).
- The guarantee has a gap to the lower bound Omega(Nm sqrt(tau) + d sqrt(m tau N)) and the experimental expert set is exponentially large in dm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BOSS without assuming task diversity | Sequential multitask linear bandits · Ellipsoid action sets | meta-regret: \tilde{O}\rbr{Nd\sqrt{\tau}} \to \tilde{O}\Big(Nm \sqrt{\tau} + N^{\frac{2}{3}} \tau^{\frac{2}{3}} d m^{\frac13}+ Nd^2 + | Helped |
| include the ground-truth subspace among the experts (ablation) | BOSS · Synthetic adversarial environment | cumulative regret | Helped |
| remove the ground-truth expert from the expert set (ablation) | BOSS · Synthetic adversarial environment | cumulative regret | Hurt |
| use BOSS-no-oracle instead of SeqRepL | Synthetic adversarial environment · Synthetic adversarial environment | cumulative regret | Helped |
| use BOSS-no-oracle rather than SeqRepL's subspace estimate | Synthetic adversarial environment · Synthetic adversarial environment | task-parameter estimation | Helped |
Surprising findings
- BOSS-no-oracle has worse subspace estimation than SeqRepL yet achieves lower regret, because its theta estimates are better.
- The authors identify a non-trivial oversight in a prior sequential representation transfer analysis (an inequality used for norm-bounded task parameters does not hold in general).
Limitations
- Meta-regret bound has a weaker N dependence than parallel results and does not beat the single-task baseline in all regimes (requires N >> m sqrt(tau), tau >> d^2).
- Requires knowing m (or an upper bound) and N; the expert set has size (sqrt(dm)/eps)^{O(dm)}, which is exponentially large and computationally intractable.
- Assumes ellipsoid action sets and exact low-rank task parameters.
Experimental setup
Benchmarks: synthetic linear bandit environment (N=4000, tau=500, d=10, m=3)
Metrics: cumulative meta-regret subspace estimation error ||B_perp^T B||_F
Baselines: PEGE (independent per task) PEGE-oracle SeqRepL BOSS-no-oracle
Builds on: PEGE exponential weights (Hedge) SeqRepL
Closest papers by meaning
- Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits (ICML 2024 · similarity 0.90)
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery (ICML 2024 · similarity 0.88)
- Bandits via Additive Quantized Representations (NeurIPS 2026 · similarity 0.88)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.87)
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.87)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · 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.