mlsanityData to 7 Oct 2026

On the Power of Multitask Representation Learning in Linear MDP

arXiv 2106.08053 ↗First posted 15 Jun 2021cs.LG cs.AIcited by 30

Not on the map. Why?

Abstract (arXiv)

While multitask representation learning has become a popular approach in reinforcement learning (RL), theoretical understanding of why and when it works remains limited. This paper presents analyses for the statistical benefit of multitask representation learning in linear Markov Decision Process (MDP) under a generative model. In this paper, we consider an agent to learn a representation function φ out of a function class Phi from T source tasks with N data per task, and then use the learned hatφ to reduce the required number of sample for a new task. We first discover a Least-Activated-Feature-Abundance (LAFA) criterion, denoted as kappa, with which we prove that a straightforward least-square algorithm learns a policy which is tildeO(H2√fracC(Phi)2 kappa dNT+frackappa dn) sub-optimal. Here H is the planning horizon, C(Phi) is Phi's complexity measure, d is the dimension of the representation (usually dll C(Phi)) and n is the number of samples for the new task. Thus the required n is O(kappa d H4) for the sub-optimality to be close to zero, which is much smaller than O(C(Phi)2kappa d H4) in the setting without multitask representation learning, whose sub-optimality gap is tildeO(H2√frackappa C(Phi)2dn). This theoretically explains the power of multitask representation learning in reducing sample complexity. Further, we note that to ensure high sample efficiency, the LAFA criterion kappa should be small. In fact, kappa varies widely in magnitude depending on the different sampling distribution for new task. This indicates adaptive sampling technique is important to make kappa solely depend on d. Finally, we provide empirical results of a noisy grid-world environment to corroborate our theoretical findings.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 23 of its 42 references that are in the map. First posted on arXiv 15 Jun 2021.

Builds on

23 of 42 references.

References · 23

  1. 2019A Theoretical Analysis of Contrastive Unsupervised Representation Learningcited by 530
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2019Meta-Learning with Differentiable Convex Optimizationcited by 461
  4. 2015Policy Distillationcited by 414
  5. 2018Meta-learning with differentiable closed-form solverscited by 395
  6. 2017Distral: Robust Multitask Reinforcement Learningcited by 231
  7. 2020Few-Shot Learning via Learning the Representation, Provablycited by 213
  8. 2015The Benefit of Multitask Representation Learningcited by 194
  9. 2020On the Theory of Transfer Learning: The Importance of Task Diversitycited by 186
  10. 2019Adaptive Gradient-Based Meta-Learning Methodscited by 183
  11. 2015Actor-Mimic: Deep Multitask and Transfer Reinforcement Learningcited by 176
  12. 2020Provable Meta-Learning of Linear Representationscited by 161
11 more
  1. 2017DARLA: Improving Zero-Shot Transfer in Reinforcement Learningcited by 147
  2. 2018Multi-task Deep Reinforcement Learning with PopArtcited by 138
  3. 2019Online Meta-Learningcited by 137
  4. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  5. 2020Impact of Representation Learning in Linear Banditscited by 51
  6. 2019Learning-to-Learn Stochastic Gradient Descent with Biased Regularizationcited by 49
  7. 2020Provable Representation Learning for Imitation Learning via Bi-level Optimizationcited by 41
  8. 2016Hypothesis Transfer Learning via Transformation Functionscited by 26
  9. 2016Regret Bounds for Lifelong Learningcited by 19
  10. 2018Incremental Learning-to-Learn with Statistical Guaranteescited by 16
  11. 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 8; 2023: 8; 2024: 7; 2025: 4.

30 papers.

Sort:

By area:

  1. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  2. 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregationcited by 71
  3. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  4. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  5. 2022Multi-Task Imitation Learning for Linear Dynamical Systemscited by 22
  6. 2023Understanding, Predicting and Better Resolving Q-Value Divergence in Offline-RLcited by 20
  7. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  8. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  9. 2021Joint Learning of Linear Time-Invariant Dynamical Systemscited by 16
  10. 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
  11. 2022Provable and Efficient Continual Representation Learningcited by 14
  12. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
18 more
  1. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  2. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12
  3. 2023Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Datacited by 12
  4. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  5. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  6. 2024Task Diversity Shortens the ICL Plateaucited by 5
  7. 2022Meta Learning MDPs with Linear Transition Modelscited by 4
  8. 2023Provable Pathways: Learning Multiple Tasks over Multiple Pathscited by 3
  9. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  10. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  11. 2023Uncertainty-aware transfer across tasks using hybrid model-based successor feature reinforcement learningcited by 1
  12. 2024Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Taskscited by 1
  13. 2024Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samplescited by 1
  14. 2024The Limits of Transfer Reinforcement Learning with Latent Low-rank Structurecited by 1
  15. 2025Towards Understanding the Benefit of Multitask Representation Learning in Decision Processcited by 1
  16. 2025Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representationcited by 1
  17. 2023Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processescited by 0
  18. 2025Generalized Linear Markov Decision Processcited by 0