Question

在点击率预测中，我们需要采取或是模型、或是特征上的手段来捕获动态信息。这也就意味着，对某种类型的（a，u，c）组合，如果没有相关历史数据的支持，很难对其合理地估计点击率。由于线上我们总是使用统计上最优的策略来投放广告，那些非最优的组合出现机会很少，因而对这部分的估计也就不准确。实际上，无法对特征空间均匀采样构造训练集，是互联网问题区别于其他机器学习问题的重要特点。

此问题属于强化学习的范畴。直觉的想法是牺牲一部分流量上 eCPM 最优的策略，采用相对随机的策略采样那些效果未知的特征空间，这称为探索（exploration）过程；再根据探索和正常决策的总体流量更有效地预测点击率，这称为利用（exploitation）过程。这样的整体策略称为探索与利用，即E&E。E&E可以形象地类比成玩老虎机时的决策问题：玩家面对老虎机上A个有不同期望收益的手柄，需要用尽可能少的筹码探索出收益最高的那个手柄，然后利用这个结果去获取回报。这种简单的 A中选 1的研究问题也称为多臂老虎机（Multi-Arm Bandit，MAB）^[37]问题。我们来看看MAB问题的数学描述。

假设有A个手柄a∈{1，2，···，A}（这里的手柄是广告），在每个决策时刻i（对应于广告展示），必须从A个手柄中选择一个，而目标是优化许多次决策后的整体收益。每个广告a在第 i次展示的收益计为 r_i（a），对于不同的 i，这些收益是独立同分布的。在 i时刻，用下面的两个量来分别表示该分布的均值hr（a）i与方差的经验估计（此处先不考虑u和c的影响）：

最优的手柄或广告定义为期望收益最高的那个：

MAB问题有一个简单的基础方法，即总是用比例为†的一小部分流量来做探索，在探索流量上随机选择A个广告中的一个；在剩余的1−†比例的流量上，总是选择经验收益最高的那个广告。这样的基础方法称为 †贪婪法。很显然，只要经过足够多次的尝试，†贪婪法是一定可以找到最优的那个手柄的。既然如此，还有什么深入研究的必要呢？我们当然是希望能够以更小的代价找到最优手柄。这里的代价定义为整个过程的回报与一开始就总是选择最优手柄这一策略的回报差值，即探索所付出的代价。对于一次选择广告a的展示，这一代价数学上的表达为：

而E&E过程的目标就是使得整体的代价（Regret）最低。以n_i（a）表示到i时刻为止分配给a的展示数，则整体代价可以写成：

假设总共需要进行T次展示决策，探索一些系统性的方法，使得我们在对最优广告a^∗没有先验了解的情形下，以比较低的代价完成这一过程，是这个问题研究的目标。这需要借鉴类似于贝叶斯学习的思想，即将估计的不确定性引入解决方案中，下面介绍一些典型的方法。

13.6.1 UCB 方法

MAB问题经典的思路是置信上界（Upper Confidence Bound，UCB）方法。此方法在每次投放时不是简单地选择经验上最优的广告，而且考虑到经验估计的不确定性，进而选择估计值有可能达到的上界最大的那个广告。

根据这一思路，在每个决策点，UCB 的过程主要分成两个步骤：首先根据过去的观测值，利用某种概率模型计算出每个a的期望回报的UCB；然后，选择UCB最大的a。可以看出，这一算法的关键在于如何计算 UCB。参考文献 [4] 中给出了一种称为 β−UCB 的策略，是按照下式计算上界：

其中。相应地，在任意一个时刻i ，只需要选择令B_k，nk（ i−1 ）最大的a即可。

β−UCB的策略并不对回报的具体参数化模型表达有所假设，而是仅通过一阶和二阶的一些统计量来完成策略，因而具有比较好的普适性。这一策略直觉的好处是我们不可能长时间地选择错误的a，参考文献[4]中对这一点做了理论上的探讨。遗憾的是，由于E&E问题的复杂性，实践中这些比较复杂的策略并未体现出比†贪婪法明显的优势，不过这样的思路和方法还是值得学习的。

13.6.2 考虑上下文的 bandit

MAB问题和UCB实际的广告问题还有一定差距。实际广告系统中的主要挑战有两点：首先，需要探索的是（a，u，c）这一组合空间，而不是简单的一组广告，这使得探索的复杂程度大大上升。以展示广告为例，我们要面临的实际情况是数十万的广告主、数百万的上下文页面以及数以亿计的用户，即使将这些信息按某种层级结构聚合起来，其组合可能性仍然相当庞大，对探索是个挑战。其次，对（a，u，c）的某一具体组合，并不像前文假设的那样有一个确定的期望收益，这是由广告问题的高度动态性决定的。

对于需要探索的空间过大的问题，工程上比较常用的思路是将此空间参数化，在一个维数较低的连续空间中进行探索。这样的E&E问题可以称为考虑上下文的bandit（contextual bandit）问题。注意这里说的“上下文”不同于上下文定向中提到的“上下文”，此处是指根据（a，u，c）组合参数化后的上下文空间位置。

考虑上下文的 bandit 的问题，代表性的思路有 LinUCB 方法^[50]。从名字就可以了解到，这一方法是将公式13.26中表达的回报分布由a决定，变成由一些环境特征的线性组合决定，也就是说，在某个时刻t，我们将某个a的期望回报表达成：

可以看出，这样的表达达到了两个目的：首先，将（a，u，c）的组合空间，而不仅仅是 a都纳入了探索的范围以内；其次，用线性组合的连续输出代替了离散的 ID 值，使得 E&E 过程可以在如此巨大的空间上实施。在参考文献[50]中，这一变换模型被称为不相交的线性模型（disjoint linear model），这里“不相交”的含义指的是对于每一个广告a适用独立的线性变换参数细心的读者一定会发现，这样的假设在a数量巨大时也会成为障碍，因此，在实际中，也可以在广告主类型或其他聚合粒度上使用不同的变换参数。