Meta Representation Learning with Contextual Linear Bandits
Meta-learning seeks to build algorithms that rapidly learn how to solve new
learning problems based on previous experience. In this paper we investigate
meta-learning in the setting of stochastic linear bandit tasks. We assume that
the tasks share a low dimensional representation, which has been partially
acquired from previous learning tasks. We aim to leverage this information in
order to learn a new downstream bandit task, which shares the same
representation. Our principal contribution is to show that if the learned
representation estimates well the unknown one, then the downstream task can be
efficiently learned by a greedy policy that we propose in this work. We derive
an upper bound on the regret of this policy, which is, up to logarithmic
factors, of order $r\sqrt{N}(1\vee \sqrt{d/T})$, where $N$ is the horizon of
the downstream task, $T$ is the number of training tasks, $d$ the ambient
dimension and $r \ll d$ the dimension of the representation. We highlight that
our strategy does not need to know $r$. We note that if $T> d$ our bound
achieves the same rate of optimal minimax bandit algorithms using the true
underlying representation. Our analysis is inspired and builds in part upon
previous work on meta-learning in the i.i.d. full information setting
\citep{tripuraneni2021provable,boursier2022trace}. As a separate contribution
we show how to relax certain assumptions in those works, thereby improving
their representation learning and risk analysis.