Online Learning 4 ε-greedy & UCB

主要介绍$\epsilon$-greedy算法和UCB算法以及他们的regret 证明。非常重要的是介绍了一个很普适的证明框架(UCB 分析1)

算法思想

简单的greedy算法：

for $t=1, \cdots, k$ pull arm $t$

for $t=k + 1, \ldots, n$, pull $argmax_{i} $$ $$ \hat{\mu}_{i}(t-1)$

每个arm实验一次，然后只拉最好的arm（边拉边更新均值）,但这显然是会有问题的。有可能最好的arm因为一开始的realize的reward不好导致永远不会再被拉到。

所以要设计一个算法让我们在后期的“exploit”阶段，也会保持explore的可能性。

算法描述

Input: $\varepsilon_{1} \varepsilon_{2} \ldots \varepsilon_{n}$

if $t\in \{1, \ldots, k\}$, pull arm $t$

if $t\in \{k+1, \ldots, n\}$ pull arm $A_t= \begin{cases}\operatorname{argmax}_i \hat{\mu}_i(t-1) & \text { w.p. } 1-\varepsilon_t \\ i & \text { w.p. } \frac{\varepsilon_t}{k}\end{cases}$

在后期也会保持一个$\epsilon_t$ 的概率尝试其他arm。

why $\epsilon_t$ not $\epsilon$ ? 可以证得，当取常数$\epsilon$ 得时候regret会趋于无穷。

Regret 分析

若取$\epsilon \sim \frac{1}{t}$ then:

Instance Independent $\sim O(\sqrt{n})$ (只知道$\mu_1,\mu_2\cdots\mu_k$取值空间$\sim [0,1]$)

Instance Dependent $\sim O(\log n)$ （知道$\mu_1,\mu_2\cdots\mu_k$ 是哪些数，但不知道各自对应哪个arm）

Upper Confidence Bound Algorithm

著名的上置信度边界（UCB）算法，它克服了ETC的策略的所有限制，包括需要知道水平线和次优差距。该算法有许多不同的形式，取决于对噪声分布的假设。

算法思想

UCB算法给人们的一个启示是“永远对未知保持乐观态度”

这样做的直观原因是，当乐观地行事时，会发生两种情况之一。

• 要么乐观是合理的，在这种情况下，学习者的行为是最优的。
• 要么乐观是不合理的。在这一情况下，learner采取了他们认为可能会带来大量奖励的行动，但事实上却并不是最优的。如果这种情况发生得足够频繁，那么学习者就会知道这个行动的真正回报并不最优，因此在未来不会选择它。

算法描述

• 计算upper bound：

Recall that if $X_{1}, X_{2}, \dots, X_{n}$ are independent and 1-subgaussian (which means that $\mathbb{E}[X_{i}]=0$ and $Var(X_i) = 1$ ) and $\hat{\mu}=\sum_{t=1}^{n} X_{t} / n$, then by chernoff bound of gaussian:

$$\mathbb{P}(\hat{\mu} \geq \varepsilon) \leq \exp (-n \varepsilon^{2} / 2)$$

Equating the right-hand side with $\delta$ and solving for $\varepsilon$ leads to an estimate of UCB at period t :

$$\hat{\mu}_{i}^{UCB}(t) = \hat{\mu}_{i}(t-1)+\sqrt{\frac{2}{T_{i}(t-1)} \log (\frac{1}{\delta})}$$

此时$\mu_i<\hat{\mu}_{i}^{UCB}(t)$ with probability $1-\delta$

• 选择有最大置信区间上确界的arm

\begin{equation} A_{t}= \begin{cases}\operatorname{argmax}_{i}(\hat{\mu}_{i}(t-1)+\sqrt{\frac{2 \log \frac{1}{\delta}}{T_{i}(t-1)}}), & \text { if } t>K \\ t, & \text { otherwise }\end{cases} \end{equation}

Besides the slightly vague "optimism guarantees optimality or learning" intuition we gave before, it is worth exploring other intuitions for this choice of index. At a very basic level, we should explore arms more often if they are:

• (a) promising (in that $\hat{\mu}_{i}(t-1)$ is large)
• (b) not well explored ( $T_{i}(t-1)$ is small).

---

在开始介绍证法之前，先总结一下proof sketch：

• 定义good event ($G$)和bad event($G^c$)
• 把regret 分解为在good event 下的regret 和 bad event 下的regret

Regret = Regret | Good Event + Regret | Bad Event

\begin{equation} \begin{aligned} R_{n} &=\sum_{t=1}^{n} E[\mu_{1}-\mu_{A_{t}}] \\ &=\sum_{t=1}^{n} E[(\mu_{1}-\mu_{A_{t}}) 1_{G}]+\sum_{t=1}^{n} E[(\mu_{1}-\mu_{A_{t}}) 1_{G^{c}}] \end{aligned} \end{equation}

• 证明good event 下 regret 很小，bad event 下发生的概率很小

这套证明思路非常常见，关键的技巧是如何构造“good event”

Regret Analysis （1）

定义好事件为真实的arm 取值落在置信区间内：

$G=\{\hat{\mu}_{i}(t-1)-\sqrt{\frac{2 \log ({\frac{1}{\sigma}})}{T_{i}(t-1)}} \leqslant \mu_{i} \leqslant \hat{\mu}_{i}(t-1)+\sqrt{\frac{2 \log ({\frac{1}{\sigma}})}{T_{i}(t-1)}}, \forall t, i\}$

在好事件下的regret

我们得到在好事件下收益差距不会过大：

$\mu_{1}-\mu_{A_{t}} \leq 2 \sqrt{2 \log (\frac{1}{\sigma})} \sqrt{\frac{1}{T_{A_{t}}(t-1)}}$

We know $T_{i}(t-1) \leq t-1$

$$\sum_{t=1}^{n} E[\sqrt{\frac{1}{T_{A_{t}}(t-1)}}] \leqslant \sum_{t=1}^{n} \sum_{i=1}^{k} \sqrt{\frac{1}{t}} \sim k \sqrt{n}$$

这一步放缩过大，每个arm i拉的次数小于t次，直接都放缩到t次

Regret | Good Event $\leq$$\sum_{t=1}^{n} 2 \sqrt{2 \log (\frac{1}{\delta})} E[\sqrt{\frac{1}{T_{A_{t}}(t-1)}}]\sim2 \sqrt{2 \log \frac{1}{\sigma }} k \sqrt{n}$

在坏事件下的概率

坏事件下要尝试证明，坏事件概率不会过大

Regret | Bad Event $\leqslant \sum_{t=1}^{n} E[(\mu_{1}-\mu_{A t}) 1_{G^c} ] \leq \sum_{t=1}^{n} P(G^{c})=n P(G^{c})$

为了方便讨论，我们denote一下每个arm的生成序列(每个arm都考虑到n期)

arm 1	$X_{11} $	$X_{21}$	…	$X_{n1}$
arm 2	$X_{12}$	$X_{22}$	…	$X_{n2}$
…
arm k	$X_{1k} $	$X_{2k}$	…	$X_{nk}$

Let $E_{t_{i}}=|\frac{\sum_{s=1}^{t} X _{si}}{t}-\mu_{i}| \leq \sqrt{\frac{2 \log (\frac{1}{\sigma})}{t}}$

E 单独定义每个arm的good event

if $\bigcap_{t=1}^{n} \bigcap_{i=1}^{k} E_{ti}$ holds, then $G$ holds（E取交集是一个更强的限制）

$$\begin{aligned}\Rightarrow \quad \bigcap_{t}^{k} \bigcap_{i}^{n} E_{t i} \subset G \\\Rightarrow \quad G_{i}^{c} \subset \bigcup_{i=1}^{n} \bigcup_{i=1}^{k} E_{t i}^{c}\end{aligned}$$

且根据置信区间的定义我们可以知道 $E_{t i}^{c}\leq \delta$ 所以 $P(G^c) \leq nk\delta$

好坏加和

好坏regret 加和 $\leq 2 \sqrt{2 \log (\frac{1}{\delta})} k \sqrt{n}+n^{2} k \delta$

令$\delta \sim 1/n^2$ $R_{n} \leq 4 \sqrt{\log n} k \sqrt{n}+k$

Regret 分析2 （bound收紧到$\sqrt{kn}$ ）

小咕🐦