Before revision:  Our theory is developed from first-principles and can also be adapted to analyze other sampling-based bandit algorithms .
After revision:  Our theory is developed from first-principles and can also be adapted to analyze other sampling-based bandit algorithms, for example, algorithms using the bootstrap for exploration. We also establish an invariance principle for multi-armed bandits with gaps scaling as 1/\sqrt{n .