强化学习在推荐系统的应用
一、业务介绍
1.1 业务背景介绍
1.2 首页推荐的系统架构
二、首推场景面临的挑战
三、首推场景的实现方案
3.1 整体方案设计
3.2 强化学习方法的选择
3.3 DPP算法原理的整理
3.4 具体方案的实现
3.5 离线流程及线上部署
四、总结
五、参考资料
一、业务介绍
1.1 业务背景介绍
电子商务行业，无论是新品电商还是二手电商一直围绕着“多、快、好、省”四字方针，有重点的布局和设计战略打法。转转也不例外，“省”一直是转转立足之本，而坚定走CBC战略和坚持官方验打出了“好”，无论是口碑还是销量都在阶跃式上行变好。同时转转作为绿色循环经济的先行者，一直致力于二手平台的建设，平台需要有充足的货品保障，才能增加平台可逛性和用户粘性。省和好同步构建进行的过程中，“多”字方针也势在必行。首页推荐是“多”字方针主要承接场景，接下来会从整体系统、面临的挑战及解法来介绍首推场景。
1.2 首页推荐的系统架构
转转推荐系统架构如下图，包括触发模块、召回模块、粗排模块、精排模块、重排序模块。承载着卖场“想得起、有的逛”的心智构建任务。
本次方案的设计主要在ZZ-Rerank模块和ZZ-Rank模块（红框圈定）来进行。其中ZZ-Rerank是重排序模块，负责多样性、打散策略、正负反馈机制等工作，ZZ-Rank包括了粗排模块和流量池模块。
二、首推场景面临的挑战
首页推荐作为用户进入 APP 的第一个页面，是天然流量场，也是整个 APP 灵活性最高的场，担负着流量高效承接和合理分发的任务。灵活性高也就意味不确定性高，因此同时也要求有足够的发现性和新颖性，满足不同用户群逛的需求，去鼓励用户与平台建立更多连接。流量承接和分发的好坏可以从流量效率和用户体验两个角度出发，其中最主要的两个优化点为：一是不同品类间流量效率的可比性。
- 二手一机一拍属性导致不同品类间的剩余价值不同，物料数有较大差异；
- 为了保证官方验，履约能力强弱也会制约品类的丰富度和物料的增长速度；
- 另外心智传达让品类间的物料数以及品类间的流量需求差异较大，进而影响后链路的效果数据。例如曝光、点击、下单等有效行为在不同品类间也有较大差异和不同的稀疏程度。
二是二手电商官方验背景下的多样性。
- 官方验履约过程中，首图的样式统一由质检部门实物拍摄而成，同品类的样式基本都是统一的。相比于新品电商的丰富性也有较大差异。左图1和2是转转手机和平板的首图，整体上看手机和平板同品类比较文案就比较单一趋同。而右1是京东手机首图，商家可以自己设计文案创意。如下图所示：
三、首推场景的实现方案
3.1 整体方案设计
整体方案是根据转转当前业务所处的发展阶段及整体优化目标进行设计的，流程图如下图所示。本文介绍的方案需要在重排、粗排和流量池阶段同时保证。第一阶段强化学习方法在重排序模块实现，第二阶段适配后的DPP策略由粗排后的流量池模块承接。第二阶段是第一阶段的通路保证。第一阶段由强化学习方法来解决可比性，同时联合DPP组件兼顾相关性和多样性。第二阶段是流量池阶段，负责通路建设，保障足量高质量的物料能够流入下游。保障不同品类内部的多样性及品类内部的低一级类目的相关性。粗排阶段流量效率的可比性由粗排模型和流量池短暂承接，最终
3.2 强化学习方法的选择
强化学习方法有很多种[1]，按是否为环境建模，分为 Model-Based 和 Model-Free 的方式。按迭代方式又分为Value-Based 和 Policy-Based。Value-Based比较经典的方法有的Q-learning、DQN及其变种，Policy-Based有的Policy-Gradient。两者结合的框架的Actor-Critic也是蓬勃发展的一种方法。经典算法有A2C、A3C、DDPG、PPO等，其中PPO(Proximal Policy Optimization)[2]也是本文选择的强化学习方法，一种Actor-Critic框架的深度强化学习算法，该方法广泛应用于业务场景中。作为OpenAI的默认算法，也从侧面证明了该算法的实用性。本文选择PPO算法有3个原因，一是该算法是On-Policy策略，可以适应动态变化的环境，使用最新的数据来更新策略。二是该方法同时引入重要性采样的思路，让该策略具有Off-Policy的特性，提高有价值数据的利用率和学习效率。三是首页推荐场景可以提供充足的探索机会，去权衡多样性和效率的平衡，去找到最优或接近最优的解法。
下图是PPO算法的设计实现流程，下面分为8步来介绍。
1、将环境信息s输入到Actor-New网络（假设action分布符合正态分布），会得到两个值，μ和σ。这两个值分别代表正态分布的均值和方差。通过这个具体的正态分布sample出来一个action， 再输入到环境中得到奖励r和下一步的状态s_，并存储[(s, a, r), …]。然后再将s_输入到Actor-New网络，循环上述步骤1，直到N步后存储了一定量的[(s, a, r), …]。整个过程是Actor-New网络没有更新。
2、将步骤1循环完最后一步得到的s_输入到Critic-Eval网络中，得到状态的v_值， 然后计算折扣奖励：Q[t](s, a) = r[t] + γ*r[t+1] + γ2 * r[t+1] + … + γT-t+1 * r[T-1] + γT-t * v_，得到Q = [Q[0], Q[1],…,Q[t],…,Q[T]]，其中T为最后一个时间步。
3、将存储的所有s组合输入到Critic-Eval网络中，得到所有状态的V值， 计算At = Q – V。
4、求c_loss = mean(square(At )), 然后反向传播更新Critic-Eval网络。
5、将存储的所有s组合输入Actor-Old和Actor-New网络(网络结构一样)，分别得到正态分布π-old和π-new，将存储的所有action组合为actions输入到正态分布π-old和π-new，得到每个actions对应的prob1和prob2，然后用prob2除以prob1得到important weight, 也就是ratio。
6、计算a_loss = mean(min((ratio* At, clip(ratio, 1-ξ, 1+ξ)* At)))，然后反向传播，更新actor-new网络。
7、循环5-6步骤，一定步后，结束循环。用Actor-New网络权重来更新Actor-Old网络。
8、循环1-7步骤。
3.3 DPP算法原理的整理
推荐场景的重排序阶段是组合优化问题的天然应用场。其中DPP(Determinantal Point Process)[3]算法将 Discrete Point Processes 问题里复杂的概率计算转换成简单的行列式计算，通过核矩阵(kernel matrix) 的行列式计算每一个子集的概率，有效地降低了问题的复杂度。这就节省了足够多的计算资源，去建模流量效率和用户体验的问题。更具体一些就是给用户推荐的商品相关性和多样性问题，可以统一建模去探索最优解。相关性：推荐给用户的商品与用户兴趣的匹配度的度量，可以通过pCTR或pCTCVR预估进行量化。多样性：衡量单个推荐列表中物品之间的差异程度。
1、构建业务的核矩阵
构建重排序候选集合的核矩阵 L，融合了相关性和多样性。L 是一个半正定矩阵，可以被分解为 L = 。每个列向量 可以分解为 =。其中：
- 为标量，表示item i与user之间的相关性，并且 >=0
- 为向量，表示item i的embedding，并且 = 1
核矩阵 L 中的元素可以被写成：
其中， 是商品 i 与商品 j 之间的相似度。
所以核矩阵 L 为:
2、目标融合：核矩阵行列式
其中， 是对角阵 (diagonal matrix)，对角向量(diagonal vector)是相关性度量向量 ，对角元素 表示用户 u 对物品 i 的兴趣偏好程度， 表示可被推荐的物品集合，S 是相似度矩阵，则核矩阵的行列式可以表示为:
取其对数：。
其中， 表示用户和商品的相关性，表示商品之间的多样性。
因此可以建模推荐商品集合的多样性以及相关性。
假设推荐给用户的商品子集为， 表示被商品子集， 索引的核矩阵的子矩阵，则商品子集 的相关性和多样性可以用下式度量:
3、DPP的MAP解法思路
推荐目标即如下MAP问题:
可以证明上式是个Submodular Maximization问题[4]。此问题函数满足如果 A 是 B 的子集，对于任何不属于 B 的元素x，满足: 。
Submodular 的无约束最大化问题(Submodular Maximization) 则是 NP 困难 (NP-Hard) 的。在实际模型应用中，贪心算法常常能得到超过近似比(非负：0.5，单调：1-）的性能保证，再加上贪心算法的高效和简洁，其在次模函数最大化优化问题中的应用极为广泛。Greedy Submodular Maximization算法求解过程简单来说就是每次从候选集中含心地选择一个能使边际收益最大的商品加入到最终的结果子集中，直到满足停止条件为止，即每次选择商品 j 添加到结果集中 中， 初始化为空集，商品 j 需要满足下面的等式(1):
其中行列式 直接求解复杂度较高，需要有巧妙的方法简化计算过程。假设 ， Cholesky 分解如下: 。其中 V 是一个可逆下三角矩阵。对于任意 ， 的Cholesky 分解可以定为等式(2)：
其中，等式右边右上角的子矩阵为 0 向量，是因为 V 是一个下三角矩阵。根据矩阵乘法公式，行向量 和标量 满足: 等式(3)
， 等式(4)。另外，根据等式(2)，可以得到等式(5):
因此，等式(1)可以简化为等式(6):
等式(6)被求解后，根据等式(2)， 的Cholesky 分解变成等式(7):
， 其中 和 是已经计算出来了的。当一个新item被添加到 之后， 的Cholesky因子可以被有效更新。即对于每个新增的 item i， 和 可以被增量更新。在等式(6)被求解后，将 和 定义为新的需求解的向量和标量，基中 。
， 由等式(8)得:
由等式(3)得:， 将其带入上式：
， 转制后得近似等式(9)：。由等式(4)得等式(10)：
式9，10实现了当一个新item被添加到 之后，对Cholesky因子的有效更新。 得到后便可根据 将最优的item放入到 。
最初， ，等式(5)意味着: 。
整个求解算法过程：
3.4 具体方案的实现
3.4.1 第一阶段-重排序模块-强化学习方法建模
强化学习MDP建模
消费者来首页推荐（可调控流量场景）的请求曝光行为轨迹，当做一个带约束的马尔科夫决策过程（CMDP)[0]， (𝑆, 𝐴, 𝑃, 𝑅,𝐶, 𝜌0, Γ)。
状态S：用户的当前状态为，一个128维的向量，由用户特征、商品特征及上下文特征组成。
- 用户特征：1+5+N品类的历史点击占比、收藏占比、加购、下单、支付占比，用户的属性特征性别、年龄、消费等级、城市等级等，1+5+N品类的某滑动窗口内曝光未点击区间，上一刷1+5+N的点击次数，当前用户对1+5+N品类的集中度等。
- 商品特征：上一刷的商品特征、400个候选商品的统计类特征。
- 上下文特征：week、周几、小时、请求次数、app停留时长等。
动作A：用户的动作空间，表示当前的动作，是一个10*（1+5+N）维的向量。
- 意义：对品类及品类内具体的商品偏好进行权重调整，让不同品类的预估效率（例如pCTR）具体可比性。
- 具体使用方式：针对DPP算法中整体优化目标中的相关性部分，即
**状态转移方程**：S X A → △(S) 表示状态转移，本次采用model-free的ppo算法，不考虑状态转移方程。
奖赏R： 定义了一个 m=1+5+N 维向量价值奖赏函数， = 。
- 针对业务的重要性和扶持程度调整系数，初始值均为1。
- 奖赏为点击数。
初始状态ρ0：以天为单位，第一次首页请求时的状态为初始状态。
折扣系数Γ： m代表各类奖赏的折扣系数构成的向量，值为0.99。
其它约束C：DPP算法中整体优化目标中的多样性部分，即
目标：最大化累计奖赏。
3.4.2 第二阶段-流量池模块-DPP组件的应用与适配
第二阶段-流量池模块，保障了系统链路上的路径通畅，为第一阶段的顺利进行打开空间，做好铺垫。同时考虑转转当前业务发展阶段，流量池模块的设计也符合现状。
保持整体优化目标不变：。
重排序阶段优化目标向上游转移，同时考虑相关性和多样性。
下面是流量池模块的设计思路：
多DPP组件的并行使用，为1+5+N品类，分别设计自己的DPP组件。
- 简化核矩阵L，每个品类的构建自己下一层级的one-hot向量，同品类相似度为1，不同品类的相似度为0。例如手机品类，下一级类目是品牌，品牌维度为m个，则one-hot向量为m维。
- MAP算法的时间复杂度由M)降为$O(NM)。
3.5 离线流程及线上部署
离线模拟器：
1、将粗排、流量池、精排的每次请求返回的日志落表，将重排序的线上规则复制到线下；
2、离线搭建推荐流程，从历史曝光的日志中取一周的数据并进行数据增强，用于构造离线模拟器。每个周期为一天、窗口时间间隔为 15min，也就是说一个周期内进行 96 步决策。
3、根据我们的状态和奖励定义，观测曝光日志和点击量，可比性 agent 可以与之交互来收集训练数据，同时也可以评估 agent 的效用。
评价指标 针对两个阶段，分别在不同层做独立的实验和贯穿性实验。
点击率：周期结束后的点击量与真实曝光量的比值，衡量整体效果；
累积奖励：这是一个反映强化学习算法效用的间接指标，衡量单uv行为量；
四、总结
首页推荐的工作总结一下，整体目标：优化相关性和多样性。在目标保持不变的前提下，又拆分为第一阶段和第二阶段。
第一阶段思路比较传统，在重排序用强化学习的思路解决不同品类间pCTR打分的可比性，同时联动DPP打散策略。
第二阶段是梳理系统链路的过程中发现瓶颈，需要将目标往上游迁移，保证下游有充足的高质量物料传递下去。DPP组件的使用也只是方法之一，也可以在粗排模型里设计多样性的目标，交给模型去权衡相关性和多样性。为什么选择DPP组件，是因为先有了流量池模块，它本身类似于重排模块。因此延续了重排的思路。
第二阶段包括粗排模型的升级以及流量池的构建。
- 粗排模型是PEPNet[5] + 双塔的思路，商品侧直接构建场景网络塔（多塔），相比于门控网络效果更立竿见影，同时分场景的独有特征也可以互不干扰的进行迭代。底层网络学到公共知识适用于各个场景，保持不变。
- 流量池又分为兴趣池、探索池及新品扶持池，通过新的方法去解决粗排阶段不同场景pCTR的可比性。以后有机会再介绍给大家。
五、参考资料
[1] Wang, Hao-nan, Ning Liu, Yi-yun Zhang, Da-wei Feng, Feng Huang, Dong-sheng Li, and Yi-ming Zhang. 2020. “Deep Reinforcement Learning: A Survey.” Frontiers of Information Technology & Electronic Engineering 21 (12): 1726–1744. doi:https://doi.org/10.1631/FITEE.1900533. [Crossref] [Web of Science ®], [Google Scholar]
[2] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
[3] Chen Laming, Zhang Guoxin, and Zhou Eric. 2018. Fast greedy map inference for determinantal point process to improve recommendation diversity. In Proceedings of the 32nd International Conference on Neural Information Processing. 5622–5633.
[4] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical programming, 14(1):265–294, 1978.
[5] Jianxin Chang, Chenbin Zhang, Yiqun Hui, Dewei Leng, Yanan Niu, Yang Song, and Kun Gai. 2023. PEPNet: Parameter and Embedding Personalized Network for Infusing with Personalized Prior Information.
更多好文：
想了解更多转转公司的业务实践，欢迎点击关注下方公众号：