mlsanityData to 7 Oct 2026

Sample Complexity of Multi-task Reinforcement Learning

arXiv 1309.6821 ↗First posted 26 Sep 2013cs.LG stat.MLcited by 58

Not on the map. Why?

Abstract (arXiv)

Transferring knowledge across a sequence of reinforcement-learning tasks is challenging, and has a number of important applications. Though there is encouraging empirical evidence that transfer can improve performance in subsequent reinforcement-learning tasks, there has been very little theoretical analysis. In this paper, we introduce a new multi-task algorithm for a sequence of reinforcement-learning tasks when each task is sampled independently from (an unknown) distribution over a finite set of Markov decision processes whose parameters are initially unknown. For this setting, we prove under certain assumptions that the per-task sample complexity of exploration is reduced significantly due to transfer compared to standard single-task algorithms. Our multi-task algorithm also has the desired characteristic that it is guaranteed not to exhibit negative transfer: in the worst case its per-task sample complexity is comparable to the corresponding single-task algorithm.

Key facts. Cited by 58 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Sep 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 19; 2023: 9; 2024: 11; 2025: 4; 2026: 8.

58 papers.

Sort:

By area:

  1. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  2. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  3. 2024Sharing Knowledge in Multi-Task Deep Reinforcement Learningcited by 42
  4. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  5. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  6. 2026Maximum Likelihood Reinforcement Learningcited by 29
  7. 2021When Is Generalizable Reinforcement Learning Tractable?cited by 19
  8. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  9. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  10. 2022Learning Mixtures of Linear Dynamical Systemscited by 15
  11. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  12. 2024Three Dogmas of Reinforcement Learningcited by 14
38 more
  1. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  2. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  3. 2022Model-Free Generative Replay for Lifelong Reinforcement Learning: Application to Starcraft-2cited by 11
  4. 2023Social Contract AI: Aligning AI Assistants with Implicit Group Normscited by 9
  5. 2025J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimizationcited by 9
  6. 2021Multitasking Inhibits Semantic Driftcited by 8
  7. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  8. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  9. 2022Curriculum-based Asymmetric Multi-task Reinforcement Learningcited by 7
  10. 2021Learning Meta Representations for Agents in Multi-Agent Reinforcement Learningcited by 6
  11. 2022Group Distributionally Robust Reinforcement Learning with Hierarchical Latent Variablescited by 6
  12. 2024Statistical Context Detection for Deep Lifelong Reinforcement Learningcited by 6
  13. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  14. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  15. 2022Meta Learning MDPs with Linear Transition Modelscited by 4
  16. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  17. 2022PAC-Bayesian Lifelong Learning For Multi-Armed Banditscited by 4
  18. 2022Multi-User Reinforcement Learning with Low Rank Rewardscited by 4
  19. 2023Bayesian Reinforcement Learning with Limited Cognitive Loadcited by 4
  20. 2023Prospective Side Information for Latent MDPscited by 4
  21. 2024LIMT: Language-Informed Multi-Task Visual World Modelscited by 4
  22. 2022Tractable Optimality in Episodic Latent MABscited by 3
  23. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  24. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  25. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  26. 2025Learning to Reason as Action Abstractions with Scalable Mid-Training RLcited by 3
  27. 2022Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximationcited by 2
  28. 2024Learning to Look: Seeking Information for Decision Making via Policy Factorizationcited by 2
  29. 2022Multi-Asset Closed-Loop Reservoir Management Using Deep Reinforcement Learningcited by 1
  30. 2023Robust Knowledge Transfer in Tiered Reinforcement Learningcited by 1
  31. 2023Scaling Distributed Multi-task Reinforcement Learning with Experience Sharingcited by 1
  32. 2024Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Taskscited by 1
  33. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  34. 2024Preparing for Black Swans: The Antifragility Imperative for Machine Learningcited by 1
  35. 2026One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RLcited by 1
  36. 2026Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewardscited by 1
  37. 2026Multi-Agent Transactive Memorycited by 1
  38. 2022Minimum Description Length Controlcited by 0

50 most cited of 58 All 58 (JSON)