Why do we have two similar action selection strategies for UCB1?

Question

In the literature, there are at least two action selection strategies associated with the UCB1's action selection strategy/policy. For example, in the paper Algorithms for the multi-armed bandit problem (2000/2014), at time step $t$, an action is selected using the following formula

$$ a^*(t) \doteq \arg \max _{i=1 \ldots k}\left(\hat{\mu}_{i}+\sqrt{\frac{2 \ln t}{n_{i}}}\right) \tag{1}\label{1}, $$ where

• $\hat{\mu}_{i}$ is an estimate of the expected return for arm $i$
• $n_i$ is the number of times the action $i$ is selected
• $k$ is the number of arms/actions

On the other hand, Sutton & Barto (2nd edition of the book) provide a slightly different formula (equation 2.10)

$$ a^*(t) \doteq \arg \max _{i=1 \ldots k}\left(\hat{\mu}_{i}+c\sqrt{\frac{\ln t}{n_{i}}}\right) \tag{2}\label{2}, $$ where $c > 0$ is a hyper-parameter that controls the amount of exploration (as explained in the book or here).

Why do we have these two formulas? I suppose that both are "upper confidence bounds" (and, in both cases, they are constants, though one is a hyper-parameter), but why (and when) would we use one over the other? They are not equivalent because $c$ only needs to be greater than $0$, i.e. it can be arbitrarily large (although, in the mentioned book, the authors use $c=2$ in one experiment/figure). If $c = \sqrt{2}$, then they are the same.

The answer to my question can probably be found in the original paper that introduced UCB1 (which actually defines the UCB1 as in \ref{1}), or in a paper that derives the bound, in the sense that the bound probably depends on some probability of error, but I have not fully read it yet, so, if you know the answer, feel free to derive both bounds and relate the two formulas.

Answer 1

In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ decides whether they indeed would, and $c=\sqrt{2}$ is the minimum choice of $c$.

We want to show that the number of runs for non-optimal machines ($n_i$, for non-optimal $i$s, in your notation) is asymptotically logarithmic. In other words, you may run them for a few times and well, it's fine, but not too often. We're devising some indicator value $a_i(t)=\hat \mu_i+(\epsilon...)$ such that the mistaken cases, where values of non-optimal ones surpass values of optimal ones ($a^*(t)<a_i(t)$), are minimized.

Think about the last inequality. We know that $\mu^* > \mu_i$ (again, optimal and non-optimal ones). Therefore, for that inequality to be true, it seems either the left-hand side should be quite small or the right-hand side should be quite large. But wait, $\hat \mu$s are actually some random trials for $\mu$, so we cannot claim directly from $\mu^* > \mu_i$ to $\hat{\mu^*} > \hat{\mu_i}$; it might be that we just need more trials.

The equations (7), (8) and (9) of the paper is the three conditions mentioned in the paragraph above; left-hand side is small, right-hand side is large or the trials are lacking. Well, in fact, as we stated the number of runs ... is asymptotically logarithmic at first, the third case can be eliminated(!), assuming that we've run this machine enough.

For the first and second case, since $\hat \mu_i$ is the average of some random variable in $[0, 1]$, we can use Chernoff–Hoeffding bound (or so called in the paper; stated as Hoeffding's inequality in Wikipedia). Now, a good choice of $(\epsilon ...)$ will guarantee (from Hoeffding's inequality) that the first two cases will occur sufficiently scarcely, or in other words, in the order of $t^{-4}$. To achieve this, we need $c \ge \sqrt 2$.

Now back to the third case, the enough number of runs is actually $l = \left \lceil 2 c^2 \ln n / (\mu^* - \mu_i)^2\right \rceil$. Thus, you may choose larger $c$ but receive longer convergence speed in penalty.

Funnily enough, after all the proofs the authors find $c=1/4$ to converge well and actually perform substantially better(!!) than $c=\sqrt{2}$. It seems they could not prove the bound as we did above.