A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
This provides a fundamental theoretical result for researchers in online learning and bandit algorithms, though it is incremental as it completes a known bound.
The paper tackles the problem of determining the minimax optimal expected regret in non-stochastic multi-armed bandits with expert advice by proving a tight lower bound that matches an existing upper bound, establishing the regret as Θ(√(T K log(N/K))).
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 $Θ\left( \sqrt{T K \log (N/K) } \right)$, where $K$ is the number of arms, $N$ is the number of experts, and $T$ is the time horizon.