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.
Code (0)
등록된 구현이 없습니다.
Tasks
Meta-LearningMulti-Armed BanditsSimilar Papers 제목 키워드 기반
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 targ…
Meta-LearningMulti-Armed BanditsAdversarial Attacks on Combinatorial Multi-Armed Bandits
We study reward poisoning attacks on Combinatorial Multi-armed Bandits (CMAB). We first provide a sufficient and necessary condition for the attackability of CMAB, a notion to capture the vulnerability and robustness of …
Multi-Armed BanditsMeta-Learning Adversarial Bandit Algorithms
We study online meta-learning with bandit feedback, with the goal of improving performance across multiple tasks if they are similar according to some natural similarity measure. As the first to target the adversarial on…
Meta-LearningMulti-Armed BanditsVersatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences
We study the problem of $K$-armed dueling bandit for both stochastic and adversarial environments, where the goal of the learner is to aggregate information through relative preferences of pair of decisions points querie…
Multi-Armed BanditsGeneralized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits
We study the adversarial multi-armed bandit problem and create a completely online algorithmic framework that is invariant under arbitrary translations and scales of the arm losses. We study the expected performance of o…
Multi-Armed BanditsTranslation