The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms

Mohsen Bayati, Nima Hamidi, Ramesh Johari +1

We investigate a Bayesian $k$-armed bandit problem in the \emph{many-armed} regime, where $k\ge \sqrt{T}$ and $T$ represents the time horizon. Initially, and aligned with recent…