Lower Bound
证明 lower bound，我们需要构造一些问题实例（problem instances, $\mathcal{F}$）可以“愚弄”任何算法。一般来说，有两种思路：
- 证明任何算法对某个问题实例都有很高的 regret
- 定义一个 $\mathcal{F}$ 上的概率分布，证明任何算法都有一个比较高的期望 regret。
KL-divergence
KL 散度可用于度量两个概率分布（probability measure）的差异。 $$ \mathrm{KL}(p, q)=\sum_{x \in \Omega} p(x) \ln \frac{p(x)}{q(x)}=\mathbb{E}_p\left[\ln \frac{p(x)}{q(x)}\right] $$
考虑样本空间 $\Omega = \{0, 1\}^{n}$ 和两个分布 $p=\mathtt{RC}_{\epsilon}^n, q = \mathtt{RC}^n_{0}$，则对 $\epsilon \in (0, 1/2)$，成立 $|p(A) - q(A)| \leq \epsilon \sqrt{n}, \; \forall A \subset \Omega$
这里 $A$ 表示一个连续投掷硬币的结果，$\mathtt{RC}_{\epsilon}$ 表示一个期望为 $(1+\epsilon)/2$ 的 0-1 Bernoulli 分布。上述引理表示，当两枚硬币出现正面的概率很接近时，它们出现某个结果的概率也是很接近的。
我们可以用它推导出一个很有意思的结果。
假如说我们拥有 $\mathtt{RC}_{\epsilon}$ 和 $\mathtt{RC}_0$ 这两枚硬币的其中一个，我们想要保证能在 $T$ 次投掷后以 99% 的概率把它分辨出来到底是哪一个，这个 $T$ 至少需要多大？
Remark
假如我们有独立的数据点 $x_1, \dots, x_n \in \Omega$，它们是从某个未知分布 $P^\ast$ 抽取得到。进一步，假如我们知道 $P^\ast$ 要么是 $P$ 要么是 $Q$，我们想通过数据来判断哪个可能性更大一些，一种方法是通过对数似然比 $$ \Lambda = \prod_{i=1}^n \frac{P(x_i)}{Q(x_i)} \quad \Rightarrow \quad \hat{\Lambda}_n = \frac{1}{n} \sum_{i=1}^n \log \frac{P(x_i)}{Q(x_i)} $$ 计算可得： $$ \mathbb{E}[\hat{\Lambda}_n] = \text{KL}(P^\ast , Q) - \text{KL}(P^\ast, P) $$
设 $P, Q$ 是两个概率测度，$A \subset \Omega$ 是一个事件
Pinsker’s inequality $$ |P(A) - Q(A)| \leq \sqrt{\frac{\text{KL}(P, Q)}{2}} $$ Bretagnolle–Huber inequality $$ |P(A) - Q(A)| \leq \sqrt{1 - e^{-\text{KL}(P, Q)}} \leq 1 - \frac{1}{2} e^{-\text{KL}(P, Q)} $$ 另一种形式是： $$ P(A) + Q(A^c) \geq \frac{1}{2} e^{-\text{KL}(P, Q)} $$ 这两个不等式说明，当两个概率测度很接近的时候，相同事件发生的概率也会很接近，接近程度与 KL 散度有关系。
对连续分布，其 KL 散度定义的思路是离散化： $$ \mathrm{KL}(P, Q)=\sup _{N \in \mathbb{N}^{+}} \sup _X \mathrm{KL}\left(P_X, Q_X\right), $$ $N$ 代表把样本空间 $\Omega$ 划分成 $N$ 部分，$P_X(A) = P(X \in A)$ 是一个基于划分的新测度，是一个离散的概率测度，由此可以定义连续分布的 KL 散度。
$$ \begin{aligned} \mathbb{E}_\nu & {\left[\log \frac{\mathrm{d} \mathbb{P}_\nu}{\mathrm{d} \mathbb{P}_{\nu^{\prime}}}\left(A_1, X_1, \ldots, A_n, X_n\right)\right]=\sum_{t=1}^n \mathbb{E}_\nu\left[\log \frac{p_{A_t}\left(X_t\right)}{p_{A_t}^{\prime}\left(X_t\right)}\right] } \\ &=\sum_{t=1}^n \mathbb{E}_\nu\left[\mathrm{D}\left(P_{A_t}, P_{A_t}^{\prime}\right)\right]=\sum_{i=1}^k \mathbb{E}_\nu\left[\sum_{t=1}^n \mathbb{I}\left\{A_t=i\right\} \mathrm{D}\left(P_{A_t}, P_{A_t}^{\prime}\right)\right] \\ &=\sum_{i=1}^k \mathbb{E}_\nu\left[T_i(n)\right] \mathrm{D}\left(P_i, P_i^{\prime}\right) . \end{aligned} $$