Multi-task Representation Learning for Pure Exploration in Bilinear
  Bandits
Subhojyoti Mukherjee Qiaomin Xie Josiah P. Hanna Robert Nowak
We study multi-task representation learning for the problem of pure
exploration in bilinear bandits. In bilinear bandits, an action takes the form
of a pair of arms from two different entity types and the reward is a bilinear
function of the known feature vectors of the arms. In the \textit{multi-task
bilinear bandit problem}, we aim to find optimal actions for multiple tasks
that share a common low-dimensional linear representation. The objective is to
leverage this characteristic to expedite the process of identifying the best
pair of arms for all tasks. We propose the algorithm GOBLIN that uses an
experimental design approach to optimize sample allocations for learning the
global representation as well as minimize the number of samples needed to
identify the optimal pair of arms in individual tasks. To the best of our
knowledge, this is the first study to give sample complexity analysis for pure
exploration in bilinear bandits with shared representation. Our results
demonstrate that by learning the shared representation across tasks, we achieve
significantly improved sample complexity compared to the traditional approach
of solving tasks independently.