作者 | mokong 搜狐技术产品

导读

      随着AlphaGO在围棋界接连战胜世界冠军，其背后的技术-强化学习逐渐获得学术界、工业界的青睐。在新闻推荐任务中，传统的推荐算法无法考虑单个请求内新闻之间的关联，也无法考虑多个请求之间的关系，而强化学习，通过学习推荐策略给解决上述问题带来了可能。

1.强化学习理论简单回顾

1.1基本概念

强化学习是人工智能的一大重要分支，模拟的是人类通用的解决序列决策问题的思维，它的总体目标是通过和环境的不断交互，选择一系列的行为让整体获得收益的最大化（虽然有可能在某个单步执行的时候收益并不是最大）。如图1-1所示，强化学习主要包括Agent、Action、Environment、State、Reward 5个主体。

图1-1. 强化学习整体框图

Agent通过从Environment观测到的State和Reward，会执行一个Action（这个Action通过策略π获得）。Environment则会产生新的State和Reward，而Agent通过新的反馈执行下一步的行为，如此往复，这就是强化学习的工作过程。强化学习的最终目标是最大化Value Function(v_\pi(s))或者Action-Value Function (q_\pi(s,a))从而学到一组最优的策略。

1.2和有监督学习的区别

有监督学习指的是对每个样本都带有标注信息的任务，例如图像分类，目标检测，ctr预估等等。它和强化学习有显著的不同，主要体现在以下几点：

① 有监督学习中含有类别，数值等作为ground truth。强化学习没有，这些目标信息是通过和环境交互中获得。

② 强化学习中的反馈（Reward）通常是延迟的，有监督学习可以立即获得。

③ 强化学习中，一系列State，Action时间上高度相关，动态产生。有监督学习中仅仅取决于实现定义好的样本。

④ 强化学习中当前执行的Action影响未来。有监督学习只是简单的拟合当前样本的数据，和过去无关，和未来无关。

1.3强化学习方法概览

对于State离散有限，Action离散有限较为简单的问题，可以使用查表的方法保存各种状态下的V值或是Q值。此种情况下，如果模型已知（状态转移方程已知），可以使用的方法包括动态规划，策略迭代和值迭代等等。如果模型未知（model free），则可以使用Monte-Carlo，Q-learning和Sarsa等方法。

然而在实际情况中，State通常连续或者搜索空间无穷，所以不能简单的利用上述的查表法，而得借助于神经网络对State进行建模。这种情况下，如果Action离散，且只有1维，现有的在学术界和工业界被证明工作良好的方法有DQN，DDQN和其他针对DQN改进的方法，这类算法都属于值函数近似，或者是REINFORCE，Actor-Critic等Policy Gradient的方法。值函数近似的实质是拟合Q值，策略梯度则是关注最优的Action本身。

如果Action连续或者离散高维，则可以使用DPG、DDPG等确定性方法，它们在机器人的连续控制中有着成功的运用。

特别强调的一点是值函估计中Q-learning近似的方法是对每个State-Action对预测Q值，然后选择使得Q值最大的Action，限定了Action为离散低维，如果Action高维或者连续，搜索出是Q最大的Action会非常困难。

策略梯度这一类基于策略的方法则为直接对策略建模，模型的输出即为执行各Action的概率（stochastic policies），或者输出单个确定的Action (deterministic policies)。它的优势是更好的收敛特性和对于Action是高维或连续空间更有效（Q-learning其实做不了）。相应的略势为容易收敛到局部最小值（这个问题在深度学习中更常见）及策略评估的高方差。图1-2展示了强化学习方法的简单汇总。

图1-2. 强化学习方法纵览

2.新闻推荐建模

2.1 新闻推荐主体定义

如图2-1所示，一次完整的推荐过程包含以下几个过程：一个用户点击app底部刷新或者下拉，后台获取到用户请求，并根据用户的标签召回候选新闻，推荐引擎则对候选新闻进行排序，最终给用户推出10条新闻，如此往复，直到用户关闭app，停止浏览新闻。如果将用户持续浏览新闻的推荐过程看成一个序列决策过程，就可以通过强化学习学习每一次推荐的最佳策略，从而使得用户从开始打开app开始到关闭app这段时间内的点击量最高

图2-1.搜狐资讯版一次推荐

整体过程中各部分主体定义如下：

Agent：推荐引擎。

Environment：用户。

Reward：如果一条新闻被点击，计+1，否则为0。一次推荐中10条新闻被点击的新闻个数作为Reward。

State：包含3个部分，分别是用户标签、候选新闻的新闻标签和用户前4屏的点击历史（如果没有就置0）。

Action：推出的10篇新闻。

2.2 和ctr预估的区别

Ctr预估只考虑预测新闻的点击率，不考虑具体的推荐策略。利用ctr进行的推荐的流程通常是预测候选新闻的ctr，策略部分是人为规定的规则，可以简单的取top10或者经过各种过滤，去掉重复，规定不同大类下的新闻个数之后取10个新闻，然后推荐给用户。强化学习可以说一方面在给新闻预测得分的同时，另一方面考虑了推荐的策略，也就是说策略部分也由模型自己学到。

Ctr模型的推荐过程只考虑了单次推荐里用户的点击率，对于不同的Session之间无法建模。相反，强化学习的本质是用于解决序列决策问题，在给用户第一次推荐的时候，就可以考虑之后第5次、第10次推荐的收益（由参数决定），让用户在整个浏览app的过程中的点击量最高，这一点是ctr完全无法胜任的。

当然强化学习也有缺点，就是训练复杂，往往需要更细致的参数设置和更多训练trick才可能有效。Ctr预测则是一个完全常规的有监督问题，输入用户和新闻特征，拟合ctr，训练起来相对强化学习简单许多。

3.具体方法

3.1 Deep Deterministic Policy Gradient (DDPG)

方法概述:

随机策略是在一个状态下以概率的形式执行可能行为，确定性策略是模型的输出即为一个选中的Action。各自定义如下：

其中θ表示网络的参数，s，a分别为状态和行为。

参考原论文中的表示方法，策略梯度的损失函数或者目标函数定义成：

其中s服从ρ分布，a由\pi_\theta决定，公式以积分的形式表示目标函数（默认了连续空间）。

根据Q-learning的定义，策略提升的时候应该选择使得Q值最大的Action，在Action为连续值的时候，这一步的操作会比较困难，所以只能在使得Q增大的梯度方向走一小步，迭代更新。

参数更新公式如下：

根据链式法则，梯度方向由Q对a的导数和a对θ的导数相乘而得(如红框标注)。Action是Actor和Critic之间的结合部分，梯度从Critic通过Action传给Actor，也就决定了Action是连续的值，可以高维。

框架图

图3-1. DDPG新闻推荐框图

如图3-1所示，整个框架分为Actor和Critic两个部分，Actor负责输出Action，再传入到Critic中进行Q值的预测。

nfm_for_candidates_user模块表示的是候选新闻和用户前4屏的点击历史（outer_history）、用户标签的匹配程度，内部借助于Neural Factorization Machine (NFM) 模型进行建模，将匹配程度表示一个向量candidates_user_match。其中NFM模型简单有效，在Ctr预估任务中表现良好。

Policy模块表示的策略部分。因为一次请求会推出10条新闻，为了建模这10条新闻的顺序关系，网络结构采用RNN完成，每步输出选中的新闻索引（news_idx）和选中的概率p，且每选一篇新闻都要考虑之前选出来的新闻（inner_history）。此处的inner_history保存一个请求内已经选出的新闻。每一步选出一篇新闻之后，将这篇新闻从候选新闻中移除，并加入inner_hisory，最后输出这篇新闻被选中的概率和更新状态。

Step模块展示的是每一步的模型，由NFM模块和神经网络搭建。

Critic部分负责预测V值，其包含两个部分，nfm_for_recommended_user表达的是选出来的新闻和用户标签及点击历史的匹配程度，而nfm_for_recommended_news则是选出的新闻和上一步Actor输出的Action结合的部分，共同预测V值。 最后position表示的是用户从开始浏览新闻在刷的第几屏。

一次推出10条新闻的Action可以看作是一个10维的向量，每一维代表某条新闻被选中的概率，于是整体就可以利用DDPG的方法实现了（DDPG适用于Action为连续高维的情况）。

选择新闻是通过argmax进行操作，它仅仅是一个选择的过程，不是数值上操作，因此不可导。为了能够让Critic和Actor之间通过Action连通起来，只有用上新闻被选中的概率p，才能让梯度通过Critic反传到Actor。于是概率p在Critic中与被选中的新闻标签做了相乘运算。

在如何表示新闻的问题上，新闻本身的内容和标题利用RNN建模，用户的点击历史同样可以用RNN进行序列建模，虽然这种表达方式可以尽可能保存新闻的信息，但是计算量非常复杂，线上模型难以承受，因此，直接利用新闻标签（由其他线上任务预先完成）表示新闻简单易行，也足以满足推荐的要求。

3.2 Deep Q Network(DQN) / Double DQN(DDQN)

方法概述:

著名的DQN算法是一种值函数近似的算法。在强化学习中，利用神经网络对值函数进行近似会造成学习过程的不稳定甚至不收敛，于是在DQN中采用了很多技巧，才使得Q-learning在实际问题中真正有效。所谓的值函数进行就是用模型来估计V或者Q：

其中w为近似模型的参数，例如神经网络的参数。再使用和MC 或者 TD learning类似的思想进行参数的更新算法中关键的亮点，一是Replay Buffer对样本（transition）进行混合，减少连续时间上的相关性；二是采用Target Network，它的结构和训练的网络完全一致，但保存了训练网络中参数的缓存，目的是为了是学习更加稳定，这样不至于让网络参数陷入局部最优。

Double DQN（DDQN）则主要改进DQN中对Q高估的问题。通常Q-leaning中更新公式：

其中max操作会引起值函数的高估，这个问题被称为：maximization bias，overestimate action values。

在上述更新公式中，有一个很明显的问题在于，Action的选择和Q值的估计都是一个模型，解决的办法就是把两者分开，选择Action和Q值的估计使用不同的模型。倘若用DQN中的Target Network来估计Q值，用DQN中Online Network选择Action，就变成了DDQN。更新公式如下：

框架图:

图3-2. 新闻推荐DQN框图

和DDPG相比，DQN去掉了Critic，简化了很多。中间每一步step的最后去掉了softmax，对每一篇新闻预测一个值，而不是概率，然后将选中的10篇新闻的数值通过加和得到最后的value。这样的做法和标准的DQN有些出入，它每次只是选择一个1维的Action。这里新闻推荐的Action则是一个10维的向量，正确的做法是对10篇新闻做路径搜索，得到一条总的Q值最大的路径作为Action。但是高维路径搜索的代价过高，所以这里选择了简化，在每一步挑出数值最大的新闻，来近似完成选择使得Q值最大的Action。

另外一种解决方案则是将Action定义成选择一条新闻。例如，原本两个请求是2个Action，一次Action为10维的向量，现在变为将两个向量拼接到一起构成20个1维的Action，如此就可以完全使用DQN来进行学习。

模型很容易稳定，如下图中的实验结果，上为预测值，下为真实值。

图3-3. DQN训练结果

3.3、总结

对于上述两种算法，依然有以下几点问题。

1、在线训练和离线训练

DDPG用到了新闻被选中的概率，这个概率在离线数据（主要是请求点击日志）中是不存在的。问题的关键不在于on-policy还是off-policy，而在于离线数据中的Action是否可以直接用来作为模型更新的Action。 例如DDPG中的Actor的输出包含了新闻被选中的概率，然而离线数据中新闻只有选中和没选中，不是概率，所以无法直接拿来更新模型。考虑到直接上线会在初期严重影响用户体验，因此DDPG不好直接在线训练。

解决这个问题的方法是预训练。可以从大量的离线数据中选取高Reward的状态行为数据(s,a)，直接进行有监督学习训练一个Actor网络，之后利用这个Actor的参数进行初始化。

DQN没有这个问题，它可以直接使用其他策略产生的数据进行训练。但是得设置Action为单独一条新闻才是标准的DQN。

综上，线上模型采用训练更为简单的DQN模型。

2、高效样本采样

强化学习中无效的行为远远大于有效的行为，探索利用困境容易导致模型学习很慢。DQN的一种改进Priority Replay Buffer可以让模型更多的去拟合那些TD-error较大的样本，有效降低loss。

3、训练过程的不稳定

不合理的超参数的设置有可能会带来很大的问题。随着训练的增加，Q值估计越来越大，尖刺会越来越多，相应的loss也越大，有可能会在某个时间段崩溃。