探索与利用(Explore and exploit) E&E

 点击率预测中还有一个重要的问题，就是探索与利用，它在工程中解决的并不好，我这章把现在论文中的常见的几种方法介绍一下。探索与利用它是所有互联网应用都要面对的一个问题，形式化一些，可以解释为：整体的效果是无法通过采样得到的，因为观察到的数据只是投放过的广告，而很多还没有投放的广告，想得到它们的效果，就很困难。

         计算广告领域的探索与利用要解决的问题是：因为长尾(a,u,c)组合极大部分在系统中并没有出现过，所以没有这些长尾(a,u,c)的统计量，所以要探索性地创造合适的展示机会以积累统计量，从而更准确地估计其CTR。但探索性的展示的过程是没有按当前的eCPM最大化方法进行广告投放，即探索的展示会让收入下降，那么如何控制探索的量和探索的有效性，使得系统长期的，整体的收入增加，就是探索与利用的核心问题。

         如果实践中做过广告系统，对于这一点应该有比较深的感触。因为无论是搜索广告，还是联盟广告，在广告主比较多的情况下，会有相当大的一批广告主是永远没有机会展示的，但我们也没有办法让他们得到一些展示的机会，因为要给他们展示的机会，是要付出相当大的代价的，有必要从算法的角度来讨论探索与利用的问题。Explore就是探索未知世界，Exploit就是利用从未知世界得到的少部分统计量，去提高eCPM统计的准确性。

         这个问题在学术界讨论的比较多，它是Reinforcement Learning中的一个具体问题，学术界通常把它描述成为一个Multi-arm Bandit(MAB)问题。这个名字的起源来自由laohuji上的扳手，扳哪个Arm赢的概率比较大，在开始的时候是不知道的，所以要用钱去探索，看哪个扳手能提供的收益最高，但试的过程是在损失自己的钱，所以用这个名字很形象地来称这个E&E问题。

         Multi-arm Bandit通常描述为：有限个arms(或称收益提供者)a（即上例中，laohuji的扳手是有限的，在广告系统中它就是广告），每个有确定有限的期望收益E(r_t,a)，在每个时刻t，我们必须从arms中选择一个，最终目标是优化整体收益。MAB最基本的方法学术界称为ε-greedy，它是一个很简单的方法，就是将ε比例的小部分流量用于随机探索。如果提出一种新的E&E算法，当然首先要和这种方法进行比较。

    广告问题中有两个主要挑战，但它们不一定能很好地在这个框架下解决。1. 海量的组合空间需要被探索，因为要探索的是(a,u,c)这个组合空间，甚至不能认为是一个有限的空间（不是指数学上的无限），2. 因为在MAB问题中假设了各个arm的期望收益是确定的，但对于广告来讲，每个arm的收益绝对不是确定的，比如在双11促销前的ROI与其它时间的ROI相比，差的就很远了。这两个问题，我自己体会，在工程上需要研究者在以后进一步解决。

E&E算法-UCB

    关于E&E算法，我介绍两个基本思路，大家不要把它认为是一篇论文或是一个具体的算法，我介绍的是两个非常有借鉴意义的思路。这个领域大家比较认可的是UCB方法。

    UCB方法的思路从直觉上非常合理，它是在时间t，通过以往观测值以及某种概率模型，计算每个arm的期望收益的upper confidence bound(UCB)，并选择UCB最大的arm。先不关注这句话中的术语，它其实也是一个bayesian的理念，在估计某个arm收益的时候，不再把它认为是一个确定的数，而是把它认为是一个分布。UCB的意思是在选择的时候，并不是按照期望收益最大的一点去选择，而是按照分布的收益上界去选择。在体会这个策略的过程中，会发现它是一个很聪明的策略，它对每个arm都是选择它最有可能达到的收益点来进行投放，随着时间的推移，随着观察值的增加，分布曲线会越来越窄，最终收敛成一个固定的值。假设一个广告的期望收益并不高，换言之，它的表现可能不是最优的，我们在UCB方法下不会永远出这个广告，因为经过几次探索，它就分布曲线会迅速收敛，当发现有别的广告比它更好的时候，就不会再出这个广告了，但这种方法不会漏掉真正好的广告，因为好的广告在没有观察的时候，它是非常宽的一个函数分布，它的upper confidence是一个很大的值，所以总是有机会选中它，选中之后，分布会迅速收敛到实际的确定的收益。Paper中主要探讨的是具体的UCB策略，比如β-UCB策略，它是证明选择非最优的arms存在着一个上界，该上界与总的选择次数无关。还有一个改进的策略，UCB-tuned，它证明了如果已经选择的次数越多，就越可能自信地抛弃不太有前途（但仍可能最优）的arm。

    介绍UCB方法是因为它是一个很符合人直觉的E&E算法，其它也有很多变形的算法，大家可以看一下相关的资料。