这篇文章系统性地建立了多臂老虎机（MAB）问题的信息论下界框架，核心结论是任何算法的样本复杂度或遗憾都受到问题实例内在区分难度的根本限制。通过构造“对抗性”实例对并利用总变差距离、KL散度和广义Hellinger距离等工具量化其数据分布的相似性，文章推导出关键下界：对于 $(\varepsilon, \Delta)$-PAC学习，所需样本至少为 $\Omega(\varepsilon^{-2} \ln \Delta^{-1})$；极小极大遗憾下界为 $\Omega(\sqrt{nT})$；而对“合理”算法，其实例依赖遗憾下界为 $\Omega(\sum_i \Delta_i^{-1} \log T)$，纯探索的样本复杂度下界为 $\Omega(\sum_i \Delta_i^{-2} \ln \Delta^{-1})$。这些下界通过散度分解引理将算法性能与臂的期望抽样次数直接关联，并借助广义距离度量扩展至非标准噪声分布（如均匀分布和三角分布），从而为MAB算法的理论极限提供了完整而严谨的刻画。

MAB 下界

热身：针对在两个臂中学习较优臂的 $(\varepsilon, \Delta)$-PAC 学习的样本复杂度下界（LB）。

定理

假设 $\mathcal{A}$ 是一个针对双臂的 $(\varepsilon, \Delta)$-PAC 算法，且 $\mathcal{A}$ 最多使用 $T$ 个样本，则 $T \geq \Omega\left(\frac{1}{\varepsilon^2} \ln \frac{1}{\Delta}\right)$。

我们首先假设 $\mathcal{A}$ 是确定性的。

观察

$\mathcal{A} \Rightarrow \exists \mathcal{A}’$ 也是 $(\varepsilon, \Delta)$-PAC，其中 $\mathcal{A}’$ 对每个臂各玩 $T$ 次，并通过函数 $f: [0,1]^T \times [0,1]^T \to {1,2}$ 做出决策。

我们关注伯努利臂，并考虑 $f: {0,1}^T \times {0,1}^T \to {1,2}$。

考虑两个实例：$I_1: \mu_1 = p, \; \mu_2 = p + \varepsilon; \quad I_2: \mu_1 = p + \varepsilon, \; \mu_2 = p.$

$\mathcal{A}’$ 是 $(\varepsilon, \Delta)$-PAC 意味着：

\[\Pr_{r \sim \mathcal{B}_p^{\otimes T} \otimes \mathcal{B}_{p+\varepsilon}^{\otimes T}} \left[ f(r) = 1 \right] \leq \Delta \tag{1}\] \[\Pr_{r \sim \mathcal{B}_{p+\varepsilon}^{\otimes T} \otimes \mathcal{B}_{p}^{\otimes T}} \left[ f(r) = 2 \right] \leq \Delta \tag{2}\]

直觉

当 $T$ 较小时 $\Rightarrow \mathcal{D}_1 \triangleq \mathcal{B}_p^{\otimes T} \otimes \mathcal{B}_{p+\varepsilon}^{\otimes T}$ 与 $\mathcal{D}_2 \triangleq \mathcal{B}_{p+\varepsilon}^{\otimes T} \otimes \mathcal{B}_{p}^{\otimes T}$ “接近”

$\Rightarrow \Pr_{\mathcal{D}_1}[f=1] \approx \Pr_{\mathcal{D}_2}[f=1] \Rightarrow$ 与 (1) 和 (2) 矛盾。

问题

如何定量衡量两个分布的“接近”程度？

信息论简短探索

定义

分布 $P$ 和 $Q$ 之间的 总变差距离 为 $\Delta(P,Q) \triangleq \frac{1}{2} \| P - Q \|_1 = \frac{1}{2} \sum_{a \in \Omega} |P(a) - Q(a)|.$

事实 1

\[\Delta(P,Q) = \max_{A \subseteq \Omega} |P(A) - Q(A)|\]

证明

令 $B = { a \in \Omega : P(a) \geq Q(a) }$。

对每个 $A \subseteq \Omega$，我们有：

\[\begin{aligned} |P(A) - Q(A)| &= \left| P(A \cap B) - Q(A \cap B) + P(A \cap \overline{B}) - Q(A \cap \overline{B}) \right| \\ &\leq \max \left\{ P(A \cap B) - Q(A \cap B), \, Q(A \cap \overline{B}) - P(A \cap \overline{B}) \right\} \\ &\leq \max \left\{ P(B) - Q(B), \, Q(\overline{B}) - P(\overline{B}) \right\} \\ &= \frac{1}{2} \left[ P(B) - Q(B) + Q(\overline{B}) - P(\overline{B}) \right] = \frac{1}{2} \sum_{a \in \Omega} |P(a) - Q(a)|. \end{aligned}\]

当 $A = B$（或 $\overline{B}$）时，不等式取等。

观察

令 $A = { f(r) = 1 }$。由事实 1，$|\mathcal{D}_1(A) - \mathcal{D}_2(A)| \leq \Delta(\mathcal{D}_1, \mathcal{D}_2)$。因此，为得出矛盾，只需证明：$\Delta(\mathcal{D}_1, \mathcal{D}_2) < 1 - 2\Delta. \tag{*}$

方法一：直接计算

$\mathcal{D}_1(r_1, \dots, r_T, r_{T+1}, \dots, r_{2T}) = p^a (1-p)^{T-a} (p+\varepsilon)^b (1-p-\varepsilon)^{T-b}$

（其中 $a = r_1 + \dots + r_T$，$b = r_{T+1} + \dots + r_{2T}$）。$\mathcal{D}_2$ 同理。

则 \(\| \mathcal{D}_1 - \mathcal{D}_2 \|_1 = \sum_{a,b} \binom{T}{a} \binom{T}{b} \\|\mathcal{D}_1(a,b) - \mathcal{D}_2(a,b)\\| = \cdots\)

方法二

定义

分布 $P$ 和 $Q$ 之间的 [Hellinger 距离]{.underline} 为：$H(P,Q) \triangleq \left[ \frac{1}{2} \sum_{a} \left( \sqrt{P(a)} - \sqrt{Q(a)} \right)^2 \right]^{1/2} = \frac{1}{\sqrt{2}} | \sqrt{P} - \sqrt{Q} |_2.$

事实 2

$H^2(P,Q) = \frac{1}{2} \sum_{a} \left( P(a) + Q(a) - 2\sqrt{P(a)Q(a)} \right) = 1 - \sum_{a} \sqrt{P(a)Q(a)} \in [0,1]$。

引理 3

$H^2(P,Q) \stackrel{(3)}{\leq} \Delta(P,Q) \stackrel{(4)}{\leq} \sqrt{H^2(P,Q)(2 - H^2(P,Q))} \leq \sqrt{2} \, H(P,Q)$。

证明

（(3) 的证明）：只需证 $\begin{aligned} \sum_{a} \left( \sqrt{P(a)} - \sqrt{Q(a)} \right)^2 &\leq \sum_{a} |P(a) - Q(a)|
\iff \forall a, \; P(a) + Q(a) - 2\sqrt{P(a)Q(a)} &\leq |P(a) - Q(a)|
\iff \forall a, \; 2\sqrt{P(a)Q(a)} &\geq P(a) + Q(a) - |P(a) - Q(a)|
&= 2 \cdot \min{P(a), Q(a)}. \quad \checkmark \end{aligned}$

（(4) 的证明）$\begin{aligned} \Delta^2(P,Q) &= \frac{1}{4} \left( \sum_{a} |P(a) - Q(a)| \right)^2 = \frac{1}{4} \left( \sum_{a} \left| \sqrt{P(a)} - \sqrt{Q(a)} \right| \cdot \left( \sqrt{P(a)} + \sqrt{Q(a)} \right) \right)^2
&\stackrel{(C-S)}{\leq} \frac{1}{4} \left[ \sum_{a} \left( \sqrt{P(a)} - \sqrt{Q(a)} \right)^2 \right] \cdot \left[ \sum_{a} \left( \sqrt{P(a)} + \sqrt{Q(a)} \right)^2 \right]
&= \frac{1}{2} H^2(P,Q) \cdot \sum_{a} \left( P(a) + Q(a) + 2\sqrt{P(a)Q(a)} \right)
&= H^2(P,Q) \cdot \left( 1 + \sum_{a} \sqrt{P(a)Q(a)} \right) = H^2(P,Q) \cdot \left( 2 - H^2(P,Q) \right). \end{aligned}$

定义

分布 $P$ 和 $Q$ 之间的 [Kullback-Leibler (KL) 散度/相对熵]{.underline} 为：$D_{\mathrm{KL}}(P | Q) \triangleq - \sum_{a \in \Omega} P(a) \ln \frac{Q(a)}{P(a)}.$

备注

1. $D_{\mathrm{KL}}(P | Q) = 0 \iff P = Q$（$D_{\mathrm{KL}}$ 始终 $\geq 0$）

2. KL 散度不是度量，不满足三角不等式，不对称。

与 Hellinger 距离的关系

引理 4

$H^2(P,Q) \leq 1 - \exp\left(-\tfrac{1}{2} D_{\mathrm{KL}}(P | Q)\right).$

证明

$\begin{aligned} 1 - H^2(P,Q) &= \sum_a \sqrt{P(a)Q(a)} = \exp\left( \ln \sum_a \sqrt{P(a)Q(a)} \right)
&= \exp\left( \ln \sum_a P(a) \sqrt{Q(a)/P(a)} \right)
&\geq \exp\left( \sum_a P(a) \ln \sqrt{Q(a)/P(a)} \right) \quad \text{(Jensen 不等式)}
&= \exp\left( -\tfrac{1}{2} D_{\mathrm{KL}}(P | Q) \right). \end{aligned}$

引理 5（Pinsker 不等式）

$\Delta(P,Q) \leq \sqrt{D_{\mathrm{KL}}(P | Q)}.$

证明

由引理 3：$\Delta(P,Q) \leq \sqrt{2H^2(P,Q)}$

由引理 4：$H^2(P,Q) \leq 1 - \exp\left(-\tfrac{1}{2} D_{\mathrm{KL}}(P | Q)\right) \leq \tfrac{1}{2} D_{\mathrm{KL}}(P | Q)$（利用 $e^{-x} \geq 1-x$）

因此，$\Delta(P,Q) \leq \sqrt{D_{\mathrm{KL}}(P | Q)}$。

备注

更精细的证明可得 $\Delta(P,Q) \leq \sqrt{\tfrac{1}{2} D_{\mathrm{KL}}(P | Q)}$。

引理 6（高概率 Pinsker）

$\Delta(P,Q) \leq 1 - \tfrac{1}{2} \exp\left(-D_{\mathrm{KL}}(P | Q)\right).$

证明

由引理 3：$\begin{aligned} \Delta(P,Q) &\leq \sqrt{2H^2(P,Q) - H^4(P,Q)} = \sqrt{1 - \left(1 - H^2(P,Q)\right)^2}
&\leq 1 - \tfrac{1}{2} \left(1 - H^2(P,Q)\right)^2 \quad \text{(利用 } \sqrt{1-x} \leq 1 - \tfrac{1}{2}x \; \forall x \in [0,1]\text{)}
&\leq 1 - \tfrac{1}{2} \exp\left(-D_{\mathrm{KL}}(P | Q)\right) \quad \text{(引理 4)} \end{aligned}$

KL 散度的可加性

事实 7

设 $P(x,y) = P_1(x)P_2(y)$，$Q(x,y) = Q_1(x)Q_2(y)$，则 $\begin{aligned} D_{\mathrm{KL}}(P | Q) &= - \sum_{x,y} P(x,y) \ln \frac{Q(x,y)}{P(x,y)} = - \sum_{x,y} P_1(x)P_2(y) \left[ \ln \frac{Q_1(x)}{P_1(x)} + \ln \frac{Q_2(y)}{P_2(y)} \right]
&= - \sum_{x,y} P_1(x)P_2(y) \ln \frac{Q_1(x)}{P_1(x)} - \sum_{x,y} P_1(x)P_2(y) \ln \frac{Q_2(y)}{P_2(y)}
&= D_{\mathrm{KL}}(P_1 | Q_1) + D_{\mathrm{KL}}(P_2 | Q_2). \end{aligned}$

回到 (*)

由引理 5，$\Delta(\mathcal{D}_1, \mathcal{D}_2) \leq \sqrt{D_{\mathrm{KL}}(\mathcal{D}_1 | \mathcal{D}_2)}$，

其中，由 KL 散度的可加性，$D_{\mathrm{KL}}(\mathcal{D}_1 | \mathcal{D}_2) = T \left[ D_{\mathrm{KL}}(\mathcal{B}_p | \mathcal{B}_{p+\varepsilon}) + D_{\mathrm{KL}}(\mathcal{B}_{p+\varepsilon} | \mathcal{B}_p) \right].$

由定义和直接计算：

\[\begin{aligned} D_{\mathrm{KL}}(\mathcal{B}_p \| \mathcal{B}_{p+\varepsilon}) &= p \ln \frac{p}{p+\varepsilon} + (1-p) \ln \frac{1-p}{1-p-\varepsilon} \\ &= \frac{1}{2} \cdot \frac{\varepsilon^2}{p(1-p)} \pm O(\varepsilon^3) \cdot \left( \frac{1}{p^2} + \frac{1}{(1-p)^2} \right) \quad \text{(当 } |\varepsilon| < \min\{p, 1-p\}\text{)} \end{aligned}\]

因此，我们有：

事实 8

当 $p \in [\alpha, 0.9]$ 时，

\[D_{\mathrm{KL}}(\mathcal{B}_p \| \mathcal{B}_{p+\varepsilon}) \leq O(\varepsilon^2), \; D_{\mathrm{KL}}(\mathcal{B}_{p+\varepsilon} \| \mathcal{B}_p) \leq O(\varepsilon^2).\]

最终，$\Delta(\mathcal{D}_1, \mathcal{D}_2) \leq \sqrt{T \cdot O(\varepsilon^2)} = O(\sqrt{T\varepsilon^2})$。

对于任意 $\Delta < \frac{1}{2} - \frac{1}{100}$，$\Delta(\mathcal{D}_1, \mathcal{D}_2)$ 必须 $\geq 1-2\Delta = \Omega(1)$，这意味着 $O(\sqrt{T\varepsilon^2}) \geq \Omega(1) \Rightarrow T \geq \Omega\left(\frac{1}{\varepsilon^2}\right).$

那么 $\Delta = o(1)$ 呢？

使用高概率 Pinsker： \(\Delta(\mathcal{D}_1, \mathcal{D}_2) \leq 1 - \tfrac{1}{2} \exp\left(-D_{\mathrm{KL}}(\mathcal{D}_1 \| \mathcal{D}_2)\right) \leq 1 - \tfrac{1}{2} \exp\left(-O(T\varepsilon^2)\right).\)

由于 $\Delta(\mathcal{D}_1, \mathcal{D}_2) \geq 1-2\Delta$，我们得到 $\exp\left(-O(T\varepsilon^2)\right) \leq 4\Delta \Rightarrow T\varepsilon^2 \geq \Omega(\ln \tfrac{1}{\Delta}) \Rightarrow T \geq \Omega\left(\tfrac{1}{\varepsilon^2} \ln \tfrac{1}{\Delta}\right)$。

一般情形：n 臂老虎机

对于任意实例 $I = (\mathcal{D}_1, \mathcal{D}_2, \dots, \mathcal{D}_n)$ 和任意（可能随机的）策略 $\pi$，在 $I$ 上运行 $\pi$ 得到 [历史]{.underline} $H = (a_1, r_1, a_2, r_2, \dots, a_H, r_H) \quad \text{（$H$ 也用于表示 $|H|$）}$。

令 $\mathcal{P}_{\pi, I}$ 为 $H$ 的分布。

引理 9（散度分解）。

设 $I = (\mathcal{D}_1, \dots, \mathcal{D}_n)$ 且 $I’ = (\mathcal{D}_1’, \dots, \mathcal{D}_n’)$。对于任意（可能随机的）策略 $\pi$，有 $D_{\mathrm{KL}}(\mathcal{P}_{\pi, I} \mid \mathcal{P}_{\pi, I’}) = \sum_{i=1}^{n} \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \left[ T_i(H) \right] \cdot D_{\mathrm{KL}}(\mathcal{D}_i \mid \mathcal{D}_i’).$ 其中，$T_i(H)$ 是历史 $H$ 中臂 $i$ 的抽样次数。

证明

注意到 \(\mathcal{P}_{\pi, I}(H) = \prod_{t=1}^{H} \pi_t(a_t \mid a_1, r_1, \dots, a_{t-1}, r_{t-1}) \cdot \mathcal{D}_{a_t}(r_t).\)

因此， \(\ln \frac{\mathcal{P}_{\pi, I}(H)}{\mathcal{P}_{\pi, I'}(H)} = \sum_{t=1}^{H} \ln \frac{\mathcal{D}_{a_t}(r_t)}{\mathcal{D}_{a_t}'(r_t)}, \quad \text{且}\)

\[D_{\mathrm{KL}}(\mathcal{P}_{\pi, I} \mid \mathcal{P}_{\pi, I'}) = \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \ln \frac{\mathcal{P}_{\pi, I}(H)}{\mathcal{P}_{\pi, I'}(H)} = \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \sum_{t=1}^{H} \ln \frac{\mathcal{D}_{a_t}(r_t)}{\mathcal{D}_{a_t}'(r_t)}.\]

这等于 \(\begin{aligned} &= \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \sum_{i=1}^{n} \sum_{t=1}^{+\infty} \mathbf{1}[t \leq H \land a_t = i] \cdot \ln \frac{\mathcal{D}_{a_t}(r_t)}{\mathcal{D}_{a_t}'(r_t)} \\ &= \sum_{i=1}^{n} \sum_{t=1}^{+\infty} \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \mathbf{1}[t \leq H \land a_t = i] \cdot \underset{r_t \sim \mathcal{D}_i}{\mathbb{E}} \ln \frac{\mathcal{D}_i(r_t)}{\mathcal{D}_i'(r_t)} \\ &= \sum_{i=1}^{n} \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \left[ T_i(H) \right] \cdot D_{\mathrm{KL}}(\mathcal{D}_i \| \mathcal{D}_i'). \end{aligned}\)

定理 10（极小极大遗憾下界）

对于任意 $n \geq 2$，以及任意（可能随机的）策略 $\pi$，存在一个实例 $I$，使得 $R_T^{\pi, I} \geq \Omega(\sqrt{nT})$。

证明

设 $\Delta \in (0, \tfrac{1}{8})$ 待定。令 $I = (\mathcal{B}_{\frac{1}{2}+\Delta}, \mathcal{B}_{\frac{1}{2}}, \dots, \mathcal{B}_{\frac{1}{2}})$。

选取 $z = \arg\min_{i \in {2, \dots, n}} \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \left[ T_i(H) \right]$，我们有 $\underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \left[ T_z(H) \right] \leq \frac{T}{n-1}$。

现在令 $I’ = (\mathcal{B}_{\frac{1}{2}+\Delta}, \mathcal{B}_{\frac{1}{2}}, \dots, \mathcal{B}_{\frac{1}{2}}, \mathcal{B}_{\frac{1}{2}+2\Delta}, \mathcal{B}_{\frac{1}{2}}, \dots, \mathcal{B}_{\frac{1}{2}})$（第 $z$ 个臂）。

令 $A$ 为事件 $T_z(H) \leq \frac{T}{2}$。

显然，$R_T^{\pi, I} | A \geq \frac{\Delta T}{2}$，$R_T^{\pi, I’} | \bar{A} \geq \frac{\Delta T}{2}$。

因此， \(\begin{aligned} R_T^{\pi, I} + R_T^{\pi, I'} &\geq \frac{\Delta T}{2} \left( \Pr_{\pi, I}[A] + \Pr_{\pi, I'}[\bar{A}] \right) \\ &= \frac{\Delta T}{2} \left( \Pr_{\pi, I}[A] + 1 - \Pr_{\pi, I'}[A] \right) \geq \frac{\Delta T}{2} \left( 1 - \left| \Pr_{\pi, I}[A] - \Pr_{\pi, I'}[A] \right| \right) \\ &\geq \frac{\Delta T}{2} \left( 1 - \Delta(\mathcal{P}_{\pi, I}, \mathcal{P}_{\pi, I'}) \right) \geq \frac{\Delta T}{2} \left( 1 - \sqrt{D_{\mathrm{KL}}(\mathcal{P}_{\pi, I} \| \mathcal{P}_{\pi, I'})} \right). \end{aligned}\)

由分解引理， \(D_{\mathrm{KL}}(\mathcal{P}_{\pi, I} \mid \mathcal{P}_{\pi, I'}) = \underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \left[ T_z(H) \right] \cdot D_{\mathrm{KL}}(\mathcal{B}_{\frac{1}{2}} \mid \mathcal{B}_{\frac{1}{2}+2\Delta}) \leq \frac{T}{n-1} \cdot O(\Delta^2).\)

现在令 $\Delta = c \cdot \sqrt{\frac{n-1}{T}}$ 使得 $D_{\mathrm{KL}}(\mathcal{B}_{\frac{1}{2}} \mid \mathcal{B}_{\frac{1}{2}+2\Delta}) \leq \frac{n-1}{T} \cdot \frac{1}{2}$，我们有 $D_{\mathrm{KL}}(\mathcal{P}_{\pi, I} \mid \mathcal{P}_{\pi, I’}) \leq \tfrac{1}{2} \quad \text{因此：} \quad R_T^{\pi, I} + R_T^{\pi, I’} \geq \frac{\Delta T}{2} \cdot (1 - \sqrt{\tfrac{1}{2}}) \geq \Omega(\Delta T) \geq \Omega(\sqrt{(n-1) \cdot T}).$

类似地，可证得：

定理 11（极小极大样本复杂度下界）。

对于任意 $n \geq 2$，以及任意 $(\varepsilon, \Delta)$-PAC 策略 $\pi$，存在一个实例 $I$，使得 $\underset{H \sim \mathcal{P}_{\pi, I}}{\mathbb{E}} \left[ |H| \right] \geq \Omega\left( \frac{n}{\varepsilon^2} \cdot \ln \frac{1}{\Delta} \right)$。

实例依赖的下界

考虑伯努利实例 $I = I(\mu_1, \mu_2, \dots, \mu_n) = (\mathcal{B}_{\mu_1}, \mathcal{B}_{\mu_2}, \dots, \mathcal{B}_{\mu_n})$，并令 $\mathcal{I} = \left\{ I(\mu_1, \mu_2, \dots, \mu_n) : \mu_i \in (0.1, 0.9) \; \forall i \in [n] \right\}.$

复杂度参数

令 $c^*(I) \triangleq \sum_{i: \Delta_i > 0} \frac{1}{\Delta_i}$，其中 $\Delta_i = \max_j \mu_j - \mu_i$。

回顾

UCB 对每个 $I \in \mathcal{I}$ 实现 $O(c^*(I) \cdot \log T)$ 的遗憾。

目标（实例最优性）。

对每个 $I \in \mathcal{I}$，证明每个策略 $\pi$ 的遗憾下界为 $\Omega(c^*(I) \log T)$？

不幸的是，上述目标并不完全可行... 我们只能对“合理”的策略证明遗憾下界。

定义

称策略 $\pi$ 是 [$(C,p)$-合理的]{.underline}，如果 $R_T^{\pi, I} \leq C \cdot T^p \; \forall I \in \mathcal{I}$。

示例

UCB 是 $(O(\sqrt{n \log T}), \tfrac{1}{2})$-合理的。

定理 12

对于任意 $(C,p)$-合理的策略 $\pi$ 和任意 $I \in \mathcal{I}$，我们有 $R_T^{\pi, I} \geq \Omega(1) \cdot \sum_{i: \Delta_i > 0} \frac{1}{\Delta_i} \cdot \left[ (1-p) \ln T + \ln \frac{\min{\Delta_i, 0.05}}{8C} \right]^+,$ 其中 $[x]^+ = \max{0, x}$。

证明

设 $I = I(\mu_1, \mu_2, \dots, \mu_n)$。令 $T_i = T_i(T)$ 为臂 $i$ 的总抽样次数。我们有：

引理 13

$\forall i: \Delta_i > 0$，$\underset{\pi, I}{\mathbb{E}} \left[ T_i \right] \geq \Omega\left(\frac{1}{\Delta_i^2}\right) \cdot \left[ (1-p) \ln T + \ln \frac{\min{\Delta_i, 0.05}}{8C} \right]^+$。

于是定理得证。

引理 13 的证明

考虑 $I’ = I(\mu_1, \dots, \mu_{i-1}, \mu_i + \lambda, \mu_{i+1}, \dots, \mu_n)$，其中 $\lambda = \Delta_i + \varepsilon$ 且 $\varepsilon = \min{\Delta_i, 0.05}$。

令 $A$ 为事件 ${ T_i > \frac{T}{2} }$，我们有：$R_T^{\pi, I} \geq \Pr_{\pi, I}[A] \cdot \frac{T \Delta_i}{2}, \quad R_T^{\pi, I’} \geq \Pr_{\pi, I’}[\bar{A}] \cdot \frac{T \varepsilon}{2}.$

因此， \(\begin{aligned} R_T^{\pi, I} + R_T^{\pi, I'} &\geq \frac{T \varepsilon}{2} \left( \Pr_{\pi, I}[A] + \Pr_{\pi, I'}[\bar{A}] \right) = \frac{T \varepsilon}{2} \left( \Pr_{\pi, I}[A] + 1 - \Pr_{\pi, I'}[A] \right) \\ &\geq \frac{T \varepsilon}{2} \left( 1 - \left| \Pr_{\pi, I}[A] - \Pr_{\pi, I'}[A] \right| \right) \geq \frac{T \varepsilon}{2} \left( 1 - \Delta(\mathcal{P}_{\pi, I}, \mathcal{P}_{\pi, I'}) \right) \\ &\geq \frac{T \varepsilon}{4} \exp\left( -D_{\mathrm{KL}}(\mathcal{P}_{\pi, I} \mid \mathcal{P}_{\pi, I'}) \right) \quad \text{(高概率 Pinsker)} \\ &= \frac{T \varepsilon}{4} \exp\left( - \underset{\pi, I}{\mathbb{E}} \left[ T_i \right] \cdot D_{\mathrm{KL}}(\mathcal{B}_{\mu_i} \mid \mathcal{B}_{\mu_i + \lambda}) \right). \end{aligned}\)

由于 $D_{\mathrm{KL}}(\mathcal{B}_{\mu_i} \mid \mathcal{B}_{\mu_i + \lambda}) \leq O(\lambda^2)$，我们有

$\underset{\pi, I}{\mathbb{E}} \left[ T_i \right] \geq \left[ \Omega(\lambda^{-2}) \cdot \ln \frac{T \varepsilon}{4(R_T^{\pi, I} + R_T^{\pi, I’})} \right]^+.$

由 $\pi$ 的 $(C,p)$-合理性，$R_T^{\pi, I} + R_T^{\pi, I’} \leq 2C \cdot T^p$。因此，

$\begin{aligned} \underset{\pi, I}{\mathbb{E}} \left[ T_i \right] &\geq \left[ \Omega(\lambda^{-2}) \cdot \ln \frac{T \varepsilon}{8C \cdot T^p} \right]^+
&\geq \left[ \Omega(\Delta_i^{-2}) \cdot \ln \frac{\varepsilon}{8C} + (1-p) \ln T \right]^+ \geq \Omega(\Delta_i^{-2}) \cdot \left[ (1-p) \ln T + \ln \frac{\varepsilon}{8C} \right]^+. \end{aligned}$

类似地，可证得：

定理 14

假设策略 $\pi$ 对每个 $I \in \mathcal{I}$（具有唯一最优臂）均以概率 $1-\Delta$ 返回最优臂。则对于每个具有唯一最优臂的 $I \in \mathcal{I}$：$\underset{\pi, I}{\mathbb{E}} \left[ \sum_{i=1}^{n} T_i \right] \geq \Omega(1) \cdot \sum_{i: \Delta_i > 0} \frac{1}{\Delta_i^2} \cdot \ln \frac{1}{\Delta}.$

一般噪声分布

问题

假设噪声分布为 $\text{Unif}[-1,1]$，则 $(\varepsilon, \Delta)$-PAC 学习两个臂中较优臂的最优样本复杂度是多少？（即两个臂的奖励分布为：$\mu_1 + \text{Unif}[-1,1], \mu_2 + \text{Unif}[-1,1]$）

回顾

对于伯努利臂或高斯噪声，我们可证明最优样本复杂度为：$\Theta(\frac{1}{\varepsilon^2} \log \frac{1}{\Delta})$，其中我们使用了关键事实：$D_{\mathrm{KL}}(\mathcal{B}_p \mid \mathcal{B}_{p+\varepsilon}) \leq O(\varepsilon^2) \quad \text{(当 } |\varepsilon| < \min{p, 1-p}\text{)} \quad \text{和}$ $D_{\mathrm{KL}}\left( \mathcal{N}(\mu, 1) \mid \mathcal{N}(\mu+\varepsilon, 1) \right) \leq O(\varepsilon^2).$

然而，$D_{\mathrm{KL}}\left( \mu + \text{Unif}[-1,1], \mu+\varepsilon + 2\text{Unif}[-1,1] \right)$ 未定义/无界。

更好的算法

1. 以 $m = T/2$ 次抽样玩臂 1，令 $\hat{X}_1$ 为观测到的最大奖励。

2. 以 $m = T/2$ 次抽样玩臂 2，令 $\hat{X}_2$ 为观测到的最大奖励。

3. 返回 $\arg\max_{i \in {1,2}} { \hat{X}_i }$。

定理 15

上述算法在 $T = c \cdot \frac{1}{\varepsilon} \ln \frac{1}{\Delta}$（其中 $c > 0$ 为常数）时是 $(\varepsilon, \Delta)$-PAC 的。

证明

不妨设 $\mu_1 > \mu_2 + \varepsilon$。我们有 $\Pr\left[ \hat{X}_1 \in [\mu_1 + 1 - \varepsilon, \mu_1 + 1] \right] = 1 - \left(1 - \frac{\varepsilon}{2}\right)^m \geq 1 - \Delta \quad \text{(当 } c > 0 \text{ 足够大)}.$

当上述事件发生时，$\hat{X}_1 \geq \mu_1 + 1 - \varepsilon > \mu_2 + 1 \geq \hat{X}_2$，意味着算法返回了正确的臂。

备注

可调整该算法以实现 $O(\log^2 T)$ 的遗憾。

那么其他噪声分布呢？例如“三角噪声”

对于具有上述噪声的臂，最优样本复杂度/遗憾是多少？

广义平方 Hellinger 距离

对于分布 $P,Q$ 和 $s \geq 2$，定义 $H_s^2(P,Q) \triangleq 1 - \sum_{a \in \Omega} P(a)^{1 - \frac{1}{s}} Q(a)^{\frac{1}{s}}.$

观察

常规平方 Hellinger 距离 $H^2(P,Q) = H_s^2(P,Q)$，其中 $s=2$。

引理 16

对于任意分布 $P,Q$ 和常数 $s \geq 2$，有 $\frac{2}{s} H_2^2(P,Q) \leq H_s^2(P,Q) \leq \frac{2(s-1)}{s} H_2^2(P,Q).$

证明

我们将使用如下 Hölder 不等式的稳定性版本。

定理 17（Aldaz 2008）

设 $1 < \alpha \leq 2$ 且 $\beta = \frac{\alpha}{\alpha-1}$ 为其共轭指数。若 $f \in L^\alpha, g \in L^\beta, \|f\|_\alpha, \|g\|_\beta > 0$，则 \(\|f\|_\alpha \|g\|_\beta \left( 1 - \frac{1}{\alpha} \left\| \frac{|f|^{\alpha/2}}{\|f\|_\alpha^{\alpha/2}} - \frac{|g|^{\beta/2}}{\|g\|_\beta^{\beta/2}} \right\|_2^2 \right) \leq \|fg\|_1 \leq \|f\|_\alpha \|g\|_\beta \left( 1 - \frac{1}{\beta} \left\| \frac{|f|^{\alpha/2}}{\|f\|_\alpha^{\alpha/2}} - \frac{|g|^{\beta/2}}{\|g\|_\beta^{\beta/2}} \right\|_2^2 \right).\)

为证明引理 16，令 $\alpha = \frac{s}{s-1}$ 和 $\beta = s$。对任意 $a \in \Omega$，令 $f(a) = P(a)^{(s-1)/s} \quad \text{和} \quad g(a) = Q(a)^{1/s}.$

验证 \(\begin{aligned} \|f\|_\alpha^\alpha &= \sum_a f(a)^\alpha = \sum_a P(a) = 1 \\ \|g\|_\beta^\beta &= \sum_a g(a)^\beta = \sum_a Q(a) = 1 \\ \|fg\|_1 &= \sum_a f(a)g(a) = \sum_a P(a)^{(s-1)/s} Q(a)^{1/s} = 1 - H_s^2(P,Q). \end{aligned}\)

应用定理 17，得 \(1 - \frac{s-1}{s} \|\sqrt{P} - \sqrt{Q}\|_2^2 \leq 1 - H_s^2(P,Q) \leq 1 - \frac{1}{s} \|\sqrt{P} - \sqrt{Q}\|_2^2.\)

回顾 $\|\sqrt{P} - \sqrt{Q}\|_2^2 = 2H_2^2(P,Q)$，我们完成证明。

结合引理 3，我们有

推论 18

$\frac{s}{2(s-1)} H_s^2(P,Q) \leq \Delta(P,Q) \leq \sqrt{s} \cdot H_s(P,Q) \quad (s \geq 2).$

对于任意实例 $I = (\mathcal{D}_1, \mathcal{D}_2, \dots, \mathcal{D}_n)$，任意（可能随机的）策略 $\pi$，和 $t \geq 1$，令 $\mathcal{P}_{\pi, I, t}$ 为在 $I$ 上运行 $\pi$ 的 $t$-截断历史 的分布。更准确地说，样本 $H_t \sim \mathcal{P}_{\pi, I, t}$ 的生成方式如下：首先采样 $H \sim \mathcal{P}_{\pi, I}$，然后令 $H_t = (a_1, r_1, a_2, r_2, \dots, a_{\min\{t, |H|\}}, r_{\min\{t, |H|\}}).$

引理 19（分解）

设 $I = (\mathcal{D}_1, \mathcal{D}_2, \dots, \mathcal{D}_n)$，$I’ = (\mathcal{D}’_1, \mathcal{D}’_2, \dots, \mathcal{D}’_n)$。对于任意（可能随机的）策略 $\pi$，任意 $t \geq 1$ 和任意 $s \geq 2$，有 $H_s^2(\mathcal{P}_{\pi, I, t}, \mathcal{P}_{\pi, I’, t}) \leq t^{1/s} \cdot \left( \sum_{i=1}^n \operatorname{\mathbb{E}}_{H_t \sim \mathcal{P}_{\pi, I, t}} \left[ T_i(H_t) \right] \cdot H_s^2(\mathcal{D}_i, \mathcal{D}’_i) \right)^{1 - 1/s}.$

证明

首先，观察 \(\begin{aligned} H_s^2(\mathcal{P}_{\pi, I, t}, \mathcal{P}_{\pi, I', t}) &= 1 - \operatorname{\mathbb{E}}_{H_t \sim \mathcal{P}_{\pi, I, t}} \left[ \frac{\mathcal{P}_{\pi, I', t}^{1/s}(H_t)}{\mathcal{P}_{\pi, I, t}^{1/s}(H_t)} \right] \text{（由定义）} \\ &= 1 - \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I, t-1}} \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot \mid H_{t-1})} \operatorname{\mathbb{E}}_{r_t \sim \mathcal{D}_{a_t}} \left[ \frac{ \left( \mathcal{P}_{\pi, I', t-1}(H_{t-1}) \cdot \pi(a_t \mid H_{t-1}) \cdot \mathcal{P}_{\mathcal{D}'_{a_t}}(r_t) \right)^{1/s} }{ \left( \mathcal{P}_{\pi, I, t-1}(H_{t-1}) \cdot \pi(a_t \mid H_{t-1}) \cdot \mathcal{P}_{\mathcal{D}_{a_t}}(r_t) \right)^{1/s} } \right] \\ & \quad \text{（可记 $a_t = \perp$ 若 $H_t$ 在时间 $t$ 前结束）} \\ &= 1 - \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I, t-1}} \frac{\mathcal{P}_{\pi, I', t-1}^{1/s}(H_{t-1})}{\mathcal{P}_{\pi, I, t-1}^{1/s}(H_{t-1})} \cdot \underbrace{ \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} \operatorname{\mathbb{E}}_{r_t \sim \mathcal{D}_{a_t}} \frac{\mathcal{P}_{\mathcal{D}'_{a_t}}^{1/s}(r_t)}{\mathcal{P}_{\mathcal{D}_{a_t}}^{1/s}(r_t)} }_{\text{波浪线}} \\ &= 1 - \underbrace{ \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I, t-1}} \frac{\mathcal{P}_{\pi, I', t-1}^{1/s}(H_{t-1})}{\mathcal{P}_{\pi, I, t-1}^{1/s}(H_{t-1})} }_{H_s^2(\mathcal{P}_{\pi, I, t-1}, \mathcal{P}_{\pi, I', t-1})} \\ & \quad + \underbrace{ \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I, t-1}} \frac{\mathcal{P}_{\pi, I', t-1}^{1/s}(H_{t-1})}{\mathcal{P}_{\pi, I, t-1}^{1/s}(H_{t-1})} \cdot \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) }_{\text{双下划线}} \\ & \quad \text{（因为 } \operatorname{\mathbb{E}}_{r_t \sim \mathcal{D}_{a_t}} \frac{\mathcal{P}_{\mathcal{D}'_{a_t}}^{1/s}(r_t)}{\mathcal{P}_{\mathcal{D}_{a_t}}^{1/s}(r_t)} \leq 1 - H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \text{）} \\ &= H_s^2(\mathcal{P}_{\pi, I, t-1}, \mathcal{P}_{\pi, I', t-1}) + \sum_{H_{t-1}} \mathcal{P}_{\pi, I, t-1}^{1 - 1/s}(H_{t-1}) \cdot \mathcal{P}_{\pi, I', t-1}^{1/s}(H_{t-1}) \cdot \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \\ & \quad \text{（Hölder 不等式）} \\ &\leq \left( \sum_{H_{t-1}} \mathcal{P}_{\pi, I, t-1}(H_{t-1}) \cdot \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \right)^{1 - 1/s} \\ & \quad \cdot \left( \sum_{H_{t-1}} \mathcal{P}_{\pi, I', t-1}(H_{t-1}) \cdot \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \right)^{1/s} \\ &\leq \left( \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I, t-1}} \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \right)^{1 - 1/s} \\ & \quad \cdot \left( \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I', t-1}} \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot | H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \right)^{1/s}. \end{aligned}\)

综上： \(H_s^2(\mathcal{P}_{\pi, I, t}, \mathcal{P}_{\pi, I', t}) \leq H_s^2(\mathcal{P}_{\pi, I, t-1}, \mathcal{P}_{\pi, I', t-1}) + \left( \operatorname{\mathbb{E}}_{H_{t-1} \sim \mathcal{P}_{\pi, I, t-1}} \operatorname{\mathbb{E}}_{a_t \sim \pi(\cdot \mid H_{t-1})} H_s^2(\mathcal{D}_{a_t}, \mathcal{D}'_{a_t}) \right)^{1 - 1/s}.\)

持续展开不等式直至 $t=1$，我们得到 \(H_s^2(\mathcal{P}_{\pi, I, t}, \mathcal{P}_{\pi, I', t}) \leq \sum_{\tau=1}^{t} \left( \operatorname{\mathbb{E}}_{H_{\tau-1} \sim \mathcal{P}_{\pi, I, \tau-1}} \operatorname{\mathbb{E}}_{a_\tau \sim \pi(\cdot \mid H_{\tau-1})} H_s^2(\mathcal{D}_{a_\tau}, \mathcal{D}'_{a_\tau}) \right)^{1 - 1/s}.\)

再次由 Hölder 不等式， \(\begin{aligned} &\leq t^{1/s} \cdot \left( \sum_{\tau=1}^{t} \operatorname{\mathbb{E}}_{H_{\tau-1} \sim \mathcal{P}_{\pi, I, \tau-1}} \operatorname{\mathbb{E}}_{a_\tau \sim \pi(\cdot | H_{\tau-1})} H_s^2(\mathcal{D}_{a_\tau}, \mathcal{D}'_{a_\tau}) \right)^{1 - 1/s} \\ &= t^{1/s} \cdot \left( \sum_{i=1}^n \operatorname{\mathbb{E}}_{H_t \sim \mathcal{P}_{\pi, I, t}} \left[ T_i(H_t) \right] \cdot H_s^2(\mathcal{D}_i, \mathcal{D}'_i) \right)^{1 - 1/s}. \end{aligned}\)

备注

更细致的推导可表明 \(H_s^2(\mathcal{P}_{\pi, I, t}, \mathcal{P}_{\pi, I', t}) \leq \left( \sum_{i=1}^n \operatorname{\mathbb{E}}_{H_t \sim \mathcal{P}_{\pi, I, t}} \left[ T_i(H_t) \right] \cdot H_s^2(\mathcal{D}_i, \mathcal{D}'_i) \right)^{1 - 1/s} \cdot \left( \sum_{i=1}^n \operatorname{\mathbb{E}}_{H_t \sim \mathcal{P}_{\pi, I', t}} \left[ T_i(H_t) \right] \cdot H_s^2(\mathcal{D}_i, \mathcal{D}'_i) \right)^{1/s}.\)

回到三角噪声

记 $p_\Delta(\cdot)$ 为三角噪声的概率密度函数。我们可计算 $\begin{aligned} H_s^2(\mu + \Delta\text{-噪声}, \mu + \varepsilon + \Delta\text{-噪声}) &= 1 - \int_{-\infty}^{+\infty} p_\Delta(x - \mu)^{1/2} \cdot p_\Delta(x - \mu - \varepsilon)^{1/2} dx
&\leq O(\varepsilon^2) \end{aligned}$

由引理 16，我们有 $H_s^2(\mu + \Delta\text{-噪声}, \mu + \varepsilon + \Delta\text{-噪声}) \leq 2 \cdot O(\varepsilon^2) = O(\varepsilon^2), \quad \forall s \geq 2$。

现在考虑两个 $\Delta$-噪声老虎机实例 $I$ 和 $I’$，其均值奖励为：$\begin{aligned} I: \quad &\mu_1 = 1/2, \quad \mu_2 = 1/2 + \varepsilon
I’: \quad &\mu_1 = 1/2 + \varepsilon, \quad \mu_2 = 1/2. \end{aligned}$

假设策略 $\pi$ 以概率 $\geq 0.9$ 区分这两个实例，且 $\pi$ 使用的样本数不超过 $T$（几乎必然），我们有 $\Delta(\mathcal{P}_{\pi, I, T}, \mathcal{P}_{\pi, I’, T}) \geq 1 - 2 \times 0.1 = 0.8.$

另一方面，由推论 18 和引理 19： \(\begin{aligned} \Delta^2(\mathcal{P}_{\pi, I, T}, \mathcal{P}_{\pi, I', T}) &\leq s \cdot H_s^2(\mathcal{P}_{\pi, I, T}, \mathcal{P}_{\pi, I', T}) \\ &\leq s \cdot T^{1/s} \cdot \left[ T \cdot O(\varepsilon^2) \right]^{1 - 1/s} = T \cdot s \cdot O(\varepsilon^2)^{1 - 1/s}. \end{aligned}\)

综上，我们得到 $0.8 \leq T \cdot s \cdot O(\varepsilon^2)^{1 - 1/s} \implies T \geq \Omega\left( \frac{1}{s \cdot \varepsilon^{2 \cdot (1 - 1/s)}} \right).$

取 $s = \ln \frac{1}{\varepsilon}$，我们得到 $T \geq \Omega\left( \frac{1}{\varepsilon^2 \cdot \ln \frac{1}{\varepsilon}} \right)$。

备注

更细致的分析可表明 $T \geq \Omega\left( \frac{1}{\varepsilon^2} \right)$。

备注

一般地，可在引理 19 中选择 $s = \ln T$，使得 $t^{1/s} \leq O(1)$，从而该引理可类似于引理 9 使用（但在应用推论 18 时，我们可能损失一个 $s^2 \ln T$ 因子）。