mlsanityData to 7 Oct 2026

Nearly Minimax Algorithms for Linear Bandits with Shared Representation

arXiv 2203.15664 ↗First posted 29 Mar 2022cs.LG stat.MLcited by 16

Not on the map. Why?

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.

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

Builds on

38 of 59 references.

References · 38

  1. 2019A Theoretical Analysis of Contrastive Unsupervised Representation Learningcited by 530
  2. 2019Meta-Learning with Differentiable Convex Optimizationcited by 461
  3. 2015Policy Distillationcited by 414
  4. 2018Meta-learning with differentiable closed-form solverscited by 395
  5. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  6. 2018Meta-Learning: A Surveycited by 254
  7. 2017Distral: Robust Multitask Reinforcement Learningcited by 231
  8. 2020Few-Shot Learning via Learning the Representation, Provablycited by 213
  9. 2015The Benefit of Multitask Representation Learningcited by 194
  10. 2020On the Theory of Transfer Learning: The Importance of Task Diversitycited by 186
  11. 2019Adaptive Gradient-Based Meta-Learning Methodscited by 183
  12. 2015Actor-Mimic: Deep Multitask and Transfer Reinforcement Learningcited by 176
26 more
  1. 2020Provable Meta-Learning of Linear Representationscited by 161
  2. 2017DARLA: Improving Zero-Shot Transfer in Reinforcement Learningcited by 147
  3. 2018Multi-task Deep Reinforcement Learning with PopArtcited by 138
  4. 2019Bilinear Bandits with Low-rank Structurecited by 54
  5. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  6. 2020Impact of Representation Learning in Linear Banditscited by 51
  7. 2015Massively Multitask Networks for Drug Discoverycited by 49
  8. 2019Learning-to-Learn Stochastic Gradient Descent with Biased Regularizationcited by 49
  9. 2020Low-Rank Generalized Linear Bandit Problemscited by 48
  10. 2017Multi-Task Learning for Contextual Banditscited by 47
  11. 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
  12. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  13. 2019Meta Dynamic Pricing: Transfer Learning Across Experimentscited by 41
  14. 2020Provable Representation Learning for Imitation Learning via Bi-level Optimizationcited by 41
  15. 2021On the Power of Multitask Representation Learning in Linear MDPcited by 30
  16. 2021Sample Efficient Linear Meta-Learning by Alternating Minimizationcited by 25
  17. 2016Regret Bounds for Lifelong Learningcited by 19
  18. 2019Towards Understanding the Importance of Shortcut Connections in Residual Networkscited by 18
  19. 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17
  20. 2018Incremental Learning-to-Learn with Statistical Guaranteescited by 16
  21. 2021Joint Learning of Linear Time-Invariant Dynamical Systemscited by 16
  22. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  23. 2021Provable Lifelong Learning of Representationscited by 15
  24. 2019Stochastic Linear Bandits with Hidden Low Rank Structurecited by 14
  25. 2022Non-Stationary Representation Learning in Sequential Linear Banditscited by 13
  26. 2021Bandit Phase Retrievalcited by 12

Built on by

Cited by year

Citing papers per year: 2022: 5; 2023: 3; 2024: 5; 2025: 3.

16 papers.

Sort:

By area:

  1. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  2. 2022Freeze then Train: Towards Provable Representation Learning under Spurious Correlations and Feature Noisecited by 22
  3. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
  4. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12
  5. 2024Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learningcited by 10
  6. 2022Meta Representation Learning with Contextual Linear Banditscited by 6
  7. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  8. 2023Multi-task Representation Learning for Pure Exploration in Bilinear Banditscited by 5
  9. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
  10. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  11. 2024Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Taskscited by 1
  12. 2024Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspectivecited by 1
4 more
  1. 2024Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samplescited by 1
  2. 2025Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Banditscited by 1
  3. 2025Towards Understanding the Benefit of Multitask Representation Learning in Decision Processcited by 1
  4. 2025Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measurecited by 0