Shawn

算法

$A_t=\operatorname{argmax}_i\left(\hat{\mu}_i(t-1)+\sqrt{\frac{2 \log f(t)}{T_i(t-1)}}\right)$

即把UCB算法中的 $1/\delta$改写成 $f(t)=1+t \log ^{2}(t)$

引理一

对于 $X_{i}-\mu$服从 $1-\text{subgaussian}$分布，$\hat{\mu}_{t}=\frac{1}{t} \sum_{s=1}^{t} X_{s}$，我们引入

$\kappa=\sum_{t=1}^n \mathbb{I}\left\{\hat{\mu}_t+\sqrt{\frac{2 a}{t}} \geqslant \varepsilon\right\}$

以及

$\kappa^{\prime}=u+\sum_{t=\lceil u\rceil}^n \mathbb{I}\left\{\hat{\mu}_t+\sqrt{\frac{2 a}{t}} \geqslant \varepsilon\right\}, \quad u=2 a \varepsilon^{-2}$

有

$\mathbb{E}[\kappa] \leqslant \mathbb{E}\left[\kappa^{\prime}\right] \leqslant 1+\frac{2}{\varepsilon^2}(a+\sqrt{\pi a}+1)$

一方面，

假设 $t\leqslant u$时，$\mathbb{I}\left\{\hat{\mu}_{t}+\sqrt{\frac{2 a}{t}} \geqslant \varepsilon\right\}$所代表的事件发生，当 $t>u$时，要满足 $\hat{\mu}_{t}+\sqrt{\frac{2 a}{t}} < \varepsilon$

，故 $u=2a\varepsilon^{-2}$，可以得出 $\mathbb{E}[\kappa] \leqslant \mathbb{E}\left[\kappa^{\prime}\right]$.

另一方面，

$\begin{aligned} \mathbb{E}[\kappa] & \leqslant \mathbb{E}\left[\kappa^{\prime}\right]=u+\sum_{t=\lceil u\rceil}^n \mathbb{P}\left(\hat{\mu}_t+\sqrt{\frac{2 a}{t}} \geqslant \varepsilon\right) \\ & \leqslant u+\sum_{t=\lceil u\rceil}^n \exp \left(-\frac{t\left(\varepsilon-\sqrt{\frac{2 a}{t}}\right)^2}{2}\right) \\ & \leqslant 1+u+\int_u^{\infty} \exp \left(-\frac{t\left(\varepsilon-\sqrt{\frac{2 a}{t}}\right)^2}{2}\right) d t=1+\frac{2}{\varepsilon^2}(a+\sqrt{\pi a}+1) \end{aligned}$

倒数第二步利用ETC算法引理三，最后一步转化成积分令 $s=\varepsilon \sqrt{t}-\sqrt{2 a}$可以计算得出

Regret分析

$R_n \leqslant \sum_{i: \Delta_i>0} \inf _{\varepsilon \in\left(0, \Delta_i\right)} \Delta_i\left(1+\frac{5}{\varepsilon^2}+\frac{2(\log f(n)+\sqrt{\pi \log f(n)}+1)}{\left(\Delta_i-\varepsilon\right)^2}\right)$

根据 $A=(A\cap B)\cup (A\cap\bar{B})$

$\begin{aligned} T_i(n)=\sum_{t=1}^n \mathbb{I}\left\{A_t=\right. & i\} \leqslant \sum_{t=1}^n \mathbb{I}\left\{\hat{\mu}_1(t-1)+\sqrt{\frac{2 \log f(t)}{T_1(t-1)}} \leqslant \mu_1-\varepsilon\right\} \\ & +\sum_{t=1}^n \mathbb{I}\left\{\hat{\mu}_i(t-1)+\sqrt{\frac{2 \log f(t)}{T_i(t-1)}} \geqslant \mu_1-\varepsilon \text { and } A_t=i\right\} \end{aligned}$

首先考虑第一项

$\begin{aligned} & \mathbb{E}\left[\sum_{t=1}^n \mathbb{I}\left\{\hat{\mu}_1(t-1)+\sqrt{\frac{2 \log f(t)}{T_1(t-1)}} \leqslant \mu_1-\varepsilon\right\}\right] \\ & \leqslant \sum_{t=1}^n \sum_{s=1}^n \mathbb{P}\left(\hat{\mu}_{1 s}+\sqrt{\frac{2 \log f(t)}{s}} \leqslant \mu_1-\varepsilon\right) \quad\left(s=T_1(t-1)\right) \\ & \leqslant \sum_{t=1}^n \sum_{s=1}^n \exp \left(-\frac{s\left(\sqrt{\frac{2 \log f(t)}{s}}+\varepsilon\right)^2}{2}\right) \\ & \leqslant \sum_{t=1}^n \frac{1}{f(t)} \sum_{s=1}^n \exp \left(-\frac{s \varepsilon^2}{2}\right) \\ & \leqslant \frac{5}{\varepsilon^2} \end{aligned}$

倒数第三步利用ETC算法引理三，倒数第二步可以拆出一个 $1/f(t)$和 $\exp \left(-\frac{s \varepsilon^{2}}{2}\right)$

对于最后一步

$\begin{aligned} & \sum_{t=1}^n \frac{1}{f(t)} \sum_{s=1}^n \exp \left(-\frac{s \varepsilon^2}{2}\right) \\ & \leqslant \sum_{t=1}^n \frac{1}{f(t)} \frac{2}{\varepsilon^2}=\frac{2}{\varepsilon^2} \sum_{t=1}^n \frac{1}{t \log ^2 t+1} \\ & \leqslant \frac{2}{\varepsilon^2}\left(1+\sum_{t=1}^n \frac{1}{t \log ^2 t}\right) \\ & \leqslant \frac{2}{\varepsilon^2}\left(1+1+\int_2^n \frac{1}{t \log ^2 t} d t\right) \\ & \leqslant \frac{5}{\varepsilon^2} \end{aligned}$

再考虑第二项

$\begin{aligned} & \mathbb{E}\left[\sum_{t=1}^n \mathbb{I}\left\{\hat{\mu}_i(t-1)+\sqrt{\frac{2 \log f(t)}{T_i(t-1)}} \geqslant \mu_1-\varepsilon \text { and } A_t=i\right\}\right] \\ & \leqslant \mathbb{E}\left[\sum_{t=1}^n \mathbb{I}\left\{\hat{\mu}_i(t-1)+\sqrt{\frac{2 \log f(n)}{T_i(t-1)}} \geqslant \mu_1-\varepsilon \text { and } A_t=i\right\}\right] \\ & \leqslant \mathbb{E}\left[\sum_{s=1}^n \mathbb{I}\left\{\hat{\mu}_{i s}+\sqrt{\frac{2 \log f(n)}{s}} \geqslant \mu_1-\varepsilon\right\}\right] \\ & =\mathbb{E}\left[\sum_{s=1}^n \mathbb{I}\left\{\hat{\mu}_{i s}-\mu_i+\sqrt{\frac{2 \log f(n)}{s}} \geqslant \Delta_i-\varepsilon\right\}\right] \\ & \leqslant 1+\frac{2}{\left(\Delta_i-\varepsilon\right)^2}(\log f(n)+\sqrt{\pi \log f(n)}+1) \end{aligned}$

将两项结合在一起便可以得出结论

如果对Regret上界取极限可得

$\limsup _{n \rightarrow \infty} \frac{R_{n}}{\log (n)} \leqslant \sum_{i: \Delta_{i}>0} \frac{2}{\Delta_{i}}$

运行结果

与ETC和UCB算法的对比