滴滴信息流数据架构（基于强化学习的探索资源约束的Contextual）

滴滴信息流数据架构（基于强化学习的探索资源约束的Contextual）这篇文章的主要内容是多臂老虎机问题。先介绍一下这个问题的背景。假设多臂老虎机有K个臂，如上图右上角的三个臂。多臂老虎机的机制就是每个回合只能选一个臂执行，然后拉不同的臂会有一个不同的收益。而且，同一个臂在不同回合的收益也有可能是不一样的。因为这是一个序列化的决策，所以这里我们的一个优化目标就是假设总共要拉T个回合，每个回合拉完之后，我们能得到一个即时及时的收益，这个是rt，它最后一个要优化的问题就是如何做一个序列的决策，让我们在总共T个回合之内的收益最大。除了围棋，强化学习在其它一些领域也获得了一些成就，比如游戏和现在非常火的自动驾驶，也会用到强化学习的相关技术。本次分享中，我将介绍一下滴滴在今年WWW 上发表的一篇论文。论文的主要内容是基于强化学习来探索资源约束的问题，主要方向是上下文多臂老虎机（Contextual Bandits）。论文主要分为四个部分，本次分享也依此展开：1）强化学

KDD Cup 2020 & 滴滴强化学习挑战赛目前正在 biendata 竞赛平台开展，比赛邀请全球算法高手共同挑战共享出行领域优化难题。针对本次竞赛，5月9日，在B站“biendata 与 paperweekly 联播 AI Industry Talk”第10期中，我们邀请到了滴滴AI Labs专家算法工程师唐小程和滴滴AI Labs 专家研究员李卿阳，分别与大家分享了“KDD CUP学习如何在共享出行平台上派单和调度”、“探索资源约束的Contextual Bandits 问题”。

关于KDD Cup 2020 & 滴滴强化学习挑战赛的更多详情大家可访问biendata 网站（biendata）了解，唐小程老师也通过分享对比赛做了详细介绍，感兴趣的同学可通过点击文末的“了解详情”观看B站的直播录像进行了解。

以下为李卿阳老师直播分享的文字实录，为方便阅读，做了相应的文字调整。

讲者简介：李卿阳，滴滴AI Labs 美国研究院专家研究员，致力于网约车交易平台的供需策略优化模拟器建模和策略优化。李卿阳本科毕业于北京航空航天大学，博士毕业于亚利桑那州立大学，研究方向是强化学习、深度学习和数据挖掘，并在国际顶级会议ICML，KDD，WWW，WICCAI 上发表过近10篇论文。

本次分享中，我将介绍一下滴滴在今年WWW 上发表的一篇论文。论文的主要内容是基于强化学习来探索资源约束的问题，主要方向是上下文多臂老虎机（Contextual Bandits）。

论文主要分为四个部分，本次分享也依此展开：1）强化学习与上下文多臂老虎机的背景介绍，2）基于层次自适应的CB方法，3）累积遗憾（Cumulative Regret）分析，4）实验结果验证。

一、强化学习与上下文多臂老虎机的背景

首先我们介绍一下强化学习的发展史。强化学习最近几年的一个重要的应用案例就是DeepMind的人工智能围棋程序AlphaGo ，效果很好，在两年内击败了李世石和柯洁，研究结果也被发表在《自然》（Nature）等刊物上。

除了围棋，强化学习在其它一些领域也获得了一些成就，比如游戏和现在非常火的自动驾驶，也会用到强化学习的相关技术。

这篇文章的主要内容是多臂老虎机问题。先介绍一下这个问题的背景。假设多臂老虎机有K个臂，如上图右上角的三个臂。多臂老虎机的机制就是每个回合只能选一个臂执行，然后拉不同的臂会有一个不同的收益。而且，同一个臂在不同回合的收益也有可能是不一样的。因为这是一个序列化的决策，所以这里我们的一个优化目标就是假设总共要拉T个回合，每个回合拉完之后，我们能得到一个即时及时的收益，这个是rt，它最后一个要优化的问题就是如何做一个序列的决策，让我们在总共T个回合之内的收益最大。

这个问题我们其实可以用一个比较简单的方法：均匀探索。假如我们每个臂都探索了相同的次数（例如每个臂都拉了N次），然后可以观察一下这几个臂的平均收益是什么，这样就能看出不同选择的结果。比如上图下方，假如我们一共有4个选择，每个选择都被执行了足够多的次数，我们其实已经可以知道剩下的回合会出现什么效果。这样我们就可以直接找到最好的臂，然后一直执行到整个回合结束。大致来说，这种方法前期进行探索，后期我们就会知道哪个决策比较好，可以一直执行下去。这是一种比较简单的方法。

还有一个比较流行的算法，叫上限置信区间（以下简称UCB）算法。这个方法首先要定义一个置信的半径，可以用r(a) 表示。在上图的r(a) 的定义公式中，T代表总共执行了T个回合，N 代表了在这个臂上执行了N 次。定义了置信半径后就可以定义置信区间。置信区间包括UCB（上区间）和LCB（下区间），miu_t(a)是执行了第a个臂后，观测到的收益。所以每次执行都可以根据算出来的UCB值，然后看一下执行了这么多次后，哪个臂的收益不错。然后，我们可以动态更新UCB的值，然后每次选择UCB最高的那个臂去执行。执行完之后，我们立刻又能看到收益，所以可以更新上次执行的那个臂的miu_t(a)，这样一直迭代到算法结束。这就是UCB，也是一个比较经典的算法。

下面我介绍一下本次内容中比较重要的Contextual Bandits部分，我们比较常见的电商推荐包括广告推荐系统的设计中，都需要应用到“多臂老虎机”去进行序列决策的问题。

以电商推荐举例，淘宝或者Amazon 亚马逊这样的购物平台怎样去给用户做推荐？我们简单介绍一下Contextual Bandits ，假设有K 个item ，针对每一位不同的用户，如何做到更加个性化的推荐？举个例子，上图中第一位的女性用户，根据她图中的特点，为她推荐一些香水可能就比较合适。第二个例子可能就是一个不太好的推荐，图中第二位女性用户从着装判断是一位职场中的Office Lady ，为她推荐机械鼠标或者游戏类的电子产品可能就不一定合适。根据第三位女性用户图片中的特点判断，为她推荐一些运动用品显然是没错的。

从这三个例子中，我们可以看出Contextual Bandits 和MAB 最大的区别就是，应用Contextual Bandits 时，推荐的每个回合中，来的用户都都会自带一些特征。而Contextual Bandits 和MAB 的共性是，两者都需要做一个序列化的决策，去最大化整个过程的收益，再根据用户的feedback，去动态更新我的模型。

下面我简单介绍一下，强化学习中的探索成本。如上图左示，在游戏领域强化学习的基本原理是，在environment 中， agent 执行action，我可以获得一个及时的反馈去更新policy。在游戏领域中由于环境相对来说比较稳定和封闭，因此探索成本相对来说比较低。比如说跑一个AlphaGo 或者AlphaZero，主要是训练时间成本。并且这个策略的可用性比较强，因为这个环境比较稳定且不受外部环境的影响。所以在游戏领域中涉及到的探索成本比较低，主要是训练时间成本。

右图中是把强化学习应用在现实应用中的场景，这里的system 就类似于左图中的agent，user 就类似于左图中的environment。假设我们要做一个在线学习，因为我们可能直接要跟用户做交互，这就会带来一些不稳定，并且外部环境会变，所以可能需要反复地实验来达到一个稳定的策略。所以在现实领域中进行一个强化学习的策略的探索，是有探索成本的，涉及到的探索成本就比较高。

所以基于这个问题，目前主流的方法有两类，一个是On-policy learning with the environment，也就是直接跟环境交互，去优化我的策略，显而易见，它探索成本会比较高。第二种，Off-policy or offlinepolicy learning，需要我有大量离线的历史数据，还有比较好的样本才能提高策略学习的效果。

在MAB 或者Contextual Bandit 当中，也会有Tradeoff，也就是标题中写的探索和挖掘的问题。RL 的优点是它具有很强大的决策能力，比如说在围棋领域，我们有AlphaGo 和AlphaZero 。RL 的缺点就是需要大量地的和环境做交互，这就会有极高的交互采样的需求，所以会出现下边那个图。利用其优点可以得到一个比较不错的策略收益，learn 一个比较好的policy，但也需要一个很高的探索成本。所以这个问题就是如何去balance exploration 和exploitation 的问题。

二、基于层次自适应的CB方法

下面我们就进行本次分享的第二部分，我们在WWW 上提的一个方法，去解决exploration 和exploitation 的问题。

举一个推荐电影的例子，大概介绍一下Contextual Bandit 的流程，图中有五部电影，哪部是比较合适给这个用户推荐的？主要是四个过程。第一步，先获取用户的contextual 信息，我就会有一个总体的item set；第二步，根据离线的Linear Function 计算，基于当前的user 不同的item 大致的收益是怎样的；第三步是做决策，就是刚才提到UCB 的过程，或者定义UCB 的过程去选较优的action执行。第四步，更新，因为执行完action 之后，我有一个user 的feedback，可以去更新model 的参数。

关于Contextual Bandit 比较有名的算法，我这里列举了两篇，第一篇就是LinUCB (WWW 2010），第二篇是Thompson Sampling (ICML 2013)

下面就引入我们下面那个topic，如何在有限的探索资源下去做Contextual Bandit的决策问题。场景如右图，在recommendation system 中，针对不同的items 会有一个收益。比如图中的 ȓa1 到 ȓak ，针对我当前有的user context，不同的items有不同的执行成本。因为涉及到探索的资源，所以这个问题就转化成：每次执行不同的action，会产生一个cost，根据这些cost 有全局cost 约束。也就是上图右下角的公式：假如说我总共执行了T次，每次执行完action 之后会产生一个cost，我得到约束整体的cost 不超过B 这样一个cost 约束范围。现实的应用场景里也有很多这样的例子，比如说广告竞价和电商推荐，因为对不同的item，价格是不一样的，所以推荐成本也是不一样的。出行平台也会有这样一个执行action的成本约束。

问题转换成一个global wise 的一个resource constraint 问题，就变成了我上边图片里边描述的问题，每次会有一个user 带着context 信息从environment 进来，这时需要agent 根据context 信息做一个决策，因为可能会有不同的items比较适合它，不同的items，后边都会有一个探索的成本。接下来再去query 总的resource，也就是查询现在剩下多少资源？做一个全局资源的分配。如果做一个全局的优化的话，整个的流程就是这样的。

定义问题的部分主要是两块，一个叫探索，一个叫挖掘。在挖掘这块，如果每次我们已经有足够的资源，就直接执行当前资源下中最优的那个action 就可以了。还有一个就是我需要做exploration，去收集更多的信息，再更新我的模型和策略。基于这两个点，我们将这个问题定义为：如何在现有的资源下最大化整体收益？这个objective function 的意思是，就是我在现有的资源约束B 的范围下，去最大化我的策略性能U(T B)，(rt at) 就是每一次我执行action 之后拿到了一个即时的收益。下方的就是我每次执行必然会产生的一个成本，我需要把所有探索的成本，控制在有限的范围内。

这个问题就是我们这篇文章主要的contribution 了，分为三点。第一，如何平衡探索和挖掘？第二，我们提出了Hierarchical Architecture (HATCH) 去优化，在上一层我们怎么做resource allocation，到下一层我们怎么做action 策略的执行。第三，我们有理论的分析，证明regret bound，在O√T 的范围内，为 HATCH 提供理论的保证。

我可以先回答一下有些朋友的问题：reward累积加和为什么没有折扣因子？这个问题是这样的，Contextual Bandit 本质上和MDP 是有区别的，在传统的MDP 中是有reward 求和带上折扣因子，它会有cumulativereward ，我回到这一点，它会有cumulative reward 带上折扣因子的计算，但是在Contextual Bandit 中，因为它不是针对用户做序列化的决策，所以每次优化我拿到当前的反馈就可以了。CB(Contextual Bandit) 和MDP 的主要区别在于MDP 是针对single agent ，再持续优化agent 获得的收益，CB主要是针对一个平台，比如说优化推荐系统的效果，每次有不同的用户来，我去优化平台总体的收益。

下面介绍一下整体方法的框架，我们提出 Hierarchical Architecture，分为两层，上层是 resource allocation 的分配，下层是 personal recommendation 的推荐。右图表示，对大量的user contexts ，先做简单的一个聚类，把它分成比如说这里边的Φ1，Φ2、Φ3，分成三个cluster ，针对三个cluster 再做resource allocation ，对不同的cluster ，分配资源也就是右上角 resource allocation level 。

一些比较重要的notation 在上图中已经有所呈现，Pt是resource allocation level 这个层中比较重要的参数，因为不同的cluster，可能会有不同资源清洗的预算，Pt描述就是不同的user context 的cluster 中我拿到资源的概率是多少。

下面这一层就是针对不同user cluster 分配的资源执行action。所以下边一层主要是针对已有的Context Information Xt，执行action。action 执行的概率就是上边resource allocation 给的参数，比如说user contexts cluster Φ1 执行到一定次数能达到比较好的效果，资源就可以向Φ1 做一定的清洗，那么P1 的概率就会比较高；如果Φ3 执行了很多次，它的效果依然很差，那么P3 解出来的概率就会低一些，这个主要是动态资源的分配和数据的收集。

下面回答一个非常好的问题：用户所属的这一类会更新吗？contexts information 相对来说，分布比较稳定，这是本文或者说本方法的前提。比如说推荐的场景，我们有很多user contexts 数据，其分布相对来说比较稳定，所以不会更新聚类的过程。还有一种情况，存在一些极端的case ，它的环境是动态变化的，这个我们暂时就不会处理，比如现在有新冠疫情了，这个是一个比较大的外部环境改变，所以user 的context information 的分布也会产生比较大的变化，这就是在环境剧烈变化的一种情况。

HATCH方法主要分为四个步骤：

第一步，做context information 的聚类.根据日志数据，做contexts 的分类；

第二步，做resource allocation，针对不同的user context 或者user contacts class 分配的资源也不同，其中是需要解出的参数，而是基于历史上执行过的不同的user contacts 的累计收益去求得的；

第三步，是做item 的推荐。该步实现的是personal recommendation，基于观测到的contacts，去执行action。执行action 主要是基于上边不同的contexts，会有资源的倾斜;

第四步，更新 直接执行action 拿到feedback。

user contacts 会受action 的影响吗？user contacts 主要是一些用户访问的特征，相对来说比较稳定，所以做的是clustering mapping，和action 是没有关系的，它主要是对context information 做聚类，所以相对来说不会受太大的影响。

下边讲的是resource allocation level 怎么做user 的clustering。

第一步，相对来说比较容易懂，对大量的logging data，也就是user data，简单做一个clustering (聚类)，不同的数据有不同的聚类中心点，来代表这一类的用户。

第二步也是比较重要的一步，做resource allocation。这里有几个annotation， Pj指的是第j个class（或class center）执行action的概率 Pj是这一步要去求的。 φj 是第j个user class 的分布，比如说有100万个数据，我把它分成100类或者50类不同的user class 的分布。φj 在整个算法过程当中是不变的，这是前提，user context information 的分布比较稳定。就是第j 个context class 预估的一个收益。所以这里边只有 Pj是未知的，所以这里直接对 Pj求解即可，可以用一些LP（线性规划）。下边就是 Pj求解的过程。

相同的聚类用户会得到相同的资源分配结果吗？这个是不一定的，Pj 只是一个 user 属于第j 个class 执行action 的概率，所以可能会得到不同资源分配的结果。

下边是的求解，我们通过Linear Function 方式去拟合，这也是大部分LinUCB或者UCB 算法的方法，通过user context 拟合出用户估计的收益是怎么样的，也就是说可以通过直接拟合出来。更新的方法，就是上图第三个公式里边写到的，也是LinUCB 的更新的过程。

刚才讲完了上层resource allocation level 怎么去做资源的分配？最终我要求概率P，不同的user context 执行action 的概率。下面讲一下，在personal recommendation level 这一层怎么去做action 的执行。

这里边action 执行也是相对来说比较直接的，我有context 对应的 xt θt就是不同的user context center 的参数，这个可以直接通过更新过程去求得，这个过程和LinUCB 的更新过程是一致的。

上图是整体算法的流程，对应前面讲得四个过程：

第一步：就是我先要针对historical context 做clustering，把它们聚集到不同的class center ；

第二步：做一个item 的recommendation，对应上图算法里边第7行，针对我mapping到的context center，得到一个action；

第三步：对应上图算法中的第9行里边讲的，如果这个B代表一个budget，表明现在还有allocation 的资源，可以做一个计算，算一下不同的user context 概率，算完之后，得出user context 的执行的概率是多少；

第四步：对应的上图算法中的第10行。

综上所述，求action 对应算法里边第5到第10行，而第13行到第22行主要是更新的过程，就是已经执行完action ，去更新一些参数。

三、累计遗憾(Cumulative Regret)分析

下面来讲累积遗憾分析。累积遗憾分析中，大部分Bandits 或者上下文多臂老虎机，通过regret 分析，会得到一个理论上的证明。

我们来看图中regret 的定义，第一个公式，针对一个Bandits 的一个算法执行T步之后，获得的收益就是U(T)。第二个公式针对不同的Bandits，U(T)可能会不一样，换句话说就是推荐的效果好或者不好，U(T) 是不一样的，第二个公式中U*(T) 的含义就是每一步都执行最优Action，执行T 步之后，它最优的一个收益是什么

所以U(T) 是小于等于U*(T) 的，不论执行任何一个Bandits 算法，它的上限是U*(T)。由此可知，regret 定义就是U*(T)-U(T)，差值是什么？就是累积的遗憾。不同的算法都会有一个U*(T)，所以大部分Bandits 算法，就是Minimize The Regret 约等于最大化累计收益，相应的会有一个regret 的分析来验证算法的收敛性。

这篇文章也有regret分析来确保理论收敛。

上图的算法会对整体的exploration resource 做budget的限制。所以它的定义是和之前的Bandits是有一些区别的，这里不是，而是，也就说在给定的探索资源下，能拿到的收益是什么，响应的regret的定义是在现有的资源下能拿到最高的收益是什么。然后就是算法的一个regret是怎么样的。这里边我们分两步去进行一个讨论。因为是有两种case 的，上图画红线的就是R1级别和R2级别。

因为regret analyze 理论性比较强，所以这里边公式会比较多。

这R1(T B)和R2(T B)的详细理论分析可以参见文章详细理论推导。

最后的理论证明，分为Non boundary case 和Boundary case 两种情况做了讨论，所以大家可以看R(T B) 的收敛结果。因为O里边是取最高项，所以最后证明了算法有一个O√Τ，这样regret bound 理论上的保证。

T是超参，会改变吗？假如我Bandits算法已经执行了足够多的次数，怎么在足够多的次数，去保证有一个regret bound的一个限制？

所以T其实不是超参，它是一个执行足够多次数之后，它能取得的一个regret bound 是什么。

四、实验结果验证

下面就讲一下实验的部分，我们主要做了两组实验，第一个是在synthetic data (合成数据)上面。

以上是一些基础定义，data generator 生成user context 信息。reward 是0/1，item 定义了10个arms。探索不同的action 会产生不同的探索成本，因此我们假设每个探索成本是相同的，即，unit cost。

一个比较重要的概念就是上图中提到的ρ，该参数指的是探索资源参数的限制。图中的T是总体执行的轮数，一般这个T都会比较大。而budget就是给定了一个探索的资源。所以这里越大，给定的探索资源就会越多，如果ρ趋于无穷，这个其实和正常的Contextual Bandits ，或者LinUCB 是没有差别的。

还有一些对比方法，如上图所示，这里对比了不同算法实验结果，在不同的探索资源约束下，对应不同regret 的效果图。regret 越小，代表算法效果越好。横轴代表不同探索资源约束的参数，纵轴是 cumulative regret（累积遗憾）。所以通过不同的算法对比，本文中方法得到的 regret 相对来说是比较低的。

有人问reward是0、1，cost 是1吗？cost 是这样的，每次执行action 中有一个选择是不执行action的，不是每次都会产生资源的消耗，如果最后选择不做，这个cost 其实是没有的。这个和广告推荐中的场景是一样的，每做一次广告推荐就会消耗一次推荐机会，然后用户质量不好也是可以选择放弃本次推荐的，这种情况下cost就是0。

第二个实验，是Real-world Applications，这是在雅虎today 的一个公开数据集上做了一次验证。数据内容主要是雅虎门户网站的新闻数据。其中，user 是浏览新闻的用户，action 是推荐的新闻，reward 是点击或者不点击。cost，因为每次做一个展示，就会花费一次推荐的机会，如果选择不展示，这次cost就是没有的。所以，评估指标主要是针对CTR 的评估，约束了总体展示的次数。看这个clicks 最高能到达多少？所以最后CTR 越高，也就代表这个推荐的效果越好。这是数据的website。

我们针对不同探索资源约束去对比曲线图，执行不同的轮数观察效果。可以看见，和其他算法对比，当执行轮数比较低时，HATCH 的趋势还不是太明显，执行轮数越高，后期效果就会越明显。其他算法，比如Cluster-UCB-ALP 后期的资源可能就没有那么多，因为它前期消耗的资源相对比较多。

第二块我们来看一下averaged reward 的分布和resource allocation 的分布，不同的ρ代表不同的资源分配， ρ越大代表分配的总体资源越多。这个趋势是，不同的contexts class center 中reward 分布和allocation 资源的分布是比较平衡的。整体上来看 平均reward 越多，给的资源也会越多。还有一个现象是ρ越大，就代表可以分配的资源越多。所以当ρ比较小时，这个算法相对来说给高收益的cluster 分配的资源就会比较多，其他的相对来说会分配得比较平均。当探索资源比较多时，会做一些探索来平衡资源，如这里第4个图，它分配的资源会比较多，所以它分配的资源和reward 的分布比较像。

以上基本是今天所有分享的内容，我们再做一个总结。这篇文章主要是研究了探索和挖掘的balance，我们知道现实应用场景中，大部分应用是受到探索资源约束的。如何去balance 探索跟挖掘，我们提出了Hierarchical Architecture (HATCH) 去最优化探索的效率，提出了一个两层的结构，上一层去做资源的动态allocation，根据推荐的效果，下一层作为action 的推荐。然后我们分析了regret bound。为整个算法提供O√Τ的regret bound 的保证。

这是一些文章的下载链接，大家感兴趣可以直接搜索文章的标题。文章在网上可以直接下载，还有GitHub的Code link，大家感兴趣可以去看看这个方法是怎么实现的。

五、Q&A环节

Q:每个资源怎么做初始化？

A:这个问得比较好，它有一个code start的过程，开始所有不同的user context执行action的概率是一样的，因为开始没有做探索。之后随着一些user context的performance逐渐变好，ρ也会逐渐变大，所以就会达到平衡的效果。

Q:AT action会不会受到user context的影响？

A: user context 是历史的logging data。我们做这个mapping 或者做clustering，主要是针对user context feature 做了clustering，所以我认为这个应该影响不会太大。

Q:下一个Bandits 方向?

A:不管是强化学习，还是一些推荐系统中Contextual Bandits 都是比较重要的方向，因为现在不管是一些推荐平台，比如Google 或Facebook，还是出行平台，比如像滴滴，我们都会往序列化决策这个方向走，因为单步决策能够产生的收益是有限的，其实大部分决策跟决策之间是会有序列化的影响，所以这个Bandits 也是我们后续优化的一个方向。

Q:线上、线下评估结果有差别吗？

A:在RL的场景里，如果去做一个online 的学习，这个肯定成本是比较大的，大部分通用的过程就是做一个offline 的policy 学习，offline policy 学习就涉及到simulator 的搭建，就是要模拟线上发生的过程。所以线上、线下评估结果肯定是会有差别的，这个主要取决于仿真器的准确程度。

Q:关于建环境有没有什么经验？

A:我们在这一块也做了很久的探索。感兴趣的同学可以看一下我们去年有一篇KDD的文章，主要是用GAN 和Imitation Learning 做了一个模拟环境。(文章名字叫：Environment Reconstruction with Hidden Confounders for Reinforcement Learning basedRecommendation）

Q:会不会导致资源愈加倾斜?

A:这个问题在我们实验部分有讲，比如说预算资源约束比较紧张的时候，这个策略就会比较好，找那些效果最好的user context 作推荐。这个取舍policy 可能觉得直接往最好的user context 做倾斜就可以了，因为资源紧张，要减少其他资源的探索；如果在资源比较多的时候，会做一个平衡，不一定都往origin reward 最高的user context 做执行，也会探索其他资源。

Q:出行平台上什么情况下需要用到这个算法？

A:在我们滴滴有很多推荐的场景，比如怎么对用户做打车的推荐？还有比如说首页上车点的推荐，在我们平台其实是比较多的是这样的推荐场景，还有定价场景，也要做action的cost约束，其实也是比较常见的，因为总共的展示次数或者价格的折扣是有限的。怎么在有限的action，或者resource constrained条件下去最大化policy的效果 这其实在出行场景当中也是比较普遍的。

Q：实验有建立仿真器吗？

A:我们的实验做了两块，第一块是做synthetic data，就是合成数据，合成数据它天然就会有一个data generator，所以天然就会有一个simulation 在里边。第二个是雅虎的数据，针对雅虎的数据我们会有一个模拟的过程，在我们文章里单独有一块写了simulation 是怎么做的，基本思想是，这个user，执行了policy 推荐的action，如果历史数据里边有，我们就会把这个数据去执行，如果历史数据没有，我们会把这个数据reject，这个也是Lin-UCB，还有一些其他文章的做法。当然也有一些比如说做仿真预测的，就是不同的用户，推荐不同的action，如果推荐的action 在历史数据中没有，我们作一个拟合，这类其实也有。这个仿真我可以再提一点，相对MDP，Bandits 仿真可以少一个过程，它只需要仿真，给不同的用户做推荐，不同的action 下收益是怎么样的。传统的MDP，是需要做两步的模拟：第一步是针对不同的状态，推荐不同的action，它的reward 是怎么样？还有一个模拟是下一个状态是什么？Bandits 算法可能只需要做reward 的模拟，传统MDP 是需要做两步的模拟，还有状态转移的模拟，状态的转移相对来说其实是比较难的。

Q:未被推荐的items 怎么进行参数的更新？

A：因为Bandits 是一个探索和挖掘的平衡，你可以看基本的算法，比如UCB 的算法，或者Lin-UCB 的算法，它是有UCB 的值，UCB 的值里可以看执行半径，执行半径对未被推荐的items 或者频繁被推荐的items 会有一个场控化，如果这个items 执行的越多，执行半径相对来说会越小。所以它会做一个天然的探索，那些没被执行过的items，它也会有一个倾斜。在我们这里其实也是，主要是看探索的资源，就是越大，它可能会探索的比较多，比较小的话，它会做资源上的简单倾斜。因为问题太多了，暂时我先回答到这里，如果大家感兴趣可以下载我们的文章，如果对实现感兴趣，也可以看一下GitHub code link。

点击文末“了解详情”可跳转至B站收看本次分享完整视频录像

本文校对、编辑：lynn、小杜、Xinyu

ppt截图由讲者提供

题图出处：medium