<p>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$.</p>

<p>This is explained, for example, in section 1.3 of <a href="https://bandits.wikischolars.columbia.edu/file/view/Lecture+3+part+1.pdf" rel="nofollow noreferrer">these lecture notes</a>.</p>

CC BY-SA 3.0
2017-10-11T01:50:02.847Z
2017-10-11T01:50:02.847Z
Lev Reyzin
<p><a href="https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf" rel="nofollow noreferrer">Acer et al. "Finite-time Analysis of the Multiarmed Bandit Problem"</a> show that the Upper Confidence Bound 1 (UCB1) algorithm has expected regret bounded by</p>

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

<p>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$.</p>

<p>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.</p>

<p><strong>Question 1:</strong> Is there a nice regret bound for UCB1 which doesn't have this singularity?</p>

<p><strong>Question 2:</strong> If no, is there a modified version of UCB1 with such a nonsingular bound?</p>

<lg.learning>
Nonsingular regret bound for UCB
Geoffrey Irving
# Nonsingular regret bound for UCB

(Asked by: username_0 on 2017-10-10)

[Acer et al. "Finite-time Analysis of the Multiarmed Bandit Problem"](https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf) 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?

**Tags:** lg.learning


---

## 1 answers

### Answer by username_1 on 2017-10-11. Score: 2 | Accepted answer

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](https://bandits.wikischolars.columbia.edu/file/view/Lecture+3+part+1.pdf).


---

