课程地址：计算广告学
课时27 探索与利用
计算广告领域的探索与利用要解决的问题是：因为长尾(a,u,c)组合极大部分在系统中并没有出现过，所以没有这些长尾(a,u,c)的统计量，所以要探索性地创造合适的展示机会以积累统计量，从而更准确地估计其CTR。但探索性的展示的过程是没有按当前的eCPM最大化方法进行广告投放，即探索的展示会让收入下降，那么如何控制探索的量和探索的有效性，使得系统长期的，整体的收入增加，就是探索与利用的核心问题。
这个问题在学术界讨论的比较多，它是Reinforcement Learning中的一个具体问题，学术界通常把它描述成为一个Multi-arm Bandit(MAB)问题。这个名字的起源来自由laohuji上的扳手，扳哪个Arm赢的概率比较大，在开始的时候是不知道的，所以要用钱去探索，看哪个扳手能提供的收益最高，但试的过程是在损失自己的钱，所以用这个名字很形象地来称这个E&E问题。
Multi-arm Bandit通常描述为：有限个arms(或称收益提供者)a（即上例中，laohuji的扳手是有限的，在广告系统中它就是广告），每个有确定有限的期望收益E(rt,a)，在每个时刻t，我们必须从arms中选择一个，最终目标是优化整体收益。MAB最基本的方法学术界称为ε-greedy，它是一个很简单的方法，就是将ε比例的小部分流量用于随机探索。如果提出一种新的E&E算法，当然首先要和这种方法进行比较。
广告问题中有两个主要挑战，但它们不一定能很好地在这个框架下解决。1. 海量的组合空间需要被探索，因为要探索的是(a,u,c)这个组合空间，甚至不能认为是一个有限的空间（不是指数学上的无限），2. 因为在MAB问题中假设了各个arm的期望收益是确定的，但对于广告来讲，每个arm的收益绝对不是确定的，比如在双11促销前的ROI与其它时间的ROI相比，差的就很远了。
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。