A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

Abstract

We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of [Kale ’14]. The two bounds determine the minimax optimal expected regret to be Θ( √(T K logN/K)), where K is the number of arms, N is the number of experts, and T is the time horizon.