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 (2014). The two bounds determine the minimax optimal expected regret to be Θ( √T K log (N/K) ), where K is the number of arms, N is the number of experts, and T is the time horizon.