Thompson Sampling for Robust Transfer in Multi-Task Bandits
We study the problem of online multi-task learning where the tasks are
performed within similar but not necessarily identical multi-armed bandit
environments. In particular, we study how a learner can improve its overall
performance across multiple related tasks through robust transfer of knowledge.
While an upper confidence bound (UCB)-based algorithm has recently been shown
to achieve nearly-optimal performance guarantees in a setting where all tasks
are solved concurrently, it remains unclear whether Thompson sampling (TS)
algorithms, which have superior empirical performance in general, share similar
theoretical properties. In this work, we present a TS-type algorithm for a more
general online multi-task learning protocol, which extends the concurrent
setting. We provide its frequentist analysis and prove that it is also
nearly-optimal using a novel concentration inequality for multi-task data
aggregation at random stopping times. Finally, we evaluate the algorithm on
synthetic data and show that the TS-type algorithm enjoys superior empirical
performance in comparison with the UCB-based algorithm and a baseline algorithm
that performs TS for each individual task without transfer.