Online Learning 5 Lower Bound Analysis

why lower bound ?

在之前的UCB / greedy等算法中，我们实际上关注的是 “upper bound”， 也即“算法最坏也不会比$\sqrt{nk}$ 差“（以UCB 为例）。但很自然的会有一个问题是：$\sqrt{nk}$ 足够好了么？ 会不会有regret为常数的算法？

lower bound analysis 解决的就是这一问题，我们通过证明问题的lower bound 来展示我们的算法足够优秀

准备工作

lower bound 的分析 根源上类似于传统统计学中假设检验的问题。 假设检验中“最好的检验rule”就类似于在找“最棒的bandits algorithm”。

例子：

$X_1 X_2 \cdots X_n iid sample$ , 判断假设（1）是否为真

(1) $X_1 \sim N(0,1)$

(2) $X_1 \sim N(\Delta, 1) \quad \Delta>0$

Rule : $\{x_1, \cdots, x_n\} \rightarrow\{0, \Delta\}$

考虑一个naive 的rule ： 若$\bar x > \Delta /2$ 则判断为（2），反之为（1）

Type I error 概率（real mean为0但sample mean$> \Delta /2$） :

$$\quad P_{0}(\bar{x}_{n} \geqslant \frac{\Delta}{2}) \sim \exp (-\frac{n \Delta^{2}}{8})$$

Type II error 概率(real mean为$\Delta$但sample mean$< \Delta /2$):

$$\quad P_{\Delta}(\bar{x}_{n} \leq \frac{\Delta}{2}) \sim \exp (-\frac{n \Delta^{2}}{8})$$

I + II 概率合: $\sim 2 \exp (-\frac{n \Delta^{2}}{8})$

有没有rule 能实现比这个更小的error？ or 最棒的rule 能实现的error 概率是多少？

Def : Total Variance (TV)

For probability measures P andQ

$$\| P-.Q|_{T V}:=\sup _{A}|P(A)-Q(A)|$$

Total Variance 衡量的是 “2个分布间的距离”

Theorem: Le Cam’s Inequality

Le Cam 不等式把判断出错的概率 与 分布间的距离，建立了联系。

For 2 distributions $P_1, P_2$ . Let $v=\{1,2\}$ with probability $\frac{1}{2}$, and $X \sim P_v$

Let $\psi: \Omega \rightarrow \{1,2\}$

We have:

\begin{align} P(\psi(x) \neq v)&=\frac{1}{2} P_{1}(\psi(x) \neq 1)+\frac{1}{2} P_{2}(\psi(x) \neq 2)\\&\geq\frac{1}{2}(1-|| P_{1}-P_{2} \|_{T V})\end {align}

• Proof:

  $\text {let } A=\{\psi(x)=1\}$

  $$\begin{aligned} & \mathrm{P}_1(\psi(\mathrm{x}) \neq 1)+\mathrm{P}_2(\psi(\mathrm{x}) \neq 2)=\mathrm{P}_1\left(\mathrm{~A}^{\mathrm{c}}\right)+\mathrm{P}_2(\mathrm{~A}) \\ =& 1-\mathrm{P}_1(\mathrm{~A})+\mathrm{P}_2(\mathrm{~A}) \\ =& 1-\left(\mathrm{P}_1(\mathrm{~A})-\mathrm{P}_2(\mathrm{~A})\right) \\ \geq & 1-\sup _{\mathrm{A}}\left|\mathrm{P}_1(\mathrm{~A})-\mathrm{P}_2(\mathrm{~A})\right|=1-\left\|\mathrm{P}_1-\mathrm{P}_2\right\|_{\mathrm{Tv}} \end{aligned}$$

KL Divergence

TV的定义很棒，但在计算上有较大的intractability。因此我们提出KL- Divergence作为替代。

$KL(P, Q)=\sum_{x} P(x) \log \frac{P(x)}{Q(x)}=E_{P}[\log \frac{P(x)}{Q(x)}]$

Properties of KL-Divergence:

基础性质：

1. $K(P, Q) \geqslant 0,(\text{and} K(P, Q) =0 \Leftrightarrow P=Q)$
2. It is not a distance; no triangle inequality
3. It is not symmetric

加和性：

$P=P_1 \times P_2 \times \cdots \times P_{n} \quad$ and $Q=Q_1 \times Q_2 \cdots Q_{n}$

We have $K L(P, Q)=\sum_{i=1}^{n} K L(P_{i}, Q_{i})$

Pinker’s Inequality:

建立了total variance 与kl divergence 之间的联系

$2\|P-Q\|_{T V}^{2} \leq K L(P, Q)$

Condition KL-Divergence

$K L(P(X, Y), Q(X Y))=K L(P(X), Q(X))+E_{P(x)}[K(P(Y \mid X), Q(Y \mid X))]$

对于特殊分布

(1) If $P_1$ and $P_2 \sim$ Bermoulli with mean $\mu_1 \mu_2 \quad KL(P_1, P_2)=2(\mu_1-\mu_2)^{2}$ (2) if $P_1 \sim N(\mu_1, 1), P_2 \sim N(\mu_2, 1)$

$$KL(P_{1}, P_{2})=(\mu_{1}-\mu_{2})^{2} / 2$$

Back To Lower Bound

要解决的问题是：

$\max _{v \in \varepsilon} R_{n}(v, \pi) \geqslant \sqrt{nk} \quad \forall \pi$

直接证明“max $v$” 是不好下手的，一般的方法为：

1. 构造一个特殊的 set $\{v_1,v_2 \dots v_k\}$
2. 证明即便只是在这个set上取环境，regret 也是很大的

Lemma 1:

$K L(P_{v}, P_{v^{\prime}})=\sum_{i=1}^{K} E_{v}[T_{i}(n)] K L(P_{v_{i}}, P_{v^{\prime} i})$

对于2个不同的environment v，其KL可以拆为：

每个arm被拉的次数 * 2个环境在这一arm上的distribution的KL-divergence

直观上非常好理解，证明如下：

• Proof:

  $$\begin{aligned} &K L(P_{v}, P_{v}) \\=& E_{P_{v}}[\log \frac{P_{v}(A_{1}, x_{1}, A_{2}, x_{2}, \ldots, A_{n}, x_{n})}{P_{v}(A_{1}, x_{1}, A_{2}, X_{2}, \ldots, A_{n}, x_{n})}] \end{aligned}$$

  $\operatorname{P}_v(a_1, x_1, \cdots, a_{n}, x_{n})=\pi_1(a_1) P_{v,a_1}(x_1) \pi_2(a_1, x_1) P_{v, a_2}(x_2)$

  因此

  $\log \frac{P_{v}(a_1 x_1, \ldots, a_{n} x_{n})}{P_{v^{\prime}}(a_1 x_1, \ldots, a_{n} x_{n})}=\log \frac{\prod_{t=1}^{n} \pi_{t}(a_{t} \mid a_1, x_{1,}, \ldots, a_{t-1}, x_{t-1}) P_{v a_{t}}(x_{t})}{\prod_{t=1}^{n} \pi_{t}(a_{t} \mid a_1, x_{1,}, \ldots, a_{t-1}, x_{t-1}) P_{v^{'} a_{t}}(x_{t})} =\sum_{t=1}^{n} \log \frac{P_{v} a_{t}(X_{t})}{P_{v^{\prime}} a_{t}(X_{t})}$

  $$\begin{aligned}&K L(P_{v}, P_{v^{\prime}})=E_{P_{v}}(\sum_{t=1}^{n} \log \frac{P_{v} \cdot A_{t}(X_{t})}{P_{v^{\prime} \cdot A_{t}}(X_{t})})\\&=\sum_{t=1}^{n} E_{P_{v}}[E[\log \frac{P_{v A_{t}}(x_{t})}{P_{v’ A_t}(x_{t})} \mid A_{t}]]\\&=\sum_{t=1}^{n} E_{P_{v}}[K L(P_{v} A_{t}, P_{v} A_{t})]\\&=\sum_{i=1}^{n} E_{p_{v}}[\sum_{i=1}^{k} 1(A_{t}=i) K L(P_{v, i}, P_{v^{\prime}, i})]\\&=\sum_{i=1}^{k} E_{P_{v}}[T_{i}(n)] K L(P_{v i}, P_{v^{\prime} i}) \end{aligned}$$

Proof of Lower Bound:

正如前文所说，首先需要构造一个environments set，我们要证明的是：

即便只是在这个sets上regret就要大于 $\sqrt{nk}$（lower bound）

$V_0$ - $V_k$ 共计k+1个 environments, 其中第i个环境下arm i的reward 均值为$\Delta$ 其他arm均值为0

$\begin{aligned}&V^{(0)}:\mu^{(0)}=(0 \ldots 0) \\&V^{(1)}: \mu^{(1)}=(\Delta, 0, \ldots 0) \\&V^{(2)} :\mu^{(2)}=(0, \Delta, 0 \ldots 0) \\&\vdots \\&V^{(k)}: \mu^{(k)}=(0, \ldots 0, \Delta)\end{aligned}$

• Proof:

  第一步： pinker inequality

  第二步： lemma 1

  第三步：根据构造，只有arm i上的分布是有区别的，其KL-divergence根据property of KL divergence 可以显式地写出来

  $$\begin{aligned}E_{i}[T_{i}(n)]-E_{0}[T_{i}(n)] &\leq n \sqrt{\frac{1}{2} KL(P_{0} \cdot P_{i})}\\&\leq n \sqrt{\frac{1}{2} \sum_{j=1}^{k} E[T_{j}(n)] KL(\mu_{j}^{(0)}, \mu_{j}^{(i)})} \\ &\leq n \sqrt{\frac{1}{2} E_{q}[T_{i}(n)] \frac{\Delta^{2}}{2}} \\ &=\frac{\Delta n}{2} \sqrt{E[T_{i}(n)]}\end{aligned}$$

  第2步： $E_0$求和为n（因为全是0，必对称）+ jensen‘s inequality

  第3步：$E_0$求和为n（因为全是0，必对称）

  $$\begin{aligned}\sum_{i=1}^{k} E_{i}[T_{i}(n)] & \leq \sum_{i=1}^{k} E_{0}[T_{i}(n)]+\frac{n \Delta}{2} \sum_{i=1}^{k} \sqrt{E_{0}[T_{i}(n)]} \\& \leq n+\frac{n \Delta}{2} \sqrt{k \sum_{i=1}^{k} E_{0}[T_{i}(n)]} \\& \leq n+\frac{n \Delta}{2} \sqrt{k n}\end{aligned}$$