On the Power of Multitask Representation Learning in Linear MDP

Abstract

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 $\varphi$ out of a function class $\Phi$ from $T$ source tasks with $N$ data per task, and then use the learned $\hat{\varphi }$ to reduce the required number of sample for a new task. We first discover a \emph{Least-Activated-Feature-Abundance} (LAFA) criterion, denoted as $\kappa$, with which we prove that a straightforward least-square algorithm learns a policy which is $\tilde{O}(H^2\sqrt{\frac{\mathcal{C}(\Phi {)}^2\kappa d}{NT}+\frac{\kappa d}{n}})$ sub-optimal. Here $H$ is the planning horizon, $\mathcal{C}(\Phi )$ is $\Phi$'s complexity measure, $d$ is the dimension of the representation (usually $d\ll \mathcal{C}(\Phi )$) and $n$ is the number of samples for the new task. Thus the required $n$ is $O(\kappa d{H}^4)$ for the sub-optimality to be close to zero, which is much smaller than $O(\mathcal{C}(\Phi {)}^2\kappa d{H}^4)$ in the setting without multitask representation learning, whose sub-optimality gap is $\tilde{O}(H^2\sqrt{\frac{\kappa \mathcal{C}(\Phi {)}^{2}d}{n}})$. 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.

References in corpus (17)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning
• DARLA: Improving Zero-Shot Transfer in Reinforcement Learning
• The Benefit of Multitask Representation Learning
• Online Meta-Learning
• On the Theory of Transfer Learning: The Importance of Task Diversity
• Sharing Knowledge in Multi-Task Deep Reinforcement Learning
• Few-Shot Learning via Learning the Representation, Provably
• Provable Meta-Learning of Linear Representations
• Learning-to-Learn Stochastic Gradient Descent with Biased Regularization
• Hypothesis Transfer Learning via Transformation Functions
• Transfer from Multiple MDPs
• Incremental Learning-to-Learn with Statistical Guarantees
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Provable Representation Learning for Imitation Learning via Bi-level Optimization
• Impact of Representation Learning in Linear Bandits

Cited by in corpus (1)

• Representation Learning for Online and Offline RL in Low-rank MDPs