mlsanityData to 7 Oct 2026

Provable Benefit of Multitask Representation Learning in Reinforcement Learning

arXiv 2206.05900 ↗First posted 13 Jun 2022cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

As representation learning becomes a powerful technique to reduce sample complexity in reinforcement learning (RL) in practice, theoretical understanding of its advantage is still limited. In this paper, we theoretically characterize the benefit of representation learning under the low-rank Markov decision process (MDP) model. We first study multitask low-rank RL (as upstream training), where all tasks share a common representation, and propose a new multitask reward-free algorithm called REFUEL. REFUEL learns both the transition kernel and the near-optimal policy for each task, and outputs a well-learned representation for downstream tasks. Our result demonstrates that multitask representation learning is provably more sample-efficient than learning each task individually, as long as the total number of tasks is above a certain threshold. We then study the downstream RL in both online and offline settings, where the agent is assigned with a new task sharing the same representation as the upstream tasks. For both online and offline settings, we develop a sample-efficient algorithm, and show that it finds a near-optimal policy with the suboptimality gap bounded by the sum of the estimation error of the learned representation in upstream and a vanishing term as the number of downstream samples becomes large. Our downstream results of online and offline RL further capture the benefit of employing the learned representation from upstream as opposed to learning the representation of the low-rank model directly. To the best of our knowledge, this is the first theoretical study that characterizes the benefit of representation learning in exploration-based reward-free multitask RL for both upstream and downstream tasks.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 53 of its 75 references that are in the map. First posted on arXiv 13 Jun 2022.

Builds on

53 of 75 references.

References · 53

  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. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  5. 2016Successor Features for Transfer in Reinforcement Learningcited by 331
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  7. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  9. 2017Distral: Robust Multitask Reinforcement Learningcited by 231
  10. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  11. 2020Few-Shot Learning via Learning the Representation, Provablycited by 213
  12. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
38 more
  1. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  2. 2015The Benefit of Multitask Representation Learningcited by 194
  3. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  4. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  7. 2021Multi-Task Reinforcement Learning with Context-based Representationscited by 169
  8. 2020Provable Meta-Learning of Linear Representationscited by 161
  9. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  10. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  11. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  12. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  13. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  14. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  15. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  16. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  17. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  18. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  19. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  20. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  21. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  22. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  23. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  24. 2020Impact of Representation Learning in Linear Banditscited by 51
  25. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  26. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  27. 2017Multi-Task Learning for Contextual Banditscited by 47
  28. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  29. 2020Meta-learning for mixed linear regressioncited by 44
  30. 2020Provable Representation Learning for Imitation Learning via Bi-level Optimizationcited by 41
  31. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  32. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  33. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  34. 2021On the Power of Multitask Representation Learning in Linear MDPcited by 30
  35. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  36. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  37. 2022Non-Stationary Representation Learning in Sequential Linear Banditscited by 13
  38. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 7; 2025: 6; 2026: 5.

29 papers.

Sort:

By area:

  1. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  2. 2022Multi-Task Imitation Learning for Linear Dynamical Systemscited by 22
  3. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  4. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  5. 2025A Survey of State Representation Learning for Deep Reinforcement Learningcited by 17
  6. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  7. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  8. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
  9. 2023Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Datacited by 12
  10. 2023QMP: Q-switch Mixture of Policies for Multi-Task Behavior Sharingcited by 6
  11. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  12. 2022Joint Representation Training in Sequential Tasks with Shared Structurecited by 5
17 more
  1. 2024Task Diversity Shortens the ICL Plateaucited by 5
  2. 2025Learning Policy Committees for Effective Personalization in MDPs with Diverse Taskscited by 4
  3. 2023Provable Pathways: Learning Multiple Tasks over Multiple Pathscited by 3
  4. 2025Task-Aware Virtual Training: Enhancing Generalization in Meta-Reinforcement Learning for Out-of-Distribution Taskscited by 3
  5. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  6. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  7. 2022Multi-Asset Closed-Loop Reservoir Management Using Deep Reinforcement Learningcited by 1
  8. 2024Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Taskscited by 1
  9. 2024The Limits of Transfer Reinforcement Learning with Latent Low-rank Structurecited by 1
  10. 2025Towards Understanding the Benefit of Multitask Representation Learning in Decision Processcited by 1
  11. 2026Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewardscited by 1
  12. 2023Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processescited by 0
  13. 2025Generalisation in Multitask Fitted Q-Iteration and Offline Q-learningcited by 0
  14. 2026Robust Transfer Learning with Side Informationcited by 0
  15. 2026Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representationcited by 0
  16. 2026BIFROST: Bridging Invariant Feature Representation for Observation-space Sim2Real Transfercited by 0
  17. 2026Out-of-Distribution Generalisation with Sequence Models in Offline Multi-Agent Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedback
  2. 2026Representation Learning Enables Scalable Multitask Deep Reinforcement Learning
  3. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
  4. 2022Task-Induced Representation Learning
  5. 2023Multi-Task Reinforcement Learning with Mixture of Orthogonal Experts
  6. 2019Multi-task Batch Reinforcement Learning with Metric Learning
  7. 2021Representation Matters: Offline Pretraining for Sequential Decision Making
  8. 2023Generalizable Task Representation Learning for Offline Meta-Reinforcement Learning with Data Limitations