Slate-based Recommender Systems 论文解读

Reinforcement Learning for Slate-based Recommender Systems: A Tractable Decomposition and Practical Methodology

论文地址：https://www.cs.toronto.edu/~cebly/Papers/SlateQ_IJCAI_2019.pdf

本博客对SlateQ论文进行了解读，如有错误请评论指正。

1. 论文算法介绍（第四、五章）

1.1. SlateQ: 基于强化学习的推荐列表分解技术

SlateQ算法将推荐列表(Slate)的整体生成 分解为了 生成单个推荐项再组成推荐列表。它的提出基于两个假设（论文第10页）：

1. SC(Single choice)
   用户一次只在推荐列表中点击一个推荐项或不点击任何推荐项
2. RTDS(Reward/transition dependence on selection)
   用户对推荐项的选择会产生不同的回报和状态转移

由上述两个假设，可以得到以下两个推论（论文11页公式12和13）：
$$R(s,A,i)=R(s,A^{\prime },i)=R(s,i)\forall A,A^{\prime }\text{containing}i$$$$P(s^{\prime }|s,A,i)=P(s^{\prime }|s,A^{\prime },i)=P(s^{\prime }|s,i)\forall A,A^{\prime }\text{containing}i$$

这两个公式表达了：无论推荐项 $i$ 出现在哪一个推荐列表中，只要它被用户选择了，那么它所产生的回报值和状态转移都是一样的。

在以上推论的前提下，论文利用马尔科夫决策过程模型(MDP)构造了推荐项辅助函数（论文11页公式14），用于计算在状态 $s$ 时推荐列表中单个推荐项的 LTV（long-term value，长期价值）：
$${\overline{Q}}^{\pi }(s,i)=R(s,i)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,i)V^{\pi }(s^{\prime })$$

在有了单个推荐项LTV的基础上，计算出推荐列表整体的LTV（论文11页Proposition 1），即所有推荐项LTV的期望值：
$$Q^{\pi }(s,A)=\sum _{i\in A}P(i|s,A){\overline{Q}}^{\pi }(s,i)$$

单个推荐项LTV值${\overline{Q}}^{\pi }(s,i)$可以用TD方法来更新（论文12页公式19）：$${\overline{Q}}^{\pi }(s,i)\leftarrow \alpha (r+\gamma \sum _{j\in A^{\prime }}P(j|s^{\prime },A^{\prime }){\overline{Q}}^{\pi }(s^{\prime },j))+(1-\alpha ){\overline{Q}}^{\pi }(s,i)$$

也可以用Q-Learning的方法来更新（论文13页公式20）：$$\overline{Q}(s,i)\leftarrow \alpha (r+\gamma \underset{A^{\prime }\in A}{\max }\sum _{j\in A^{\prime }}P(j|s^{\prime },A^{\prime })\overline{Q}(s^{\prime },j))+(1-\alpha )\overline{Q}(s,i)$$

显然，使用Q-Learning的方法来更新时可以选取到最大的$\overline{Q}(s,i)$，也就可以得到最优的$Q(s,A)$（论文13页公式Proposition 3）：$$Q(s,A)=\sum _{i\in A}P(i|s,A)\overline{Q}(s,i)$$

1.2. 用Q值对推荐列表进行优化

在已经明确可以通过组合单个推荐项得到整体推荐列表的情况下，我们具体怎么去得到最优的推荐列表$A$呢？这就涉及到对$Q(s,A)$的优化了。

如论文13页Proposition 3 和 论文14页公式21所示，对$Q(s,A)$的优化公式表示为：$$\underset{A\in I,|A|=k}{\max }Q(S,A)=\underset{A\in I,|A|=k}{\max }\sum _{i\in A}P(i|s,A)\overline{Q}(s,i)$$其中，$A\in I,|A|=k$表示推荐列表中的推荐项从整体数据集中选取而来，且推荐列表的长度为$k$（实际上在在线实验时$k$值不固定，参考论文30页第九章）。

论文提出了三种方法对$Q^{\pi }(s,A)$进行优化：
方法一：LP(Linear Program，线性规划)
定义（论文15页公式22和23）：$$\max \sum _{i\in I}\frac{x_{i}v(s,i)\overline{Q}(s,i)}{v(s,\perp )+{\sum }_j{x}_{j}v(s,j)}$$$$s.t.\sum _{i\in I}{x}_i=k;x_i\in 0,1,\forall i\in I$$其中，$x_i$表示推荐项$i$是否属于$A$，是则为1，否则为0；$v(s,i)$表示推荐项对用户的吸引力，可以是推荐项的评分或即时pCTR等；$x_j$和$v(s,j)$同理；$v(s,\perp )$表示空推荐对用户的吸引力。

公式（24-28）是对上述定义的简化，这里不作介绍。

方法二：Top-k
Top-k方法通过计算推荐项的$V=v(s,i)\overline{Q}(s,i)$，然后每次取$V$最大推荐项 $i$ 的进行推荐，最终组成推荐列表。

方法三：Greedy(贪心)
贪婪方法通过下列公式产生单个推荐项（论文16页），最终组成推荐列表：$$i=\underset{i\notin A^{\prime }}{\mathrm{argmax}}\frac{v(s,i)\overline{Q}(s,i)+{\sum }_{l<L}v(s,i_{(l)})\overline{Q}(s,i_{(l)})}{v(s,i)+v(s,\perp )+{\sum }_{l<L}v(s,i_{(l)})}$$其中，$i\notin A^{\prime }$表示新推荐的推荐项 $i$ 不属于已经推荐出去的推荐项；$L\in [1,k]$，表示已经推荐出去的推荐项个数。

Greedy方法可以看做是每进行一次推荐，就从推荐集合$I$中去除被推荐出去的项的Top-k方法。

1.3. 三种优化方法的比较

考虑以下例子，推荐列表大小$k=2$，待推荐集合$I$为（论文16页表格）:

1、用LP方法进行产生推荐项
V ( { a , ⊥ } ) = ∑ i ∈ I x i v ( s , i ) Q ‾ ( s , i ) v ( s , ⊥ ) + ∑ j x j v ( s , j ) = 1 × 2 × 0.8 + 0 1 + 1 × 2 + 0 = 1.6 3 = 0.53 V(\{a,\bot\})=\sum_{i\in I}\frac{x_iv(s,i)\overline{Q}(s,i)}{v(s,\bot)+\sum_{j}x_jv(s,j)}=\frac{1 \times 2 \times 0.8+0}{1+1\times2+0}=\frac{1.6}{3}=0.53 V({a,⊥})=i∈I∑​v(s,⊥)+∑j​xj​v(s,j)xi​v(s,i)Q​(s,i)​=1+1×2+01×2×0.8+0​=31.6​=0.53 V ( { b i , ⊥ } ) = ∑ i ∈ I x i v ( s , i ) Q ‾ ( s , i ) v ( s , ⊥ ) + ∑ j x j v ( s , j ) = 1 × 1 × 1 + 0 1 + 1 × 1 + 0 = 1 2 = 0.5 V(\{b_i,\bot\})=\sum_{i\in I}\frac{x_iv(s,i)\overline{Q}(s,i)}{v(s,\bot)+\sum_{j}x_jv(s,j)}=\frac{1 \times 1 \times 1+0}{1+1\times1+0}=\frac{1}{2}=0.5 V({bi​,⊥})=i∈I∑​v(s,⊥)+∑j​xj​v(s,j)xi​v(s,i)Q​(s,i)​=1+1×1+01×1×1+0​=21​=0.5 V ( { a , a } ) = ∑ i ∈ I x i v ( s , i ) Q ‾ ( s , i ) v ( s , ⊥ ) + ∑ j x j v ( s , j ) = 1 × 2 × 0.8 + 1 × 2 × 0.8 1 + 1 × 2 + 1 × 2 = 3.2 5 = 0.64 V(\{a,a\})=\sum_{i\in I}\frac{x_iv(s,i)\overline{Q}(s,i)}{v(s,\bot)+\sum_{j}x_jv(s,j)}=\frac{1 \times 2 \times 0.8 + 1 \times 2 \times 0.8}{1+1 \times 2 + 1\times2}=\frac{3.2}{5}=0.64 V({a,a})=i∈I∑​v(s,⊥)+∑j​xj​v(s,j)xi​v(s,i)Q​(s,i)​=1+1×2+1×21×2×0.8+1×2×0.8​=53.2​=0.64 V ( { a , b i } ) = ∑ i ∈ I x i v ( s , i ) Q ‾ ( s , i ) v ( s , ⊥ ) + ∑ j x j v ( s , j ) = 1 × 2 × 0.8 + 1 × 1 × 1 1 + 1 × 2 + 1 × 1 = 2.6 4 = 0.65 V(\{a,b_i\})=\sum_{i\in I}\frac{x_iv(s,i)\overline{Q}(s,i)}{v(s,\bot)+\sum_{j}x_jv(s,j)}=\frac{1 \times 2 \times 0.8 + 1 \times 1 \times 1}{1+1 \times 2 + 1\times1}=\frac{2.6}{4}=0.65 V({a,bi​})=i∈I∑​v(s,⊥)+∑j​xj​v(s,j)xi​v(s,i)Q​(s,i)​=1+1×2+1×11×2×0.8+1×1×1​=42.6​=0.65 V ( { b 1 , b 2 } ) = ∑ i ∈ I x i v ( s , i ) Q ‾ ( s , i ) v ( s , ⊥ ) + ∑ j x j v ( s , j ) = 1 × 1 × 1 + 1 × 1 × 1 1 + 1 × 1 + 1 × 1 = 2 3 = 0.67 V(\{b_1,b_2\})=\sum_{i\in I}\frac{x_iv(s,i)\overline{Q}(s,i)}{v(s,\bot)+\sum_{j}x_jv(s,j)}=\frac{1 \times 1 \times 1 + 1 \times 1 \times 1}{1+1 \times 1 + 1\times1}=\frac{2}{3}=0.67 V({b1​,b2​})=i∈I∑​v(s,⊥)+∑j​xj​v(s,j)xi​v(s,i)Q​(s,i)​=1+1×1+1×11×1×1+1×1×1​=32​=0.67

其中，$b_i$表示$b_1$或$b_2$。

显然为了可以得到$Q(s,A)$，应当推荐$b_1,b_2$组成推荐列表。

2、用Top-k方法进行产生推荐项
V ( { a , ⊥ } ) = v ( s , i ) Q ‾ ( s , i ) = 2 × 0.8 + 0 = 1.6 V(\{a,\bot\})=v(s,i)\overline{Q}(s,i)=2\times 0.8 + 0=1.6 V({a,⊥})=v(s,i)Q​(s,i)=2×0.8+0=1.6 V ( { b i , ⊥ } ) = v ( s , i ) Q ‾ ( s , i ) = 1 × 1 + 0 = 1 V(\{b_i,\bot\})=v(s,i)\overline{Q}(s,i)=1\times 1 + 0=1 V({bi​,⊥})=v(s,i)Q​(s,i)=1×1+0=1 V ( { a , a } ) = v ( s , i ) Q ‾ ( s , i ) = 2 × 0.8 + 2 × 0.8 = 3.2 V(\{a,a\})=v(s,i)\overline{Q}(s,i)=2\times 0.8 + 2\times 0.8=3.2 V({a,a})=v(s,i)Q​(s,i)=2×0.8+2×0.8=3.2 V ( { a , b i } ) = v ( s , i ) Q ‾ ( s , i ) = 2 × 0.8 + 1 × 1 = 2.6 V(\{a,b_i\})=v(s,i)\overline{Q}(s,i)=2\times 0.8 + 1\times 1=2.6 V({a,bi​})=v(s,i)Q​(s,i)=2×0.8+1×1=2.6 V ( { b 1 , b 2 } ) = v ( s , i ) Q ‾ ( s , i ) = 1 × 1 + 1 × 1 = 2 V(\{b_1,b_2\})=v(s,i)\overline{Q}(s,i)=1\times 1 + 1\times 1=2 V({b1​,b2​})=v(s,i)Q​(s,i)=1×1+1×1=2

显然为了可以得到$Q(s,A)$，应当推荐$a,a$组成推荐列表。

2、用Greedy方法进行产生推荐项

公式太长，不写了，很显然为了可以得到$Q(s,A)$，应当推荐出去$a,b_1$或$a,b_2$。

2. 论文算法的在线实现（第九章）

2.1. 两个重要组件

论文介绍的在线实验中定义了两个关键组件（论文28页）

1. 候选推荐项生成器
   从一个最匹配用户上下文(当前状态$s$)的大推荐数据集中生成一个含有数百个候选推荐项的小子集$I$；
2. 排名器
   将用户上下文(当前状态$s$)和推荐项特征 $i$ 输入进深度神经网络$\overline{Q}(s,i)$对候选推荐项进行评分和排名（使用LTV）

其中深度神经网络$\overline{Q}(s,i)$含有4个隐藏层（2048、1024、512、256），激活函数为ReLu。

2.2. SlateQ算法流程

2.2.1. 伪代码

论文29页Algorithm 1

2.2.2. 对伪代码的解释

1、参数

• $T$：算法迭代的次数
• $M$：更新标签神经网络${\overline{Q}}_{label}$的间隔频率参数
• $\gamma$：计算LTV时的时间折扣率。如果两个访问分别发生在时间$t_1$和 $t_2$，则在$t_2$处的奖励的相对折扣为${\gamma }^{t_2-t_1/c}$，其中$c$是控制折扣时间尺度的参数。
• ${\theta }_{main}$：主神经网络${\overline{Q}}_{main}$的参数
• ${\overline{Q}}_{main}$：主神经网络，用于预测项目的长期价值（LTV）
• ${\theta }_{label}$：标签神经网络${\overline{Q}}_{label}$的参数
• ${\theta }_{pctr}$：用于预测pCTR的神经网络参数（pCTR：每个推荐项的点击率，点击率：点击次数占展示次数的百分比）

2、输入

• $D_{training}=(s,A,C,L_{myopic},s^{\prime },A^{\prime })$：训练数据集（适用于Sarsa）
• $s$：当前状态。即用户的各类信息（例如，用户过去的历史记录、行为和响应以及静态用户属性）
• $A=(a_1,...,a_k)$：在状态$s$时的推荐列表，$a_i$表示单个的推荐项，$k$的大小可以不固定
• $C=(c_1,...,c_k)$：$c_i$表示用户是否点击了推荐项 $a_i$
• $L_{myopic}=(L_{myopic}^1,...,L_{myopic}^k)$：$L_{myopic}^i$表示推荐项$a_i$的短视价值（立即回报）
• $s^{\prime }$：下一个要转移过去的状态
• $A^{\prime }=(a_1^{\prime },...,a_k^{\prime })$：状态$s^{\prime }$时产生的推荐列表

3、输出
训练好的主神经网络${\overline{Q}}_{main}$，用于预测推荐项的长期价值

4、初始化
${\theta }_{label}=0$；
${\theta }_{main}$和${\theta }_{pctr}$随机初始化；

5、流程
5. 循环$T$次 $i=1,...,T$：
6. \qquad 若$i\text{mod}M=0$，则更新标签网络${\overline{Q}}_{label}$：
7. \qquad\qquad ${\theta }_{label}\leftarrow {\theta }_{main}$
9. \qquad\qquad 循环 取出每一个训练数据$(s,A,C,L_{myopic},s^{\prime },A^{\prime })\in D_{training}$
10. \qquad\qquad\qquad 循环 取出推荐列表中的每一个推荐项$a_i\in A$
11. \qquad\qquad\qquad\qquad 根据点击标签$c_i$更新${\theta }_{pctr}$
12. \qquad\qquad\qquad\qquad 若$a_i$被用户点击，则：
13. \qquad\qquad\qquad\qquad\qquad 更新pCTR：$pCTR(s^{\prime },a_i^{\prime },A^{\prime })\leftarrow \frac{pCTR(s^{\prime },a_i^{\prime })}{{\sum }_{a_i^{\prime }\in A}pCTR(s^{\prime },a_i^{\prime })}$
14. \qquad\qquad\qquad\qquad\qquad 更新项目的LTV：$l_{ltv}^i=l_{myopic}^i+{\sum }_{a_i^{\prime }\in A}pCTR(s^{\prime },a_i^{\prime },A^{\prime }){\overline{Q}}_{label}(s^{\prime },a_i^{\prime })$
15. \qquad\qquad\qquad\qquad\qquad 使用$l_{ltv}^i$更新主神经网络参数${\theta }_{main}$