Shawn

算法

$\begin{aligned} & \mathrm{UCB}_i(t-1, \delta)= \begin{cases}\infty & \text { if } T_i(t-1)=0 \\ \hat{\mu}_i(t-1)+\sqrt{\frac{2 \log (1 / \delta)}{T_i(t-1)}} & \text { otherwise }\end{cases} \end{aligned}$

$A_t=\operatorname{argmax}_i \mathrm{UCB}_i(t-1, \delta)$

当 $\hat{\mu}_i(t-1)$很大或 $T_i(t-1)$很小时，算法在直觉上都能满足

引理一

$\mathbb{P}\left(\mu \geqslant \hat{\mu}+\sqrt{\frac{2 \log (1 / \delta)}{n}}\right) \leqslant \delta \quad \text { for all } \delta \in(0,1)$

对于 $X_{i}-\mu$服从 $\sigma-\text{subgaussian}$分布

$\mathbb{P}(\hat{\mu} \geqslant \mu+\epsilon) \leqslant e^{-\frac{n \epsilon^2}{2 \sigma^2}} \quad \text { and } \quad \mathbb{P}(\hat{\mu} \leqslant \mu-\epsilon) \leqslant e^{-\frac{n \epsilon^2}{2 \sigma^2}}$

（详见ETC算法的引理三证明）

对于上式，令 $\delta=e^{-\frac{n \epsilon^2}{2 \sigma^2}}$ 则 $\epsilon=\sqrt{\frac{2 \log (1 / \delta)}{n}}$

Regret分析

假设 $\mu_{1}=\mu^{*}$

$R_n=\sum_{i=1}^k \Delta_i \mathbb{E}\left[T_i(n)\right]$

设定 $G_{i}$为一个“好事件”

$G_i=\left\{\mu_1<\min _{t \in[n]} \mathrm{UCB}_1(t, \delta)\right\} \cap\left\{\hat{\mu}_{i u_i}+\sqrt{\frac{2}{u_i} \log \left(\frac{1}{\delta}\right)}<\mu_1\right\}$

可以得到“好事件”发生的两个性质

$T_i(n) \leqslant u_i$

假设在时刻 $t$，满足 $T_i(t-1)=u_i$ 和 $A_t=i$

$\begin{aligned} \mathrm{UCB}_i(t-1, \delta) & =\hat{\mu}_i(t-1)+\sqrt{\frac{2 \log (1 / \delta)}{T_i(t-1)}} \\ & =\hat{\mu}_{i u_i}+\sqrt{\frac{2 \log (1 / \delta)}{u_i}} \\ & <\mu_1 \\ & <\mathrm{UCB}_1(t-1, \delta) \end{aligned}$

故 $A_t=\operatorname{argmax}_j \mathrm{UCB}_j(t-1, \delta)=i$

以及

$G_{i}^{c}\text{ 为小概率事件}$

$G_i^c=\left\{\mu_1 \geqslant \min _{t \in[n]} \mathrm{UCB}_1(t, \delta)\right\} \cup\left\{\hat{\mu}_{i u_i}+\sqrt{\frac{2}{u_i} \log \left(\frac{1}{\delta}\right)} \geqslant \mu_1\right\}$

对于左式

$\begin{aligned} \mathbb{P}\left(\mu_1 \geqslant \min _{t \in[n]} \mathrm{UCB}_1(t, \delta)\right) & \leqslant \mathbb{P}\left(\bigcup_{s \in[n]}\left\{\mu_1 \geqslant \hat{\mu}_{1 s}+\sqrt{\frac{2 \log (1 / \delta)}{s}}\right\}\right) \\ & \leqslant \sum_{s=1}^n \mathbb{P}\left(\mu_1 \geqslant \hat{\mu}_{1 s}+\sqrt{\frac{2 \log (1 / \delta)}{s}}\right) \\ & \leqslant n \delta \end{aligned}$

对于右式，$\mu_1-\mu_i=\Delta_i$

$\begin{aligned} \mathbb{P}\left(\hat{\mu}_{i u_i}+\sqrt{\left.\frac{2 \log (1 / \delta)}{u_i} \geqslant \mu_1\right)}\right. & =\mathbb{P}\left(\hat{\mu}_{i u_i}-\mu_i \geqslant \Delta_i-\sqrt{\frac{2 \log (1 / \delta)}{u_i}}\right) \\ & \leqslant \mathbb{P}\left(\hat{\mu}_{i u_i}-\mu_i \geqslant c \Delta_i\right) \\ & \leqslant \exp \left(-\frac{u_i c^2 \Delta_i^2}{2}\right) \end{aligned}$

注意 $0<c<1$

对于最后一步，$X \sim \sigma \text {-subgaussian }$

$\mathbb{P}(X \geqslant \varepsilon) \leqslant \exp \left(-\frac{\varepsilon^2}{2 \sigma^2}\right)$

结合起来可得

$\mathbb{P}\left(G_i^c\right) \leq n \delta+\exp \left(-\frac{u_i c^2 \Delta_i^2}{2}\right)$

根据“好事情”的两个性质，我们可以得到

$\begin{aligned} \mathbb{E}\left[T_i(n)\right] & \leqslant \mathbb{E}\left[\mathbb{I}\left\{G_i\right\} T_i(n)\right]+\mathbb{E}\left[\mathbb{I}\left\{G_i^c\right\} T_i(n)\right] \\ & \leqslant u_i+n\left(n \delta+\exp \left(-\frac{u_i c^2 \Delta_i^2}{2}\right)\right) \end{aligned}$

不妨取 $u_i=\left\lceil\frac{2 \log (1 / \delta)}{(1-c)^2 \Delta_i^2}\right\rceil, \quad \delta=1 / n^2$ 以及 $c=1 / 2$

$\begin{aligned} \mathbb{E}\left[T_i(n)\right] & \leqslant u_i+n\left(n \delta+\exp \left(-\frac{u_i c^2 \Delta_i^2}{2}\right)\right) \\ & \leqslant u_i+1+n^{1-2 c^2 /(1-c)^2}=\left\lceil\frac{2 \log \left(n^2\right)}{(1-c)^2 \Delta_i^2}\right\rceil+1+n^{1-2 c^2 /(1-c)^2} \\ & \leqslant 3+\frac{16 \log (n)}{\Delta_i^2} \end{aligned}$

Regret的上界为

$\begin{aligned} R_n & =\sum_{i=1}^k \Delta_i \mathbb{E}\left[T_i(n)\right]=\sum_{i: \Delta_i<\Delta} \Delta_i \mathbb{E}\left[T_i(n)\right]+\sum_{i: \Delta_i \geqslant \Delta} \Delta_i \mathbb{E}\left[T_i(n)\right] \\ & \leqslant n \Delta+\sum_{i: \Delta_i \geqslant \Delta}\left(3 \Delta_i+\frac{16 \log (n)}{\Delta_i}\right) \leqslant n \Delta+\frac{16 k \log (n)}{\Delta}+3 \sum_i \Delta_i \\ & \leqslant 8 \sqrt{n k \log (n)}+3 \sum_{i=1}^k \Delta_i, \end{aligned}$

运行结果