Sample Complexity of Multi-task Reinforcement Learning

By Emma Brunskill, Lihong Li. 2013

149 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, background): “Brunskill & Li (2013) introduce an MDP clustering approach that reduces negative transfer in MTRL, and prove reduction of sample complexity of exploration using transfer.”
Multi-task Deep Reinforcement Learning with PopArt (2018, background): “In multi-task reinforcement learning, a single agent must learn to master N different environments T = {Di = (Si,Ai, pi, γ)}i=1, each with its own distinct dynamics (Brunskill and Li 2013).”
PAC-inspired Option Discovery in Lifelong Reinforcement Learning (2014, methodology): “In phase 1 that lasts for T 1 tasks, a variant of the E 3 algorithm is used for each task encountered, as in Brunskill & Li (2013).”
Context-Aware Policy Reuse (2018, background): “Multi-Task Learning (MTL) co-learns a set of tasks jointly via some shared knowledge [7, 10, 12], so an agent needs the environment information of all the tasks.”
Online Clustering of Bandits (2014, background): “The most closely related papers are (Djolonga et al., 2013; Azar et al., 2013; Brunskill & Li, 2013; Maillard & Man-nor, 2014).”
Invariant Causal Prediction for Block MDPs (2020, background): “D’Eramo et al. (2020) show the beneﬁts of learning a shared representation in multi-task settings with an approximate value iteration bound and Brunskill and Li (2013) also demonstrate a PAC-MDP algorithm with improved sample efﬁciency bounds through transfer across similar tasks.”
Robust and Efficient Transfer Learning with Hidden Parameter Markov Decision Processes (2017, background): “There has been a large body of work on solving single POMDP models efficiently [6, 16, 24, 37, 45].”
State Abstractions for Lifelong Reinforcement Learning (2018, background): “Naturally, lifelong RL is closely related to the objectives and models of transfer learning (Taylor & Stone, 2009; Thrun, 1996) and multitask RL Tanaka & Ya-mamura (2003); Brunskill & Li (2013).”
Sharing Knowledge in Multi-Task Deep Reinforcement Learning (2020, methodology): “Among the others, Lazaric & Restelli (2011) and Brunskill & Li (2013) give theoretical proofs of the advantage of learning from multiple MDPs and introduces new algorithms to empirically support their claims, as done in this work.”
Bootstrap Latent-Predictive Representations for Multitask Reinforcement Learning (2020, methodology): “We evaluate PBL in the challenging partially observable, multitask setting, where the task indices are kept hidden from the agent (Brunskill & Li, 2013).”
Multitasking Inhibits Semantic Drift (2021, background): “…problem of semantic drift , in which agents come to deploy messages in ways inconsistent with their original (natural language) meanings (Lewis et al., 2017; Lee et al., 2019); secondarily, the general problem of sample inef-ﬁciency in RL algorithms (Kakade et al., 2003; Brunskill and Li, 2013).”
From Skills to Symbols: Learning Symbolic Representations for Abstract High-Level Planning (2018, background): “However, we are interested in the multi-task reinforcement learning setting (Wilson, Fern, Ray, & Tadepalli, 2007; Brunskill & Li, 2013) where the agent must optimize expected reward over a distribution over tasks.”
Model-Free Generative Replay for Lifelong Reinforcement Learning: Application to Starcraft-2 (2022, unknown): “One strategy for managing experiences is to recall data from previous tasks and mix it with data from the current task when training, essentially transforming sequential LRL into batch multi-task reinforcement learning (RL) (Brunskill & Li, 2013).”
Concurrent PAC RL (2015, background): “…sequential decision making, like reinforcement learning, prior work has focused on sharing information serially across consecutive related tasks, such as in transfer learning (e.g. (Taylor and Stone 2009; Lazaric and Restelli 2011)) or online learning across a set of tasks (Brunskill and Li 2013).”