Online Meta-Learning in Adversarial Multi-Armed Bandits
We study meta-learning for adversarial multi-armed bandits. We consider the
online-within-online setup, in which a player (learner) encounters a sequence
of multi-armed bandit episodes. The player's performance is measured as regret
against the best arm in each episode, according to the losses generated by an
adversary. The difficulty of the problem depends on the empirical distribution
of the per-episode best arm chosen by the adversary. We present an algorithm
that can leverage the non-uniformity in this empirical distribution, and derive
problem-dependent regret bounds. This solution comprises an inner learner that
plays each episode separately, and an outer learner that updates the
hyper-parameters of the inner algorithm between the episodes. In the case where
the best arm distribution is far from uniform, it improves upon the best bound
that can be achieved by any online algorithm executed on each episode
individually without meta-learning.