Meta-Learning Adversarial Bandits
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.