推荐搜索之Bandit算法

多臂赌博机问题 ( Multi-armed bandit problem, K-armed bandit problem, MAB )。相比大家都是知道的，就是有多个把手每次坂动一个把手的时候会有不同的收益，也可能没有收益，那么怎么做才能知道收益最大的方法呢？这就是一个典型的如何分配Explore和Exploit的次数的问题，就是著名的探索-利用困境(Explore-Exploit dilemma(EE dilemma))。一直探索和尝试，找到最优解，这个时候聪明的你是不是第一时间想到，这不就是一个强化学习的问题吗？绕了这么半天，其实这确实是一个强化学习场景，但是本文用到了推荐搜索的方案中。
之前的文章中介绍了在推荐中最核心的问题是什么？ 就是冷启动的问题，那么如何使用 Bandit 算法解决冷启动问题呢？

1. 用分类或者 Topic 来表示每个用户兴趣，也就是 MAB 问题中的臂 ( Arm ) ，我们可以通过几次试验，来刻画出新用户心目中对每个Topic的感兴趣概率。
2. 如果用户对某个 Topic 感兴趣（获得点击或者转化），就表示我们得到了收益，如果推给了它不感兴趣的 Topic ，推荐系统就表示很遗憾 ( regret ) 了。
3. 如此经历“选择-观察-更新-选择”的循环，理论上是越来越逼近用户真正感兴趣的 Topic 的。
   接下来介绍一下能够使用的探索方法。

朴素Bandit算法

先随机试若干次，计算每个臂的平均收益，一直选均值最大那个臂。这个算法是人类在实际中最常采用的，不可否认，它还是比随机乱猜要好。简单粗暴，理解起来也比较容易。

Epsilon-Greedy 算法

这个算法有点类似模拟退火的思想。选一个 [0,1] 之间较小的数 $\sigma$ ，每次以$\sigma$ 的概率在所有臂中随机选一个。以 $\sigma$ 的概率选择截止当前，平均收益最大的那个臂。根据选择臂的回报值来对回报期望进行更新。
这种方法咱们在强化学习中经常使用，就是贪心加一定概率的探索，最终能够保证搜索到最优结果。

Thompson sampling 算法

这个是本文的重点，假设每个臂是否产生收益，其背后有一个概率分布，产生收益的概率为p ，同时该概率 p的概率分布符合Beta分布(Beta分布)。 这里为什么要使用beta分布呢？一方面beta分布比较适合描述一个时间的成功与失败，另一方面beta分布中有两个形状参数，a、b正好符合长期概率实验中的失败和成功，这样为每个臂都维护一个 beta 分布的参数，即 loss，win 。每次试验后，选中一个臂摇一下，有收益则该臂的 win 增加 1 ，否则该臂的 loss 增加 1。每次选择臂的方式是：用每个臂现有的 beta 分布产生一个随机数，选择所有臂产生的随机数中最大的那个臂去摇。就解决了动作选取的问题，其实也是一种策略生成方案。

UCB算法

UCB 算法全称是 Upper Confidence Bound（置信区间上界，先对每一个臂都试一遍，之后在任意时刻按照如下公式计算每个臂的分数，然后选择分数最大的臂作为选择。

$$score=\bar{x_{j}}(t)+\sqrt{\frac{2\ln^{t}}{T_{j,t}}}$$

其中观察选择结果更新$t$和$T_{j,t}$,其中$\bar{x_{j}}(t)$表示平均收益，推荐中使用的平均转化率，t表示的是目前的试验次数，$T_{j,t}$共实验了多少次？
UCB算法和Thompson采样算法会比前面两种算法更优秀一些。

LinUCB

不知道大家发现了没有，之前的算法都是耗费大量精力去找到老虎机内部的机制，但是对于推荐搜索中最终决定成功还是失败是给哪个用户推荐了什么的item决定的。很明显这个环境是以上几种算法无法覆盖的。那么怎么把这个上下文的环境建模进去呢。就是接下来要说的LinUCB。

直接来看这个伪代码，其中参数$\alpha$决定探索的程度，$x_{t,a}$表示每个arm的特征向量，接下来开始计算每一个 arm 的预估回报及其置信区间，如果arm 还未被试验过，那么用单位矩阵初始化$A_{a}$, 用 0 向量初始化$b_{a}$,计算线性参数$\theta$,用 $\theta$和特征向量$x_{t,a}$计算预估回报,同时加上置信区间宽度。处理完每一个 arm 之后，选择计算出的最大值对应的 arm,观察真实的回报$r_{t}$,最后更新$A_{a_{t}}$和$b_{a_{t}}$.

大家发现了没有。其实linUCB有一个十分强的先验假设，一个 Item 被选择后推送给一个 User，其回报和相关 Feature 成线性关系，可以看到源码中也是的参数也是符合线性规律的。