2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.