1. 朴素法
先对每个item进行一定次数（如100次）选择尝试，计算item的回报率，接下来选择回报率高的item。算法简单直接，但存在以下问题：
- item很多导致获取item回报率的成本太大
- 尝试一定次数（如100次）得到的“高回报”item未必靠谱
- item的回报率有可能会随时间发生变化：好的变差、差的变好
2. Epsilon-Greedy
选一个(0,1)之间较小的数ε，每次决策以概率ε去勘探Exploration，1-ε的概率来开发Exploitation，基于选择的item及回报，更新item的回报期望（见“增量更新期望回报”），不断循环下去。
这样做的好处在于：
- 能够应对变化：如果item的回报发生变化，能及时改变策略，避免卡在次优状态
- 可以控制对Exploration和Exploitation的偏好程度：ε大，模型具有更大的灵活性（能更快的探索潜在可能高回报item，适应变化，收敛速度更快），ε小，模型具有更好的稳定性（更多的机会用来开发利用当前最好回报的item），收敛速度变慢。
但：
- 设置最好的ε比较困难，大则适应变化较快，但长期累积回报低，小则适应变好的能力不够，但能获取更好的长期回报。
- 策略运行一段时间后，我们对item的好坏了解的确定性增强，但仍然花费固定的精力去exploration，浪费本应该更多进行exploitation机会
- 策略运行一段时间后，我们已经对各item有了一定程度了解，但没用利用这些信息，仍然不做任何区分地随机exploration（会选择到明显较差的item）
3. Softmax
ε-Greedy在探索时采用完全随机的策略，经常会选择一个看起来很差的item，此问题的解决方法之一是，基于我们目前已经知道部分item回报信息，不进行随机决策，而是使用softmax决策找出回报最大的item。
SoftMax利用softmax函数来确定各item的回报的期望概率排序，进而在选择item时考虑该信息，减少exploration过程中低回报率item的选择机会，同时收敛速度也会较ε-Greedy更快。
但是，softmax算法的缺点是：
- 没有考虑预估item回报率期望的置信度信息，因而选择的高回报率item未必靠谱。
- 无法事先知道t的大小，因问题而异，同时也不容易与其他算法直接比较
4. UCB
统计学中，我们使用置信区间来度量估计的不确定性/置信性。如我们摇骰子一次得到的点数为2，那么得到均值的估计也是2（实际平均点数是3.5），但显然这个估计不太靠谱，可以用置信区间量化估计的变化性：骰子点数均值为2，其95%置信区间的上限、下限分别为1.4、5.2。
UCB思想是乐观地面对不确定性，以item回报的置信上限作为回报预估值的一类算法，其基本思想是：我们对某个item尝试的次数越多，对该item回报估计的置信区间越窄、估计的不确定性降低，那些均值更大的item倾向于被多次选择，这是算法保守的部分（exploitation）；对某个item的尝试次数越少，置信区间越宽，不确定性较高，置信区间较宽的item倾向于被多次选择，这是算法激进的部分（exploration）。
其计算item期望的公式：
其中，x_j是item_j的平均回报，n_j是item_j截至当前被选择的次数，n为当前选择所有item的次数。上式反映了，均值越大，标准差越小，被选中的概率会越来越大，起到了exploit的作用；同时哪些被选次数较少的item也会得到试验机会，起到了explore的作用。
与ε-Greedy算法、softmax算法相比，这种策略的好处在于：
- 考虑了回报均值的不确定性，让新的item更快得到尝试机会，将探索+开发融为一体
- 基础的UCB算法不需要任何参数，因此不需要考虑如何验证参数（ε如何确定）的问题
UCB1算法的缺点：
- UCB1算法需要首先尝试一遍所有item，因此当item数量很多时是一个问题
- 一开始各item选择次数都比较少，导致得到的回报波动较大（经常选中实际比较差的item）
5. LinUCB
参考：LinUCB
上述算法均没用充分利用上下文信息Contextual。单纯的老虎机，它回报情况就是老虎机自己内部决定的，而在广告推荐领域，一个选择的回报，是由User和Item一起决定的，如果我们能用feature来刻画User和Item这一对CP，在选择之前通过feature预估每一个arm的期望回报及置信区间，那就合理多了。
为UCB插上特征的翅膀，这就是LinUCB最大的特色。
LinUCB算法做了一个假设：一个Item被选择后推送给一个User，其回报和相关Feature成线性关系，这里的“相关feature”就是context，也是实际项目中发挥空间最大的部分。
于是试验过程就变成：用User和Item的特征预估回报及其置信区间，选择置信区间上界最大的item推荐，观察回报后更新线性关系的参数，以此达到试验学习的目的。
LinUCB算法有一个很重要的步骤，就是给User和Item构建特征，也就是刻画context。在原始论文里，Item是文章，其中专门介绍了它们怎么构建特征的，也甚是精妙。容我慢慢表来。
- 原始用户特征有：
人口统计学：性别特征（2类），年龄特征（离散成10个区间）
地域信息：遍布全球的大都市，美国各个州
行为类别：代表用户历史行为的1000个类别取值
- 原始文章特征：
URL类别：根据文章来源分成了几十个类别
编辑打标签：编辑人工给内容从几十个话题标签中挑选出来的
用Logistic Regression去拟合用户对文章的点击历史。
总结一下LinUCB算法，有以下优点：
- 由于加入了特征，所以收敛比UCB更快（论文有证明）；
- 特征构建是效果的关键，也是工程上最麻烦和值的发挥的地方；
- 由于参与计算的是特征，所以可以处理动态的推荐候选池，编辑可以增删文章；
- 特征降维很有必要，关系到计算效率。
6. Thompson Sampling
假设每个item有一个产生回报的概率p，我们通过不断试验来估计一个置信度较高的概率p的概率分布。如何估计概率p的概率分布呢？ 假设概率p的概率分布符合beta(wins, lose)分布，它有两个参数: wins, lose， 每个item都维护一个beta分布的参数。每次试验选中一个item，有回报则该item的wins增加1，否则lose增加1。每次选择item的方式是：用每个item现有的beta分布产生一个随机数b，选择所有item产生的随机数中最大的那个item。
相比于UCB算法，Thompson sampling：
- UCB采用确定的选择策略，可能导致每次返回结果相同（不是推荐想要的），Thompson Sampling则是随机化策略。
- Thompson sampling实现相对更简单，UCB计算量更大（可能需要离线/异步计算）
- 在计算机广告、文章推荐领域，效果与UCB不相上下或更好competitive to or better
- 对于数据延迟反馈、批量数据反馈更加稳健robust
