Source-linked AI summary
Sample Complexity of Multi-task Reinforcement Learning
Emma Brunskill, Lihong Li
TL;DR
The paper asks whether knowledge can reduce exploration costs across independently sampled reinforcement-learning tasks when the underlying finite MDPs are initially unknown. It introduces a two-phase algorithm that learns candidate models, identifies each new task, and transfers accumulated information. Under stated assumptions, transfer substantially reduces sample complexity while preserving single-task worst-case guarantees and avoiding negative transfer.
Problem
The paper addresses the limited theoretical understanding of whether transfer reduces exploration sample complexity across tasks drawn from an unknown distribution over a finite set of MDPs.
Method
The method uses an initial phase of single-task learning and model clustering, followed by Finite-Model-RL to identify candidate MDPs and transfer their accumulated data to new tasks.
Results
Under stated assumptions, the overall sample complexity across tasks is substantially smaller with transfer than when solving tasks individually, while phase-two complexity depends on the number of models and diameter rather than state–action-space size.
Takeaways & Limitations
The analysis shows that multi-task reinforcement learning can accelerate exploration without negative transfer when tasks share a finite underlying MDP family.
Takeaways & Limitations
The results rely on assumptions including non-rare MDPs, a bounded number of sufficiently distinct models, and a diameter condition, and the paper calls for broader algorithms beyond finite MDPs.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper studies knowledge transfer across reinforcement-learning tasks drawn from a finite family of MDPs, addressing a theoretical gap in a field with encouraging empirical evidence but limited formal analysis.
- The paper considers sequences of reinforcement-learning tasks drawn from a finite set of MDPs sharing state and action spaces but differing in reward or transition parameters.
- Although empirical work suggests transfer can improve reinforcement-learning performance, theoretical analysis of its benefits remains limited.
- The paper introduces a multi-task algorithm that significantly reduces per-task exploration sample complexity under stated assumptions compared with single-task learning.
- The algorithm is guaranteed to avoid negative transfer, so misleading information does not worsen its worst-case per-task sample complexity relative to a corresponding single-task algorithm.
2 PRELIMINARIES
The preliminaries formalize finite discounted MDPs, policies and value functions, and define reinforcement-learning sample complexity as the effort required to learn near-optimal behavior under unknown dynamics.
- A finite discounted MDP is represented by ⟨S, A, P, R, γ⟩, comprising state and action spaces, transition probabilities, rewards, and a discount factor.
- A deterministic policy maps each state to an action, while V^π and Q^π quantify expected discounted returns from states and state–action pairs.
- Reinforcement learning assumes unknown transition and reward functions and seeks an approximately optimal policy using as few environment interactions as possible.
- The multi-task setting contains T tasks sampled from C MDPs sharing state and action spaces and discount factor but differing in reward or transition dynamics.
3 PAC-MDP MULTI-TASK RL
The proposed method first learns and clusters the underlying MDPs, then uses candidate models to identify each new task and accelerate exploration while retaining single-task guarantees.
- Phase 2: In phase two, the method runs Finite-Model-RL on each new task and incorporates its visitation counts into the corresponding model group after identification.
- Phase 1: The two-phase algorithm first applies single-task learning across initial tasks, then clusters observed data to estimate at most C-bar underlying MDPs.
- Phase 2: Candidate-model identification can be faster than standard exploration because once the task model is identified, all state–action pairs may become known through transferred data.
- Finite-Model-RL: Finite-Model-RL extends the noisy-union algorithm to compare candidate models with imperfect parameter estimates and eliminate models inconsistent with observed data.
- Guarantees: The algorithm maintains single-task sample-complexity guarantees in phase two, thereby avoiding negative transfer on individual tasks.
4 ANALYSIS
The analysis shows that, under assumptions on task frequencies, model separation, model count, and MDP diameter, transferred experience reduces multi-task sample complexity. The proof establishes reliable task coverage, clustering, identification, and fewer visits to unknown state–actions.
- The analysis assumes a positive minimum task probability, a known model-count bound, a known model-separation gap, and a known diameter.The diameter assumption is identified as the major assumption because it supports sufficiently fast reachability and task identification.
- Theorem 1 establishes that solving T tasks with transfer has substantially lower overall sample complexity than solving them independently.The comparison relies on the paper’s multi-task algorithm and its PAC-MDP analysis.
- Phase 2 removes dependence on state- and action-space size, replacing it with dependence on the number of candidate models and the MDP diameter.Without transfer, the stated bound can scale as ˜O(TNSA), whereas the transferred analysis depends on C̄ and D.
- With probability at least 1 − δ, every MDP is encountered in phase 1, enabling the algorithm to accumulate estimates across tasks.The phase-1 guarantee is derived from the minimum task prior and the upper bound on the number of MDPs.
- With probability 1 − δ, each state–action receives enough samples, phase-1 tasks are grouped by MDP, and phase-2 tasks are identified correctly.The grouping argument uses model separation and concentration bounds to distinguish different MDPs while merging tasks from the same MDP.
- The algorithm’s second phase limits visits to unknown state–actions by identifying the underlying model and then applying a single-task exploration procedure.The proof separates model-identification visits from later exploration visits and notes that identification requires reaching informative states.
5 EXPERIMENTS
The experiments evaluate the proposed multi-task method against single-task E3 and HMTL in a three-MDP gridworld, showing that learned model transfer improves later-task reward and total performance.
- The experiment used three reward-distinct MDPs sharing a 5 × 5 state space, with 150 tasks per round repeated for 20 rounds.
- p < 10^-4: transferring knowledge substantially improved performance over single-task E3 when comparing first- and last-task performance.The proposed method initially performs worse during phase 1 but improves after estimating the three MDPs.
- The method leveraged learned models in phase 2 to identify each new task’s MDP and then act optimally for the remainder of the task.
- p = 0.03: the proposed approach achieved significantly higher total reward than HMTL across a 150-task round.The comparison used a Mann-Whitney U test.
- HMTL performed well initially but did not significantly improve over a round, which the authors associate with its lack of explicit exploration.The authors report that HMTL’s learned posterior appeared to mix the true MDPs.
6 RELATED WORK
Related work spans hierarchical multi-task transfer, batch value-function approximation, and model-elimination methods, while this paper emphasizes online exploration and formal analysis.
- Wilson et al.’s hierarchical multi-task method uses Bayesian updates and transfer but provides no formal analysis, unlike this work.
- Lazaric and Restelli study batch transfer through target-task value-function approximation error bounds, whereas this paper studies online exploration with exploration–exploitation trade-offs.
- The paper’s model-elimination approach generalizes noisy union ideas to eliminate models before a state–action becomes fully known.
7 CONCLUSIONS
The paper presents theoretically grounded multi-task RL with substantial sample-complexity advantages and possible avoidance of negative transfer, while identifying broader applicability as future work.
- The work reports substantial sample-complexity advantages over single-task learning and the possibility of avoiding negative transfer in multi-task RL.
- Future work includes relaxing assumptions, testing benchmark problems, studying parameter robustness, extending beyond finite MDPs, and exploiting task-distribution information.
A A CONCENTRATION INEQUALITY
The appendix extends Hoeffding’s inequality from real-valued to vector-valued random variables, with a tail bound only a constant factor worse than Hoeffding’s.
- The vector-valued extension has a tail-probability upper bound only a constant factor worse than Hoeffding’s inequality.
- The stated lemma provides a probability bound for the norm of a vector-valued martingale.