置信区间上界算法-原理

楔子：

多臂老虎机.PNG

1、机器狗

机器狗.PNG

原始方法：通过周围的环境决定机器狗的走路方式
强化学习方法：通过让机器狗自己试错，如果结果顺利加分，如果结果错误减分。

2、老虎机

老虎机.PNG

老虎机就是一种你往里头投硬币，会返给你一个或者多个硬币，或者吞掉你的硬币的机器。多臂老虎机就是多个老虎机。

老虎机分布.PNG

每个老虎机的直方图都是随机的，只有商家知道，这里我们假设这五台老虎机吐硬币的个数分布服从上图。

3、广告商业案例

广告商业案例.PNG

强化学习就是探索加利用，我们要用最快速高效的算法探索出最好的机器或者广告，然后多加利用这个最好的结果。
对于老虎机而言我们需要找到均值最高的五号机，探索次数太少，可能结果不正确，探索次数太高会增加试错成本。
对于这五个广告而言，我们需要找到转化率最高的广告，可以分别把他们放到5个网页上，统计转化率，也就是点击广告的次数除以打开网页的次数。如果分别在网页上挂3天，这个试错成本比较高，如果第一天的统计结果明显较低的广告，我们就不考虑再挂第二天和第三天了。

4、置信区间上界算法

楔子：

置信区间上界.PNG

强化学习就是探索在结果正确的保证下相对高效快速，然后最大程度的利用。

解决问题.PNG
问题：我们在同一个网页轮番的展示5个广告，如果用户在打开网页是点击了该网页上展示的广告。我们就为这个广告加一分。
置信区间上界算法步骤.PNG

在每经过一轮，我们都会重新计算均值和置信上限，选择当前置信上限最高的广告进行下一次投放，如此迭代，如果出现置信上限等高的就随机选取。如此迭代投放，直到置信区间收敛到一个很小的值。

初始情况.PNG
在一开始我们假设均值是一样的，置信区间比较大，因为我们没有经过探索，对于预估的均值非常不自信。
这里横坐标代表广告，纵坐标代表广告的转化率。
D3进行探索之后的值.PNG
最终结果.PNG
通过不断的选择置信区间上限最大的值进行投放。我们会得到一个置信区间上限最大且范围越来越小的均值。