# Sample Complexity of Multi-task Reinforcement Learning

arXiv: https://arxiv.org/abs/1309.6821 · HTML: https://mlsanity.com/paper/1309.6821/

## Key facts

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

## Built on by (most cited first, 30 of 58)

- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Sharing Knowledge in Multi-Task Deep Reinforcement Learning](https://mlsanity.com/paper/2401.09561/) (2024)
- [Provable Benefits of Representational Transfer in Reinforcement Learning](https://mlsanity.com/paper/2205.14571/) (2022)
- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [When Is Generalizable Reinforcement Learning Tractable?](https://mlsanity.com/paper/2101.00300/) (2021)
- [Provably Efficient Multi-Task Reinforcement Learning with Model Transfer](https://mlsanity.com/paper/2107.08622/) (2021)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning](https://mlsanity.com/paper/2304.08944/) (2023)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization](https://mlsanity.com/paper/2202.06545/) (2022)
- [Learning Mixtures of Markov Chains and MDPs](https://mlsanity.com/paper/2211.09403/) (2022)
- [Model-Free Generative Replay for Lifelong Reinforcement Learning: Application to Starcraft-2](https://mlsanity.com/paper/2208.05056/) (2022)
- [Social Contract AI: Aligning AI Assistants with Implicit Group Norms](https://mlsanity.com/paper/2310.17769/) (2023)
- [J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimization](https://mlsanity.com/paper/2505.13346/) (2025)
- [Multitasking Inhibits Semantic Drift](https://mlsanity.com/paper/2104.07219/) (2021)
- [Curriculum-based Asymmetric Multi-task Reinforcement Learning](https://mlsanity.com/paper/2211.03352/) (2022)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardness](https://mlsanity.com/paper/2210.10464/) (2022)
- [Group Distributionally Robust Reinforcement Learning with Hierarchical Latent Variables](https://mlsanity.com/paper/2210.12262/) (2022)
- [Statistical Context Detection for Deep Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.19047/) (2024)
- [Learning Meta Representations for Agents in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2108.12988/) (2021)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [Meta Learning MDPs with Linear Transition Models](https://mlsanity.com/paper/2201.08732/) (2022)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [PAC-Bayesian Lifelong Learning For Multi-Armed Bandits](https://mlsanity.com/paper/2203.03303/) (2022)
- [Multi-User Reinforcement Learning with Low Rank Rewards](https://mlsanity.com/paper/2210.05355/) (2022)

## 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.