Nearly Minimax Algorithms for Linear Bandits with Shared Representation

In this paper, we give nearly minimax optimal algorithms for multi-task linear bandits with shared representation. Multi-task representation learning learns a joint low-dimensional feature extractor from different but related tasks, so the composition of this feature extractor and a simple function (e.g., linear function) can give more accurate predictions than the standard single-task learning paradigm [Baxter, 2000; Caruana, 1997]. The fundamental reason for this improvement is that the relatedness among tasks make us learn the joint feature extractor more efficiently than treating each task independently. Empirically, representation learning has led to successes in applications such as computer vision [Li et al., 2014], natural language processing [Ando and Zhang, 2005; Liu et al., 2019], and drug discovery [Ramsundar et al., 2015].