Near-optimal Representation Learning for Linear Bandits and Linear RL

Abstract

This paper studies representation learning for multi-task linear bandits and multi-task episodic RL with linear value function approximation. We first consider the setting where we play $M$ linear bandits with dimension $d$ concurrently, and these bandits share a common $k$-dimensional linear representation so that $k\ll d$ and $k\ll M$. We propose a sample-efficient algorithm, MTLR-OFUL, which leverages the shared representation to achieve $\tilde{O}(M\sqrt{dkT}+d\sqrt{kMT})$ regret, with $T$ being the number of total steps. Our regret significantly improves upon the baseline $\tilde{O}(Md\sqrt{T})$ achieved by solving each task independently. We further develop a lower bound that shows our regret is near-optimal when $d>M$. Furthermore, we extend the algorithm and analysis to multi-task episodic RL with linear value function approximation under low inherent Bellman error \citep{zanette2020learning}. To the best of our knowledge, this is the first theoretical result that characterizes the benefits of multi-task representation learning for exploration in RL with function approximation.

References in corpus (23)

• Massively Multitask Networks for Drug Discovery
• Multi-Task Deep Neural Networks for Natural Language Understanding
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Sharing Knowledge in Multi-Task Deep Reinforcement Learning
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Few-Shot Learning via Learning the Representation, Provably
• Provable Meta-Learning of Linear Representations
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Is Q-learning Provably Efficient?
• High-Dimensional Sparse Linear Bandits
• Bilinear Bandits with Low-rank Structure
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
• Provable Representation Learning for Imitation Learning via Bi-level Optimization
• Low-Rank Generalized Linear Bandit Problems