科学网-【RL系列】Multi-Armed Bandit笔记补充（二）—

【RL系列】Multi-Armed Bandit笔记补充（二）—— UCB策略

2018-7-2 20:37

阅读：7636

本篇的主题是对Upper Conference Bound(UCB)策略进行一个理论上的解释补充，主要探讨UCB方法的由来与相关公式的推导，这一部分书中并未给出详细的过程与分析。

UCB是一种动作选择策略，主要用来解决epsilon-greedy在选择时的低效率问题。对于解释UCB的使用机理上，我认为下面这篇文章写的还不错，深入浅出，只不过在公式推导上有一点点问题：

Multi-Armed Bandit: UCB (Upper Bound Confidence)

我们先来说一说epsilon-greedy策略在选择动作时有什么问题。如果epsilon值较小，例如epsilon = 0.1，那么每次实验都有10%的概率是随机选择动作，如果K值（选择较多）较大的话，这样的选择效率是较低的。为什么说这样的选择效率是较低的，因为在一定的实验次数内，epsilon-greedy只能大概率判断出最优动作，而对于其它动作的收益如何是没办法判断的。举个例子吧，如果说epsilon-greedy策略可以帮你找到最好吃的那家餐厅，那么UCB就可以帮你选出最喜欢吃的三家餐厅，并粗略的排个序。但UCB的坏处也显而易见，当数据量较小时，这个排序并非是与真实期望情况严格相符的排序，只是估计而已，也就是说UCB长于exploration，短于exploitation，所以UCB常用于个性化推送而不适用于寻求最优。

为什么epsilon-greedy策略不能这样做呢？实际上在实验次数不变的情况下，除去最优动作外，很有可能某些动作的实验次数不够多，这样很难保证我们由实验统计出的各个动作收益均值与实际的收益均值相吻合。其实在概率统计上，由均值产生的统计概率与真实期望总是会产生一定的差值，这个差值小于一个较小值delta的概率就可以称之为置信度。举个例子，如若置信度为95%时，我们就可以说，有大于95%的可能性，估计的均值与实际的期望之差小于delta，用数学语言描述出来就是，alpha为置信度：

$\mathbb{P}\left (\left|\frac{1}{n} \sum_{i=1}^{n} X_i - E(X)\right|<\delta \right) > \alpha \\$

我们将式子稍稍变换一下形式：

$\mathbb{P}\left( -\delta <\frac{\sum (X_i -E(X))}{n} < \delta \right) > \alpha$

依据中心极限定理，可知：

$\frac{1}{\sqrt{n}}\sum_{i = 1}^{n} (X_i - E(X)) \sim N(0, \sigma^2)$

所以有：

$\mathbb{P}\left( -\delta \sqrt{n} <\frac{1}{\sqrt{n}} \sum_{i = 1}^n (X_i - \mu) < \delta \sqrt{n}\right) = \int_{-\delta \sqrt{n}}^{\delta \sqrt{n}} \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2}{2\sigma^2}} dx = \mathbb{erf} \left(\frac{\delta \sqrt{n}}{\sigma \sqrt{2}}\right)$

这里的delta与n皆为大于0的数，依据不等式[1]，

$\mathbb{erfc}\left(x \right) < \exp(-x^2)$

$\mathbb{erf}\left( \frac{\delta \sqrt{n}}{\sigma \sqrt{2}} \right) = 1-\mathbb{erfc}\left( \frac{\delta \sqrt{n}}{\sigma \sqrt{2}} \right) > 1- \exp\left[-\left(\frac{\delta \sqrt{n}}{\sigma \sqrt{2}} \right)^2\right] =1-\exp\left(- \frac{n\delta^2 }{2\sigma^2} \right)$