mlsanityData to 7 Oct 2026

Near-optimal Representation Learning for Linear Bandits and Linear RL

arXiv 2102.04132 ↗First posted 8 Feb 2021cs.LGcited by 45

Not on the map. Why?

Abstract (arXiv)

This paper studies representation learning for multi-task linear bandits and multi-task episodic RL with linear value function approximation. We first consider the setting where we play M linear bandits with dimension d concurrently, and these bandits share a common k-dimensional linear representation so that kll d and k ll M. We propose a sample-efficient algorithm, MTLR-OFUL, which leverages the shared representation to achieve tildeO(M√dkT + d√kMT ) regret, with T being the number of total steps. Our regret significantly improves upon the baseline tildeO(Md√T) achieved by solving each task independently. We further develop a lower bound that shows our regret is near-optimal when d > M. Furthermore, we extend the algorithm and analysis to multi-task episodic RL with linear value function approximation under low inherent Bellman error citepzanette2020learning. To the best of our knowledge, this is the first theoretical result that characterizes the benefits of multi-task representation learning for exploration in RL with function approximation.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). Builds on 27 of its 48 references that are in the map. First posted on arXiv 8 Feb 2021.

Builds on

27 of 48 references.

References · 27

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2019Multi-Task Deep Neural Networks for Natural Language Understandingcited by 349
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2017Distral: Robust Multitask Reinforcement Learningcited by 231
  8. 2020Few-Shot Learning via Learning the Representation, Provablycited by 213
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  11. 2015The Benefit of Multitask Representation Learningcited by 194
  12. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
15 more
  1. 2015Actor-Mimic: Deep Multitask and Transfer Reinforcement Learningcited by 176
  2. 2020Provable Meta-Learning of Linear Representationscited by 161
  3. 2018Multi-task Deep Reinforcement Learning with PopArtcited by 138
  4. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2020High-Dimensional Sparse Linear Banditscited by 61
  8. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  9. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  10. 2019Bilinear Bandits with Low-rank Structurecited by 54
  11. 2015Massively Multitask Networks for Drug Discoverycited by 49
  12. 2020Low-Rank Generalized Linear Bandit Problemscited by 48
  13. 2020Provable Representation Learning for Imitation Learning via Bi-level Optimizationcited by 41
  14. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  15. 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 17; 2023: 6; 2024: 7; 2025: 6; 2026: 4.

45 papers.

Sort:

By area:

  1. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  2. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  3. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  4. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  5. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  6. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  7. 2021Joint Learning of Linear Time-Invariant Dynamical Systemscited by 16
  8. 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
  9. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  10. 2022Mixed-Effect Thompson Samplingcited by 14
  11. 2022Non-Stationary Representation Learning in Sequential Linear Banditscited by 13
  12. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
33 more
  1. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12
  2. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  3. 2023Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricingcited by 8
  4. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  5. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  6. 2022Meta Representation Learning with Contextual Linear Banditscited by 6
  7. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  8. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  9. 2022Joint Representation Training in Sequential Tasks with Shared Structurecited by 5
  10. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  11. 2024Diffusion Models Meet Contextual Banditscited by 5
  12. 2024Task Diversity Shortens the ICL Plateaucited by 5
  13. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  14. 2022Multi-User Reinforcement Learning with Low Rank Rewardscited by 4
  15. 2023Prospective Side Information for Latent MDPscited by 4
  16. 2022Tractable Optimality in Episodic Latent MABscited by 3
  17. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
  18. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  19. 2024Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraintscited by 2
  20. 2022Representation Learning for Context-Dependent Decision-Makingcited by 1
  21. 2023Robust Knowledge Transfer in Tiered Reinforcement Learningcited by 1
  22. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  23. 2024Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspectivecited by 1
  24. 2025Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Banditscited by 1
  25. 2025Towards Understanding the Benefit of Multitask Representation Learning in Decision Processcited by 1
  26. 2026One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RLcited by 1
  27. 2026Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewardscited by 1
  28. 2023Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processescited by 0
  29. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0
  30. 2025Decentralized Contextual Bandits with Network Adaptivitycited by 0
  31. 2025Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measurecited by 0
  32. 2026RepUCB: Representation Learning-Based UCB for Heterogeneous Multi-Task Linear Banditscited by 0
  33. 2026Multi-Task Representation Learning for Conservative Linear Banditscited by 0