这篇文章介绍了多臂老虎机（MAB）中两种改进的纯探索（Best-Arm Identification）算法：中值消除（Median Elimination） 和 指数间隙消除（Exponential-Gap Elimination），以及一种基于迭代对数定律（LIL）的 lil’UCB 算法。

中值消除 是一种参数无关的 $(\varepsilon, \Delta)$-PAC 算法。它通过多轮迭代，每轮淘汰一半表现较差的臂（即经验均值排名后50%的臂），并增加每轮的采样次数。该算法以至少 $1-\Delta$ 的概率返回一个 $\varepsilon$-最优臂，样本复杂度为 $O\left(\frac{n}{\varepsilon^2} \log \frac{1}{\Delta}\right)$，匹配了该问题的下界。

指数间隙消除 是一种参数相关的纯探索算法，目标是精确找到最优臂（即 $\varepsilon=0$）。它同样进行多轮迭代，但每轮的精度要求 $\varepsilon_r$ 呈指数级提高（$\varepsilon_r = 2^{-r}/4$）。算法在每轮中使用中值消除作为子程序来找到一个候选臂，然后淘汰那些经验均值明显低于该候选臂的臂。其样本复杂度为 $O\left( \sum_{i=2}^{n} \Delta_i^{-2} \log\left(\frac{1}{\Delta} \log \frac{1}{\Delta_i}\right) \right)$，接近参数依赖的下界。

lil’UCB 算法将用于悔恨最小化的 UCB 思想与一个精心设计的停止条件相结合，用于纯探索。它使用基于迭代对数定律构造的更紧致的置信区间 $CI_i^{\Delta}(t)$，并规定当任何一个臂的拉动次数超过其他臂拉动次数总和的某个常数倍时停止。分析表明，该算法以高概率返回最优臂，其样本复杂度为 $O\left( \sum_{i=2}^{n} \frac{\ln(1/\Delta) + \ln\ln(1/\Delta_i)}{\Delta_i^2} \right)$，进一步改进了指数间隙消除的结果，更接近理论下界。文章的核心是通过更精细的概率工具（如霍夫丁极大不等式和LIL）和算法设计，在纯探索问题上获得近乎最优的样本复杂度。

MAB 改进的纯探索算法

中值消除

算法

（输入参数：$\varepsilon, \Delta$，用于 $(\varepsilon,\Delta)$-PAC 学习）

1. 令 $S_0 \leftarrow [n]$，$r \leftarrow 0$

2. 当 $|S_r| > 1$ 时，执行以下操作：

3. $r \leftarrow r+1$

4. 对 $S_{r-1}$ 中的每个臂执行 $\frac{c \cdot r^4 \ln(r^2/\Delta)}{\varepsilon^2}$ 次

其中 $c$ 是一个足够大的通用常数，将在后续确定。

1. 令 $S_r$ 为 $S_{r-1}$ 中 $\hat{\mu}_{i,r}$ 值最高的 $\frac{|S_{r-1}|}{2}$ 个臂。

其中 $\hat{\mu}_{i,r}$ 是使用第 $r$ 轮数据的经验估计值。

1. 返回 $S_r$ 中唯一的臂。

分析

令 $i_r = \arg\max_{i \in S_r} {\mu_i}$，$\mathcal{E}_r = \left\{ \mu_{i_r} \geq \mu_{i_{r-1}} - \frac{\varepsilon}{3r^2} \right\}$

结论

$\operatorname{Prb}[\mathcal{E}_r] \geq 1$ -对于每个 $r = 1, 2, \dots, r^\ast$（$r^\ast$：最后一轮），$\frac{3\Delta}{8r^2}$ 成立。

证明

对于每个 $i \in S_{r-1}$，根据霍夫丁定理：（如果我们选择足够大的 $c$）\(\operatorname{Prb}\left[ \\|\mu_i - \hat{\mu}_{i,r}\\| < \frac{\varepsilon}{6r^2} \right] \geq 1 - \frac{\Delta}{8r^2}.\)

特别地，

1. $\operatorname{Prb}\left[ |\mu_{i_{r-1}} - \hat{\mu}_{i_{r-1},r}| < \frac{\varepsilon}{6r^2} \right] \geq 1 - \frac{\Delta}{8r^2}$。

2. 假设 $i \in S_{r-1}$ 为“坏的”，如果 $\mu_i < \mu_{i_{r-1}} - \frac{\varepsilon}{3r^2}$，则 \(\mathbb{E}\left[ \#\left\{ i \in S_{r-1} \text{ 是坏的 } \hat{\mu}_{i,r} > \mu_i + \frac{\varepsilon}{6r^2} \right\} \right] \leq \frac{\Delta}{8r^2} \cdot \#\left\{ \text{坏的 } i \in S_{r-1} \right\} \leq \frac{\Delta}{8r^2} \cdot \\|S_{r-1}\\|.\) 将这样的臂 $i$ 称为“可怕的”。

根据马尔可夫不等式：\(\operatorname{Prb}\left[ \#\{\text{terrible } i\} \geq \frac{\\|S_{r-1}\\|}{2} \right] \leq \frac{\frac{\Delta}{8r^2} \cdot \\|S_{r-1}\\|}{\\|S_{r-1}\\|/2} = \frac{\Delta}{4r^2}.\)

因此，根据并集界，\(\operatorname{Prb}\left[ \\|\mu_{i_{r-1}} - \hat{\mu}_{i_{r-1},r}\\| < \frac{\varepsilon}{6r^2} \text{ 且 } \#\{\text{糟糕的 } i\} < \frac{\\|S_{r-1}\\|}{2} \right] \geq 1 - \frac{\Delta}{8r^2} - \frac{\Delta}{4r^2} = 1 - \frac{3\Delta}{8r^2}.\)

当上述事件发生时，我们有：\(\#\left\{ \text{坏 } i \in S_{r-1} \text{ 在 } \hat{\mu}_{i,r} \text{ 排序中位于 } i_{r-1} \text{ 之前 } \right\} < \frac{\\|S_{r-1}\\|}{2}\) $\Rightarrow$ 至少存在1个非坏臂保留在$S_r$中

$\Rightarrow \mu_{i_r} \geq \mu_{i_{r-1}} - \frac{\varepsilon}{3r^2}$。

定理

中值消除算法

1. 返回一个臂 $j$，使得 $\mu_j \geq \mu_1 - \varepsilon$ 的概率为 $\geq 1-\Delta$。

2. 样本复杂度为$O\left(\frac{n}{\varepsilon^2} \log \frac{1}{\Delta}\right)$。

证明

1. 通过并集，我们有 \(\operatorname{Prb}[\mathcal{E}_1 \wedge \mathcal{E}_2 \wedge \dots \wedge \mathcal{E}_{r^\ast}] \geq 1 - \sum_{r=1}^{r^\ast} \frac{3\Delta}{8r^2} \geq 1 - \Delta。\) 当上述事件发生时，我们有： \(\mu_j = \mu_{i_{r^\ast}} \geq \mu_{i_0} - \sum_{r=1}^{r^\ast} \frac{\varepsilon}{3r^2} \geq \mu_{i_0} - \varepsilon = \mu_1 - \varepsilon。\)

2. 样本复杂度该算法的界限为 \(\sum_{r=1}^{r^\ast} \frac{n}{2^{r-1}} \cdot \frac{c \cdot r^4 \ln(r^2/\Delta)}{\varepsilon^2} \leq O\left(\frac{n}{\varepsilon^2} \cdot \log \frac{1}{\Delta}\right).\)

指数间隙消除算法（参数相关的纯探索算法）

算法

（输入参数：$\Delta$）

1. 令 $S_1 \leftarrow [n]$，$r \leftarrow 1$

2. 当 $|S_r| > 1$ DO

   1. $\varepsilon_r \leftarrow 2^{-r}/4$, $\Delta_r \leftarrow \Delta/(50r^3)$

   2. 对每个臂 $i \in S_r$ 进行 $t_r \leftarrow \frac{2}{\varepsilon_r^2} \ln \frac{2}{\Delta_r}$ 次操作。

   3. 令 $\hat{i}_r \leftarrow \text{中值消除}(S_r, \varepsilon_r/2, \Delta_r)$

   4. 令 $S_{r+1} \leftarrow S_r \setminus \left\{ i \in S_r : \hat{\mu}_{i,r} < \hat{\mu}_{\hat{i}_r,r} - \varepsilon_r \right\}$

   5. 令 $r \leftarrow r+1$

3. 返回 $S_r$ 中唯一的臂。

定理

Exp-Gap 算法以 $\geq 1-\Delta$ 的概率返回最优臂，其样本复杂度为 $O\left( \sum_{i=2}^{n} \Delta_i^{-2} \log\left(\frac{1}{\Delta} \log \frac{1}{\Delta_i}\right) \right)$。

证明思路

• 步骤 2c 的样本复杂度可以“计入”步骤 2b。

• 对于每个次优臂 $i>1$，当 $\varepsilon_r < \Delta_i$ 时，它不会持续太久。

因此，$\# \text{臂 i 的样本} \lesssim \sum_{r=1}^{\log_2 \frac{1}{\Delta_i}} \frac{1}{\varepsilon_r^2} \log \frac{1}{\Delta_r^2} \approx \Delta_i^{-2} \log\left(\frac{1}{\Delta} \log \frac{1}{\Delta_i}\right)$.

霍夫丁极大不等式 [Hoeffding’1963]

设 $X_1, X_2, \dots, X_n$ 为独立随机变量，且 $\mathbb{E}X_i = 0$, $X_i \in [a_i, b_i]$ a.s. $\forall i$。那么，对于每个 $t > 0$，\(\operatorname{Prb}\left[ \forall i \in \{1,2,\dots,n\}, \sum_{j=1}^{i} X_j \leq t \right] \geq 1 - \exp\left(-\frac{2t^2}{\sum_{i=1}^{n} (b_i - a_i)^2}\right).\)

引理（迭代对数界律）

设 $X_1, X_2, X_3, \dots$ 为独立随机变量，且 $\mathbb{E}X_i = 0$, $X_i \in [a_i, a_{i+1}]$ a.s. $\forall i$。对于每个 $\Delta \in (0, 1/2)$，我们有 \(\operatorname{Prb}\left[ \forall t \in \{1,2,3,\dots\}, \sum_{i=1}^{t} X_i \leq \sqrt{4t \ln \frac{2.89 \ln(t+1)}{\Delta}} \right] \geq 1-\Delta.\)

证明

令事件 $\mathcal{E} = \left\{ \forall k \in {1,2,\dots}, \sum_{i=1}^{2^k} X_i \leq \sqrt{2^{k-1} \ln\left(\frac{4k^2}{\Delta}\right)} \right\}$.

根据霍夫丁不等式和并集界，\(\operatorname{Prb}[\mathcal{E}] \geq 1 - \sum_{k=1}^{\infty} \frac{\Delta}{4k^2} = 1 - \frac{\Delta}{4} \cdot \frac{\pi^2}{6} \geq 1 - \frac{\Delta}{2}.\)

对于每个 $k = 1,2,3,\dots$，令事件 $\mathcal{F}_k = \left\{ \forall s \in {1,2,\dots,2^k-1}, \sum_{i=2^k+1}^{2^k+s} X_i \leq \sqrt{2^{k-1} \ln\left(\frac{4k^2}{\Delta}\right)} \right\}$.

根据霍夫丁极大不等式：$\operatorname{Prb}[\mathcal{F}_k] \geq 1 - \frac{\Delta}{4k^2}$.

因此，根据并集界，\(\operatorname{Prb}\left[ \mathcal{E} \wedge \left( \bigwedge_{k=1}^{\infty} \mathcal{F}_k \right) \right] \geq 1 - \frac{\Delta}{2} - \sum_{k=1}^{\infty} \frac{\Delta}{4k^2} \geq 1 - \frac{\Delta}{2} - \frac{\Delta}{2} = 1 - \Delta.\)

当上述事件发生时，对于每个 $t \geq 2$，我们记 $t = 2^k + s$ ($s \in [0, 2^k-1]$)，并且我们有

\[\begin{aligned} \sum_{i=1}^{t} X_i &= \sum_{i=1}^{2^k} X_i + \sum_{i=2^k+1}^{2^k+s} X_i \\ &\leq \sqrt{2^{k-1} \ln\left(\frac{4k^2}{\Delta}\right)} + \sqrt{2^{k-1} \ln\left(\frac{4k^2}{\Delta}\right)} \\ &= \sqrt{2 \cdot 2^k \ln\left(\frac{4k^2}{\Delta}\right)} \leq \sqrt{2t \cdot \ln \frac{4(\ln t / \ln 2)^2}{\Delta}} \leq \sqrt{4t \cdot \ln \frac{2.89 \ln(t+1)}{\Delta}}. \end{aligned}\]

lil’UCB（迭代对数 UCB 法则）

算法

1. 对每个臂进行一次操作，令 $t=n$，$T_i(t)=1$ （对于所有 i）。

2. 当 $\forall i: T_i(t) \leq 1 + 80 \sum_{j \neq i} T_j(t)$ 时执行以下操作：

3. 选择 $I_{t+1} = \arg\max_i \left\{ \hat{\mu}_i(t) + 2 \cdot CI_i^{\Delta}(t) \right\}$

其中 $CI_i^{\Delta}(t) \triangleq CI_{i,T_i(t)}^{\Delta} \triangleq 2 \sqrt{\frac{\ln(6 \ln(T_i(t)+1)/\Delta)}{T_i(t)}}$

1. 执行一次 $I_{t+1}$ 臂。

2. 当 $t \leftarrow t+1$ 时，更新 $T_i(t)$，$\hat{\mu}_i(t)$ 对所有 i 成立。

3. 返回 $\arg\max_i {T_i(t)}$

分析

对于每个臂 $i$，定义事件（参数为 $\omega > 0$）：\(\mathcal{E}_i(\omega) \triangleq \left\{ \forall \tau \geq 1, \\|\hat{\mu}_{i,\tau} - \mu_i\\| \leq CI_{i,\tau}^{\omega} \right\}\)

按 LIL Bound，\(\operatorname{Prb}[\mathcal{E}_i(\omega)] \geq 1-\omega \quad \text{holds } \forall i, \forall \omega \in (0, 1/2)。\)

像往常一样，假设 w.l.o.g. $\mu_1 > \mu_2 \geq \mu_3 \geq \dots \geq \mu_n$。

给定 $\mathcal{E}_i(\Delta)$ 的条件（其发生的概率为 $\geq 1-\Delta$），我们有（根据定义）\(\hat{\mu}_{i,\tau} \geq \mu_i - CI_{i,\tau}^{\Delta} \quad \text{成立} \forall \tau.\)

对于每个 $i=2,3,\dots,n$，定义 \(g_i \triangleq \frac{64 \ln\left(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta\right)}{\Delta_i^2}.\)

对于每个 $z=1,2,3,\dots$，我们有

\[\begin{aligned} \operatorname{Prb}[T_i > z \cdot g_i] &\leq \operatorname{Prb}\left[ \hat{\mu}_{i,zg_i} + 2 \cdot CI_{i,zg_i}^{\Delta} \geq \hat{\mu}_{1}(t) + 2 \cdot CI_{1}^{\Delta}(t) \right] \quad \text{(UCB)} \\ &\leq \operatorname{Prb}\left[ \hat{\mu}_{i,zg_i} + 2 \cdot CI_{i,zg_i}^{\Delta} \geq \mu_1 \right] \quad \text{(by $\mathcal{E}_1(\Delta)$)} \\ &= \operatorname{Prb}\left[ \hat{\mu}_{i,zg_i} - \mu_i \geq \Delta_i - 2 \cdot CI_{i,zg_i}^{\Delta} \right]。 \end{aligned}\]

当 $z \geq 1$ 时，对于较小的 $\Delta_i > 0$，我们有 \(\frac{\ln\left(6 \ln(zg_i+1)/\Delta\right)}{2z \ln\left(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta\right)} \leq 1.\)

因此，\(\begin{aligned} \Delta_i - 2 \cdot CI_{i,zg_i}^{\Delta} &= \Delta_i - 4 \sqrt{\frac{\ln(6 \ln(zg_i+1)/\Delta)}{zg_i}} \\ &\geq \Delta_i - 4 \sqrt{\frac{2 \ln(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta)}{zg_i}} \cdot \frac{\Delta_i}{4} \sqrt{\frac{2 \ln(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta)}{g_i}} \\ &= \Delta_i - 4 \sqrt{\frac{2 \ln(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta)}{64 \ln(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta) \cdot \Delta_i^{-2}}} \cdot \Delta_i \\ &= \Delta_i - 4 \Delta_i \sqrt{\frac{2}{64}} = \Delta_i - 4 \Delta_i \cdot \frac{\sqrt{2}}{8} \geq \frac{\Delta_i}{4}. \end{aligned}\)

因此，\(\begin{aligned} \operatorname{Prb}[T_i > z \cdot g_i] &\leq \operatorname{Prb}\left[ \hat{\mu}_{i,zg_i} - \mu_i \geq \frac{\Delta_i}{4} \right] \\ &\leq \exp\left(-\left(\frac{\Delta_i}{4}\right)^2 \cdot 2zg_i\right) \quad \text{(Hoeffding)} \\ &= \exp\left(-\frac{\Delta_i^2}{16} \cdot 2z \cdot \frac{64 \ln(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta)}{\Delta_i^2}\right) \leq \Delta^{8z}. \end{aligned}\)

断言 1

对于 $z=1,2,3,\dots$，$\operatorname{Prb}[T_i > zg_i] \leq \Delta^{8z}$（以 $\mathcal{E}_i(\Delta)$ 为条件）。

令 $\widetilde{T}_i = T_i - g_i$，则有 \(\mathbb{E}\widetilde{T}_i^+ \leq \sum_{z=1}^{\infty} g_i \cdot \operatorname{Prb}[\widetilde{T}_i > (z-1)g_i] \leq \sum_{z=1}^{\infty} g_i \cdot \Delta^{8z} \leq 2g_i \cdot \Delta^8.\)

因此，\(\operatorname{Prb}\left[ \sum_{i=2}^{n} T_i > 2 \sum_{i=2}^{n} g_i \right] \leq \operatorname{Prb}\left[ \sum_{i=2}^{n} \widetilde{T}_i^+ > \sum_{i=2}^{n} g_i \right] \overset{\text{(Markov)}}{\leq} \frac{\mathbb{E} \sum_{i=2}^{n} \widetilde{T}_i^+}{\sum_{i=2}^{n} g_i} \leq \frac{2 \cdot \Delta^8 \cdot \sum_{i=2}^{n} g_i}{\sum_{i=2}^{n} g_i} = 2 \cdot \Delta^8 \leq \Delta.\)

断言 2

以概率 $\geq 1-2\Delta$，我们有 \(\sum_{i=2}^{n} T_i \leq 2 \sum_{i=2}^{n} g_i = 128 \sum_{i=2}^{n} \frac{\ln\left(6 \ln\left(\frac{1}{\Delta_i^2} + 1\right)/\Delta\right)}{\Delta_i^2}.\)

停止条件（防止使用次优臂提前停止）

令 $\mathcal{H}_i \triangleq \left\{ T_i(t) < 1 + 80 \sum_{j=1}^{i-1} T_j(t), \forall i \right\}$，其中 $i=2,3,\dots,n$。

目标

证明 $\operatorname{Prb}\left[ \bigwedge_{i=2}^{n} \mathcal{H}_i \right] \geq 1 - \text{poly}(\Delta)$。

固定 $i$ 并考虑 $\mathcal{H}_i$，令 \(\mathcal{G}_i \triangleq \left\{ \text{至少有 } \frac{i-1}{2} \text{ 个 } \mathcal{E}_1(\Delta), \mathcal{E}_2(\Delta), \dots, \mathcal{E}_{i-1}(\Delta) \text{ 发生} \right\}.\)

事实

由于 $\mathcal{E}_1(\Delta), \mathcal{E}_2(\Delta), \dots, \mathcal{E}_{i-1}(\Delta)$ 相互独立，根据切尔诺夫界，

\[\operatorname{Prb}\left[ \underbrace{1_{\overline{\mathcal{E}_1(\Delta)}} + 1_{\overline{\mathcal{E}_2(\Delta)}} + \dots + 1_{\overline{\mathcal{E}_{i-1}(\Delta)}}}_{\text{回顾切尔诺夫界: } \operatorname{Prb}[X > (1+\gamma)\mu] < \left[\frac{e^\gamma}{(1+\gamma)^{1+\gamma}}\right]^\mu} > \frac{i-1}{2} \right] < \left[ \frac{e^{\frac{1}{2\Delta}-1}}{(\frac{1}{2\Delta})^{\frac{1}{2\Delta}}} \right]^{(i-1)\cdot \Delta}\]

这里，$\mu = \Delta(i-1)$，$(1+\gamma)\mu = \frac{i-1}{2} \iff 1+\gamma = \frac{1}{2\Delta} \iff \gamma = \frac{1}{2\Delta} - 1$

\[= \left[ \frac{e^{\frac{1}{2\Delta}} / e}{(\frac{1}{2\Delta})^{\frac{1}{2\Delta}}} \right]^\frac{i-1}{2} = \left( \frac{e / e^{2\Delta}}{\frac{1}{2\Delta}} \right)^{\frac{i-1}{2}} \leq (2\Delta e)^{\frac{i-1}{2}}.\]

因此，$\operatorname{Prb}[\mathcal{G}_i] > 1 - (2\Delta e)^{\frac{i-1}{2}}$。

事实

$\forall i \geq 2$，$\mathcal{G}_i \wedge \mathcal{E}_i(\Delta^{i-1}) \Rightarrow \mathcal{H}_i$。因此，\(\operatorname{Prb}[\mathcal{H}_i] \geq \operatorname{Prb}[\mathcal{G}_i \wedge \mathcal{E}_i(\Delta^{i-1})] \geq \operatorname{Prb}[\mathcal{G}_i] - \operatorname{Prb}[\overline{\mathcal{E}_i(\Delta^{i-1})}] \geq 1 - (2\Delta e)^{\frac{i-1}{2}} - \Delta^{i-1}.\)

证明

假设在某个时刻 $t$，我们有 $T_i(t) = 80 \sum_{j=1}^{i-1} T_j(t)$。

我们将证明，在时刻 $t+1$ 不会使用臂 $i$，即 \(\exists j < i, \text{ s.t. } \underbrace{\hat{\mu}_j(t) + 2 CI_j^{\Delta}(t)}_{\text{LHS}} > \underbrace{\hat{\mu}_i(t) + 2 CI_i^{\Delta}(t)}_{\text{RHS}}.\)

令 $\sum_{j=1}^{i-1} T_j(t) = \frac{i-1}{2} \cdot S$，则 $T_i(t) = 40(i-1) \cdot S$。

令 $\mathcal{Q} = { j < i : \mathcal{E}_j(\Delta) \text{ 发生} }$。我们有 $\mathcal{G}_i \Rightarrow |\mathcal{Q}| \geq \frac{i-1}{2}$。

注意 \(\sum_{j \in \mathcal{Q}} T_j(t) \leq \sum_{j=1}^{i-1} T_j(t) = \frac{i-1}{2} S\)

因此，存在 $j^\ast \in \mathcal{Q}$ 使得 $T_{j^\ast}(t) \leq S$，

即，存在 $j^\ast < i$ 使得 $\mathcal{E}_{j^\ast}(\Delta)$ 且 $T_{j^\ast}(t) \leq S$。

现在计算：

左轴（对于 $j=j^\ast$）：$\hat{\mu}_{j^\ast}(t) + 2 CI_{j^\ast}^{\Delta}(t) \geq \mu_{j^\ast} + CI_{j^\ast, T_{j^\ast}(t)}^{\Delta} \geq \mu_{j^\ast} + CI_{j^\ast, S}^{\Delta}$。

等式右侧：$\hat{\mu}_i(t) + 2 CI_i^{\Delta}(t) \leq \mu_i + CI_{i, T_i(t)}^{\Delta} + 2 CI_i^{\Delta}(t) \leq \mu_i + 3 CI_{i, T_i(t)}^{\Delta} = \mu_i + 3 CI_{i, 40(i-1)S}^{\Delta}$

注意 \(\begin{aligned} 3 CI_{i, 40(i-1)S}^{\Delta} &= 6 \sqrt{\frac{\ln(6 \ln(40(i-1)S + 1)/\Delta) + (i-1)\ln(1/\Delta)}{40(i-1)S}} \\ &\leq \sqrt{\frac{9}{10}} \cdot \sqrt{\frac{\ln(6 \ln(S+1)) + 2 + \ln(1/\Delta)}{S}} < 2 \sqrt{\frac{\ln(6 \ln(S+1)/\Delta)}{S}} = CI_{j^\ast, S}^{\Delta}. \end{aligned}\)

因此，左侧 > 右侧。

引理

\[\operatorname{Prb}\left[ \bigwedge_{i=2}^{n} \mathcal{H}_i \right] \geq 1 - \sum_{i=2}^{n} \left( (2e\Delta)^{\frac{i-1}{2}} + \Delta^{i-1} \right) \geq 1 - O(\sqrt{\Delta})\]

综上所述，我们有以下结论：

定理

lil’UCB 以 $\geq 1 - O(\sqrt{\Delta})$ 的概率返回最佳臂，并且其样本复杂度受限于 $O(1) \cdot \sum_{i=2}^{n} \frac{\ln(1/\Delta) + \ln\ln(1/\Delta_i + 1)}{\Delta_i^2}$。