  We study online learning with bandit feedback across multiple tasks, with the
goal of improving average performance across tasks if they are similar
according to some natural task-similarity measure. As the first to target the
adversarial setting, we design a unified meta-algorithm that yields
setting-specific guarantees for two important cases: multi-armed bandits (MAB)
and bandit linear optimization (BLO). For MAB, the meta-algorithm tunes the
initialization, step-size, and entropy parameter of the Tsallis-entropy
generalization of the well-known Exp3 method, with the task-averaged regret
provably improving if the entropy of the distribution over estimated
optima-in-hindsight is small. For BLO, we learn the initialization, step-size,
and boundary-offset of online mirror descent (OMD) with self-concordant barrier
regularizers, showing that task-averaged regret varies directly with a measure
induced by these functions on the interior of the action space. Our adaptive
guarantees rely on proving that unregularized follow-the-leader combined with
multiplicative weights is enough to online learn a non-smooth and non-convex
sequence of affine functions of Bregman divergences that upper-bound the regret
of OMD.
