Optimal UCB Adjustments for Large Arm Sizes

Hock Peng Chan, Shouri Hu

The regret lower bound of Lai and Robbins (1985), the gold standard for checking optimality of bandit algorithms, considers arm size fixed as sample size goes to infinity. We show…