2020
Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms
NeurIPS 2020spotlight
We study the structure of regret-minimizing policies in the {\em many-armed} Bayesian multi-armed bandit problem: in particular, with $k$ the number of arms and $T$ the time horizon, we consider the case where $k \geq \sqrt{T}$. We first show that {\em subsampling} is a critical step for designing o…