2021 重启强化学习(5) 多摇臂老虎机(UCB)

2021-03-24 本文已影响0人 zidea

020.jpg

如果想观看相关视频可以在西瓜视频(账号zidea)或者哔哩哔哩(账号zidea2015)找到我发布视频解说，注意头像和简书使用头像一致。

通过一个问题引入置信区间

老虎机
1	1,0,0,1,1,0,0,1,0,1	0.5
2	1	1
3	1,1,0,1,1,1,0,1,1,1	0.8

不只是看平均赢率，还要看赢率的置信度(confidence)

置信区间

其实置信区间没有那么复杂，这里简单用语言描述一下，就是对 MAB(多摇臂老虎机)我们都是通过尝试来得到值去推测其概率分布，那么我们看到均值是否接近真实值是和我们做实验次数多少有关系的，也就是实验次数越多这个值就越准确，这是我们想的，如何用数学严谨表达这件事，就引入置信区间的概念。

定义一个范围，均值会以一定概率落在这个范围，例如会 0.95 的概率，落在在 0.2 到 0.5 内
实验次数少，置信区间大，也就是不可靠
实验次数增加，置信区间变窄，估计越来越准确

乐观策略

选择置信区间上界最大摇臂老虎机
通过线性回归估计出 $\hat{p}$ 通常会

置信区间的上界

假设已经对老虎机 $i$ 实验了 $m$ 次
对其均值的估计
$\hat{\mu}_m = \frac{1}{m} \sum_{i=1}^m R_i$
一定概率的置信区间
$|\mu - \hat{\mu}_m| \le b$
一定置信区间的概率
$P(|\mu - \hat{\mu}_m| \le b)$

Heoffding's inequality

$X_1,\cdots,X_m$ 为独立同分布的随机变量，取值范围为 $[0,1]$
真实均值 $\mu =\mathbb{E}[X]$
实验估计 $\hat{\mu}_m \frac{1}{m} \sum_{i=1}^m X_i$
$P(|\mu - \hat{\mu}_m| \le b) \le 2 \exp(-2b^2 m) = \delta$
置信区间 b，其中 $\delta$ 是超参数

$2 e^{-2b^2m} \le \delta \rightarrow b \ge \sqrt{\frac{\ln(\frac{2}{\delta})}{2m}}$

UCB(Upper confidence smapling) 算法

初始化 $\hat{\mu}_1 = \cdots = \hat{\mu}_k = 0$ 以及 $n_1 = \cdots = n_k = 0$
每一步，计算摇臂的 UCB
$UCB(i) = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}}$
总实验次数 t 越多，置信区间的 bound 就越大
摇臂老虎机 i 尝试次数 $n_i$ 越多，置信区间就越窄
让每个摇臂老虎机总被试，但又考虑已经发现的举止

UCB 具体操作流程

初始化:对每一臂都尝试一次
按照如下公式计算每个臂的分数，然后选择分数最大的臂作为选择

$UCB(i) = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}}$

观察结果更新 $n_i$ 和 $t$
$\hat{\mu}_i$ 这个臂到目前的收益均值
$\sqrt{\frac{2 \ln t}{n_i}}$ 是上界，本质上是均值的标准差
$t$ 是实验次数 $n_i$ 是摇臂 $i$ 臂的次数。
这个公式反映一个特点：均值越大，标准差越小，被选中的概率会越来越大，同时哪些被选次数较少的臂也会得到试验机会。

上一篇下一篇

猜你喜欢

热点阅读