From Finite to Countable-Armed Bandits
This work addresses a theoretical challenge in bandit learning for scenarios with infinitely many arms, which is incremental as it extends finite-armed bandit methods to a countable setting.
The paper tackles the problem of stochastic bandit learning with countably many arms grouped into a finite set of types, where the decision maker lacks knowledge of arm types and their distribution but knows the total number of types. It proposes an adaptive algorithm that achieves O(log n) distribution-dependent expected cumulative regret, proven to be optimal.
We consider a stochastic bandit problem with countably many arms that belong to a finite set of types, each characterized by a unique mean reward. In addition, there is a fixed distribution over types which sets the proportion of each type in the population of arms. The decision maker is oblivious to the type of any arm and to the aforementioned distribution over types, but perfectly knows the total number of types occurring in the population of arms. We propose a fully adaptive online learning algorithm that achieves O(log n) distribution-dependent expected cumulative regret after any number of plays n, and show that this order of regret is best possible. The analysis of our algorithm relies on newly discovered concentration and convergence properties of optimism-based policies like UCB in finite-armed bandit problems with "zero gap," which may be of independent interest.