Why do we have two similar action selection strategies for UCB1?
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)&lt;a_i(t)$), are minimized.
Think about the last inequality. We know that $\mu^* &gt; \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^* &gt; \mu_i$ to $\hat{\mu^*} &gt; \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.