深度强化学习应用于推荐排序

京东与密歇根州立大学合作发表论文,Deep Reinforcement Learning for List-wise Recommendations,介绍了如何在其推荐排序中使用深度强化学习。阿里也推出了电子书<强化学习在阿里的技术演进与业务创新>,介绍了强化学习在搜索场景、推荐场景、智能客服、广告系统的实践。下面记录自己对将如何将强化学习应用到推荐排序的理解。

1.京东 Deep Reinforcement Learning for List-wise Recommendations

1.1 问题描述

将推荐过程可视作为一个马尔科夫过程 (Markov Decision Process),那么 - 状态空间S: 一个用户的按时间排序的商品历史浏览记录定义为状态$s_t=\{s_t^1,...,s_t^N\} \in S$。 - 动作空间A: 在时间t时刻向用户推荐的商品列表定义为动作$a_t=\{a_t^1,...,a_T^K\} \in A$。这里K表示商品个数。注意到这里,因为推荐的商品数量众多,导致动作空间巨大。 - Reward R: 在经过推荐代理在状态$s_t$采取动作$a_t$后,用户所采取的略过、点击或购买的行为。这里推荐代理接收到reward $r(s_t,a_t)$。 - 转换概率P: 即当推荐代理采用动作$a_t$后,从状态$s_t$向状态$s_{t+1}$转移的概率$p(s_{t+1}|s_t,a_t)$. - 折扣因子$\gamma$:即在计算所有动作的回报时,各步的折扣因子。

上面在表示商品时,一般使用商品的离散序列号来表示,这样子会丧失商品之间的关系。所以这里使用 表达学习(represent learning,类似于 word2vec),将商品视为word,浏览序列视为 sentence,将商品训练表达为低维向量。

马尔科夫过程图示如下。

Snip20180303_2.png

1.2 Actor-Critic算法

Actor-Critic算法中,Actor 更新策略,用来调整策略函数的参数𝜽,即决定特定状态下的最佳动作。 Critic 更新价值,评估Actor估计出来的策略函数。这里Critic使用Q-Learning 算法。所采用的这种Actor-Critic适宜处理这种状态空间巨大的问题。 如下图所示。

image.png

1.3 在线环境模拟器

不同于将 Deep Q-learning 方法来玩 Atari 游戏,它可以采取任意动作,并马上得到反馈。将强化学习应用到在线推荐,不上线是难以得到反馈的。所以这里采用了离线训练,论文提出了一种在线环境模拟器,通过用户历史记录来训练强化学习。

我们来回顾一下推荐过程。给定用户当前状态$s_t$,推荐系统推荐商品列表$a_t$给用户。用户浏览商品后给予反馈,即略过/点击/下单。推荐系统接收到回报$r(s_t,a_t)$。模拟器的任务是基于当于当前状态和选定的动作,预测其回报,即$f:(s_t,a_t) \rightarrow r_t$

那么这里存在一个问题,用户浏览过的商品是稀疏的,对于一个不在任何浏览历史里的商品,如何得到其回报呢。

假设有集合$M=\{m_1,m_2,...\}$来存储用户的历史浏览记录,这里$m_i$表示一个用户与 agent 交互的三元组$((s_i,a_i) \rightarrow r_i)$。集合$M$可以通过对用户浏览记录滑动窗口而取到。例如,推荐系统推荐了5个商品给用户${a_1,...,a_5}$,如果用户点击了商品$a_1$和下单$a_5$,那么更新状态为$\{s^3,...s^N,a_1,a_5\}$

然后我们计算 state-action对(state-action pair)的相似度。 这里state-action对用$p_t(s_t,a_t)$来表示。计算两 state-action 对的相似度仍以 cos值计算。 $$Cosine(pt,mi)=\alpha \frac{st,si^T}{||st|||si||}+(1-\alpha)\frac{at,ai^T}{||at|||ai||}$$ 这里参数$\alpha$控制状态与动作的比例。

这里面提到协同过滤的思想,用户如果有相似的兴趣(即这里的状态),那么对于相似的商品会有相似的点击等行为。对于上式,如果$p_t$$m_i$相似,那么 $p_t$的回报与$m_i$的回报$r_i$的关系可定义为 $$P(pt\rightarrow ri)=\frac{Cosine(pt,mi)}{\sum Cosine(pt,mj)}, m_j\in M$$

1.4 Actor部分

Actor 部分更新策略。首先将状态映射到特征向量,如下式

$$f{\theta^{\pi}}:st \rightarrow w_t $$

这里$f_{\theta^\pi}$是由参数$\theta^\pi$确定的函数,这里可选择 DNN作为产生权重参数的函数。

随之是基于上步的权重向量而产生动作,如下式

$$socrei=wt^ke_i^T$$

其中$e_i$是商品的 embedding vector。这里推荐系统根据商品的得分,即可以选择出得分最高的商品进行推荐了。

1.5 Critic部分

Critic部分这里使用了 DQN对当前的state以及action的表现进行估计,得到value function,用来给actor更新梯度。

Critic部分对参数$θ_u$的更新即采用DQN中的TD error方式,loss function公式为: $$L(\thetau)=E[(yt-Q(st,at; \theta_u))^2]$$

其中,$y_t=E[r_t+\gamma Q'(s_{t+1},a_{t+1}; \theta^{u'})|s_t,a_t]$为目标函数。

2.基于强化学习的实时搜索排序策略调控

其整体算法设计与< Deep Reinforcement Learning for List-wise Recommendations>类似,均采用了 actor-critic 算法。有一些不同的地方。 - 在表示用户状态时,把⽤户在最近⼀段时间内点击的商品的特征(包括:价格、转化率、销量等)作为当前Agent感知到的状态,令s 代表状态,则有 $$s=(price1;cvr1;sale1;...pricen;cvrn;sale_n)$$ 另外还加入用户特征。 - 利⽤奖赏塑形(Reward Shaping)⽅法对奖赏函数的表达进⾏丰富,不仅提高CTR这一目标,也提高CVR. - 值函数学习中引入优势函数(Advantage Function)。