推荐广告或推荐系统领域的EE问题：
- Explore 探索用户兴趣，或者避免算法走入死胡同。
- Exploit 确定了用户兴趣，然后推荐与之相关的内容。
对于固定流量来说，Exploit的这部分流量显然会产生收益，而Explore不一定能立刻就有收益。所以，如何分配E&E流量，最大化收益是值得研究的内容。
E&E一般常等同于多臂老虎机问题（Multi-armed bandit problem）进行解决。
累积后悔
累积后悔（Cumulative Expected Regret）可以来评估bandit算法，或其他一些在线学习算法。
多arm的回报可以看作一组真实的随机分布：$B=( R_i,\dots,R_K )$，其中，$K$代表arm。
设 $\mu_1,\dots,\mu_K$ 代表每个arm的平均回报，每一轮拉动一个arm得到一次回报。多arm问题等同于一个状态的马尔科夫问题。
设$T$轮之后的后悔度为 $\rho$，则可以表示如下：
\[\rho = T\mu^* - \sum_{t=1}^T \hat{r_t}\]其中，$\mu^*=\max_k( \mu_k )$ 是最大回报的平均数，$\hat{r_t}$ 是在t时获得的回报。
一个零后悔度的策略会使得 $\rho/T$在无限次选择arm后以概率1趋向于0。
Epsilon-Greedy
利用概率ε来探索，概率1-ε来开发。
Thompson sampling
认为每个arm服从一个beta分布，Thompson采样算法：
- 每个arm都维护一个 beta 分布的参数，获取每个臂对应的参数 α 和 β，然后使用 beta 分布生成随机数。
- 选取生成随机数最大的那个臂作为本次结果。
- 观察用户反馈，如果用户点击则将对应臂的 α 加 1，否则 β 加 1。
choice = numpy.argmax(pymc.rbeta(1 + self.wins, 1 + self.trials - self.wins))
UCB
置信区间上界（Upper Confidence Bound）
在统计学中，对于一个未知量的估计，总能找到一种量化其置信度的方法。最普遍的分布正态分布 N(μ,δ)，其中的μ就是估计量的期望，而δ则表示其不确定性（δ越大则表示越不可信）。
而UCB就是以arm均值 μ 的置信上限为来代表它的预估值：
\[\hat{\mu_i} = \hat{\mu_i} +2 \sqrt{\frac1{n_i}}\]其中，$\mu_i$ 是对期望的预估，$n_i$是尝试次数，可以看到对i的尝试越多，其预估值与置信上限的差值就越小。也就是越有置信度。
参考实现：https://github.com/jkomiyama/banditlib/blob/master/policy/policy_ucb.hpp
LinUCB
单纯的UCB回报是由arm本身决定的，而广告或推荐领域，应该是由user和item共同决定的。
所以，LinUCB对比UCB加入了user和item(arm)的特征，并且假设feature回报线性相关（所以是Linear UCB），通过feature预估每个arm的期望回报和置信区间，选择置信区间上界最大的arm，观察回报后更新线性关系的参数。这样看起来更加合理。
并且由于加入了特征，LinUCB比UCB收敛更快，在最终rank上有相关应用。
参考
- 《计算广告学》刘鹏 6.3 探索与利用