这篇文章系统介绍了多臂老虎机（Multi-Armed Bandit）的基础算法与分析框架。首先以两臂老虎机为例，介绍了简单均匀采样算法及其在识别最优臂时的概率保证（PAC）和遗憾（Regret）分析，指出其遗憾可能达到线性级别。随后引入“先探索后利用”（ETC）策略，通过平衡探索与利用将遗憾降低至 $O(T^{2/3} \log^{1/3} T)$。文章指出纯贪婪策略因缺乏主动探索可能导致线性遗憾，进而介绍 $\varepsilon$-贪婪和上置信界（UCB）算法。UCB采用乐观估计原则，给出了 $O(\sqrt{nT \log T})$ 的遗憾上界，并进一步推导出参数依赖的遗憾界 $O\left(\sum_{i=2}^{n} \Delta_i^{-1} \log T\right)$。最后，文章转向纯探索（Best-Arm Identification）目标，分别介绍了均匀采样和逐步淘汰（Successive Elimination）等算法，给出了参数无关和参数依赖的样本复杂度上界，并简要提及了对应的算法下界，展示了该领域基础算法的理论轮廓。

多臂老虎机基础算法

预热：更好臂问题

给定两个臂，臂 $i \in {1,2}$ 的奖励分布为 $D_i$（玩家未知）。

假设：$\mu_i = \mathbb{E}D_i$，$D_i$ 的支撑集为 $[0,1]$。

目标

识别更优臂：$\arg\max_{i \in {1,2}} {\mu_i}$

算法 1

设时间跨度为 $T$，每条臂操作 $T/2$ 次。令 $\hat{\mu}_i$ 为经验均值。

报告 $\arg\max_{i \in {1,2}} {\hat{\mu}_i}$。

分析

令 $\Delta = |\mu_1 - \mu_2|$ 为两臂间的“差距”。

根据霍夫丁定理： \(\operatorname{Prb}[\\|\mu_1 - \hat{\mu}_1\\| < \Delta/2] \geq 1 - 2\exp\left(-\frac{\Delta^2 T}{4}\right)\) \(\operatorname{Prb}[\\|\mu_2 - \hat{\mu}_2\\| < \Delta/2] \geq 1 - 2\exp\left(-\frac{\Delta^2 T}{4}\right)\)

根据并集不等式： \(\operatorname{Prb}[\underbrace{\max\{\\|\mu_1 - \hat{\mu}_1\\|, \\|\mu_2 - \hat{\mu}_2\\|\} < \Delta/2}_{\text{事件 } \mathcal{E}}] \geq 1 - 4\exp\left(-\frac{\Delta^2 T}{4}\right)\)

当事件 $\mathcal{E}$ 发生时： \(\\|(\mu_1 - \mu_2) - (\hat{\mu}_1 - \hat{\mu}_2)\\| \leq \\|\mu_1 - \hat{\mu}_1\\| + \\|\mu_2 - \hat{\mu}_2\\| < \Delta/2 + \Delta/2 = \Delta.\) \(\Rightarrow \arg\max_{i \in \{1,2\}} \{\hat{\mu}_i\} = \arg\max_{i \in \{1,2\}} \{\mu_i\}\)

因此，$\operatorname{Prb}[\text{算法返回正确臂}] \geq \operatorname{Prb}[\mathcal{E}] \geq 1 - 4\exp\left(-\frac{\Delta^2 T}{4}\right)$。

换言之，若要求算法成功概率 $\geq 1-\Delta$，则需满足 $T \geq \Omega(\Delta^{-2} \log \frac{1}{\Delta})$。

推论

在无间隙假设下，当概率 $\geq 1-\Delta$ 时（假设算法返回手臂 $a$），满足： \(\mu_a \geq \max\{\mu_1, \mu_2\} - \varepsilon\) 只要满足 $T \geq \Omega(\varepsilon^{-2} \log \frac{1}{\Delta})$。

即$(\varepsilon, \Delta)$-可能近似正确性(PAC)保证。

悔恨最小化

目标

最大化 $\mathbb{E}\sum_{t=1}^{T} r_t$，其中 $r_t$ 表示时间 $t$ 实现的奖励。

等价地，最小化后悔值 $R_T \triangleq T \cdot \max{\mu_1, \mu_2} - \mathbb{E}\sum_{t=1}^{T} r_t$

算法1的后悔值：$\Delta \cdot \frac{T}{2}$（可能达到$\Omega(T)$量级）。

先探索后承诺（ETC）

1. 调用算法1，设定地平线参数$T_0$

2. 从时间$T_0+1$至$T$，承诺执行算法1返回的操作臂

分析

• 步骤1产生的后悔值：$O(T_0)$

• 算法1以概率$(1-\frac{1}{T})$返回$O\left(\sqrt{\frac{\ln T}{T_0}}\right)$最优臂

• 步骤2的期望后悔值： \(\frac{1}{T} \cdot (T-T_0) + \left(1-\frac{1}{T}\right) \cdot O\left(\sqrt{\frac{\ln T}{T_0}}\right) \cdot (T-T_0) \leq 1 + O\left(\sqrt{\frac{\ln T}{T_0}}\right) \cdot T\)

• 总预期后悔值：\(R_T \leq O(T_0) + 1 + O\left(\sqrt{\frac{\ln T}{T_0}}\right) \cdot T\)

• 令 $T_0 = T^{2/3} (\ln T)^{1/3}$，可得 $R_T \leq O(T^{2/3} \ln^{1/3} T)$。

注释

$O(\sqrt{\frac{\ln T}{T_0}})$最优意味着什么？这意味着高概率下，所选臂 $\mu_a \ge \mu^* - O(\sqrt{\frac{\ln T}{T_0}})$，其中 $\mu^* = \max{\mu_1, \mu_2}$ 是最佳臂（概率至少为 $1- 1/ T$）。

习题

证明：对于任意 $T$，存在强盗问题实例使得 $R_T^{\text{ETC}} \geq \Omega(T^{2/3})$。

能否利用最新信息优化决策？

贪婪策略

在每个时间点 $t$，选择臂 $\arg\max_{i \in {1,2}} {\hat{\mu}_i(t-1)}$

其中 $\hat{\mu}_i(t-1)$：基于截至时间 $t-1$ 的历史数据计算的臂 $i$ 的经验均值。

结论

存在多臂老虎机实例使得 $R_T^{\text{贪婪}} \geq \Omega(T)$。

证明

设 $D_1 = \text{Ber}(0.6)$，$D_2 = \text{Ber}(0.4)$

设事件 $\mathcal{E} = \left\{ \begin{array}{l} \text{时间1选择臂1，奖励=0} \ \text{时间2选择臂2，奖励=1} \end{array} \right\}$

则概率 $\operatorname{Prb}[\mathcal{E}] = 0.4 \times 0.4 = 0.16$。

当 $\mathcal{E}$ 发生时，贪婪算法从时间点 3 起持续选择臂 2。

$\Rightarrow$ 产生 $0.2 \cdot (T-2) = \Omega(T)$ 的后悔值。

因此，$R_T \geq \operatorname{Prb}[\mathcal{E}] \cdot \Omega(T) = \Omega(T)$。

经验教训

需要“主动探索”。

$\varepsilon$-贪婪算法

在每个时间点 $t$，执行： $\begin{cases} \text{按贪婪策略选择的概率 } 1-\varepsilon \ \text{随机选择（探索）的概率 } \varepsilon \end{cases}$。

分析

如何选择 $\varepsilon$？

• $\varepsilon = 0 \Rightarrow$ 贪婪策略

• 常数 $\varepsilon > 0 \Rightarrow \varepsilon \cdot T = \Omega(T)$ 探索所需的预期后悔值。

上置信界限法（UCB）

核心思想

采取乐观策略（OFU：不确定性中的乐观主义）。

乐观程度 $\approx$ 探索深度。

现考虑 $n$ 个臂，不妨设 $\mu_1 \geq \mu_2 \geq \mu_3 \geq \dots \geq \mu_n$。

符号定义

• $T_i(t)$：时间 $t$ 之前选择臂 $i$ 的次数。

• $\hat{\mu}_i(t) = \hat{\mu}_{i, T_i(t)}$：基于前 $T_i(t)$ 次观测值计算的臂 $i$ 的经验均值。

置信界限 （霍夫丁公式）

$\forall i \in {1,2,\dots,n}, t \in {1,2,3,\dots}$： \(\operatorname{Prb}\left[ \mu_i \in \hat{\mu}_i(t) \pm \sqrt{\frac{\ln(2T)}{T_i(t)}} \right] \geq 1 - \frac{1}{2T^2}\)

UCB算法

1. 每条策略臂各执行一次，初始化$t=n$，$T_i(t)=1$，并据此设定$\hat{\mu}_i(t)$。

2. 当$t < T$时循环执行

   1. 选取 $I_{t+1} = \arg\max_{i \in [n]} \left\{ \hat{\mu}_i(t) + \underbrace{\mathrm{CI}_i(t)}_{\substack{\text{置信区间半径} \ = \sqrt{\frac{\ln(2T)}{T_i(t)}}}} \right\}$

   2. 执行方案 $I_{t+1}$ 一次。

   3. 更新 $\hat{\mu}_i(t+1), T_i(t+1)$ $\forall i$。

   4. 设置 $t \leftarrow t+1$。

遗憾分析

定义（期望事件）

设 $\mathcal{E} = \left\{ \mu_i \in \hat{\mu}_i(t) \pm \mathrm{CI}_i(t) \quad \forall i \in [n], t \in [T] \right\}$

由并集界定式：$\operatorname{Prb}[\mathcal{E}] \geq 1 - \frac{1}{2T^2} \cdot T \geq 1 - \frac{1}{T}$。

结论

当事件 $\mathcal{E}$ 发生时，在每个时间点 $t+1$，选择臂 $I_{t+1}$ 的（期望）已发生后悔值不超过 $2 \cdot \mathrm{CI}{I{t+1}}(t)$。

证明

（期望）累积遗憾： \(\begin{aligned} \mu_1 - \mu_{I_{t+1}} &\leq \underbrace{\hat{\mu}_1(t) + \mathrm{CI}_1(t)}_{\text{（由 } \mathcal{E}\text{）}} - \mu_{I_{t+1}} \\ &\leq \underbrace{\hat{\mu}_{I_{t+1}}(t) + \mathrm{CI}_{I_{t+1}}(t)}_{\text{（由 UCB）}} - \mu_{I_{t+1}} \\ &\leq \hat{\mu}_{I_{t+1}}(t) + \mathrm{CI}_{I_{t+1}}(t) - (\underbrace{\hat{\mu}_{I_{t+1}}(t) - \mathrm{CI}_{I_{t+1}}(t)}_{\text{（由 } \mathcal{E}\text{）}}) \\ &= 2 \cdot \mathrm{CI}_{I_{t+1}}(t). \end{aligned}\)

因此，当 $\mathcal{E}$ 发生时， \(\begin{aligned} R_T^{\text{UCB}} &\underset{\substack{\downarrow \\ \text{条件期望} \\ \text{事件 } \mathcal{E}}}{\leq} n + \mathbb{E} \sum_{t=n}^{T-1} 2 \cdot \mathrm{CI}_{I_{t+1}}(t) = n + \mathbb{E} \cdot 2 \sum_{i=1}^{n} \sum_{\tau=1}^{T_i(T)-1} \mathrm{CI}_{i,\tau} \\ &\leq n + \mathbb{E} \cdot 2 \sum_{i=1}^{n} \sum_{\tau=1}^{T_i(T)} \sqrt{\frac{\ln(2T)}{\tau}} \\ &\leq n + \mathbb{E} \cdot O(\sqrt{\ln(2T)}) \cdot \sum_{i=1}^{n} \sqrt{T_i(T)} \text{(柯西-施瓦茨不等式)} \\ &\leq n + \mathbb{E} \cdot O(\sqrt{\ln(2T)}) \cdot \sqrt{n \cdot \sum_{i=1}^{n} T_i(T)} \\ &= n + O(\sqrt{\ln(2T)}) \cdot \sqrt{nT} \end{aligned}\)

一般而言，当 $T \geq n$（通常情况）时，有 \(R_T^{\text{UCB}} \leq \mathbb{E}[\text{regret} \mid \mathcal{E}] + \operatorname{Prb}[\overline{\mathcal{E}}] \cdot T \leq O(\sqrt{nT \ln T}).\)

参数依赖型后悔界

定义 $\Delta_i \triangleq \mu_1 - \mu_i$（当 $i \geq 2$）。

当事件 $\mathcal{E}$ 发生时，有 $\Delta_{I_{t+1}} = \mu_1 - \mu_{I_{t+1}} \leq 2 \cdot \mathrm{CI}_{I_{t+1}}(t) = 2 \cdot \sqrt{\frac{\ln(2T)}{T_{I_{t+1}}(t)}}$

$\Rightarrow T_{I_{t+1}} \leq \frac{4\ln(2T)}{\Delta_{I_{t+1}}^2}$（当$I_{t+1} \neq 1$时）

因此，对于所有 $i > 1$，有 $T_i(T) \leq O\left(\frac{\ln T}{\Delta_i^2}\right)$ 且 \(R_T^{\text{UCB}} \leq \mathbb{E} \sum_{i=2}^ {n} T_i(T) \cdot \Delta_i \leq O(\ln T) \cdot \sum_{i=2}^{n} \Delta_i^{-1}.\)

备注（下界）

即使对于伯努利臂，当 $\mu_i \in [0.1, 0.9]$ $\forall i$ 时，

对于任意策略 $\pi$，我们有：

• (参数依赖)：$\liminf_{T \to \infty} \frac{R_T^{\pi}}{\ln T} \geq \Omega(1) \cdot \sum_{i=2}^{n} \Delta_i^{-1}$ ($\forall$ 实例)

• (参数无关)：对于任意 $T$，存在实例使得 $R_T^{\pi} \geq \Omega(\sqrt{nT})$。

纯探索策略

目标

以概率 $\geq 1-\Delta$（通常作为输入参数 $\Delta$）识别最优臂，同时最小化样本复杂度。

参数无关纯探索算法（$\varepsilon, \Delta$ - PAC 上界）

目标

设 $j$ 为算法返回的臂，要求 $\operatorname{Prb}[\mu_1 - \mu_j \leq \varepsilon] \geq 1-\Delta$。（$\varepsilon, \Delta$ 作为输入给定）。

均匀采样算法

1. 对每个臂执行 $\frac{4\ln(2n/\Delta)}{\varepsilon^2}$ 次操作。

2. 返回 $\arg\max_i {\hat{\mu}_i}$

正确性

根据霍夫丁不等式：$\operatorname{Prb}[\mu_i \in \hat{\mu}_i \pm \varepsilon/2] \geq 1 - \frac{\Delta^2}{2n^2}$ $\forall i$。

由联合界：$\operatorname{Prb}[\forall i, \mu_i \in \hat{\mu}_i \pm \varepsilon/2] \geq 1 - \frac{\Delta^2}{2n^2} \cdot n \geq 1-\Delta$。

当该事件发生时： \(\mu_j \geq \hat{\mu}_j - \varepsilon/2 \geq \hat{\mu}_1 - \varepsilon/2 \geq \mu_1 - \varepsilon/2 - \varepsilon/2 = \mu_1 - \varepsilon.\)

样本复杂度

$O\left(\frac{n}{\varepsilon^2} \cdot \ln \frac{n}{\Delta}\right)$。

问题

为何必须对所有 $n$ 个臂进行联合界，而非仅对臂 1 和臂 j 进行？

参数依赖纯探索算法

定义

对于任意多臂老虎机实例，定义其复杂度参数 \(H = H(I) \triangleq \sum_{i=2}^{n} \Delta_i^{-2}\)

对UCB算法的修改

将$\mathrm{CI}_{i,t}$替换为$\sqrt{\frac{\ln(2T/\Delta)}{t}}$。

此时，以相同方式定义$\mathcal{E}$：所有置信区间均保持正确。

我们仍可得：$\operatorname{Prb}[\mathcal{E}] \geq 1 - \frac{\Delta^2}{T^2} \cdot T \geq 1-\Delta$。

同理分析：$\forall i$，$T_i(T) \leq \frac{4\ln(2T/\Delta)}{\Delta_i^2}$。

$\Rightarrow \sum_{i=2}^{n} T_i(T) \leq 4\ln(2T/\Delta) \cdot H$。

结论

当 $T > 8 \cdot \ln(2T/\Delta) \cdot H$（或 $T > c \cdot H \cdot \ln(T/\Delta)$，其中 $c>0$ 为常数）时，概率不小于 $1-\Delta$ 的情况下，最佳臂是运行 $T$ 次后被选择次数最多的臂。

问题

能否省去输入参数 $H$？

逐步淘汰法

置信区间

$\mathrm{CI}_{i,t} \triangleq \sqrt{\frac{\ln(2n^2/\Delta)}{t}}$，$\mathrm{CI}_i(t) = \mathrm{CI}_{i,T_i(t)}$

算法

1. 初始化所有臂为“活动”状态

2. 当存在 $\geq 2$ 个活动臂时循环执行

   1. 对每个活动臂执行一次

   2. 对于每个活动臂 $i$ 执行

   3. 若存在活动臂 $j$ 满足 $\underbrace{\hat{\mu}_i(t) + \mathrm{CI}_i(t)}_{\text{UCB}_i(t)} < \underbrace{\hat{\mu}_j (t) - \mathrm{CI}_j(t)}_{\text{LCB}_j(t)}$ 则停用臂 $i$。

3. 返回唯一活动臂。

分析

根据霍夫丁定理，对于任意 $i,t$，我们有 \(\operatorname{Prb}[\mu_i \in \hat{\mu}_{i,t} \pm \mathrm{CI}_{i,t}] \geq 1 - \frac{\Delta^2}{2n^2 t^2}.\)

因此，对于每个 $i \in [n]$，根据并界定理，我们有 \(\operatorname{Prb}[\forall t, \mu_i \in \hat{\mu}_{i,t} \pm \mathrm{CI}_{i,t}] \geq 1 - \sum_{t=1}^{\infty} \frac{\Delta^2}{2n^2 t^2} = 1 - \frac{\Delta^2}{2n^2} \cdot \frac{\pi^2}{6} \geq 1 - \frac{\Delta^2}{n^2}.\)

因此，再次应用并集不等式可得： \(\operatorname{Prb}[\underbrace{\forall i, \forall t, \mu_i \in \hat{\mu}_{i,t} \pm \mathrm{CI}_{i,t}}_{\text{期望事件 } \mathcal{E}}] \geq 1 - \frac{\Delta^2}{n^2} \cdot n \geq 1-\Delta.\)

结论

当事件 $\mathcal{E}$ 发生时，最佳臂不会被淘汰。（算法正确性）

样本复杂度

首先，需注意算法运行期间所有活跃臂的执行次数均相等。

假设事件 $\mathcal{E}$ 发生，且臂 $i$（$i \geq 2$）被执行 $T$ 次，使得 $\mathrm{CI}_{i,T} < \Delta_i/2$，

则可知 $\mathrm{CI}_i(t) < \Delta_i/2$，臂 $i$ 将被淘汰。

因此，设$N_i$为臂$i$（$i \geq 2$）的执行次数，则有 \(\mathrm{CI}_{i,N_i} = \sqrt{\frac{\ln(2n \cdot N_i / \Delta)}{N_i}} \geq \Delta_i/2 \ 由此可得 N_i \leq O\left(\frac{1}{\Delta_i^2} \cdot \left(\ln \frac{n}{\Delta} + \ln \frac{1}{\Delta_i^2}\right)\right).\)

因此当事件 $\mathcal{E}$ 发生时，算法的样本复杂度为：\(N_1 + \sum_{i=2}^ {n} N_i \leq O(1) \cdot \sum_{i=2}^{n} \frac{1}{\Delta_i^2} \left[\ln \frac{n}{\Delta} + \ln \frac{1}{\Delta_i^2}\right] \leq O\left(H \cdot \ln \frac{n}{\Delta}\right).\)

下界（参数无关纯探索）

定理

对于任意$(\varepsilon, \Delta)$-PAC算法，存在多臂老虎机实例使得采样复杂度$\geq \Omega\left(\frac{n}{\varepsilon^2} \cdot \ln \frac{1}{\Delta}\right)$。

下界（参数依赖的纯探索）

1. 定理 设 $T$ 为算法以概率 $\geq 1-\Delta$ 成功所需的操作次数。对于所有满足 $0.9 \geq \mu_1 > \mu_2 \geq \mu_3 \geq \dots \geq \mu_n \geq 0.1$ 的伯努利臂，有 \(\mathbb{E}[T] \geq \Omega(1) \cdot H \ln(1/\Delta)\)

2. 定理 [Farrell’1964] 即使当 $n=2$ 时，若算法以概率 $\geq 0.9$ 返回较优臂，则 \(\limsup_{\Delta_2 \to 0} \frac{\mathbb{E}[T]}{\Delta_2^{-2} \ln \ln \Delta_2^{-1}} \geq \Omega(1).\)

计划

缩小/降低样本复杂度上界与下界之间的差距（主要提升上界）。