读论文笔记——Jointly Learning to Recommend and Advertise

论文：Jointly Learning to Recommend and Advertise

链接：https://arxiv.org/pdf/2003.00097

作者：msu+头条

预备知识

强化学习：假定一个智能体（agent），在一个未知的环境中（当前状态state），采取了一个行动（action），然后收获了一个回报（reward），并进入了下一个状态。最终目的是求解一个策略让agent的回报最大化。

提出问题

1. 大多数平台将推荐和广告业务由不同的团队分开优化，这样可能降低整体性能
2. 优化的目标都是short term reward，比如点击率、观看时长，很难对long term reward建模

论文目的

1. 设计一个两级强化学习框架，联合优化推荐和广告策略。第一级得到推荐结果来优化用户长期体验，第二级在推荐list中插入广告，来平衡来自广告商的即时广告收入和对用户长期体验产生的负面影响。
2. 利用MDP（马尔可夫决策过程）的思想，两级强化学习框架RS和AS，与环境（用户）交互，产生rec-ad混合列表，并且使得累积反馈最大化。
   MDP(S,A,P,R,r):

• $S_t$St​——状态空间，包括时间t之前，用户浏览的所有推荐item和ad,以及时间t请求的上下文环境，AS的状态还包括RS产生的时间t的推荐list。
• $A_t$At​——动作空间，$at=(at^{rs},at^{as})$at=(atrs,atas),即RS的动作和AS的动作，RS的动作主要是生成推荐list, AS的动作包含三个有内在关联的动作（1，是否插入广告；2，插入哪个广告；3，在哪个位置插入广告）。
• $R_t$Rt​——反馈，在状态st，执行动作at之后，用户会浏览到推荐的list和ad, 并且给出即时反馈$rt(st,at^{rs})和rt(st,at^{as})$rt(st,atrs)和rt(st,atas).
• $P$P——转移概率，$P(s_{t+1}|s_t, a_t )$P(st+1​∣st​,at​)代表在状态$s_t$st​下执行动作$a_t$at​, 将转移到状态$s_{t+1}$st+1​的概率。
• $r$r——折扣因子，在对人类的试验中发现，人类对立即回报的偏爱会呈现接近于指数函数的增长，折扣因子用来模拟这样的一种认知模式，以模仿生物做出决策的过程。立即回报可以赚取比延迟回报更多的利息。折扣因子r为(0，1]，累计回报
  
  而累计回报在状态 s 处的期望值定义为
  
  通过公式可以看出，折扣因子对时间越近的状态回报值影响越小，所以时间近的状态对值函数影响更大，从而对决策结果影响更大。

问题定义

给定一个MDP，目标就是找到一个两级 $rec/ad$rec/ad $policy$policy $π = \{π_{rs} , π_{as} \}: S → A$π={πrs​,πas​}:S→A,使得用户累积回报最大。也就是同时优化用户体验和广告收益。

假设条件

1. 所有推荐list的长度一致
2. 每个推荐list最多只能插入一条广告
3. P(st+1|st, at, …, s1, a1) = P(st+1|st, at )

研究内容

1. 第一级模型RS（Deep Q-networks），在大规模item 空间n中如何选择推荐子集k（计算复杂度是A(n,k)排列，因为item的位置顺序也会有影响）
2. 第二级模型AS(DQN)，主要判定是否向当前推荐list插入广告，以及在哪个位置插入哪个广告。

Deep Q-networks for RS

2个挑战：

• 在At^rs中选择k个item,是一个排列问题A(At,k)，计算复杂度高
• 在两级的强化学习框架中怎样计算Q-function

解决方案

级联的Deep Q-network

1. RS中，state和action的特征的处理

• 一个state $s_t$st​包含用户的历史浏览信息（rec/ads）,以及本次请求的上下文信息
• 分别用两个带GRU的RNN网络来计算用户对rec和ad的偏好，用最后一层隐藏层的输出表示$p^{rec}$prec和$p^{ad}$pad
• $c_t$ct​表示当前请求的上下文环境
• state: $s_t = concat(p^{rec},p^{ad} , c_t )$st​=concat(prec,pad,ct​)

2. 级联的DQN for RS

• 序列化地产生推荐的item，以一种级联的方式，先产生第一个item，然后将它作为state输入网络，产生第二个item,依次类推，最终返回{a1,a2,…,ak}
• 通过级联的方式得到推荐list，可以将复杂度由$O(A(A_t,k))$O(A(At​,k))降低为$O(kA_t)$O(kAt​)
• 在级联得到推荐list时，每一次选出的$a_j$aj​,将在下一次的候选item集合中删除，避免重复选同一个item。

3. Q-function

• 若对于k个推荐item的选择，使用k个独立层的网络，当k很大时，参数空间巨大，难以计算。将k个独立的层用带GRU的RNN替换，RNN的第j个input就是第j个推荐的item的特征；RNN最后的输出就是推荐list的embedding。
• 保持如下限制条件：同样的状态下，给同一个用户，展示推荐list的子集，得到的q值是一致的。
  
  即：
  
  其中 $r_t(s_t, a^{rs}(1 : k) )$rt​(st​,ars(1:k))是奖励函数.

DQN for AS

3个挑战

1. AS需要完成3件事——是否插入广告、插入哪个广告、在哪个位置插入
2. 这3件事是相互依赖的，比如，只有先确定要插入广告，才能开始选择插入哪个广告，而目前的DQN模型无法做到
3. AS的目标不仅是最大化广告的收益，还要最小化对用户体验的负面影响。

解决方案

设计了一种新颖的Deep Q-network

1. AS中对state和action的特征的处理

• state除了与RS中一样的特征，还包含RS中输出的rec-list
• action为 $at^{as} = (at^{ad},at^{loc} )$atas=(atad,atloc)，ad是推荐的广告的embedding，loc为插入广告的位置
• 给定k个推荐item，有k+1个位置插入广告，故使用k+1维度的one hot向量来表示loc，$at^{loc}∈ R^{(k+1)}$atloc∈R(k+1)

2. novel DQN for AS

• 经典模型在此处的局限：(a)图输入state(包含$s_t$st​和$a_t^{rs}$atrs​)，输出k+1个位置的值。但是这只能确定最佳插入广告的位置，而不能确定插入哪个广告；(b)图输入$state(s_t,a_t^{rs})$state(st​,atrs​)和$action(a_t^{ad})$action(atad​)，然后输出ad对应的q值，但是这只能确定选择哪个广告最佳，而不能得到广告插入的位置。有一种方法，就是分别对每个ad增加位置信息（one hot）得到每个ad每个loc的q值，但是这样计算复杂，不适用。
• 新的模型结合上述两者的优点：©图所示，输入st（包括$a_t^{rs}$atrs​）和广告$a_t^{ad}$atad​，输出为k+1个位置的q值。
• ©图将输出的k+1个位置的q值，增加到k+2个，使得第一个位置的q值表示不插入广告的情况，并且，输入中at^ad，增加使用零向量表示不插入广告的情况。
• 将q-function分为value function $V(s_t)$V(st​)和advantage function $A(s_t,a_t^{ad})$A(st​,atad​). 因为是否插入广告，受RS给出的rec-list的质量的影响，而用户对插入广告的反映，则受到所有信息的影响。