Nonsingular regret bound for UCB

Question

Acer et al. "Finite-time Analysis of the Multiarmed Bandit Problem" show that the Upper Confidence Bound 1 (UCB1) algorithm has expected regret bounded by

$$\left[ 8 \sum_{i: \mu_i < \mu^\ast} \frac{\log n}{\Delta_i} \right]+ \left(1 + \frac{\pi^2}{3}\right) \sum_i \Delta_i$$

when run for $n$ steps, where $\mu_i$ are the means of the $K$ arms, $\mu^\ast = \max_i \mu_i$, and $\Delta_i = \mu^\ast - \mu_i$.

However, this bound explodes as any $\Delta_i \to 0$, i.e. when there a nearly optimal non-best arm. Certainly the true expected regret does not go singular in this case (for any strategy), and intuitively I would expect UBC1 to do fairly well if there are several nearly optimal arms.

Question 1: Is there a nice regret bound for UCB1 which doesn't have this singularity?

Question 2: If no, is there a modified version of UCB1 with such a nonsingular bound?

Answer 1

You can improve this bound by grouping the arms into "almost optimal" arms (arms whose expected payoffs are within a fixed $\Delta$) and the rest of the arms. So you can bound the regret contributed by the almost optimal arms by $O(T \Delta)$, which actually implies that the worst-case setting of $\Delta$ is approximately $\sqrt{N/T \log T}$, and not a value arbitrarily close to $0$.

This is explained, for example, in section 1.3 of these lecture notes.