插一句：这个问题，我之前写过三篇相关的博客（有一篇竟然不知道怎么被不小心覆盖了。悲伤。。。），感兴趣的可以先参考： ● http://blog.csdn.net/allenalex/article/details/78220926 ● http://blog.csdn.net/allenalex/article/details/78242068 当然，这本书里的这一章节，对这个问题整理的非常好。推荐大家认真学习一遍。
推荐系统总的EE问题 直译过来就是“探索-利用”问题。 先直观理解： 探索：我要不要尝试新的（推个新物品怎么样?) 利用：现在推的这个东西还可以阿。要不要继续？ 所谓EE均衡，就是在这两者之间达到某种平衡。
本章主要包括以下内容： 3.1节：简单介绍了EE均衡问题 3.2节：常见的EE方法 3.3节：讨论了推荐系统中的EE挑战 3.4节：处理EE挑战的主要思想
MAB的简单描述网上一搜一大把。这里不过多探讨。给出书中的一段较形式化的定义： 使用 θt 代表赌徒在t时刻摇臂前所获得的所有信息。 θt 可称之为t时刻的状态参数或者就叫做t时刻的状态。主要包括每个臂i到t时刻时的摇臂次数 γi 以及总奖励 αi 。 一个摇臂机制（bandit scheme，或者又叫EE机制（explore-exploit scheme）、策略）就是一个决策函数 π ：它的输入时θt,输出是下次要摇的臂。摇臂机制可以是状态参数的一个确定性函数，也可以是一个随机函数。
MAB 主要可以分为以下三类： ● 贝叶斯方法（Bayesian methods ） ● 极大极小方法（minimax methods） ● 启发法（heuristic methods）
：（这块还没完全弄懂。主要是beta分布那块） 从贝叶斯的角度，可以把MAB问题定义为一个马尔科夫决策过程(MDP)。最优解可以通过动态规划解决。当然，尽管存在最优解，但要求解，计算复杂度非常高。 对MAB定义一个 β-二项式 MDP（Beta-binomial MDP）:
状态 了最大化收益，赌徒需要估计每个臂的奖励概率。 设t时刻的状态 θt 表示赌徒在t时刻前基于实验数据所获得的知识。 对于每个臂，所知的信息用一个两个参数的贝塔分布表示。也就是： θt=(θ1t,...,θKt) 其中 θit 为t时刻i的状态： θit=(αit,γit) 也就是臂i用一个两个参数的beta分布表示。其中 γit 表示臂i到t时刻时的摇臂次数， αit 表示臂i到t是所获得的总收益。 分布满足： 平均值表示基于到目前为止所有数据，赌徒对奖励概率的一个经验估计。而方差衡量他的估计的不确定性。状态转换 赌徒通过摇臂i并观察它的输出可以获得关于臂i的更多输出。状态由θt转换为θ(t+1)。这里，对应是否获得收益（奖励），有两种可能的新状态： - 赌徒有 αit/γit 的概率获得奖励，状态由 θit=(αit,γit) 转换为状态 θi,t+1=(αit+1,γit+1) - 1. 没获得奖励的概率为1 - αit/γit ， 状态转换为 θi,t+1=(αit,γit+1) 其他所有的臂j的状态保持不变；也就是 θj,t+1=θj,t ，这是经典老虎机问题（classical bandit problem）的一个重要特性。我们使用 p(θt+1|θt,i) 表示转换概率，表示摇臂i后状态由 θt 到 θt+1 的概率。因为在当前状态下转换的新状态只有两种，所以转换到其他其他状态的概率为0。 以上的状态转换遵循beta-二项式共轭（这个不太懂）。使用ci ∈ {0, 1}表示赌徒在摇臂i后是否获得收益。如果我们假定： 其中，pi为 奖励概率，那么， (pi|ci)∼Beta(αit+ci,γit+1) 奖励 奖励函数Ri(θt, θt+1)定义摇臂i从状态θt 到 θt+1 期望的奖励。经典的老虎机问题中，这个奖励函数定义非常简单：如果状态由 (αit, γit) 转换为 (αit + 1, γit + 1); 就换的一单位的奖励，否则 就是没有奖励。最优策略（Optimal Policy） 原文没有给出具体的算法。提到了一种‘Gittins index’，感兴趣的读者可以参考： 1） Gittins, J. C. 1979. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society. Series B (Methodological), 41(2), 148–77 2）Nino-Mora, Jos ˜ e. 2007. A (2 ´ /3)n3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain. INFORMS Journal on Computing, 19(4),596–606
此外，还有一段比较详细的讨论了最优解问题。有一定的理论深度，我也没有深入研读。感兴趣的读者可以参考原文。
关注UCB算法。
其中，3.12公式的前一项表示臂i当前奖励概率的一个估值，后一项表示估计的不确定性。 参考：Auer, P. 2002. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3, 397–422. 除此之外，还可以参考我的另一篇博文：http://blog.csdn.net/allenalex/article/details/78242068
有以下几种机制（方法）：
epsilon-Greedy算法.这个方法，可以直接参考我的另一篇博文：http://blog.csdn.net/allenalex/article/details/78220926SoftMax; 首先定义一个称之为“温度”的参数–τ，每次摇臂i的概率为： 当τ很高的时候， ep^i/τ→1 ,那么每个臂被选中的概率就几乎一样。相反，如果 τ很低，则几乎总是选择奖励概率最大的那个臂。 下面这两种，本文见得比较少。不翻译整理了，直接贴出原文。通常，贝叶斯方法计算复杂度高，但是如果建模假设合理，性能相对更好。相反，极大极小值方法在最坏的情况下能够实现最好的性能，但是要平均要尝试的次数更多。实践中通常使用基于启发式的方法。启发式方法实现相对更简单，并且通过合适的调节，能够实现合理的性能。
