THE CONFIDENCE BOUND METHOD FOR THE MULTI-ARMED BANDIT PROBLEM WITH LARGE ARM SIZE

Abstract

We consider two modifications of the confidence bound method that achieve optimality in the case of large arm sizes. In the first situation we assume the arm size is infinitely large. We establish a regret lower bound and construct confidence bounds that achieve the regret lower bound asymptotically. A novel feature of these confidence bounds is a target value for deciding whether to stick to arms that have been played, or to play a new arm. In the second situation we consider asymptotics when the arm size grows at a polynomial rate with respect to the number of trials. We show that the regret lower bound has an expression similar to that of Lai and Robbins (1985), but with a smaller asymptotic constant. We show how the confidence bounds proposed by Agarwal (1995) can be corrected for arm size so that the new regret lower bound is achieved.