# Nearly Minimax Algorithms for Linear Bandits with Shared Representation

arXiv: https://arxiv.org/abs/2203.15664 · HTML: https://mlsanity.com/paper/2203.15664/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 59 references that are in the map.
- First posted on arXiv 29 Mar 2022.

## Builds on (most cited first, 30 of 38)

- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Meta-Learning with Differentiable Convex Optimization](https://mlsanity.com/paper/1904.03758/) (2019)
- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Meta-Learning: A Survey](https://mlsanity.com/paper/1810.03548/) (2018)
- [Distral: Robust Multitask Reinforcement Learning](https://mlsanity.com/paper/1707.04175/) (2017)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [On the Theory of Transfer Learning: The Importance of Task Diversity](https://mlsanity.com/paper/2006.11650/) (2020)
- [Adaptive Gradient-Based Meta-Learning Methods](https://mlsanity.com/paper/1906.02717/) (2019)
- [Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning](https://mlsanity.com/paper/1511.06342/) (2015)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [DARLA: Improving Zero-Shot Transfer in Reinforcement Learning](https://mlsanity.com/paper/1707.08475/) (2017)
- [Multi-task Deep Reinforcement Learning with PopArt](https://mlsanity.com/paper/1809.04474/) (2018)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Impact of Representation Learning in Linear Bandits](https://mlsanity.com/paper/2010.06531/) (2020)
- [Massively Multitask Networks for Drug Discovery](https://mlsanity.com/paper/1502.02072/) (2015)
- [Learning-to-Learn Stochastic Gradient Descent with Biased Regularization](https://mlsanity.com/paper/1903.10399/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Multi-Task Learning for Contextual Bandits](https://mlsanity.com/paper/1705.08618/) (2017)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Meta Dynamic Pricing: Transfer Learning Across Experiments](https://mlsanity.com/paper/1902.10918/) (2019)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [On the Power of Multitask Representation Learning in Linear MDP](https://mlsanity.com/paper/2106.08053/) (2021)
- [Sample Efficient Linear Meta-Learning by Alternating Minimization](https://mlsanity.com/paper/2105.08306/) (2021)
- [Regret Bounds for Lifelong Learning](https://mlsanity.com/paper/1610.08628/) (2016)
- [Towards Understanding the Importance of Shortcut Connections in Residual Networks](https://mlsanity.com/paper/1909.04653/) (2019)

## Built on by (most cited first, 16 of 16)

- [Provable Benefits of Representational Transfer in Reinforcement Learning](https://mlsanity.com/paper/2205.14571/) (2022)
- [Freeze then Train: Towards Provable Representation Learning under Spurious Correlations and Feature Noise](https://mlsanity.com/paper/2210.11075/) (2022)
- [Offline Multi-task Transfer RL with Representational Penalization](https://mlsanity.com/paper/2402.12570/) (2024)
- [Provable General Function Class Representation Learning in Multitask Bandits and MDPs](https://mlsanity.com/paper/2205.15701/) (2022)
- [Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning](https://mlsanity.com/paper/2406.05064/) (2024)
- [Meta Representation Learning with Contextual Linear Bandits](https://mlsanity.com/paper/2205.15100/) (2022)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Lifelong Bandit Optimization: No Prior and No Regret](https://mlsanity.com/paper/2210.15513/) (2022)
- [Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources](https://mlsanity.com/paper/2306.08364/) (2023)
- [Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks](https://mlsanity.com/paper/2403.01636/) (2024)
- [Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples](https://mlsanity.com/paper/2410.11227/) (2024)
- [Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspective](https://mlsanity.com/paper/2406.11249/) (2024)
- [Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits](https://mlsanity.com/paper/2501.13390/) (2025)
- [Towards Understanding the Benefit of Multitask Representation Learning in Decision Process](https://mlsanity.com/paper/2503.00345/) (2025)
- [Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measure](https://mlsanity.com/paper/2511.01847/) (2025)

## Abstract (arXiv)

We give novel algorithms for multi-task and lifelong linear bandits with shared representation. Specifically, we consider the setting where we play M linear bandits with dimension d, each for T rounds, and these M bandit tasks share a common k(ll d) dimensional linear representation. For both the multi-task setting where we play the tasks concurrently, and the lifelong setting where we play tasks sequentially, we come up with novel algorithms that achieve widetildeOleft(d√kMT + kM√Tright) regret bounds, which matches the known minimax regret lower bound up to logarithmic factors and closes the gap in existing results [Yang et al., 2021]. Our main technique include a more efficient estimator for the low-rank linear feature extractor and an accompanied novel analysis for this estimator.