Multitask Learning with No Regret: from Improved Confidence Bounds to
  Active Learning
Pier Giuseppe Sessa Pierre Laforgue Nicolò Cesa-Bianchi Andreas Krause
Multitask learning is a powerful framework that enables one to simultaneously
learn multiple related tasks by sharing information between them. Quantifying
uncertainty in the estimated tasks is of pivotal importance for many downstream
applications, such as online or active learning. In this work, we provide novel
multitask confidence intervals in the challenging agnostic setting, i.e., when
neither the similarity between tasks nor the tasks' features are available to
the learner. The obtained intervals do not require i.i.d. data and can be
directly applied to bound the regret in online learning. Through a refined
analysis of the multitask information gain, we obtain new regret guarantees
that, depending on a task similarity parameter, can significantly improve over
treating tasks independently. We further propose a novel online learning
algorithm that achieves such improved regret without knowing this parameter in
advance, i.e., automatically adapting to task similarity. As a second key
application of our results, we introduce a novel multitask active learning
setup where several tasks must be simultaneously optimized, but only one of
them can be queried for feedback by the learner at each round. For this
problem, we design a no-regret algorithm that uses our confidence intervals to
decide which task should be queried. Finally, we empirically validate our
bounds and algorithms on synthetic and real-world (drug discovery) data.