选择问题
选择强迫症
在没有先验信息或者有部分先验信息的情况下，如何持续的作出更好的选择。
（第一次写，抄一个有用的练练手）
- bandit算法
- Thompson sampling算法
- UCB算法
- *Epsilon-Greedy算法
- 均值最大
背景
bandit算法来源于人民群众喜闻乐见的赌博学，它要解决的问题是这样的：
一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么想最大化收益该怎么整？这就是多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)。
怎么解决这个问题呢？求菩萨？拜赌神？都不好使，最好的办法是去试一试，而这个试一试也不是盲目地试，而是有策略地试，越快越好，这些策略就是bandit算法。
这个多臂问题，它是一个可以装下很多问题的万能框：
- 假设一个用户对不同类别的内容感兴趣程度不同，那么我们的推荐系统初次见到这个用户时，怎么快速地知道他对每类内容的感兴趣程度？这就是推荐系统的冷启动。
- 假设我们有若干广告库存，怎么知道该给每个用户展示哪个广告，从而获得最大的点击收益？是每次都挑效果最好那个么？那么新广告如何才有出头之日？
- 我们的算法工程师又想出了新的模型，有没有比A/B test更快的方法知道它和旧模型相比谁更靠谱？
- …
全都是关于选择的问题。只要是关于选择的问题，都可以简化成一个多臂赌博机问题，毕竟小赌怡情嘛，人生何处不赌博。
exploit－explore问题
特别提出，在计算广告和推荐系统领域，针对这个问题，还有个说法叫做EE问题：exploit－explore问题。
exploit意思就是：比较确定的兴趣，当然要用啊。好比说我们已经挣到的钱，当然要花啊；
explore意思就是：不断探索用户新的兴趣才行，不然很快就会出现一模一样的反复推荐。就好比我们虽然有一点钱可以花了，但是还得继续搬砖挣钱啊，不然花完了喝西北风啊。
bandit算法哪家强
怎么衡量不同bandit算法解决多臂问题的好坏？多臂问题里有一个概念叫做累计遗憾(regret)：
解释一下这个公式：
首先，这里我们讨论的每个臂的收益非0即1，也就是伯努利收益。
公式1最直接：每次选择后，上帝都告诉你，和本该最佳的选择差了多少，然后把每次差距累加起来就是总的遗憾。
wB(i)是第i次试验时被选中臂的期望收益， w*是所有臂中的最佳那个，如果上帝提前告诉你，我们当然每次试验都选它，问题是上帝不告诉你，所以我们就有了这篇文章。
这个公式可以用来对比不同bandit算法的效果：对同样的多臂问题，用不同的bandit算法试验相同次数，看看谁的regret增长得慢。
本着大家可以直接堆代码的原则，所以本文跳过一切数学上的分析，赤裸裸地陈列出最常用的几个bandit算法。
（以下是几个Bandit的算法）
Thompson sampling算法
第一个算法Thompson sampling算法。这个算法我喜欢它，因为它只有一行代码就可以实现。
假设每个臂是否产生收益，其背后有一个概率分布，产生收益的概率为p
我们不断地试验，去估计出一个置信度较高的概率p的概率分布就能近似解决这个问题了。
怎么能估计概率p的概率分布呢？ 答案是假设概率p的概率分布符合beta(wins, lose)分布，它有两个参数: wins, lose。
每个臂都维护一个beta分布的参数。每次试验后，选中一个臂，摇一下，有收益则该臂的wins增加1，否则该臂的lose增加1。
每次选择臂的方式是：用每个臂现有的beta分布产生一个随机数b（根据每个摇臂机当前的beta分布随机产生一个数b），选择所有臂产生的随机数中最大的那个臂去摇。
（关于beta分布）
UCB算法
第二个是UCB算法，UCB算法全称是Upper Confidence Bound(置信区间上界)，不多说了，它的算法步骤如下[4]：
先对每一个臂都试一遍，之后，每次选择以下值最大的那个臂
其中加号前面是这个臂到目前的收益均值，后面的叫做bonus，本质上是均值的标准差，t是目前总的试验次数，Tjt是这个臂被试次数。
这个公式反映：均值越大，标准差越小，被选中的概率会越来越大，起到了exploit的作用；同时哪些被选次数较少的臂也会得到试验机会，起到了explore的作用。
Epsilon-Greedy算法
第三个是Epsilon-Greedy算法。这是一个朴素的算法，也很简单有效，有点类似模拟退火：
选一个(0,1)之间较小的数epsilon，每次以概率epsilon（产生一个[0,1]之间的随机数，比epsilon小）做一件事：所有臂中随机选一个。否则，选择截止当前，平均收益最大的那个臂。
是不是简单粗暴？epsilon的值可以控制对Exploit和Explore的偏好程度。越接近0，越保守，只想花钱不想挣钱。
均值最大
最后还有一个完全是朴素的：
先试几次，每个臂都有了均值之后，一直选均值最大那个臂。这个算法是我们人类在实际中最常采用的，不可否认，它还是比随机乱猜要好。
比较
以上五个算法，我们用10000次模拟试验的方式对比了其效果如图：
算法效果对比一目了然：UCB算法和Thompson采样算法显著优秀一些。
至于你实际上要选哪一种bandit算法，你可以选一种bandit算法来选bandit算法。
目录
用 [TOC]来生成目录：