在您链接的 UCB1 原始论文的 PDF 中，在第 242-243 页中，作者证明了为什么非最佳机器的播放次数比最佳机器少得多（实际上，对数更少）。$c$决定他们是否真的愿意，并且$c=\sqrt{2}$是最小的选择$c$.

我们想证明非最优机器的运行次数（$n_i$, 对于非最优$i$s，在你的符号中）是渐近对数的。换句话说，您可以运行它们几次，这很好，但不要太频繁。我们正在设计一些指标值$a_i(t)=\hat \mu_i+(\epsilon...)$这样错误的情况下，非最优值超过最优值（$a^*(t)<a_i(t)$)，被最小化。

想想最后一个不等式。我们知道$\mu^* > \mu_i$（再次，最优和非最优）。因此，要使该不等式成立，似乎左侧应该很小，或者右侧应该很大。可是等等，$\hat \mu$s 实际上是一些随机试验$\mu$，所以我们不能直接从$\mu^* > \mu_i$到$\hat{\mu^*} > \hat{\mu_i}$; 可能我们只是需要更多的试验。

论文的方程（7）、（8）和（9）就是上一段提到的三个条件；左侧小，右侧大，或缺少试验。好吧，事实上，正如我们所说的运行次数......起初是渐近对数的，假设我们已经运行了足够多的机器，可以消除第三种情况（！）。

对于第一种和第二种情况，因为$\hat \mu_i$是某个随机变量的平均值$[0, 1]$，我们可以使用 Chernoff–Hoeffding 界（或在论文中所谓的；在 Wikipedia 中表示为Hoeffding 不等式）。现在，一个不错的选择$(\epsilon ...)$将保证（从 Hoeffding 的不等式）前两种情况将足够少地发生，或者换句话说，按照$t^{-4}$. 为了实现这一点，我们需要$c \ge \sqrt 2$.

现在回到第三种情况，足够的运行次数实际上是$l = \left \lceil 2 c^2 \ln n / (\mu^* - \mu_i)^2\right \rceil$. 因此，您可以选择更大的$c$但在惩罚中获得更长的收敛速度。

有趣的是，在作者找到所有证据之后$c=1/4$收敛得很好并且实际上表现得更好（！！）比$c=\sqrt{2}$. 似乎他们无法像我们上面所做的那样证明界限。