多臂赌博机2

这一节我们来了解下多臂赌博机问题的提出和理论基础,最后讨论下UCB系列策略.当然,这里的多臂赌博机问题是随机式的. 随机式多臂赌博机的问题描述就不在这里重复了,可以参考上一节

理论

问题的证明

Lai & Robbins在1985年论证了对于某些特定的分布(只有一个实参的分布),存在有策略使得它的累积遗憾的期望服从$\log n$增长.同时也证明了对于任何策略任何次优臂,总有$ \mathbb{E}[T_j(n)]\ge (\ln n)/D(p_j||p^*)$, 即累积遗憾的期望存在有一个下界.

当然他们也提出了一些针对特定分布的策略,虽然结果较好(对数增长的常数项较小),但是由于计算复杂度和特定分布的限制,并不具有较好的实用性.

改进

为了克服上面的缺点, Agrawal提出了基于采样平均值作为上部信心指数(upper confidence index)的多臂赌博机策略,它将各臂采样平均值的某些函数作为该臂优越性的指标,然后总选取最优越的臂. 同时证明结果显示它们同样服从对数增长,只不过对数增长的常数项较大了些.

UCB策略

UCB1

该策略已经在上一节讨论过了,这里只列举下算法.

UCB1算法: 在前$K$轮,每臂各选择一次, 在$t=K,K+1…$轮:
选择指数$I_i$最大的臂,其中$I_i=\bar{x}_i+\sqrt{2\frac{\log t}{n_i}}$,其中$\bar{x}_i$是均值,$n_i$是臂$i$当前累积被选择的次数
记录获得的奖励,并更新$\bar{x}_i$和$n_i$

UCB2

UCB2算法在前$K$轮,每臂各选择一次,并$r_i=0$
选出指数$I_i$最大的臂,其中$I_i=\bar{x}i+a{n,r_i}$,其中 $$ a_{n,r_i}=\sqrt{\frac{(1+\alpha)\ln (en/\tau (r))}{2\tau (r)}} $$ 其中$\tau (r)=\lceil (1+\alpha)^r\rceil$
选择该臂$\tau (r_i+1)-\tau (r_i)$次
$r_i++$

定理: 如果$n\ge \max \frac{1}{2\Delta_i^2}$,则总的遗憾期望不超过 $$ \sum_{i:\mu_i \lt \mu^*}(\frac{(1+\alpha)(1+4\alpha)\ln (2e\Delta_i^2 n)}{2\Delta_i}+\frac{c_\alpha}{\Delta_i}) $$

e-Greedy策略

在多臂赌博机问题中贪婪算法并不适用,但是,可以改良一下,如Sutton &Barto在1998年提出的$\epsilon -greedy$算法,它简单地以$1-\epsilon$的概率选择最大的采样均值的臂,而以$\epsilon$的概率去随机选择臂. 但是,它并不是对数增长的. 它需要人为地设定一个停止规则,而且,这个停止规则必然和各臂期望有关.

一个好的改良叫做$\epsilon_n -greedy$算法.

定义参数$c>0$, $d: 0\lt d \le \min \Delta_i$和$\epsilon_n =\min (1,\frac{cK}{d^2 n})$

$\epsilon_n -greedy$算法在前$K$轮,每臂各选择一次,
以$1-\epsilon_n$的概率选择最大的采样均值的臂,而以$\epsilon_n$的概率去随机选择臂.
更新$\epsilon_n$

虽然该方法在仿真中能得到很好的结果,但实际情况是各臂期望不可知,无法确定较好的$d$,所以只能设置一个较大的$c$(其实c,d可以合并成同一参数).

一般来说,如果$d$满足条件,$c>5$足够保证对数增长.

UCB1-NORMAL

UCB1-NORMAL算法
如果有臂被选择的次数少于$\lceil 8\log n\rceil$,那么就选择该臂
否则,选择指数$I_i$最大的臂,其中 $$ I_i=\bar{x}_i+\sqrt{\frac{16(q_i-n_i \bar{x}_i^2)\ln (n-1)}{(n_i-1)(n_i)}} $$ 其中$q_i=\sum x_i^2$
更新$\bar{x}_i$和$q_i$

定理 UCB1-NORMAL算法下总的遗憾期望不超过 $$ 256\log n (\sum_{i:\mu_i\lt\mu^*} \frac{\sigma_i^2}{\Delta_i})+(1+\frac{\pi^2}{2}+8\ln n)(\sum_{i=1}^{K}\Delta_i) $$

好了,这样就列举完了UCB基本算法了.当然,还有很多变种,留待以后补充. 但其实,各UCB算法的差异并不足够大.

文章目录

理论