Alex Beutel等人在KDD 2019《Fairness in Recommendation Ranking through Pairwise Comparisons》中提出pairwise比较来看fairness。具体方法如下:

介绍

我们希望什么样的推荐系统?推荐器对于将用户连接到网络上的相关内容、items或者信息来说很重要,用户、内容提供商、零售商、信息提供商都依赖这些系统,我们需要明白谁应该是否被支持很重要。在本paper中,我们主要关注一个推荐系统在关于items的under-ranking groups上的风险。例如,一个under-ranked的社交网络通过一个给定的demographic group发表,会限定在该group范围内可见。

对于分类(classification)的公平性度量(fairness metrics)有许多研究,每种metric都是恰当的,但对于推荐系统来说,这方面考虑的较少。在推荐系统中,公平性的研究是很有挑战性的,它们很复杂。通常包含了多个模型,必须平衡多个目标,由于存在很大、倾斜的稀疏性以及许多动态性(dynamics)很难评估。所有这些要点在推荐系统社区中很难解决,在提升推荐公平性上提出了额外的挑战。

一个挑战性的划分是介于:将推荐看成是一个pointwise prediction问题、将这些预测应用于排序列表的构建。pointwise recommenders会为每个item做出一个关于用户兴趣的预测,接着基于这些预测决定一个推荐排序(ranking)。该setup在实际中很常见,但大多数研究都是深入去缩小pointwise predictions和ranking construction间的构建。公平性会陷入进退两难的境地。最近围绕pointwise accuracy为中心的关于fairness metrics的研究[8,49],并不能表明产生的ranking是用户实际想看的。做为对比,[52,44,45,11]探索了什么是一个fair ranking,但都关注于非个性化排序(unpersonalized rankings),它们会考虑上items的相关度、并且大多数情况下需要使用上item group关系的一个后处理算法(post-processing algorithm),这在实际中通常是不可行的[10]。

另外,推荐系统的评估是很难的,因为系统的动态变化性。一个用户昨天感兴趣的东西,在明天可能会不感兴趣,我们只能通过一个用户的偏好来推荐一个item给他们。因而,metrics通常是对之前的推荐系统(previous)[3]是有偏的(biased:在统计上),大量研究会做无偏离线评估[43,42],由于存在很大的item space、以及极其稀疏的feedback、users和items的不断演化,很难进行评估。当尝试衡量推荐系统的公平性时,这些issues只能变得更显著;而当你尝试评估complete rankings时更甚。

我们通过一个pairwise recommendation fairness metric来解决所有的这些挑战。通过使用易运行、随机化的实验,我们可以得到关于用户偏好的无偏估计(unbiased estimates)。基于这些观察到的(observed) pairwise偏好,我们甚至都可以对一个pointwise的推荐系统的公平性进行measure,我们展示了这些metrics与排序效果直接相关。另外,我们提供了一种新的正则项(regularization term),结果表明它可以提升一个pointwise recommender的最终ranking fairness,如图1所示。我们在生产环境中的一个大规模推荐系统上进行测试,结果表明实际是有益的,并且理论上和经验上是可同时trade-offs的。我们的贡献有:

  • Pairwise Fairness:
  • Pairwise Regularization:
  • 真实实验:

2.相关工作

推荐系统:。。。

机器学习公平性(Machine Learning Fairness.):机器学习公平性主要关注分类问题的公平性,提出了许多定义。基于这些定义的group fairness,一个模型将两组样本进行比较,成为了最常见的结构,但研究者们展示了不同定义间的调节器。我们主要根据Hardt[23]的机会等式(equality of opportunity intuition),其中我们会关注不同groups上在accuracy上的差异。我们的metric更接近于构建在一个AUC-based 分类和回归问题上的fairness metrics,它由Dixon[18]提出,并在[12]中展开可以作为不同的Mann-Whitney U-tests。

Recommender System Fairness。在ranking和recommendation上的fairness上,已经有一些研究,但这些研究都从不同的视角出发。Zehlike[52]从排序公平性的目标出发,但没有考虑推荐系统(它的数据是很稀疏的)。相似的,Singh[44]采用一个full-ranking的公平性视角,可以通过一个后处理算法(post-processing) 对模型预测应用于推荐系统;接着[45]将它移到模型训练中。所有这些工作[52,44,45,11]关注于一个非个性化的信息检索系统,其中主要关注每个item的相关labels;我们关于的个性化推荐场景存在:数据稀疏性和biases。[8,49]则关注于CF pointwise accuracy跨不同groups的差异,但没有将这些metrics连接到最终的rankings上。

更多研究在统计等价(statistical parity),其中在一些应用上还有争议:items应跨不同groups以相同的rate被展示。Diversity、filter bubbles、feedback loops,以及机器学习的fairness,在本paper不是关注重点。

Fairness Optimization. 许多方法的提出是为了解决公平性问题。Post-processing可以提供优雅解法【23,44】,但通常需要已经对于所有样本的group memberships,这对于demographic数据来说几乎是未知的。然而,许多方法在分类训练期间来优化fairness metrics,比如:constriaint-based optimization、adversarial learning、以及通过模型预测的regularzation。我们构建了这些regularization方法来提升我们推荐系统的fairness属性。

3.推荐的pairwise fairness

我们考虑一个生产环境推荐系统,它会推荐一个关于K个items的个性化列表给用户。我们考虑一个cascading recommender,它会使用检索系统(retrieval systems)集合,后跟着一个排序系统(ranking system)。我们假设:retrival systems会从一个包含M个items的语料J中,返回一个关于的相关items的集合R,其中。排序模型(ranking model)接着必须进行打分,并对个items进行排序来得到最终的K items排序列表。这里,我们主要关注ranker的角色。

当做出一个推荐时,系统会为user i观察用户特征,和一个上下文特征集合c(比如时序(timing)、或设备信息);我们将它称为query:。另外,对于每个item ,我们观察到特征向量 ;这里,我们会包含对于item的稀疏表示或学到的embeddings,以及与该item相关的其它属性。ranker会基于user feedback(包含:clickes, ratings, 文上的停留时间,items的后续购买等)的估计执行ranking。对于我们的系统,我们会估计用户是否会在该item上的点击,以及在点击该item上的用户参与度(user engagement),比如:停留时间、购买、raitings。这样,我们的数据集包含了历史样本 。(注意,由于z是在一个点击之后的user engagement,如果没有点击发生,z=0)。D只包含了之前被推荐的样本。

ranker是一个模型,参数为;该模型被训练来预测用户参与度。最终,一个items的ranking会通过打分函数来生成,用户会从由g排序的相关items R中选取topK个items。

3.2 Fairness concerns的动机

在之前的讨论中,有许多公平性关注点在文献中有强调。在本paper中,我们主要关注items分组成为under-recommended的风险。例如,如果一个under-ranked的社交网络,通过一个给定的demographics group进行发表,它会限制分组在该服务上的可见性和参与度。如果一个网络的评估部分是个性化的,那么一个demographic group的用户评论也是under-ranked,接着该demographic会在该网络上有更少的话语权(voice)。在一个更抽象的层次上,我们假设,每个item j具有敏感属性。我们会measure:来自一个group上的items是否在系统上是under-ranked。

尽管并非是我们的主要关注点,这些issues可以user group concerns并列,如果一个items的group是否被一个特定的user group更偏好。该框架会显式扩展到包含user groups。如果每个user具有一个敏感属性,我们可以通过每个user group来计算所有以下的metrics,并计算跨groups的性能比较。例如,如果我们关注的是,一个社交网络是under-ranking,特定主题的items只限定于特定的demographic人群,我们可以比较:跨demographic groups的主题内容的under-ranking的degree。

3.3 Pairwise Fairness Metric

上述fairness目标看起来很重要,对于一个”under-ranked”的item来说,我们必须准确搞清它的含义。这里我们吸收了[23]的思想:一个classifier的fairness通过比较它的false postive rate and/or false negative rate进行量化。不同的是,给定一个item的label是postive的,classifier预测它为positive的probability。在分类中,由于模型预测可以通过一个预测定阀值进行比较,这可以有效工作。

在推荐系统中,一个positive prediction是不明确的,即使人们将分析限制在clicks(y)和ignore engagement(z)中。例如,如果一个item被点击,y=1,那么被预测的点击概率为,这是一个positive prediction吗?它可以被看成是一个0.4的under-prediction,如果其它items都具有一个预测的它仍是top-ranked item。因而,理解在pointwise predictions中的errors需要对比对于相同query的items预测。

我们开始定义了一个pairwise accuracy:一个clicked item的概率被排在另一个相关uncliked item之上,对于一个相同的query有:

…(1)

有了该定义,我们可以知道ranking系统会对cliked item进行rank的频次。出于简洁,我们使用来表示:对于query q,item j和间的预测比较;我们会隐掉项,但我们只考虑对于所有以下定义相关items间的比较。

对于余下的fairness研究,我们会关注groups间的相对performance,而非绝对performance。因而,我们可以比较:

也就是说,来自一个group 的items的PairwiseAccuarcy,要比来自另一个group 的PairwiseAccuarcy或高或低些。

这是一个直觉上的metric,这里还有疑问:它会忽略整个user engagement z,因而可能会有促进ckickbait的风险。

定义1(Pairwise Fairness)。一个具有ranking公式g的模型,如果一个clicked item的likelihood被排到另一个相关的uncliked item之上(跨相同的groups),被认为是服从pairwise fairness,则被认为是服从pairwise fairness:

对于来自每个group的items,该定义给出了一个关于ranker accuracy的聚合概念。

由于它是valuable的,它不会区别来自mis-orderings types。对于来自一个group的under-exposing items可能是有问题的。为了说明,考虑以下两个示例:在两种情况下,每个group 存在三个items,在第一个case中,系统给出了一个 ranking ,在第二个case中,系统给出了,我们可以看到,overall pairwise accuracy在两个cases中相同,,但在第二个case中,当group B中的一个item有兴趣(clicked),所有group B items会排在group A items之下。两者在ranking中都有问题(排在clicked item之下),但第二个case有系统上更有问题,偏向于某个group,这独立于用户偏好。

为了解决该问题,我们可以将上述pairwise fairness定义分割成两个独立的criteria:在相同group中items间的pairwise accuracy,不同groups的items间的pairwise accuracy;我们将这些metrics称为:”intra-group pairwise accuracy”和”inter-group pairwise accuracy”:

…(3) …(4)

定义2

定义3

3.4 Measurement

在推荐系统中,users和items是高度动态的,我们通常只在之前的recommended items上观察user feedback,这会使得metrics容易偏偏于previous recommender system。

然而,对于上述给出的三个fairness定义,我们希望在item pairs间用户偏好的无偏估计。为了这样做,我们在小量queries上运行随机实验。

参考

Minmin Chen、Alex Beutel等在《Top-K Off-Policy Correction for a REINFORCE Recommender System》中提出使用强化学习来提升youtube推荐。主要是从bias/variance的角度出发,具体方法如下:

摘要

工业界推荐系统会处理非常大的动作空间(action spaces)——数百万items来进行推荐。同时,他们需要服务数十亿的用户,这些用户在任意时间点都是唯一的,使得用户状态空间(user state space)很复杂。幸运的是,存在海量的隐式反馈日志(比如:用户点击,停留时间等)可用于学习。从日志反馈中学习是有偏的(biases),这是因为只有在推荐系统上观察到的反馈是由之前版本的推荐系统(previous versions)选中的。在本文中,我们提出了一种通用的方法,在youtube生产环境上的top-k推荐系统中,使用一个基于策略梯度的算法(policy-gradient-based algorithm,比如:REINFORCE),来解决这样的偏差。该paper的主要贡献有:

  • 1.将REINFORCE扩展到生产环境推荐系统上,动作空间有数百万;
  • 2.使用off-policy correction来解决在从多种行为策略中收集的日志反馈的数据偏差(data biases)
  • 3.提出了一种新的top-K off-policy correction来解释我们一次推荐多个items的策略推荐
  • 4.展示了探索(exploration)的价值

我们通过一系列仿真(simulations)和youtube的多个真实环境,来展示我们的方法的效果。

1.介绍

在工业界,通过推荐系统来帮助用户从海量内容中挑选和发现用户感兴趣的少部分内容。该问题十分具有挑战性,因为要推荐海量的items数目。另一方面,将合适的item在合适的时间上曝光给正确的用户,需要推荐系统能基于历史交互,不断地适应用户的兴趣漂移。不幸的是,对于一个大的状态空间(state space)和动作空间(action space),我们只观察到相对少量的数据,大多数用户只被曝光了少量items,而显式反馈的数据占比更少。也就是说,推荐系统在训练时只能接受相当稀疏的数据,例如:Netflix Prize Dataset只有0.1%的数据是dense的。因此,推荐系统的大量研究会探索不同的机制来处理相当稀疏的情况。从隐式用户反馈(比如:点击、停留时间)中学习,对未观察到的交互进行填充,对于提升推荐是很重要的一步。

大多数独立的研究线上,增强学习(RL)已经在游戏、机器人领域取得了相当大的进步。RL通常聚焦于构建agents,在一个环境(environment)中采取哪些动作(action)来最大化一些长期收益(long term reward)。这里,我们探索了将推荐解析成:构建RL agents来最大化每个用户使用该系统的长期满意度。在推荐问题上,这提供给我们一个新的视角和机会来基于在RL最新进展之上进行构建。然而,将这些新东西应用于实际还是有许多挑战。

如上所述,推荐系统需要处理大的状态空间(state spaces)和动作空间(action spaces),在工业界尤其显著。推荐可提供的items集合是不确定的(non-stationary),新items会不断被引入到系统中,从而产生一个日益增长的带新items的动作空间(action space),这会产生更稀疏的反馈。另外,在这些items上的用户偏好是会随时间一直漂移的(shifting),从而产生连续演化的用户状态(user states)。在这样一个复杂的环境(environment)中,通过这些大量actions进行reason,在应用已有RL算法时提出了独特的挑战。这里,我们分享了我们的实践:在非常大的动作空间和状态空间中,在一个神经网络候选生成器(neural candidate generator)上(一个top-k推荐系统)应用REINFORCE算法[48]。

除了大量动作和状态空间外,推荐系统中的RL仍是有区别的:只有有限提供的数据。经典的RL应用通过self-play和仿真(simulation)生成的大量训练数据,已经克服了数据无效性(data inefficiencies)。相比较而言,推荐系统的复杂动态性,使得对于仿真生成真实推荐数据是不可能的。因此,我们不能轻易寻找(probe for)关于之前的state和action space的未探索领域上的回报(reward),因为观测到的回报(observing reward)需要为一个真实用户给出一个真实推荐。作为替代,该模型几乎依赖于之前推荐模型们(models即policies)所提供的数据,大多数模型我们是不能控制的或不再可以控制。对于从其它policies中大多数日志反馈,我们采用一个off-policy learning方法,在该方法中我们会同时学习之前policies的一个模型,当训练我们的新policy时,在纠正数据偏差时包含它。我们也通过实验演示了在探索数据(exploratory data)上的价值(value)。

最终,在RL方法中大多数研究主要关注于:产生一个可以选择单个item的policy。而真实世界的推荐系统,通常会一次提供用户多个推荐[44]。因此,我们为我们的top-K推荐系统定义了一个新的top-K off-policy correction。我们发现,在模拟和真实环境中,标准off-policy correction会产生一个对于top-1推荐来说最优的policy,而我们的top-K off-policy correction会生成更好的top-K推荐。我们提供了以下的贡献:

  • 1.REINFORCE推荐系统:我们在一个非常大的action space中,扩展了一个REINFORCE policy-gradient-based方法来学习一个神经网络推荐policy。
  • 2.Off-Policy候选生成:我们使用off-policy correction来从日志反馈中学习,这些日志从之前的model policies的一个ensemble中收集而来。我们会结合一个已经学到的关于行为策略(behavior policies)的神经网络模型来纠正数据偏差。
  • 3.Top-K Off-policy Correction:我们提供了一个新的top-K off-policy correction来说明:我们的推荐一次输出多个items。
  • 4.真实环境的提升:我们展示了在真实环境中(在RL文献中很少有这种情况),这些方法对于提升用户长期满意度的价值。

我们发现,这些方法的组合对于增加用户满意度是很有用的,并相信对于在推荐中进一步使用RL仍有许多实际挑战。

2.相关工作

增强学习:Value-based方法(比如:Q-learning),policy-based方法(比如:policy gradients constitue经典方法)来解决RL问题。[29]中罗列了现代RL方法的常见比较,主要关注于异步学习(asynchronous learning),它的关键点是扩展到更大问题上。尽管value-based方法有许多优点(比如:seamless off-policy learning),他们被证明是在函数逼近(function approximation)上是不稳定的[41]。通常,对于这些方法来说,需要进行大量的超参数调参(hyperparameter tuning)才能达到稳定行为。尽管许多value-based方法(比如:Q-learning)取得了实际成功,这些算法的策略收敛(policy convergence)没有被充分研究。另外,对于函数逼近来说,Policy-based方法只要给定一个足够小的learning rate,仍然相当稳定。因此,我们选择一个policy-gradient-based方法(尤其是REINFORCE[48]),将这种on-policy方法适配到在当训练off-policy时提供可靠的policy gradient估计。

神经网络推荐系统:与我们的方法紧密相关的另一条线是,在推荐系统中应用深度神经网络[11,16,37],特别是使用RNN结合时序信息和历史事件用于推荐[6,17,20,45,49]。我们使用相似的网络结构,通过与推荐系统的交互来建模用户状态(user states)的演进。由于神经网络架构设计不是本文重点,有兴趣可以自己了解。

推荐系统中的Bandit问题:在线学习方法很流行,由于新的用户反馈是可提供的,可以快速被适配到推荐系统中。Bandit算法比如(UCB)[3],会以一种解析可跟踪的方式(它在regret上提供了很强的保证)来权衡exploration和exploitation。不同的算法,比如:Thomson sampling【9】,已经被成功应用于新闻推荐和展示广告。Contextual bandits提供了一种关于基础在线学习方法的context-aware refinement,并会将推荐系统朝着用户兴趣的方向裁减[27]。Agarwal【2】使得contextual bandits可跟踪,并且很容易实现。MF和bandits的混合方法被开发出来用于解决cold-start问题[28]。

推荐系统中的倾向得分(Propensity Scoring)和增强学习(Reinforcement learning):学习off-policy的问题在RL中是很普遍的,通常会影响policy gradient。由于一个policy会演进,因此在对应梯度期望下的分布需要重新计算。在机器人领域的标准方法[1,36],会通过限制policy更新的方式来绕过,以便在某一更新policy下新数据被收集之前,不能从实质上变更policy,作为回报,它会提供关于RL目标函数的单调提升保证。这样的近似(proximal)算法很不幸不能应用于item目录和用户行为快速变化的推荐情景中,因此大量的policy会发生变更。同时,对于大的状态空间和动作空间规模来说,收集日志反馈很慢。事实上,在推荐系统环境中,对于一个给定policy的离线评估已经是个挑战。多个off-policy estimators会利用逆倾向得分(inverse-propensity scores)、上限逆倾向得分(capped inverse-propensity scores)、以及许多变量控制的measures已经被开发出[13,42,43,47]。Off-policy评估会将一个相似的数据框架纠正为off-policy RL,相似的方法会被应用于两个问题上。逆倾向指数已经被大规模的用于提升一个serving policy【39】。Joachims[21]为一个无偏排序模型学习了一个日志反馈的模型;我们采用一个相似的方式,但使用一个DNN来建模日志行为策略(logged behavior policy),它对于off-policy learning来说是必需的。更常见的是,off-policy方法已经被适配到更复杂的问题上(比如:[44]为石板推荐)。

3.增强推荐

为便于理解,这里插入了张图(from 李宏毅课程)。

我们开始描述我们的推荐系统,及我们的RL-based算法。

对于每个用户,我们考虑一个关于用户历史交互行为的序列,它会记录下由推荐系统的动作(actions,比如:视频推荐)、用户反馈(比如:点击和观看时长)。给定这样一个序列,我们会预测下一个发生的动作(action:比如:视频推荐),以便提升用户满意度指标(比如:点击、观看时长)。

我们将该过程翻译成一个马尔可夫决策过程(Markov Decision Process: MDP),其中:

  • S:用于描述用户状态(user states)的一个连续状态空间(state space)
  • A:一个离散的动作空间(action space),它包含了推荐可提供的items
  • :是一个状态转移概率
  • :回报函数(reward function),其中是立即回报(immediate reward),它通过在用户状态(user state)s上执行动作a得到
  • :初始state分布
  • :对于future rewards的discount factor

我们的目标是:寻找一个policy (它会将一个在item上的分布转化成:基于用户状态的条件来推荐),以便最大化由推荐系统获得的期望累积回报(expected cumulative reward)

这里,在轨迹(trajectories) 上采用的期望,它通过根据policy: 来获得。

提供了不同族的方法来解决这样的RL问题:Q-learning[38], Policy Gradient[26,36,48]以及黑盒优化(black box potimization)[15]。这里我们主要关注policy-gradient-based方法,比如:REINFORCE[48]。

我们假设:policy的一个函数形式为,参数为。根据各policy参数的期望累积回报(expected cumulative reward)的梯度,可以通过”log-trick”的方式进行解析法求导,生成以下的REINFORCE梯度:

…(1)

在online RL中,policy gradient由正在更新的policy生成的轨迹(trajectories)上计算得到,policy gradient的估计是无偏的,可以分解成:

…(2)

对于一个在时间t上的动作(action),通过使用一个discouted future reward 将替换得到的该近似结果,可以减小在梯度估计时的方差(variance)。

4.off-policy collrection

由于学习和基础设施的限制,我们的学习器(learner)没有与推荐系统的实时交互控制,这不同于经典的增强学习。换句话说,我们不能执行对policy的在线更新,以及立即根据updated policy来生成轨迹(trajectories)。作为替代,我们会接收的的关于actions的日志反馈由一个历史policy(或者一个policies组合)选中,它们在action space上会具有一个与正在更新的policy不同的分布。

我们主要关注解决:当在该环境中应用policy gradient方法时所带来的数据偏差。特别的,在生产环境中在部署一个新版本的policy前,我们会收集包含多个小时的一个周期性数据,并计算许多policy参数更新,这意味着我们用来估计policy gradient的轨迹集合是由一个不同的policy生成的。再者,我们会从其它推荐(它们采用弹性的不同policies)收集到的成批的反馈数据中学习。一个navie policy gradient estimator不再是无偏的,因为在等式(2)中的gradient需要从updated policy 中抽取轨迹(trajectories),而我们收集的轨迹会从一个历史policies 的一个组合中抽取

我们会使用importance weighting[31,33,34]的方法来解决该分布不匹配问题(distribution)。考虑到一个轨迹 ,它根据一个行为策略抽样得到,那么off-policy-corrected gradient estimator为:

其中:

是importance weight。该correction会生成一个无偏估计器(unbiased estimator),其中:轨迹(trajectories)会使用根据抽样到的actions进行收集得到。然而,由于链式乘积(chained products),该estimator的方差是很大的,这会快速导致非常低或非常高的importance weights值

为了减少在时间t时该轨迹上的每个gradient项的方差,我们会首先忽略在该链式乘法中时间t后的项,并在将来时间采用一个一阶近似来对importance weights进行近似:

这会产生一个具有更低方差的关于policy gradient的有偏估计器(biased estimator):

…(3)

Achiam[1]证明了:该一阶近似对于学到的policy上的总回报的影响,会通过来限定幅值,其中是在间的总方差,是在下的discounted future state分布。该estimator会权衡精确的off-policy correction的方差,并仍能为一个non-corrected policy gradient收集大的偏差,这更适合on-policy learning。

4.1 对policy 进行参数化

这里有:

  • user state (): 我们对每个时间t上的user state建模,这可以同时捕获用户兴趣的演进,它使用n维向量来表示。
  • action (): 沿着该轨迹(trajectory)每个时间t上的action会使用一个m维向量进行嵌入。

我们会使用一个RNN [6, 49]来建模状态转移

我们使用了许多流行的RNN cells(比如:LSTM, GRU)进行实验,最终使用一个简单的cell,称为:Chaos Free RNN (CFN)[24],因为它的稳定性和计算高效性。该state会被递归更新:

…(4)

其中:

  • 是update gate
  • 是input gate

考虑到一个user state s, policy 接着使用一个简单的softmax进行建模:

…(5)

其中:

  • 是每个action a在action space A中的另一个embedding(注:前面的是m维,而是与相同维度)
  • T是时序(通常设置为1)。T值越大会在action space上产生一个更平滑的policy。

在softmax中的归一化项需要检查所有可能的动作,在我们的环境中有数百万量级。为了加速计算,我们会在训练中使用sampled softmax。在serving时,我们使用一个高效的最近邻查寻算法来检索top actions,并使用这些actions来近似softmax概率,如第5节所述。

总之,policy 的参数包含了:

  • 两个action embeddings
  • 在RNN cell中的权重矩阵:
  • biases:

图1展示了一个描述main policy 的神经网络架构。给定一个观察到的轨迹 它从一个行为策略(behavior policy)中抽样得到,该新策略(new policy)首先会生成一个关于user state 的模型,它使用一个initial state 并通过等式(4)的recurrent cell迭代得到。给定user state ,policy head会通过等式(5)的softmax来转化在action space分布。有了,我们接着使用等式(3)生成一个policy gradient来更新该policy。

图1 该图展示了policy 的参数变量(parametrisation)以及behavior policy

4.2 估计behavior policy

伴随等式(3)的off-policy corrected estimator出现的一个难题是:得到behavior policy 。理想状态下,对于一个选中action的日志反馈(logged feedback),我们希望也能记录(log)下选中该action的behavior policy概率。直接记录该behavior policy在我们的情况下是不可行的,因为:

  • (1) 在我们的系统中有许多agents,许多是不可控的
  • (2) 一些agents具有一个deterministic policy,将设置成0或1并不是使用这些日志反馈(logged feedback)的最有效方式

作为替代,我们采用[39]中首先引入的方法,并估计行为策略,在我们的情况中是在系统中一个多种agents的policies的混合(它们使用logged actions)。给定一个logged feedback集合 ,Strehlet[39]会以不依赖user state的方式,通过对整个语料的action频率进行聚合来估计。作为对比,我们会采用一个依赖上下文(context-dependent)的neural estimator。对于收集到的每个state-action pair(s, a),我们会估计概率,它指的是该behavior policies的混合体来选中该action的概率,使用另一个softmax来计算,参数为如图1所示,我们会复用该user state s(它由main policy的RNN model生成),接着使用另一个softmax layer来建模该mixed behavior policy。为了阻止该behavior head干扰到该main policy的该user state,我们会阻止该gradient反向传播回该RNN。我们也进行了将的estimators分离开的实验,由于会计算另一个state representation,这会增加计算开销,但在离线和在线实验中不会产生任何指标提升。

尽管在两个policy head 间存在大量参数共享,但两者间还是有两个明显的不同之处

  • (1) main policy 会使用一个weighted softmax来考虑长期回报(long term reward)进行有效训练;而behavior policy head 只会使用state-action pairs进行训练(言下之意,不考虑reward?)
  • (2) main policy head 只使用在该trajectory上具有非零回报(non-zero reward)的items进行训练(注3);而behavior policy 使用在该轨迹上的所有items进行训练,从而避免引入在估计时的bias

注3:1.具有零回报(zero-reward)的Actions不会对中的梯度更新有贡献;2.我们会在user state update中忽略它们,因为用户不可能会注意到它们,因此,我们假设user state不会被这些actions所影响 3.它会节约计算开销

在[39]中是有争议的:一个behavior policy(在给定state s,在time 上的它会确定式选中(deterministically choosing)一个action a;在time 上选中action b),可以看成是:在日志的时间间隔上,在action a和action b间的随机化(randomizing)。这里,我们在同一点上是有争议的,这也解释了:给定一个deterministic policy,为什么behavior policy可以是0或1。另外,由于我们有多个policies同时进行acting,在给定user state s的情况下,如果一个policy会确定式选中(determinstically choosing)action a,另一个policy会确定式选中action b,那么,以这样的方式估计可以近似成:在给定user state s下通过这些混合的behavior policies,action a被选中的期望频率(expected frequency)。

4.3 Top-K off-policy Correction

在我们的setting中存在的另一个挑战是:我们的系统一次会推荐一个包含k个items的页面给用户。由于用户会浏览我们的推荐(整个集合或部分集合),并与一个以上的item存在潜在交互,我们需要选择一个相关items集合(而非单个item)。换句话说,我们会寻找一个policy ,这样每个action A会选择一个关于k个items的集合,来最大化期望累积回报(expected cumulative reward):

轨迹(trajectory) 会通过根据 进行acting来获得。不幸的是,动作空间(action space)在该集合推荐公式下是指数级增长,在给定items数时这会过大(从阶数为百万级的语料中选择items)。

为了让该问题可跟踪,我们假设:一个无重复(non-repetitive) items的集合的期望回报(expected reward)等于在集合中每个item的expected reward的和(该假设仍会认为:用户会独立地检查每个item)。更进一步,我们通过对每个item a根据softmax policy 进行独立抽样,接着进行去重来限制生成action A集合。也就是:

注意:集合会包含重复的items,可以移除重复项来形成一个无重复的集合A。

在这些假设下,我们可以对该集合推荐setting采用REINFORCE算法,将在等式(2)的梯度更新修改为:

其中:

  • :表示的是一个item a出现在最终的无重复集合A中的概率。这里,。(注:作为有放回(replacement)和去重(de-duplicate)抽样的结果,最终集合A的size是可变的)

我们接着更新等式(3)中的off-policy corrected gradient,通过使用替代,生成top-K off-policy correction factor:

…(6)

对比等式(6)和等式(3),top-K policy会增加一个额外的乘子到original off-policy correction factor的中:

…(7)

现在,我们回顾下该额外乘子:

  • 随着。对比起标准的off-policy correction,top-K off-policy correction会通过一个K因子来增加policy update;
  • 随着。该乘子会使policy update归0
  • 随着K的增加,以及会达到一个合理的范围, 该乘子会更快地将graident减小于0

总之,当期望的item在softmax policy 具有一个很小的量,比起标准的correction,top-K correction会更可能推高它的likelihood。一旦softmax policy 在期望的item上转化成一个合理的量(以确认它可能出现在top-K中),correction接着会将梯度归0, 不再尝试推高它的似然。作为回报,它允许其它感兴趣的items在softmax policy中占据一定的量。我们会在仿真和真实环境中进一步演示,而标准的off-policy correction会收敛到一个当选择单个item时最优的policy,top-K correction会产生更好的top-K推荐。

4.4 Variance Reduction技术

在本节开始,我们会采用一个一阶近似来减小在梯度估计时的方差(Variance)。尽管如此,梯度仍会有较大的方差,因为等式(3)中展示的具有很大的importance weight,这与top-K off-policy correction相类似。具有较大值的importance weight是因为由(1)中来自behavior policy的new policy 的导数具有较大值所产生,特别的,new policy会探索那些被behavior policy很少探索过的区域。也就是说,和(2)在估计中有大的方差

我们测试了在counterfactual learning和RL文献中提出的许多技术来控制在梯度估计时的方差。大多数这些技术会减小方差,但在梯度估计时会引入一些bias。

Weight Capping。

我们测试的第一种方法会简单的将weight设置上限

…(8)

c的值越小,会减小在梯度估计时的方差,但会引入更大的bias。

NIS(归一化重要性抽样:Normalized Importance Sampling)

我们使用的第二种技术是引入一个ratio来控制变量,其中我们使用经典的权重归一化,如下:

由于,归一化常数等于n,batch size在预期之中。随着n的增大,NIS的效果等价于调低learning rate。

TRPO(Trusted Region Policy Optimization). TRPO会阻止new policy 背离behavior policy,它通过增加一个正则项来惩罚这两个policies的KL散度。它会达到与weight capping相似的效果。

5.探索(EXPLORATION)

有一点很明确:训练数据的分布对于学习一个好的policy来说很重要。现有的推荐系统很少采用会询问actions的探索策略(exploration policies),这已经被广泛研究过。实际上,暴力探索(brute-force exploration),比如:,对于像Youtube这样的生产系统来说并不是可行的,这很可能产生不合适的推荐和一个较差的用户体验。例如,Schnabel【35】研究了探索(exploration)的代价。

作为替代,我们使用Boltzmann exploration[12]来获取探索数据(exploratory data)的收益,不会给用户体验带来负面影响。我们会考虑使用一个随机policy,其中推荐会从中抽样,而非采用最高概率的K个items。由于计算低效性(我们需要计算full softmax),这对于考虑我们的action space来说开销过于高昂。另外,我们会利用高效的ANN-based系统来查询在softmax中的top M个items。我们接着会feed这些M个items的logits到一个更小的softmax中来归一化该概率,接着从该分布中抽样。通过设置,我们仍可以检索大多数概率块,限制了生成坏的推荐的风险,并允许计算高效的抽样。实际上,我们会通过返回top 个最大概率的items,以及从剩余的个items中抽取个items,来进一步平衡exploration和exploitation

6.实验结果

我们展示了:在一个工业界规模的推荐系统中,在一系列仿真实验和真实实验中,这些用于解决数据偏差(data biases)的方法的效果。

6.1 仿真

我们设计了仿真实验来阐明:在更多受控环境下off-policy correction的思想。为了简化我们的仿真,我们假设:该问题是无状态的(stateless),换句话说,reward R与user states是相互独立的,action不会改变user states。作为结果,在一个trajectory上的每个action可以被独立选中。

6.1.1 off-policy correction

在第一个仿真中,我们假设存在10个items:每个action的reward等于它的index,也就是说:(可以理解成按reward大小排好序)。当我们选中单个item时,在该setting下最优的policy总是会选中第10个item(因为它的reward最大),也就是说:

我们使用一个无状态的softmax来对参数化:

如果observations是从behavior policy 中抽样得到的,那么等式(1)中不对数据偏差负责的naively使用policy gradient的方式,会收敛到以下的一个policy:

这具有一个明显的缺点(downside):behavior policy越选择一个次优(sub-optimal)的item,new policy越会朝着选择相同的item偏移

图2: 当behavior policy 倾向于喜欢最小reward的actions时,(比如:),所学到的policy ,(左):没有使用off-policy correction; (右): 使用off-policy correction

这里我附上了我的理解代码(本节的目的,主要是为说明:当存在behavior policy倾向喜欢选择较小reward actions时,不使用off-policy correction效果会差):

1
2
3
4
5
6
7
8
actions = [1,2,3,4,5,6,7,8,9,10]
b = lambda x: (11-x)/55.0
beta = [b(i) for i in actions]
rxb = [(i+1)*j for i, j in enumerate(beta)]
total = sum(rxb)
pi = [i/total for i in rxb]

图2比较了:当behavior policy 倾向于最少回报的items,分别使用/不使用 off-policy correction及SGD所学到的policies 。如图2(左)所示,没有对数据偏差负责naivly使用behavior policy的方式,会导致一个sub-optimal policy。在最坏的case下,如果behavior policy总是选择具有最低回报的action,我们将以一个任意差(poor)的policy结束,并模仿该behavior policy(例如:收敛到选择最少回报的item)。另外一方面,使用off-policy correction则允许我们收敛到最优policy ,无需关注数据是如何收集的,如图2(右)。

6.1.2 Top-K-policy correction

为了理解标准off-policy correction和top-K off-policy correction间的不同,我们设计了另一个仿真实验,它可以推荐多个items。我们假设有10个items,其中,具有更低reward的其余items为:这里,我们关注推荐两个items的问题,即K=2。 behavior policy 会符合一个均匀分布(uniform distribution),例如:以平等的机率选择每个item。

给定从中抽样到的一个observation ,标准的off-policy correction具有一个SGD,以如下形式进行更新:

其中,是learning rate。SGD会根据在下的expected reward的比例继续增加item 的似然(likelihood),直到,此时的梯度为0。换句话说,top-K off-policy correction以如下形式进行更新:

其中,是在第4.3节定义的乘子。当很小时,,SGD会更强烈地增加item 的似然。由于会达到一个足够大的值,会趋向于0. 作为结果,SGD不再强制增加该item的likelihood,即使当仍小于1时。作为回报(in return),这会允许第二好(second-best)的item在所学到的policy上占据一些位置。

图3 学到的policy . (左): 标准的off-policy correction; (右): 对于top-2推荐,使用top-k correction.

图3展示了使用标准(left) off-policy correction和top-k off policy correction)(右)学到的policies 。我们可以看到,使用标准的off-policy correction,尽管学到的policy会校准(calibrated),从某种意义上说,它仍会维持items关于expected reward的顺序,它会收敛到一个policy:它能在top-1 item上将整个mass转换(cast),也就是:。作为结果,学到的policy会与在次优item(本例中的)和其余items间的差异失去联系。换句话说,该top-K correction会收敛到一个在第二优item上具有较大mass的policy,而维持在items间optimality的次序。作为结果,我们可以推荐给用户两个高回报(high-reward) items,并在整体上聚合更多reward。

6.2 真实环境

具有仿真实验对于理解新方法有价值,任何推荐系统的目标最终都是提升真实用户体验。我们因此在真实系统中运行A/B test实验。

我们在Youtube中所使用的生产环境上的 RNN candidate genreation model上评估这了些方法,相似的描述见[6,11]。该模型是生产环境推荐系统的众多候选生成器(candidate generators)之一,它们会进行打分(scored)然后通过一个独立的ranking模型进行排序(ranked),之后再在Youtube主页或视频观看页的侧边栏上展示给用户视频。如上所述,该模型的训练会采用REINFORCE算法。该立即回报(immediate reward) r被设计来体现不同的用户活动(user activities);被推荐的视频如果没有点击会收到零回报(zero reward)。长期回报(long-term reward)r会在4-10小时的时间范围内进行聚合。在每个实验中,控制模型(control model)和测试模型(test model)会使用相同的reward function。实验会运行许多天,在这期间模型会每隔24小时使用新事件作为训练数据进行持续训练。我们可以查看推荐系统的多种在线指标,我们主要关注用户观看视频时长,被称为:ViewTime。

这里的实验描述了在生产系统中的多个顺序提升。不幸的是,在这样的setting中,最新(latest)的推荐系统会为下一次实验提供训练数据,结果是,一旦生产系统包含了一个新方法,后续的实验就不能与之前的系统相进行比较。因此,后续的每个实验都应该看成是为每个(compoenent)单独分析,我需要在每一部分声明:在从新方法接收数据起,之前的推荐系统是什么。

6.2.1 Exploration

我们开始理解探索数据(exploratory data)在提升模型质量上的价值。特别的,我们会measure是否服务(serving)一个随机策略(stochastic policy),在该policy下我们使用在第5节中描述的softmax模型进行抽样,可以比serving一个确定策略(deterministic policy)(这种模型总是推荐根据softmax使用最高概率的K个items)来产生成好的推荐。

我们开展了一系列实验来理解:serving一个随机策略(stochastic policy) vs. serving一个确定策略(deterministic policy)的影响,并保持训练过程不变。在该实验中,控制流量(control polulation)使用一个deterministic policy进行serving,测试流量(test traffic)的一小部分使用第5节描述的stochastic policy进行serving。两种policies都基于等式(2)相同softmax model进行训练。为了控制在serving时stochastic policy的随机量,我们使用等式(5)的不同时间(temperature) T来区分。T值越低,会将stochastic policy降为一个deterministic policy,而一个更高的T会产生一个random policy,它以相等的机会推荐任意item。T设置为1, 我们可以观察到,在实验期间ViewTime在统计上没有较大变化,这意味着从sampling引入的随机量不会直接伤害用户体验。

然而,该实验的setup不会说明,在训练期间提供探索数据的好处。从日志数据中学习的一个主要偏差之一是,该模型不会观察未被之前推荐policy所选中actions的反馈(feedback),对数据进行探索会缓和该问题。我们展开了以下实验,其中,我们将探索数据引入到训练中。为了这样做,我们将平台上的用户分成三个buckets:90%,5%,5%。前两个buckets使用一个deterministic policy并基于一个deterministic model进行serving,最后一个bucket的用户使用一个基于一个使用exploratory data训练的模型得到的stochastic policy进行serving。deterministic model只使用由前两个分桶的数据进行训练,而stochastic model则使用第一和第三个buckets的数据进行训练。这两个模型会接收相同量的训练数据,结果表明,由于存在exploration,stochastic model更可能观察到一些更罕见state、action pairs的结果。

根据该实验过程,我们观察到在test流量中,在ViewTime上一个很大的增长。尽管提升并不大,它由一个相当小量的探索数据(只有5%的用户体验了该stochastic policy)所带来。我们期待stochastic policy被全量后所能带来的更高增益。

6.2.2 Off-policy Correction

在使用一个stochastic policy之后,我们会在训练期间对合并进的(incorporating)off-policy correction进行测试。这里,我们遵循一个更传统的A/B testing setup【注6】,我们会训练两个模型,它们均会使用所有流量。控制模型(control model)会根据等式(2)进行训练,通过reward对样本进行加权。测试模型(test model)会遵循图1的结构,其中该模型会同时学习一个serving policy 以及behavior policy 。serving policy会使用等式(3)描述的off-policy correction进行训练,其中每个样本会同时使用reward以及importance weight 进行加权来解决数据偏差。

【注6】:实际中,我们使用一个相当小比例的用户做为test polulation;作为结果,我们记录的feedback则几乎通过control model获取

在实验期间,我们观察到,学到的policy(test)会开始偏离behavior policy(control)(它被用于获取流量)。图4画出了:根据在控制流量中视频的排序(rank),对应在control/experiment流量中nominator所选中的视频(videos)的CDF(累积分布函数)(rank 1是由控制模型最可能指定的视频,最右表示最小可能指定)。我们看到,test model并不会模仿收集数据所用的模型(如蓝色所示),test model(绿色所示)会更喜欢那些被control model更少曝光的视频。我们观察到:来自top ranks之外视频的nominations的比例,在experiment流量中以几倍的因子递增。这与我们在图2仿真中观察到的现象一致。当忽略在数据收集过程中的偏差时,会创建一个“rich get richer”现象,其中,在学到的policy所指定(nominated)的一个视频,会只因为它在behavior policy上很难指定,采用off-policy correction可以减小该效应。

图4: 根据在control population中视频的排序(rank),在control 和test population中nominated的视频的CDF。标准的off-policy correction会解决”rich get richer”现象

有意思的是,在真实环境中,我们不会观察到control和test 流量(polulation)间在ViewTime上有一个大的改变。然而,我们看到,在视频观看(vv)数上有0.53%的提升,这在统计上是很大的,表明用户确实获得了更大的enjoyment。

6.2.3 top-k off-policy

理解超参数

最后,我们直接比较了超参数的不同选择对top-k off-policy correction的影响,以及在用户体验上的不同。我们会在top-k off-policy correction成为生产模型之后执行这些测试。

actions数目

我们首先探索了在top-K off-policy correction中K的选择。我们训练了三个结构相同的模型,分别使用:。控制(生产)模型(control(production) model)是top-K off-policy model,它使用K=16. 我们在图5中绘制了在5天实验中的结果。如第4.3节所示,K=1时,top-K off-policy correction会变成标准的off-policy correction。当K=1时,会失去0.66%的ViewTime(对比baseline K=16)。这进一步证明,该收益是由top-K off-policy correction带来的。设置K=2时,效果比生产模型还差,但gap降到了0.35%。K=32时效果与baseline相当。K=8时,有+0.15%的提升。

Capping

这里,我们在所学推荐器的最终质量上考虑了variance reduction技术。如4.4节所述,weight capping可以在初始实验中带来最大的online收益。我们不会观察到从归一化importance sampling或TRPO中进一步的metric提升。我们使用一个回归测试来学习weight capping的影响。我们比较了一个模型,它使用等式(8)中cap ,以及进行训练。正如我们在importance weight上提出的限制,学到的policy 可以潜在overfit到一个更少记录的actions,它们可能接收高的reward。在真实实验中,我们观察到使用importance weight在ViewTime中有0.52的损失。

参考

openai在《Proximal Policy Optimization Algorithms》提出了PPO。我们来看下:

摘要

我们提出了一个在RL中关于policy gradient方法的一个新家族,它可以在以下两者间做交替:通过与enviroment进行交互的方式sampling data,以及使用SGA(随机梯度上升)来最优化一个目标函数。标准的policy gradient方法会在每个data sample上执行一个梯度更新(gradient update),我们提出了一个新的目标函数,它可以允许多个关于minibatch updates的epochs。新的方法,我们称之为proximal policy optimization(PPO),它具有一些TRPO的优点,但更易于实际,更通用,并且具有更好的抽样复杂度(经验上)。我们的实验在许多benchmark任务上测试了PPO,包括仿真机器人运动(simulated robotic locomotion)和Atari游戏,我们展示了PPO的效果要好于其它online policy gradient方法,整体会在样本复杂度、简洁性和Wall-time上达到一个较好的平衡。

1.介绍

2.背景: Policy Optimization

2.1 Policy Gradient方法

Policy Gradient方法通过计算一个关于policy gradient的estimator,并将它插入到一个SGA(随机梯度上升)算法上。最常用的gradient estimator具有以下形式:

…(1)

其中:

  • 是一个stochastic policy
  • 是一个在timestep t时advatage function的estimator
  • 期望表示在一个会在sampling和optimization间做交替的算法中,一个有限batch的样本上的经验平均(empirical average)。

那些使用自动微分软件(automatic differentiation software)的实现,通过构建一个目标函数:它的梯度是policy gradient estimator,estimator 通过对以下的目标函数进行微分得到:

…(2)

在该loss 上使用相同的trajectory执行多个step的optimization时,这样做并不是空穴来风,经验上它通常会导致具有破坏性的大梯度更新(见6.1节)

2.2 Trust Region方法

在TRPO中,目标函数(”surrogate” objective)会服从在policy update的size上的一个constraint的方式最大化。特别的:

服从:

…(4)

此处,是在更新之前policy参数的向量。在对目标函数做一个线性近似、并且对constraint做一个二次方近似后,该问题可以使用共轭梯度算法(conjugate gradient)有效地被近似求解。

TRPO的理论证明建议我们使用一个正则项(penalty)来替代constraint,比如,对一些系数求解以下没有constraint的最优化问题:

…(5)

这遵循以下事实:一个固定的surrogate objective(它会计算在states上的最大KL)会形成在policy 一个下界(例如:一个pessimistic bound)。TRPO会使用一个hard constraint,而非一个penalty,因为它很难选择单个值在多个不同问题(或者甚至在单个问题中,其中特征会随学习过程发生变化)上效果好。因而,为了达到我们关于一阶算法的目标(模仿TRPO的单调提升),实验展示了,它不足以简单选择一个固定的penalty系数,并使用SGD对等式(5)的penalized objective进行最优化;需要额外的修改。

3.对Surrogate Objective进行裁减(Clip)

假设表示概率比值,因而。TRPO会最大化一个”surrogate”目标函数:

…(6)

上标CPI指的是保守策略迭代(conservative policy iteration)[KL02],其中该objective是被提出的。没有constraint后,对最大化将会导致一个过大的policy update;因而,我们现在会考虑如何去修改该objective,来惩罚将远离1的那些policy的变更

我们提出的主要的objective如下:

…(7)

其中epsilon是一个超参数,比如。该objective的动机如下。min中的第一项是。第二项 ,通过将概率进行clipping来修改surrogate objective,它会移除这样的动机:将移出区间外。最终,我们采用clipped和unclipped objective的最小值,因此,最终的objective是在unclipped objective上的一个下界(例如:一个pessimistic bound)。有了这个scheme,当对该objective做出提升时,我们只能忽略在概率上的变更,如果包含它会使得objective更糟糕。注意:对应围绕(比如:r=1)的一阶,然而,当远移时他们变得不同。图1画出了在上的单个项(比如:单个t);注意,概率 r是在或者上做裁减取决于advantage是正或负。

图1: 画出了surrogate function 的某一项(比如:单个timestep),作为概率比值r的一个函数,对于正的advantages(左)和负的advantages(右)。每个polit上的红色部分展示了optimization的起点(比如:r=1)。注意:会对所有这些项进行求和

图2: surrogate objectives,因为我们会在初始policy参数间插入,updated policy参数,我们会在PPO的一次迭代后计算。updated policy具有与intial policy相差0.02的KL divergence,这一点上是最大的。。。

图2提供了另一个关于surrogate objective 的来源。它展示了一些objectives是如何随着我们沿policy update的方向(通过PPO在一个continuous control问题上)变化的。我们可以看到,是在上的一个下界,它带有一个penalty,会对过大的policy update进行惩罚

4.Adaptive KL Penalty系数

另一种方法可以被做为是clipped surrogate objective的一个替代选择,这种方法为:在KL divergence上使用一个penalty,并对该penalty系数自适应(adapt)以便在每次policy update时能完成达到KL divergence 的一些target value。在我们的实验中,我们发现,KL penalty比clipped surrogate objective的效果要差,然而,我们在这里仍会包含它,因为它是一个很重要的baseline

在该算法是最简单实现中,我们会在每次policy update时执行以下steps:

  • 1.使用一些minibatch SGD的epochs,来优化KL-penalized objective:
  • 计算
    • if
    • if

更新后的被用于下一次policy update。有了该scheme,我们会偶尔看到那些KL divergence与存在很大差异的policy updates,然而,这很少见,因为会很快进行调整。上述关于参数1.5和2的选择是启发式的,但算法对它们非常不敏感。的初始值是另一个超参数,但实际上不是很重要,因为该算法会很快对它进行调整。

5.算法

前一节的surrogate losses可以被计算,并使用一个关于典型的policy gradient实现上一个很小变更的版本进行微分。对于使用自动微分的实现,一个简单的构建loss 来替代,会在该objective上执行多个SGA steps。

大多数用于计算variance-reduced advantage-function的estimators会使用一个学到的state-value function;例如,generalized advantage estimation[Sch+15a],或者finite-horizon estimators[Mni+16]。如果要使用一个在policy function和value function间共享参数的神经网络架构,我们必须使用这样一个loss function:它可以结合policy surrogate和一个value function error项。该objective可以进一步通过添加一个entropy bonus进行扩展来确保足够的探索(exploration),正如[Wil92, Mni+16]所建议的。通过组合这些项,我们可以获取以下的objective,它可以近似最大化每个迭代:

….(9)

其中:

  • 是系数
  • S表示一个entropy bonus
  • 是一个squared-error loss:

在[Mni+16]中普及的一种policy gradient实现,很适合使用RNN,可以为T timesteps运行policy(其中:T要比episode length要小很多),并使用收集到的样本进行一个upate。该种实现需要一个advantage estimator(它不会看到超过timestep T后的)。[Mni+16]中所使用的该estimator为:

…(10)

其中:t指的是time index ,在一个长度为T的trajectory segment内。

我们可以使用一个truncated版本的generalized advantage estimation对该方式进行泛化,当时即可以化简为等式(10):

….(11)(12)

使用固定长度的trajectory segments的一个PPO算法,如下所示。每个迭代中,(并行的)N个actors中的每个都会收集T timesteps的数据。接着,我们会在这些NT timesteps的数据上构建surrogate loss,并在K个epochs上使用minibatch SGD(或者,Adam)来进行optimize。

算法1

6.实验

参考

deepmind在《Emergence of Locomotion Behaviours in Rich Environments》提出了PPO。我们来看下:

1.介绍

2.使用Distributed PPO进行大规模增强学习

我们在增强学习上关注的点是,在丰富的仿真环境上使用连续state和action spaces。我们的算法在多个任务变种上是健壮的,可以有效扩展到其它领域。我们将轮流介绍每个issues。

使用PPO的Robust policy gradients

深度学习算法基于大规模、高吞吐的optimization方法,在离散和低维action spaces中(比如:Atari games和三维导航(3D navigation))可以产生state-of-the-art的结果。作为对比,许多之前的工作都是基于连续动作空间的,关注一些可对比的小问题。大规模、分布式的optimization较少广泛使用,相应的算法也很少被开发。我们发布了一个robust policy gradient算法,很适合高维连续控制的问题,可以使用分布式计算扩展到许多更大的领域上。

Policy gradient算法为连续控制(continuous control)提供了一个吸引人的范式。他们通过根据stochastic policy 的参数直接最大化rewards的期望和:

该期望会对应于由policy 和系统动态性(dynamics) 两者所联合生成的trajectories的分布:

对应的目标函数的梯度是:

其中:

  • 是一个baseline(它不依赖于或者future states和actions)。该baseline通常会选择

实际上,期望的future return通常近似于使用一个sample rollout,通过一个学到的近似和参数来替代。

Policy gradient的estimates可以有很高的variance,算法对于超参数的设置很敏感。有许多方法可以使得policy gradient算法更健壮。一种有效的measure是:采用一个trust region constraint,可以限制policy update的任意更新量(amount)。采用该思想的一种流行算法是:TRPO(trust region policy optimization)。在每个迭代中,给定当前参数,TRPO会收集一个(相对较大)的batch数据,并优化surrogate loss:

它会服从一个constraint:policy被允许更改多少,以KL divergence的方式表示:

是advantage function,可以通过得到。

PPO算法可以被看成是一个依赖于一阶梯度的TRPO的近似版本,它可以更方便地使用RNNs,并可以用在一个大规模分布式setting中。trust region constraint通过一个正则项来实现。使用的正则项系数依赖于该是否先前违反了constraint。算法1展示了PPO算法的伪代码。

算法1 PPO

在算法1中,超参数是在每个iteration上policy的期望变更。如果在policy上的实际变更很低、或者大大超过target KL,归一化项可以控制着KL-正则参数的调整(例如:落在区间之外)。

分布式PPO(DPPO)进行可扩展增强学习

为了在丰富的、仿真环境上达到较好性能,我们实现了一个分布式版本的PPO算法(DPPO),数据的收集和梯度计算在workers间是分布式的。我们使用同步更新和异步更新进行实验,发现平均梯度和将以同步方式使用会导致更好的结果。

原始的PPO算法会使用完整的rewords求和来估计advantages。为了使用RNN及batch updates,同时支持可变长的episodes,我们会遵循与[2]相似的策略(strategy),并使用一个长度为K的空间的截断BPTT(truncated backpropagation through time)。这使得它很自然地(虽然不是必须)使用K-step returns来估计advantage,例如:我们会在相同的K-step windows对rewards求和,并在K-steps后对value function进行bootstrap:

John Schulman[20]的公开提供的PPO实现对于核心算法增加了一些修改。它们包含了对inputs、rewards、以及在loss中的一个额外项(它会惩罚对于较大违反trust region constraint的情况)的normalization。我们采用在分布式setting中相似的augmentations,但发现在跨多个workers间对多个统计进行sharing和synchronization需要一些注意。我们的分布式实现(DPPO)采用tensorflow,参数在一个parameter server中,workers会在每个gradient step后同步它们的参数。伪码和详情在附件中提供。

A.DPPO

A.1 算法详情

DPPO算法的伪码在算法2和算法3中提供。W是workers的数目;D会为workers的数目设置一个阀值,它们的gradients必须被提供来更新参数。M,B是在给定一个batch的datapoints,使用policy和baseline updates的sub-iterations的数目。T是在参数更新被计算之前每个worker收集的data points的数目。K是用于计算K-step returns和truncated BPTT的time steps的数目。

算法2:

算法3:

normalization

根据[20]我们会执行以下的normalization steps:

  • 1.我们会通过减mean并除以标准差,将observations(或者 states )进行归一化。。。
  • 2.我们会通过一个正在运行的关于标准差的estimate对reward进行缩放(scale),在整个实验过程中进行聚合
  • 3.我们会使用关于advantages的per-batch normalization

跨workers共享算法参数

在分布式setting中,我们发现,对于跨workers的data normalization来说共享相关统计很重要。Normalization在数据收集(collection)期间使用,统计会在每个environment step之后被本地更新。当一次迭代完成时,统计的本地变改(local changes)在数据收集(collection)后被应用到全局统计中。随时间变化(time-varying)的正则化参数也会跨workers共享,但更新会基于本地统计(它基于对每个worker在本地计算的平均KL)来决定,通过使用一个调整参数由每个worker单独使用。

额外的trust region constraint

当KL超过期望变更的一个特定margin时(),我们也会采用一个额外的罚项。在我们的分布式实现中,该criterion会在一个per-worker basis上进行测试和应用。

参考

阿里在paper《Deep Session Interest Network for Click-Through Rate Prediction》中提出了基于session的ctr预测模型,我们可以借鉴一下:

0.

大多数已经存在的研究会忽略序列内在的结构:序列由sessions组成,其中sessions是发生时间内独立的用户行为。我们可以观察到,在每个session中的用户行为是同度同质的,不同sessions间差异很大。基于此观察,提出了新的CTR模型:DSIN,它可以利用在行为序列中的用户多个历史sessions。我们首先使用self-attention机制以及bias encoding来抽取每个sessions的用户兴趣。接着,我们应用Bi-LSTM来建模:用户兴趣是如何在sessions间演化和交互的。最后,我们使用local activation unit来自适应学习多个session interests对target item的影响。实验表明:DSIN效果要好于state-of-the-art模型。

1.

如图1所示,从真实工业界应用中抽样得到的一个用户,我们将它的行为序列分为3个sessions。sessions按如下原则进行划分:时间间隔超过30分钟[Grbovic and Cheng, 2018]。在session 1内用户主要浏览长裤(trousers),在session 2中浏览戒指(finger rings),在sessions 3内浏览大衣(coats)。图1的现像很普遍。它表明:一个用户通常在一个session内有一个明确唯一的意图,而该用户开启另一个session时会发生剧烈变化。

图1 真实应用中的一个关于sessions的demo。图片下的数字表示当前item上点击时间与首个item点击时间之间的时间间隔,以秒计。原则上,Sessions以超过30分钟进行划分.

受上述观察的启发,我们提出了DSIN(Deep Session Interest Network)来在CTR预测任务上,通过利用多个历史sessions来建模用户序列行为。DSIN有三个关键部分。首先,将用户序列行为划分成sessions,接着使用self-attention network以及bias encoding来建模每个session。Self-attention可以捕获session行为(s)的内在交互/相关,接着抽取每个session的用户兴趣(s)。这些不同的session interests可能相互间相关,接着遵循一个序列模式。在第二部分,我们使用Bi-LSTM来捕获交互、以及用户多个历史session interests的演进。由于不同session interests对于target item具有不同的影响,最终我们设计了local activation unit根据target item来聚合他们,形成该行为序列的最终表示。

主要贡献:

  • 我们强调用户行为在每个session中高度同质,不同sessions差异很大。
  • 设计了一个self-attention network以及bias encoding来获得每个session的精准兴趣表示。接着我们使用Bi-LSTM来捕获历史sessions间的顺序关系(sequential relationship)。最后,考虑到不同session interest在target item上的影响,我们使用local activation unit来聚合。
  • 两组比较实验。表明DSIN效果更好。

2.相关工作

2.1 CTR

2.2 Session-based推荐

session的概率常被序列化推荐提及,但很少出现在CTR预测任务中。Session-based推荐受益于用户兴趣在sessions上动态演化的启发。GFF使用关于items的sum pooling来表示一个session。每个item具有两种表示,一个表示自身,另一个表示session的上下文(context)。最近,RNN-based方法被应用于session-based推荐中来捕获在一个session中的顺序关系。基于此,Li 2017提出了一个新的NARM(attentive neural networks framework)来建模用户的序列化行为,并能捕获用户在当前session中的主要目的。Quadrana 2017提出的Hierarchical RNN依赖于RNNs的latent hidden states跨用户历史sessions的演化。另外,Liu 2018 的RNNs使用self-attention based模型来有效捕获一个session的long-term和short-term兴趣。Tang 2018使用CNN、Chen 2018使用user memory network来增强序列模型的表现力。

3.DSIN

3.1 BaseModel

本节主要介绍BaseModel所使用的:feature representation, embedding, MLP以及loss function。

特征表示

CTR预测任务中统计了大量信息特征。总共使用了三大组:User profile、item profile、User Behavior。每组包含了一些稀疏特征:

  • User Profile包含了gender、city等;
  • Item Profile包含了:seller id、brand id等;
  • User Behavior包含了用户最近点击的item ids等

注意,item的side information可以进行拼接来表示自身。

Embedding

MLP

Loss Function

3.2 模型总览

在推荐系统中,用户行为序列包含了多个历史sessions。用户在不同sessions上兴趣不同。另外,用户的session interests相互间有顺序关联。DSIN提出了在每个session上抽取用户的session interest,并捕获session interests间的顺序关系。

图2 DSIN模型总览。在MLP layers前,DSIN主要由两部分组成。一部分是sparse features,另一部分处理用户行为序列。自顶向上,用户行为序列S首先被划分成sessions Q,它接着会加上bias encoding,并使用self-attention来抽取session interests I。有了Bi-LSTM,我们将session interests I和上下文信息进行混合作为hidden states H。session interests I和hidden states H的Vectors受target item的激活,User profile和item profile的embedding vectors被拼接在一起,进行flatten并被feed到MLP layers中进行最终预测

如图2所示,DSIN在MLP前包含了两部分。一部分是从User Profile和Item Profile转向后的embedding vectors。另一部分是对User Behavior进行建模,自顶向上具有4个layers:

  • 1) session division layer,会将用户行为序列划分为sessions
  • 2) session interest extractor layer:会抽取用户的session interests
  • 3) session interest interacting layer:会捕获session interests间的顺序关系
  • 4) session interest activating layer:会对与target item有关的session interests使用local activation unit

最后,session interest activating layer的最终输出、以及User Profile和Item Profile的embedding vectors被feed给MLP做最终预测。以下述章节中,我们会引入这4个layers。

Session Division Layer

为了抽取更精准的用户的session interests,我们将用户行为序列S划分成sessions Q,其中第k个session ,其中,T是我们在该session中的行为数,是在该session中的用户第i个行为。相邻行为间存在的user sessions的划分,会遵循该原则:时间间隔超过30分钟。

Session Interest Extractor Layer

在相同session中的行为,相互之间强相关。另外,用户在session中的偶然行为会使得该session interest偏离它的原始表示(original expression)。为了捕获在相同session中的行为间的内在关系,并减少这些不相关行为的效果,我们在每个session中使用multi-head self-attention机制。我们也对self-attention机制做了一些改进来更好地达到我们的目的。

Bias Encoding

为了利用sequence的顺序关系,self-attention机制会应用positional encoding到input embeddings中。另外,sessions的顺序关系,以及在不同表示子空间中存在的bias需要被捕获。因而,我们在position encoding的基础上提出了bias encoding ,其中BE中的每个元素被如下定义:

…(2)

其中:

  • :是session的bias vector
  • k:是sessions的索引
  • :是在session中position的bias vector
  • t:是在sessions中行为的索引
  • :是在behavior embedding中unit position的bias vector
  • c:是在behavior embedding中unit的index。

在加上bias encoding后,用户的behavior sessions Q按如下方式更新:

…(3)

Multi-head Self-attention.。在推荐系统中,用户的点击行为受许多因素(颜色、风格、价格等)的影响。Multi-head self-attention可以捕获不同表示子空间的表示。数学上,假设:,其中的第h个head,H是heads的数目,的输出如下计算:

…(4)

其中,是线性矩阵。接着不同heads的vectors被拼接到一起被feed到一个feed-forward network中:

…(5)

其中,是feed-forward network,是线性矩阵。我们也在相继使用了residual connections和layer normalization。用户的第k个session的兴趣按如下方式计算:

…(6)

其中,是average pooling。注意,在不同sessions间self-attention机制中的weights是共享的。

Session Interest Interacting Layer

用户的session interests会持有带上下文的顺序关系。建模动态变化会增强session interests的表示。Bi-LSTM在捕获顺序关系是很优秀的,很天然地可应用于在DSIN中建模session interest的交互。LSTM cell的实现如下:

…(7)

其中,是logistic function,其中: i,f,o,c分别是:input gate、forget gate、output gate、cell vector,它们具有与相同的size。权重矩阵的shapes可以通过下标来表示。Bi-direction意味着存在forward和backward RNNs,hidden states H按如下方式计算:

…(8)

其中,是forward LSTM的hidden state,是backward LSTM的hidden state。

Session Interest Activating Layer

与target item更相关的用户的session interests,对于用户是否点击该target item的影响更大。用户的session interests的weights需要根据target item进行重新分配。Attention机制会使用在source和target间的soft alignment,被证明是一个很有效的weight allocation机制。与target item相关的session interests的自适应表示可以如下计算得到:

…(9)

其中具有相应的shape。相似的,session interests的自适应表示会混杂着与target item相关的上下文信息,如下计算:

…(10)

其中具有相应的shape。User Profile和Item Profile的Embedding vectors,会被拼接到一起,flatten,然后feed给MLP layer。

4.实验

略.

参考