Near-optimal Representation Learning for Linear Bandits and Linear RL
This work provides the first theoretical characterization of the benefits of multi-task representation learning for exploration in RL with function approximation, which is important for researchers and practitioners working on efficient learning in multi-task scenarios.
This paper addresses representation learning for multi-task linear bandits and multi-task episodic reinforcement learning (RL) with linear value function approximation. For linear bandits, the proposed MTLR-OFUL algorithm achieves a regret of O(M*sqrt(d*k*T) + d*sqrt(k*M*T)), which is a significant improvement over the O(M*d*sqrt(T)) regret of independent task solutions and is shown to be near-optimal when d > M.
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.