沈冰阳：强化学习在推荐冷启动优化中的实践探索！
分享嘉宾：沈冰阳 58集团 算法高级工程师
编辑整理：吴祺尧 加州大学圣地亚哥分校
出品平台：DataFunTalk
导读：58招聘是国内最大的蓝领招聘平台，是58集团的四大核心业务之一，每天有着上千万的职位在平台上发布，同时也有百万量级的求职者在平台上进行简历投递，达成海量连接并促进大量的成功就业。招聘业务是一个典型的双边匹配任务。我们会向B端客户（招聘者）连接C端的用户（求职者）。与业界其他推荐系统相比，58职位推荐面临着更明显的冷启动问题以及蓝领用户兴趣发散的问题。本次分享想跟大家讨论我们针对以上问题使用强化学习的模型设计与应用实践。
今天的介绍会围绕下面五点展开：
58招聘业务概述
强化学习概述
推荐中的强化学习算法
强化学习在招聘冷启动的实践
总结和展望
首先和大家分享下58的招聘业务场景。
首先求职者对系统给其推荐的职位进行点击，然后对感兴趣的职位进行简历投递、发起微聊、拨打电话等操作，相当于求职者单边的意向表达。然后招聘者对于求职者发起的单边连接进行回复，比如简历反馈、微聊回复、接通电话等。在进行沟通后，双方最终达成面试和入职。推荐算法工程师其实是在推荐系统的召回、过滤、粗排、精排等各个环节，设计算法和策略，解决具体业务问题，或者提升某个技术细节，最终达到平台整体连接提效的目标。
我们的招聘业务目前存在两个问题：
冷启动问题，即针对新用户应该如何进行职位推荐；
用户兴趣发散问题，即由于平台用户的性质，很多求职者的从事过不同类别的职位，具有多个兴趣域的需求。
其实在不同业务场景上都有类似的问题，其关键点是如何利用现有信息和用户行为进行个性化推荐，我们考虑通过强化学习的思路和方法来解决这两个问题。下面简单介绍一下强化学习。
强化学习描述了一个智能体如何在环境中采取一系列行为，从而获得最大的累计回报。它与常见的监督学习有两点区别：
强化学习是一种试错学习，它没有直接的指导信息，所以智能体需要不断地与环境进行交互，通过试错的方式来获得最佳策略。相较于监督学习，强化学习能够利用的信息更加少，但也使得其面对一些特定信息比较缺乏的场景表现更加出色；
强化学习面临着延迟回报的问题，即其进行决策的时候并不知道具体的回报值，而是在达到最后的状态后才会得到相应回报。而监督学习模型在训练时标签和特征是同时给出。延迟回报的特性使得强化学习比较适合智能体与环境连续交互的场景。
强化学习本身学习的是一个策略，即在某种特定的情况下，智能体应该做出何种行为。强化学习有四个关键要素：状态、动作、回报以及状态转移概率。
在推荐系统中，要对应这四要素进行建模：
s（状态），可以是用户的一个特征。用户的一个行为序列，也可以是上下文信息（如手机型号、时间等）；
a（动作），在推荐系统中对应着为了解决一个问题我们算法选择的推荐动作，它可以是选择推出的item类别（职位类别），具体的多个item（具体职位），item排序，某组融合参数等。我们要解决什么问题，就会把相应的一些问题定义成action；
s'（状态转移概率），是用户接收到推荐后其的新状态，比如新用户通过我们的推荐和其与推荐系统之间的交互，由状态转移概率决定其进入的一个新状态；
r（收益），是指用户接收到推荐后对我们的业务的贡献，例如点击率、转化率、实际的停留时长等。
我们来看一个具体的推荐问题。我们希望从职位列表中挑选职位向用户进行推荐。我们可以使用推荐中常用的技巧，例如拿用户信息、职位信息来计算偏好，并根据偏好建立起一个用户对职位的兴趣预测模型。这实际上对应着基于有监督学习的解决方案。
但是存在两个问题。首先，有监督学习是特征base的，即特征往往决定模型的上限，而算法和调参只是逐渐逼近上限。有监督学习在训练过程中，模型会尽量将输入信息利用好，但是在一些特征比较缺乏的场景，模型的效果受到明显的制约。第二个缺点是实际上在用户与推荐的item进行交互的过程中往往呈现一个连续的决策过程，而有监督学习很难对这个问题进行处理。
接下来我们使用强化学习的思路来切入这些问题，试图根据当前我们所能获取的信息，通过某种方式来选择一个职位，然后再根据用户的反馈来决定后续的策略。
首先考虑最简单的情况。比如说一个求职者没有看过程序员这个职位，我下次就给他推荐程序员试试看。相反地，如果他已经看过很多次程序员这个职位，我下次就不给他推荐程序员。这个思路本质上就是先试探，根据得到的结果进行相应的策略调整。这其实就是MAB（多臂老虎机）算法。整个算法模型是由一个动作来决定一个回报，即只考虑了动作和奖励，并以最小累积遗憾为目标。累计遗憾就是每个步骤中采取的一个方案与最优方案之间的差值，这个差值越小就代表目前的一系列决策行为是越好的。
MAB算法的应用有：
epsilon Greedy算法：给定一个概率p，每次以p的概率选择最大的收益，每次以1-p的概率随机选择一个策略。虽然算法的形式非常简单，但是它的收敛性有比较严格的数学证明。
UCB算法：首先把所有可选择的策略选择一次，然后根据当前拿到的收益得到UCB公式的前项。之后计算得到一个最大置信区间，即公式的后项，置信区间代表若一个策略被选择的次数较少，则可以有更大概率选择这个策略。
汤普森采样：根据贝塔先验分布进行采样。
这些算法目前在推荐业界有一些相关的应用，例如腾讯、堆糖等。但是它们的缺点也比较明显。首先算法并没有利用到推荐场景的一些先验信息；其次算法的反应比较慢，因为它依赖用户和系统的不断交互，然后根据不断累积的试探结果来达到比较好的效果。
针对利用先验信息这个问题，我们可以对MAB进行算法改进。比如我知道用户的定位在软件园，并且他最近没有被推荐过程序员这个职位，我就认定他可能是要找一个程序员的工作。这种方法其实就是在老虎机问题中加入上下文的概念，即CMAB算法。它相较于MAB加入了一个状态信息，算法会根据状态来决定相应的动作，最后的奖励是由状态和动作同时决定的。上下文其实就是推荐系统中运用的特征或者我们所拥有的一些环境信息等。在CMAB每轮运行的过程中，它会根据当前所能拿到的上下文信息作为状态，来计算对应每一个动作的收益，之后再结合探索-利用的思想来选择下一步动作。
从算法原理上来看CMAB还是一种单步强化学习算法，并没有考虑奖励延迟的问题。相较于有监督学习来说，因为CMAB所有算法参数的选择都是用线上实时交互来得到的，它能比较好地针对新物品或者新用户进行推荐；其次CMAB本身具有探索-利用的优势。CMAB根据特征、动作、奖励进行不同的设计，衍生出LinUCB以及Context-Tompson Sampling等不同形式的算法。
下面对线性UCB算法进行一个简单的介绍。线性UCB算法假设取得的回报和特征是呈线性关系的，也就是说我们可以将其类比有监督学习中的LR算法来进行理解。首先我们取得每个策略的特征，然后通过一系列计算得到每个策略对应的参数集合（相关样本的特征矩阵等）。在上图算法第9行中，线性UCB的前项实际上可以直接类比LR中W乘以X，即得到一个策略的期望收益，后项实际上就是探索-利用机制中的模型的预测方差（探索部分的分值），使得算法不能单纯贪心地选当前最大值，还可以探索之前没有选择或者选择次数比较少的一些策略。最后，算法通过线性更新来改变对应的权重。线性UCB算法的核心点主要在于特征工程的设计和相应的业务理解，其具体实现难度相对来说并不大，而且它在解决冷启动问题以及其他强化学习的问题上都有比较出色的效果。
目前我们也是在探索完整强化学习问题在职位推荐的应用。还是拿之前的例子来说：如果一个人定位在软件园，且一般看三次程序员的职位后会选择投递，他之前已经看了两次该职位，那么下次就给他推荐程序员这个职位。相较于MAB方法，完整强化学习问题通过引入状态转变，使得算法能够学习到奖励延迟。在状态空间中只有部分状态是有奖励的，通过多个状态之间的相互转移，强化学习算法就可以学到单步最大的收益并不一定是全局最大收益。
针对这种问题的建模，目前通用做法是采取一个马尔可夫决策过程，然后通过求解转态转移概率和价值函数来解决这个问题。目前强化学习方法种类非常多，大体上可以分为：model-based/ model-free，on-policy/ off-policy，以及深度/非深度学习方法等。
具体到推荐系统领域，运用强化学习算法需要考虑到额外的限制条件。
首先，推荐系统的状态空间和动作空间十分庞大。因为状态空间其实就是我们的特征空间，诸如行为序列等特征往往是连续多值的，它并不像围棋、走迷宫这种场景一样可以简单地被定义。动作空间对应着我们业务上会解决的实际问题，比如我们要决定一种参数融合权重，那么我们最终输出的结果也是一个连续空间，并不像某些游戏应用中有限的动作空间（如上下左右移动）。
推荐系统的第二个特点就是高实时性。一般来说，系统在线上的最大延迟都在毫秒级。
此外，推荐系统需要考虑到业务效果的影响。强化学习是一种在线学习的算法，参数往往需要在用户进行交互的过程中进行学习，而在实际场景中我们的算法一上线就需要对业务效果负责，所以我们不能接受一个需要在线上学习三天、五天后才能得到一个较为满意的效果的模型。
针对这三个特点，就带来了三个问题：难以建立环境模型、较低的计算复杂度以及算法收敛的稳定性与收敛速度。结合上文提到的强化学习方法划分大类，Model-free其实就是针对状态空间比较大的问题，我们不需要对状态空间进行刻画，而直接刻画值函数。而off-policy是指每一步迭代，我们可以使用之前的一些经验来加快收敛速度。这两种方式都非常符合推荐场景的特点，目前业界已经提出了对model-free off-policy模型的改进策略，代表方法有经验回放、双网络、预训练部署等。
国内比如阿里、腾讯、美团等公司在多目标参数融合、排序调整以及流量分配上也有相应的方法改进，在此就不一一赘述。
1. 问题拆解
现在回到我们58的业务问题上去，详细介绍一下在58招聘场景针对冷启动问题实现的一个单步强化学习算法。
从58的平台特点来看，在新求职者推荐上主要有以下现状：
用户首次的求职时间周期长，对平台贡献的连接以及相应的收入贡献都是最多的，重要性不言而喻，同时新用户对于体验更加敏感；
业界中效果比较好的召回策略大多是基于用户行为触发的，即我们会通过用户最近的一些行为序列得到用户本身的兴趣表达。但是新用户本身行为比较少，导致相应的召回策略具有缺陷。
最终反馈到实际数据维度，我们可以看到平台上目前处于不同状态的用户的行为转化是有差别的，冷启动用户和正常用户在转化效率上会有一定程度的差距，新用户的转化率往往较低。
冷启动在推荐系统中是一个非常常见的问题。一般来说我们可以从产品和技术两个角度来考虑解决方案。从产品角度来说，我们可以从产品上设计一些新用户信息收集的方法，例如添加一些弹窗等，向推荐系统提供一些基础的信息来对新用户进行推荐。在用户对信息进行完善的时候，我们也可以通过一些奖励机制来激励用户补充自己的信息。从技术上我们可以进一步细分为两个点：多来源和个性化。
多来源是指尽可能利用我们能够采集到的信息来构建给用户进行推荐的机制，如用户的定位、手机型号、IP地址等。在我们推荐中做了招聘特有的POI机制，会把全国的工业园区和商圈信息进行收集，在职位推荐时我们可以根据用户的定位向他推荐附近的一些工业园区的职位等。这种做法在线上也取得了一定的效果。
针对个性化，我们需要在较短的时间内完成对新用户的兴趣探索，而这正是强化学习可以完成的任务。
目前我们从业务目标上会关注于还没有建立简历的用户群体，他们是由当日的新增用户以及未创建简历的沉寂用户组成。冷启动问题的难点在于用户侧的信息十分匮乏，我们提出基于上下文的MAB算法来进行兴趣试探。算法的整体流程是构建出一系列职位桶，之后通过MAB策略在桶中取出职位向用户进行推荐。而这一算法的关键点在于如何设计桶以及相应的选择策略。
2. MAB算法设计
具体算法设计需要基于业务的特点。对于招聘来说，类目体系的数量达到千级，如果结合标签体系则可以接近万级。类目数量巨大导致我们没办法直接根据职位类目设计桶，因为这导致动作空间过于庞大。另外，我们要解决的是冷启动问题，但用户发生投递后便会创建简历，转化为一个有信息的用户，这导致了冷启动用户状态时间短，推荐系统可以尝试的次数比较少。
针对第一个业务难点，我们通过用户不同属性来划分探索空间。用户属性由地域、年龄、性别、期望薪资等组成。我们使用构建群体画像的思路，基于用户在平台上的点击和简历投递行为构建出用户的不同属性与职位职类体系的映射关系。通过映射关系我们可以根据用户的具体属性得到它所感兴趣的职类。当然我们也可以反过来通过职类对用户的相应属性进行映射。
对于第二个问题，我们考察了多种常用的MAB算法，发现epsilon-Greedy算法对收益变化更加敏感，这与我们后续的设计目标更为相近，最终它在线上也取得了比较好的效果。
从强化学习的角度，我们的策略目标就是在缺少信息的情况下判断出用户最有可能具有的一系列属性。具体地，状态其实就是用户属性，包含年龄、性别、地域等；动作就是算法对状态进行推测的维度，它根据探索-利用的概率p来选择属性中使得维度取值最大的一个属性，或者选择随机的一个属性。确定属性后，我们可以向用户推荐属性映射的职位；然后我们根据用户的线上行为，比如点击了某个职位，来得到用户相应的回报，最后根据回报来更新用户状态，更新方式如下：使用之前建立的映射关系从职位的类别得到用户属性上的倾向向量，基于这个向量并结合他行为的权重更新用户状态。这样我们就完成了从状态决定动作，再从动作得到一个回报，最后根据回报更新状态的流程。
举个简单例子，图中给出一个用户向量，它包含了用户的三个属性（地域，性别，年龄）。用户的定位在北京；性别0代表男性1代表女性，图中0.36代表其男性的概率是0.36，对应女性的概率是0.64；年龄上分为十个区间，也对应着相应的概率取值。通过这三个属性，我们使用epsilon-Greedy算法进行职位属性选择，得到了北京、男性20-25岁这个确切的职位属性。之后会拉取属性下对应的职位进行前端的展现。最后根据用户序列，即用户点击过的职位集合（如送餐员），通过一个权重矩阵来对职位属性进行对应的更新，在这个例子中代表送餐员这个职位男性20到45岁点击得比较多，该用户更可能具有男性和20-45岁的属性。最后把向量更新到用户的状态中。
下面说一下具体的一些细节和思考点。
初始化：一个新用户到达时，我们冷启动策略中用户状态向量的初始化采用的是均值初始化。比如性别这个维度，我们认为男性和女性的概率都是0.5，年龄这个维度十个区间的概率都取相同的值。采用均值初始化的出发点是保证探索维度上的平等，而采用平台的统计先验信息进行初始化会导致类别比较少的用户会得到比较差的效果；
Reward更新方式：线上是一个多路召回的模式，冷启动只是其中的一路召回。我们会使用用户所有点击过的职位，也不区分其是从哪一路召回产出的，而是直接将所有召回并得到用户点击行为的职位进行向量拉取。这样可以使系统在用户冷启动阶段利用更多的信息，使得整体的算法收敛得更快；
职位队列：针对桶中放的职位，我们会选取高转化率且低饱和度的新职位放入，旨在提升新用户的连接体验；
与画像召回的区别：画像召回也是利用用户最近的一些行为来拉取相应的职位。但是MAB算法的关键点在于我们在数据组织形式上更加泛化。画像往往就是用户最近点击的两到三个职位及其类别，而我们采用的方法对用户所处于的状态进行了泛化，例如北京、20-25岁的男性等。而对应的用户属性在我们平台上的职位是多种多样的。采用泛化的技巧，我们可以使推荐系统更好地探索用户兴趣。
3. 算法离线学习、验证以及评估方法
强化学习算法往往需要上线才能进行学习以及验证评估，但在实际业务场景中，算法效果需要对业务负责，完全在线的参数实验产生的时间代价和收益风险是难以接受的。下面介绍一下我们在离线评估阶段采用的方案。
我们通过使用线上真实的用户序列以及画像数据来模拟冷用户到有信息用户的转化，以此来达成我们的思路验证和离线评估以及训练的目标。整个系统大概由四个模块组成。首先是MAB算法模块，该模块根据前述的算法流程来模拟进行职位的推荐。最重要的模块是决策模块，负责将MAB算法的结果和用户真实数据进行计算。这部分进行了两部分计算，第一部分是对MAB推荐的职位和用户真实的行为序列进行相似度计算，通过设定相似度阈值的方法取相似度比较高的一些职位送到更新模块中来模拟用户点击了MAB算法推荐出来的职位，然后依照相应的权重对用户向量进行更新。另外一部分是将MAB试探的用户属性与用户真实的画像和简历进行相似度计算。通过这部分计算，我们可以得到简历匹配度、画像相似度等指标，并将这部分结果送到评估模块中。
对于整个离线模拟系统，如果我们将其和强化学习算法的关键点进行一个映射的话，状态就是用户向量，我们需要对其进行维护与更新；策略就是强化学习学习的策略，系统在算法模块会根据状态给出的相应的一些action；决策模块负责的离线模拟，就是接受算法输出的一个action并给出对应的一些reward。
在离线评估及调参中，我们主要关注用户结构化信息的匹配度以及用户画像信息的相似度。结构化信息实际上就是用户的简历，我们希望推荐的职位与用户真实信息尽量匹配。用户行为画像主要是用户在平台上交互过的职位的职类信息。每一轮MAB算法推荐出来的职位的类别可以与两部分信息进行相似评分计算。最终的分数是两部分分数的加权和。
我们在离线系统中关注的点实际上与强化学习在线上的部署目标一致，即收敛速度与最终相似度得分。通过实验损失变化我们可以发现系统一开始得分比较低，随着迭代次数的增加，即我们离线模拟的用户和MAB的交互次数增加后，用户相似度会收敛到一个相对较好的得分，且收敛情况比较稳定。
我们离线模拟实验主要针对三点进行调整实验。首先是不同action的设计，比如我们可以选择桶的个数是可以调整的，或者系统给出的用户状态维度也可以不同。其次，我们也可以尝试不同的策略算法，比如epsilon-Greedy算法、UCB算法或者汤普森采样算法等。第三，我们可以调整具体MAB算法的参数，通过离线实验选取最佳参数，并最终将其部署到线上。
4. 线上流转
对于线上流转系统的实现方案，主要有以下几点：
职位桶和更新向量：线上使用redis进行存储，更新频率是天粒度的。天级更新可以保证职位桶和桶与用户属性的映射与线上平台用户属性保持基本一致；
实时用户行为序列：使用spark streaming来记录用户关键的行为；
用户状态：使用redis存储，进行实时的读写；
日志系统：在线记录用户的状态和算法模块采取的动作，然后我们通过一些串联信息离线关联到reward，使得我们在日志中可以拿到状态、动作和收益，进而可以使得系统在后续使用这些数据采用强化学习算法进行离线建模和实验。
线上流转和离线实验流程基本一致，但我们在其中加入了状态惰性更新的思路。用户向量的更新不是在用户行为触发的实时流处更新，而是在用户进入推荐系统的时候进行更新。在用户进入推荐系统时，我们先判断用户之前是否存在用户向量，若不存在用户向量则表明其是一个新用户，我们需要对它进行初始化，否则我们去实时流中获取用户的行为序列，然后进行相应的更新。
这样的设计使得系统的逻辑主要集中在推荐侧，减少实时流的计算成本，并且系统上线或者策略迭代时我们只需要关心推荐系统这一侧的工程代码，使得维护成本大幅减低。整个系统耗时目前比较低，可以比较好地满足我们目前的需求。用户reward的获取时间，即用户这次点击和推荐职位下一次刷新之间的间隔延迟目前是小于5秒的，也比较符合平台的用户习惯，即用户点击一个职位详情，浏览5秒后退出来刷新职位推荐列表，这时候用户的行为会被我们的更新机制捕捉。用户向量整体的更新率超过95%，即用户只要有操作，它的向量基本上都会被我们的系统所更新。
5. 效果收益
最后是线上指标的介绍。对于冷启动用户，他们在平台整体用户的占比较少，我们不关心他们贡献出多少点击或者贡献出多少简历，而更关心他们有多少人最终发生了转化行为，也就是最终发生投递及转化为有信息的用户占比。所以在线上指标的设计上，我们更关注uv维度的转化效率。经过A/B实验，我们可以看到在点击uv占比和投递uv占比这两部分指标上，我们采用强化学习算法都取得了比较明显的提升，特别是对于用户的首次投递转化提升了大约8%。
本次分享主要介绍我们使用了强化学习的方法对用户冷启动问题进行了建模，并且实现了上下文MAB的召回策略，取得了比较好的线上效果。此外，还建立了一个基于强化学习的离线模拟系统，使得我们可以离线进行思路验证和算法探索。
对于后续的优化主要分为两个方面：
首先，我们希望将目前基于强化学习的召回业务覆盖的用户群体从新用户扩展到全部用户。这样其实会多出来两部分用户：已经建立简历的新用户和已经具有精确画像的老用户。针对前者，我们需要最大化这部分群体的转化效果；而对于后者，我们希望能发掘出他的兴趣，在多样性层面进行更多探索。
第二点，强化学习可以在其他场景进行应用，例如多目标参数融合，重排场景多样性控制等，目前业界也有很多成功的实践可以借鉴。
Q：运用MAB算法之前会先对用户聚类，能否分享一下聚类的思路？
A：我们对用户的划分还是比较简单的。因为我们关注的用户群体是实际上没有建立简历的用户，所以强化学习算法线上面对的用户范围是这些没有建立简历的冷启动用户。
Q：请问连续决策过程中能否使用类似于RNN的结构？使用RNN是否也能取得对应的收益？在实际落地中是否有考虑？
A：决策的关键点集中在对于用户自身特征的刻画，即怎样利用现有的特征更好地学习用户的兴趣。其实在目前的一些强化学习算法中，它们在Q网络，以及后续的一些算法中使用到了RNN结构。这部分设计思路我们还在探索中。
Q：请问对于新用户冷启动问题中MAB算法中的汤普森采样算法，β参数是如何初始化的？
A：针对新用户，参数初始化最简单的方式就是将β分布的两个参数都置为1，即将它看成一个均匀分布，它落入每一个桶的概率都是相同的。
Q：能不能详细说一下线上用户向量的更新方法和线上流转的流程？
A：首先，针对用户属性和职位桶的映射关系的设计，我们基于群体画像的思路，也就是说我们会根据用户在平台上的一系列行为（点击、投递、IM电话等）以及用户侧的简历信息（包含地域、性别、年龄等），与职位类目体系进行关联分析。我们目前采用较为简单的聚类作为关联分析的方法，通过此来建立出不同用户属性到相应的职位类的映射，然后通过映射在线上进行更新。对于线上的参数，它的更新完全在线上进行。线上的参数由两部分组成：一个是模型本身的参数，主要是设计的算法使用用户的交互行为序列进行学习；另一部分是算法的超参数，比如探索-利用概率，以及桶的数量设置等，这部分参数是我们离线进行调试后再部署至线上系统，然后观察A/B实验的效果进行进一步调整，直至模型在A/B实验中效果比较稳定后便将其固定。
Q：对于新用户冷启动策略上线后的评估指标，关注的重点是集合转化率吗？
A：我们关注的重点是以业务为导向的，即我们关注用户能否在我们的平台上留下来。而平台主要的一些连接贡献是老用户产生的，不适合作为评估指标。所以我们更加关注新用户是否对我们平台具有好感，进而使得用户进行转化。这对应着uv维度的转化效率，即加入策略后所有新用户中能够多多少人产生点击行为，能够多多少人发生简历创建和投递行为。
今天的分享就到这里，谢谢大家。
在文末分享、点赞、在看，给个3连击呗~
分享嘉宾：
🧐分享、点赞、在看，给个3连击呗！👇
本文分享自微信公众号 - 58技术（architects_58）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
