在线广告中的深度上下文强盗引导程序

2314GuideBoot：在线广告中深度上下文强盗的引导程序潘飞扬中国科学院计算技术研究所中国北京WeiWangTencent深圳，中国李浩明中国科学院计算技术研究所Yanrong Kang腾讯深圳，中国何清中国科学院计算技术研究所XiangAo中国科学院计算技术研究所Ao Tan腾讯深圳，中国摘要探索/利用（E& E）困境在于交互系统的核心，如在线广告，上下文强盗算法已被提出。贝叶斯方法通过不确定性估计提供指导性探索，但由于过度简化的假设，其另一方面，非贝叶斯自助方法可以通过使用深度奖励模型来应用于复杂问题，但缺乏对探索行为的明确指导。它仍然在很大程度上没有解决开发一个实用的方法，复杂的深上下文土匪。在本文中，我们介绍了引导引导（GuideBoot），结合两个世界的最佳GuideBoot通过在真实样本和带有假标签的噪声样本上训练多个模型来为探索行为提供明确的指导，其中噪声根据预测不确定性添加所提出的方法是有效的，因为它可以通过仅利用一个随机选择的模型在飞行中做出决策，但也是有效的，因为我们表明，它可以被视为汤普森抽样的非贝叶斯近似此外，我们将其扩展到一个在线版本，可以只从流数据中学习，这是在实际应用中的青睐在合成任务和大规模广告环境上的广泛实验表明，GuideBoot相对于以前的最先进的方法实现了显着的改进。中 国科学院智能信息处理重点实验室.也在中国科学院大学（UCAS）。†对应：Xiang Ao .本文在知识共享署名4.0国际（CC-BY 4.0）许可下发布作者保留在其个人和公司网站上以适当的署名传播作品的权利WWW©2021 IW 3C 2（国际万维网大会委员会），在知识共享CC-BY 4.0许可下发布。ACM ISBN 978-1-4503-8312-7/21/04。https://doi.org/10.1145/3442381.3449987CCS概念• 计算方法学→机器学习;·信息系统 →在线广告。关键词深度上下文强盗，Bootstrap，在线广告ACM参考格式：潘飞扬、李浩明、敖翔、 王伟、康艳荣、敖昙、清河。2021.GuideBoot：在线广告中 在网络会议2021（WWW '21）的会议记录，2021年4月19日至23日，斯洛文尼亚卢布尔雅那。ACM，美国纽约州纽约市，10页。https://doi.org/10.1145/3442381.34499871介绍随着深度学习的发展，机器学习驱动的在线广告和推荐系统近年来取得了巨大的成功，因为它能够对用户、广告和上下文之间的复杂深度依赖关系进行建模。然而，对于成本敏感的决策问题，如冷启动问题，它仍然是具有挑战性的开发实用的方法，以尽量减少累积遗憾。在线广告可以被视为一个巨大的决策问题，其最终目标是向正确的用户提供正确的广告探索和开发（E E）之间的权衡对于解决这个问题至关重要，因为决策者只能通过与环境的交互来获得反馈这样的问题可以被公式化为上下文强盗，已经提出了许多算法，并且在特定设置中从理论上或经验上证明是成功的。背景下的多武装匪徒有两个主要的探索路径贝叶斯方法通过贝叶斯后验推理来估计模型的不确定性，从而提供有指导的探索，并做出决策。例如，对于输入和奖励之间的依赖关系是线性函数的线性强盗，LinUCB [ 22 ]和Thompson Sampling[ 4 ]依赖于贝叶斯线性回归（BLR）。2315∈X轴--（·）（）∈ []∼ ()[（）]（·）WWWSGD型号-1型号-2Model-3······K型不可能不，我是B组2诺西湾···˜3不，我不知道随机选择恢复真实数据&生成虚假数据模型-k指导作用XyH={ （x，r）}不⌧⌧=1图1：GuideBoot的推理和训练。实线是用于推理的前馈传递，利用K个模型中的一个模型。虚线用于训练，包括每个模型的数据生成过程（红色虚线）和用于训练每个模型的反向传播（绿色虚线）。来推断后验奖励分布。 对于Bernoulli上下文强盗，GLM-UCB [8]使用贝叶斯逻辑回归来推导策略。也有研究使用高斯过程[19]和神经过程[11]在非线性设置中进行后验推理然而，这些方法难以扩展，因为精确的概率推理在具有高维输入和特征与结果之间的非线性依赖关系的复杂问题中通常是棘手的相比之下，非贝叶斯方法不需要底层模型的特定函数形式，因此适用于复杂问题。典型的选择是引导启发式，即，为了训练多个奖励模型（即， 深度神经网络）具有不同的初始化[24]以及随机样本子集[31]，并随机使用其中一个来做出决定。然而，这样的引导探索方法的行为没有被明确地指导。由每个单一模型诱导的子策略本质上是贪婪的，因此总体策略很有可能最终退化为次优贪婪策略。因此，对于复杂的深层背景的强盗，开发实用的方法仍然在很大程度上没有解决在本文中，我们提出了一种新的上下文强盗算法命名为引导引导引导（GuideBoot），它结合了贝叶斯和非贝叶斯方法的最佳GuideBoot的高级思想是为引导程序恢复行为提供基于不确定性的明确指导。与传统的基于bootstrap的方法类似，我们的方法训练了一组奖励模型，并在每一步随机选择一个模型来做出决定与以前的方法相比，我们不仅使用收集的样本的不同子集来训练模型，而且在训练模型时随机生成少量假样本，以便实现分布预测并防止过拟合。特别地，每个假样本是随机化真实样本的奖励信号而生成的，并且生成这样的假样本的概率与奖励的预测不确定性成比例通过这种方式，不熟悉的环境和很少选择的行动可以有机会被探索。GuideBoot的一个重要好处是，它总是可以在推理过程中以最小的计算复杂度动态地做出决策。如图1所示，它将耗时的不确定性估计留给了训练阶段，而不是推理（决策）阶段。因此，GuideBoot可以与任意奖励模型（即，用于点击率预测的现代深度神经网络）以及从简单的基于非参数计数的方法到复杂的贝叶斯方法的任何类型的不确定性估计方法。为了更好地适应在线广告和推荐系统等高频决策的实际应用，提出了一种能够高效处理流数据的扩展版GuideBoot，即Online GuideBoot。开发在线算法的最大挑战是代理只能从流数据中学习，而不能访问完整的历史。 我们的算法取代了自举重新启动的步骤与洗牌和分裂的步骤，它只运行在一个在线的缓冲区，这是很容易实现和经验强大。我们进行了系统的实验合成任务和两个大规模的现实世界的任务上的工业应用的在线广告。实验结果表明，我们的方法表现得更好，更稳定，比国家的最先进的经典设置和在线设置。本文的其余部分组织如下。第二节介绍了问题的设置和背景。第3节详细介绍了标准设置中的GuideBoot，其中代理维护完整的历史记录。第4节说明了如何在具有流数据的在线设置中部署我们的算法，其中代理仅从最近的经验中学习，而不访问整个历史。第5节演示了实验。2预赛2.1背景多武装匪徒我们考虑一个标准的上下文多臂强盗问题[21，22]。在每一步，环境揭示了一个上下文（即，推荐系统中的用户属性）和M个候选动作（即，在平台上不失一般性，我们写xt，a作为步骤t处的第a个动作的输入特征，包括相关的上下文信息。 环境还通过固定函数y t、a_rta定义了每个动作的预期回报 =fxt，a，其中奖励函数f是未知的那个特工要求代理选择一个动作at（即，要推荐的项目）。. . ，m. 为了简单起见，我们写xt<$xt，at。然后，环境根据xt抽取奖励。由于网络上的许多应用程序涉及优化二元结果（即，点击或转换），我们假设奖励是从伯努利分布中得出，即，rt伯努利y t，其中y t 如果t=0，1，则是期望奖励。在导出GuideBoot时，我们假设f是固定的。第3节中的算法当扩展到第4节中的在线版本时，可以放松这个静态假设。2.2贝叶斯方法上下文强盗的贝叶斯方法依赖于期望回报的准确概率推断，从而获得不确定性2316（一）|D）−（）的方式一（）下一页−（）下一页（）的方式∼ （一）|D）−一（·）（·）（·）一一GuideBoot：用于深度上下文Bandits的引导引导程序在线广告WWW'21，2021年4月19日至23日对每一个动作的评价。令D t−1 ={（xτ，rτ）}t−1是col-Wang等人[33]第33话被骗的人时间步长t之前的选定样本τ=1.贝叶斯方法不仅历史遗留下来的学习近似的奖励模型ya=fθxa，但也学习参数pθt1的后验分布。利用后验UCB类算法，可以得到最优估计的置信上界UCB，即：例如，p（yay<$UCB）>1−δ，并且<然而，这些方法缺乏不确定性或先验的明确概念的明确指导，因此与非深度设置中的贝叶斯方法相比，它们往往具有次优遗憾我们的工作与这些无指导的探索选择具有最高置信上限at=arg maxyUC B。方法，因为我们的GuideBoot会在一个明确的指导的不确定性的奖励，其中aa引导是通过操纵假样本来模仿a数据来实现的另一方面，汤普森采样从后验θ′pθt1中随机采样一组参数来预测奖励，并由此做出决定，at = arg max fθ ′（xa）.这些贝叶斯方法的缺点是双重的。首先，精确的概率推理往往是棘手的实际问题。当奖励函数被假设为（广义）线性模型时，后验可以用贝叶斯线性（逻辑）回归来推断。对于复杂的问题，这是不可行的，特别是当人们想使用深度神经网络来预测奖励时。第二，即使我们假设后验是已知的，与简单的贪婪策略相比，做出决策所需的计算负担也会大幅增加对于线性强盗，LinUCB[22]和GLM-UCB [8]需要Od2的时间复杂度来计算置信上限，比普通线性模型慢一个数量级来进行预测。汤普森抽样与线性回报需要O d3的采样参数从多变量高斯后验分布。在非线性情况下，高斯过程bandit [19]需要更多的计算来获得核矩阵。最近的贝叶斯神经网络依赖于蒙特卡洛变分推理[3，9，10，17]也显着增加了推理时间成本。在实际应用中，决策过程中的这种放缓往往是不可接受的在本文中，所提出的方法具有相同的计算复杂度作为一个标准的前馈神经网络，它可以作出决定的飞行。2.3非贝叶斯方法相反，非贝叶斯方法可以应用于具有任意复杂奖励函数的问题。例如，最简单的启发式搜索-贪婪算法以概率1选择argmax操作arg max afθxa，否则随机搜索。玻尔兹曼策略计算候选操作的预测奖励上的softmax，以导出随机策略，该策略在[26]中也具有基于Bootstrap的探索在强化学习[24，27]和强盗问题[6，7，20，31，32]中也是有效的。，它要么维护历史的多个自举样本，要么从不同的数据子集训练多个奖励模型这些方法可以与深度神经网络结合，因此可以在深度上下文禁令中实现最先进的性能。Tang等人[31]使用泊松分布来绘制重复的样本，以便用在线流数据来模拟恢复过程Elmachtoub等人[7]提出了一种上下文bandit算法，该算法遵循相同的自举方法，但使用决策树作为基本学习者。 除了自举真实样本和更新真实观察到的奖励，Kveton等人。[20]提出Giro，为每一次拉手臂设计伪奖励前科2.4其他相关工作也有研究在（上下文）多武装土匪问题的理论证明自助。奥斯班德和范罗伊[25]提出了一种名为BootstrapThompson的强盗算法，并证明该算法近似于伯努利强盗中的Thompson采样。Vaswani等人[32]将其推广到分类和高斯奖励。Hao等[13]用乘子引导法扩展了UCB，并为所提出的算法导出了问题相关和问题无关的正则界。虽然这些方法具有很强的理论性质，但往往局限于过于简化的设置。在本文中，我们还提供了一个贝叶斯的观点来解释我们的算法（在第3.4节）。 我们表明，我们的GuideBoot可以用信息先验近似贝叶斯后验，这比以前基于退化先验的工作更通用和灵活[25]。3引导器3.1概览方法GuideBoot是一种实用的方法，可以让深度上下文强盗在飞行中做出决定。基本的推理和训练过程如图1所示。在这一部分中，我们描述了在记录的数据集（又名经验缓冲区）上进行模型更新的过程，与之前对基于引导的上下文强盗的研究相同[20，31] 。 在 第 4 节 的 后 面 ， 我 们 将 介 绍 一 个 更 实 用 的 在 线GuideBoot的实现。GuideBoot代理维护K个独立训练的奖励模型f（1），. . . ，f（K）. 在第t步，当一个带有多个候选动作的查询到达系统时，代理随机选择一个模型f（k）来预测动作的分数，并选择具有最大分数的动作，即，at =arg max f（k）（xt，a）.（一）对于训练，所有模型都在由真实样本和随机生成的假样本组成的不同自举数据子集上并行地更新梯度下降。GuideBoot的伪代码在算法1中概述。GuideBoot的关键新颖之处在于基于不确定性的指导，用于探索和利用之间的权衡，通过使用包括一小部分假样本的扰动数据集训练模型来实现。 在本章的其余部分，我们将在3.2节介绍什么是假样本，在3.3节介绍如何使用假样本训练模型，在3.4节介绍为什么要使用假样本。2317H（·）（）下一页←H ← H {（）}联系我们←（）（）≤（）（）（）下一页B（）B联系我们 /（）}B← B {（）B← B {（）WWW表1：符号符号描述设置时间步长m是候选操作K候选模型1：t存储所有历史样本的重放缓冲区on在更新模型之前临时收集一批样本的在线缓冲区在步骤t输入候选动作a的特征（包括yt，a步骤tt的操作a的预定期望值t步骤t的所xtxt，at的简化表示法Bi样本的第i个剩余子集f（k）（·）第k个奖励模型<$（·）将输入x映射到算法1GuideBoot（经验回放）要求：模型数量K，引导批量b。要求：方程中的引导<$的参数α（五）、1：初始化重放缓冲区=;2：初始化K个模型f（1），. . . ，f（K）独立地;3：初始化密度函数ρρ。4：对于t=1，2，. . . 做//第一部分决策5：观察m个动作xt，1，. . . ，xt，m。6：选择k1，K作为模型索引。7：估计y=t，af（k）xt，a 对于所有a=1，. . . ，m.8：采取行动，最大限度地提高警惕，并重新审视自己。9：追加历史xt，at ，rt.//第二部分.准备引导数据10： 用xt，at，rt更新密度函数ρ。11： 对于k = 1，. . . ，K do12：Bk←从H中重新采样一个大小为b的批次。产生假样本13：Bk← Bkρε（·）非标准化密度估计3.2从假样品中获得指导我们从一个示例开始，该示例显示vanilla bootstrap重新采样失败的情况考虑一个冷启动广告问题，我们希望最大化点击率（CTR）。考虑两个候选广告Ad_A和Ad_B，其地面实况CTR分别为0.02和0.03。假设两个广告都已经被打动了50次，Ad_A有1次点击，Ad_B没有点击。在这种情况下，不幸的是，Ad_B的CTR的自助估计量在均值和方差方面都将始终为零虽然估计完全符合收集的数据，但诱导策略总是推荐Ad_A，这显然是次优的。为了解决这个问题，我们应该直观地向代理引入“广告的点击率不可能为零”。然后，当没有足够的数据时，智能体可以探索不熟悉的动作，并且当所有候选动作都有足够的数据时，可以利用学习的奖励模型来进行奖励。传统上，参数贝叶斯方法在训练过程中将先验分布添加到模型参数中作为正则化。相比之下，我们实现这一点，通过引入一个先验的数据，而不是参数，和派生的算法可以成功地与非参数引导技术。数据先验通过在训练过程中生成假样本来实现，以规范优化过程。伪样本的生成过程如下。 在步骤t，如果智能体选择具有输入特征xt<$xt的动作a t，at并获得奖励它收集一个真实的样本xt，然后，我们生成假样本xt，0和xt，1，它们对真实样本具有相同的输入，但具有假奖励。接下来，当训练奖励模型时，两个假样本中的每一个都以概率0<$xt 1被使用，否则就不<通过添加随机化的假样本，样本分布14：对于每个记录xj，rj 在我15：<$jminα ρxj，116：概率为<$j：k17：概率为<$j：k18：结束19：结束//第三部分.更新模型20： 对于k = 1，. . . ，K do21：使用梯度下降法更新模型f（k）22：结束23：结束其本质上是给定上下文xt的数据先验上的显著性权重。直觉上，指导函数表示输入的不确定性：智能体对动作越熟悉，指导函数给出的概率就越小。这可以通过使用简单的基于计数的方法或复杂的贝叶斯方法来实现。在3.4节中详细介绍了正式的概率解释以及实际应用中指导函数的具体选择。让通过使用数据先验，如果我们分配一个正的指导函数来为Ad_A和Ad_B生成假样本，则通过从Ad_B的数据中恢复的自举估计量可以以很大的概率为非零，因此Ad_B总是有机会被打动。3.3使用重新采样的真实样本和生成的假样本进行训练GuideBoot的训练结合了来自真实数据的vanilla bootstrap恢复和生成的假样本。我们需要训练K个模型（例如，K前馈神经网络）可以平滑，所以代理人不太可能过度-在经验缓冲器H1上：t={（xτ，rτ）}t的所有收集的相信自己的预测。我们称之为时间步长t之前的样本τ=1. 在训练过程中，所有的模型都运行-伪样本<$（·）：X →（0， 1]是引导函数或引导，domly初始化，然后与minibatchHH2318≤≤1998年，）的方式2α+n（）（）（）BB∈ B（）BBH一/（）下一页（）下一页（·）（）≥（）下一页（）（）→.ˆJ1一（）下一页S且方差为SSGuideBoot：用于深度上下文Bandits的引导引导程序在线广告WWW'21，2021年4月19日至23日梯度下降对于第k个模型的更新，我们首先按照Bag of LittleBootstrap（BLB，[18]）执行b-out-tbootstrap，1：t（i.i.d.用替换重新排序）并得到子集k，其中b是k的大小的超参数。接下来，对于每个样本xk，我们计算指导函数<$x并以概率<$x生成假样本x，0或x，1。所以我们可以得到一个混合样本集，作为k和集合的并集，生成的假样本最后，我们执行梯度步骤下降以最小化样本上的负对数似然更新模型。GuideBoot的伪代码如算法1所示。不同的是-使用不同的样本集训练ENT模型，可以并行完成模型包的自举响应、假数据生成和梯度下降更新。3.4GuideBoot作为贝叶斯近似在统计学文献中已知，“自举分布表示（近似）非参数、非信息后验概率”（参见[ 14 ]的第8.4章），[ 25 ]中也使用该分布来推导基于自举的多臂bandit。 在这一部分中，我们提出了一个新的结果，我们的GuideBoot可以被看作是一个近似的信息后验，由于显式的指导。为了具体展示GuideBoot和贝叶斯推理之间的联系，让我们首先考虑一个简化的的反馈ra，1，. . .，ra，n伯努利ya 对于动作a，0nsn次成功。在这种情况下，如果我们使用贝叶斯推断来估计ya，y a的先验分布是对称的Beta（α，α），ya的后验分布是伊 贾 |{Ra ， 1 ， . . . ， ra ， N}<$Beta （ α+ns ， α+n−ns），（2）是ya的有偏估计，均值为α +ns，方差为（α +ns）2（α +n − ns）的概率。此外，由于bootstrap rescue是替换的，我们证明了y_n_d也可以通过在stan之后添加假样本来构造标准引导恢复过程。也就是说，对于每个重新采样的数据点，我们添加奖励为0或1的假样本，两者的概率都是α n。由于n是动作a的印象数，我们可以将此概率改写为<$（a）=α/计数（a），（4）这是GuideBoot在应用于非上下文多武装匪徒时的引导功能。通过上述分析，这种算法可以被视为具有Beta先验的贝叶斯汤普森采样请注意，在我们的算法中，在重新加载之后移动假数据生成过程是必不可少的，这使得体验重新加载而无需向缓冲区添加假样本。它还支持第4节所述的在线培训。最后，上述方法可以扩展到上下文强盗。 当每个样本都有一个特征输入x并且奖励模型是深度神经网络时，使用贝叶斯方法是非常重要的，因为神经网络的先验和后验都不容易获得。然而，我们的非参数GuideBoot仍然很容易运行。回想一下，等式中的计数a（4）可以看作是一个非标准化的密度估计的行动a. 用同样的直觉，具有输入x的上下文强盗的指导函数被公式化为与未归一化密度估计成反比<$（x）= α/ρ <$（x）。（五）其中ρρx表示经验缓冲区中输入x的未归一化密度估计特别地，我们假设对于任何可见的输入x，ρ∈x1，使得<$x的值是严格有界的。现在，我们推荐几种特定的ρ选择，的指导功能。 从上面的分析中，可以看出，在等式（1）中提到的基于计数的引导函数是有效的。（4）成为2 α+n2α+n+ 1另一方面，通过以下方法获得的bootstrap均值估计Eq的特殊情况（5）设ρ（xa）=Count（a），则a可以是雷塞林国际公司从该数据中得到的替换样本遵循二项分布nybBi（n，ns/n）（3）上下文向量xa内的分类索引。例如，对于冷启动广告，我们希望促进对小广告或新广告的探索，我们可以简单地让一其中Bi（·，·）表示二项分布。所以y=b是无偏的ρα（xa）=Count（ad_ID），（6）y的估计量平均值为n/nan（n-n）/n3.其中，Count（ad_ID）是该事件的历史印象的计数，所以y的后验的均值和方差非常ad. 对于包含多个分类字段的输入，可以相似交替地使用计数的未定标谐波平均，即，请注意，自助后验可以被视为具有无信息先验α0的近似贝叶斯后验然而，在强盗算法中，信息先验是必不可少的，例如，Jρ（x）=[=计数-1（xj）]−1、（7）伯努利多臂强盗的经典汤普森采样通常对每个臂使用β 1， 1的先验那么现在的问题是，我们如何修改bootstrap算法来近似具有信息先验的解决方案是GuideBoot。在上面的情况下，我们可以通过向数据添加两个假反馈0和1，然后运行bootstrap resource来实现这一点。具体来说，假奖励设为α。得到的估计量y其中J是分类字段的数量，xj是x的第j个条目。在之前关于Thompson Sampling的研究中已经表明，它可以作为贝叶斯线性回归的精确对角后验近似，在一系列任务中具有良好的性能4在线引导对于GuideBoot）的平均值为α+ns在广告和推荐等实际应用中，2α+n与ya相同，（α+ns）（α+n−ns）的方差，其渐近等于算法必须响应大量的并发请求，并实时更新模型与流数据大那是你的。（2α+n）3数据量和实时响应的要求使得B2319中文（简体）H ← H 联系我们←（）下一页←HH中文（简体）1←H ← H 联系我们联系我们←（）H1（）B联系我们 /（）}BB ← B {（）}1B ← B {（）}WWW算法不可能从完整的历史缓冲区进行引导恢复。在许多应用中，即使单独存储经验缓冲区也可能是昂贵的为了弥补在线场景中的挑战，我们提出了在线GuideBoot，一个简单而有效的版本的GuideBoot，更实用的在线设置。4.1在线设置中的GuideBoot为了更好地描述在线环境，我们给出了算法2中使用贪婪策略的在线强盗的典型轮廓。下面描述具有流数据的在线学习环境的设置。我们假设在线代理在更新自己之前总是收集一批样本，这在许多具有并发查询的实际系统我们表示在线收集的算法2常规贪婪算法（在线）1：初始化模型f。2：whileTruedo3：清除在线缓冲区对//第一部分服务4：对于t = 1，. . . ，c do5：观察m个动作xt，1，. . . ，xt，m6：估计y=t，afxt，a 对于所有a=1，. . . ，m.7：采取行动，最大限度地提高警惕，并重新采取行动。8：添加缓冲区ononxt，at ，rt.9：结束//第二部分.学习10：将H〇 n拆分成小批次{Bi}n小批量的c样品由HonHt−c：t，应用于11： 更新模型f1在{Bi}n上的梯度下降更新奖励模型。 为了最大化一般性，这里批量大小c可以是变化的或固定的数字，这取决于在线服务的实际设计。例如，如果它是常数（例如，c=512），这意味着代理仅每c个时间步更新其奖励模型c可能是一个变量，例如，是最近10秒内收到的在线样本数。要在没有完整历史数据的情况下在这种在线设置中使用引导技术，可以仅对最近的批处理执行重新加载，这可能会降低性能。然而，幸运的是，我们的GuideBoot算法仍然可以很好地工作，通过构建一个随机的网络流数据。虽然我们提出的自举方法并不完全遵循传统的自举方法，但它具有很强的经验性能，并且易于实现。回想一下，使用在不同的回报数据集上训练的多个模型的原因是为了跟踪预测回报中的模型不确定性。考虑到奖励模型（即，在实际的在线学习中，通常采用随机梯度下降（SGD）方法对模型进行更新，但我们可以通过随机化到达样本的序列来直接获得模型的随机更新因此，我们建议使用洗牌和minimizing而不是重新洗牌来构造批处理12：结束时Algorithm 3Online GuideBoot1：初始化K个模型f（1），. . . ，f（K）独立地;2：初始化密度函数ρρ。3：whileTruedo4：清除在线缓冲区对//第一部分服务5：对于t = 1，. . . ，c do6：观察m个动作xt，1，. . . ，xt，m。7：选择k1，K作为模型索引。8：估计y=t，af（k）xt，a 对于所有a=1，. . . ，m.9：采取行动，最大限度地提高警惕，并重新采取行动。10：添加缓冲区ononxt，at ，rt.11：结束//第二部分.学习图12：更新密度函数ρ，基于.13： 对于k = 1，. . . ，K do14：混洗并将H分成小批次{B1}n。真实的数据。 在获得真实数据的子集之后，我们使用与上一节相同的生成假样本的过程，这是为每个模型独立完成的。因此，不同的模型在训练时仍然可以接收不同的假样本。所导出的在线算法的伪代码（名为Online GuideBoot）被示出为算法3。具体地，在收集具有c个样本的在线缓冲区之后，我们如下构造用于更新每个模型的流水线：首先，缓冲区中的样本被混洗并分成n个不相交的小批次，其中n是预定义的小批次数量。其次，对于每个小批次，我们15：对于每个小批次我做16：对于每个记录xj，rj 在我做17：<$jminα ρxj，118：概率为<$j：l lxj，119：概率为<$j：l lxj，020：结束21：结束22：用小批量{B1}n更新模型f（k）使用上一节中描述的相同原理生成假样本，并将其添加到小批量中。最后，通过梯度下降法对这些小批量数据进行更新。因此，更新每个模型的梯度是在具有随机生成的假样本的不同小批量上计算的，这使得能够进行随机优化。4.2实施和部署我们的算法可以很容易地在工业平台上实现，如广告系统[5，15，23]或现代工业RL23： 结束第24章：结束平台[12]，这在冷启动问题[28，30]中特别有用。在线广告系统上的学习管道的概述如图2所示。 管道由两部分组成：在线服务和在线学习。2320（·）−[客户端]、∈∈[][] −）∈联系我们（）（ [][] U{}GuideBoot：用于深度上下文Bandits的引导引导程序在线广告WWW'21，2021年4月19日至23日服务部分负责对每个到来的请求进行实时决策。每当系统接收到具有输入上下文1的新请求时，随后处理以下步骤。1. 检索候选集。一组候选动作（即，广告或项目）连同输入属性和特征一起根据上下文（查询）来提供。2. 推理。每个候选人都由从K个模型中随机选择的奖励模型进行评估，并得到一个预测得分 分数通常是预期的奖励，例如eCPM（每千次展示的预期成本），需要根据预测点击率（pCTR）进行估计。系统将使用特定的模型在后端服务器上进行预测，该后端服务器是从模型的后端集群中随机选择的。3. 决策的将排名靠前的广告发送给用户。另一方面，学习部分收集用户反馈并更新模型。我们考虑用c步骤记录一个小的在线缓冲区，以便我们可以运行GuideBoot算法。1. 测井用户点击与否）连同输入上下文和所选动作一起被收集并发布到消息队列。记录从消息队列中获取并存储到在线缓冲区，直到有足够的数据来训练模型。2. 更新不确定性估计值。 如第3.4节所述，制导函数<$与未归一化密度模型成反比，因此可以将其理解为不确定性估计量。观察在线缓冲区后，应更新估计器。例如，当使用等式中的基于计数的指导时，（4）、系统需要维护计数表。3. GuideBoot指南。第4.1节详细介绍了该流程以及算法3中的第12-20行。该算法通过对在线缓冲区进行混洗和分割，并行构造K系列小批量，并利用引导函数生成伪样本。4. 以服从为基础的训练学习者更新模型引导引导器的样本只有在更新完成后，模型才会被推送到服务区。在训练之后，缓冲器和缓冲器流被清除并且准备好接收新的样本。5实验在本节中，我们将在合成任务和大规模真实广告环境中评估我们的GuideBoot。具体而言，我们试图通过实验回答以下问题：Q1. 在一个标准的非深度伯努利设置中，Guide- Boot与经典的UCB和Thompson采样算法相比如何Q2. 在复杂的深度上下文bandits中，GuideBoot与最近的高级深度方法相比如何？Q3. 什么有助于GuideBoot的改进？1我们使用在线广告场景作为示例。输入上下文通常包含来自用户的查询，以及查询的文本输入、用户的属性，服务查询（上下候选人库候选人库后端群集（行动集）（行动集）广告（行模型服务 复 制副本消息队列GuideBoot数据流以服从为基础的学习者用户响应（奖估计器不确定决策学习图2：使用Online GuideBoot的在线广告系统的整体管道。5.1合成任务5.1.1设置. 虽然本文的原始动机是为深度复杂的上下文强盗构建实用算法，但我们想首先检查经典设置中的Guide-Boot因此，我们建立了标准的伯努利强盗环境，其中奖励函数是广义线性模型。 在这 样的 设置中 ， 已经 广泛研 究了 许 多 基 于 UCB 和Thompson采样的算法在次线性累积遗憾界限下可证明是有效的[8]。现在我们描述伯努利强盗的详细设置在每一步中，我们观察到m = 25个动作，每个动作都有三个分类属性xa = a，xa，1 ， xa ， 2 ， 其 中 a = 1 ， . ..， 25 ， xa ，11，5，和xa，21， 5。对于每个输入xa，奖励从伯努利ya，其中预言机的预期回报是ya=σ wa+w1xa，1 +w2xa，21 其中σ是sigmoid函数，w0R25、w1R5和w2R5是三个场的系数向量。这里我们用符号wi表示向量w的第i项.我们生成100个这种设置的随机环境，其中每个环境中w0，w1和w2的系数是i.i.d.。从U（-0）25，0。25）。5.1.2比较方法。由于问题是标准的伯努利上下文强盗，我们将我们的GuideBoot与以下经典算法进行比较。贪婪算法：最简单的无引导算法，它以1/2的概率选择具有最大预期回报的动作，否则随机探索我们设置= 0。1是以往研究中常见的选择。贪婪（decay）：贪婪的一个变体，带有decaying贪婪的增量虽然和普通的贪婪算法一样简单，但它通常被用作一种经验上很强的基线方法。我们让从0开始线性衰减。从1到0，全程训练。GLM-UCB：广义线性模型的UCB算法，在[8]中提出 它依赖于用贝叶斯广义线性模型估计奖励预测的置信上界。探索奖励的系数已设置以及用户当αt=log（t+1），如其原始文件中所建议的2321（·）WWW0.80.70.60.50.40.30.2合成数据：平均标准化遗憾与时间- 贪婪（GLM-UCBOBBGiro引导eBoot新指南Guid昂立陷阱LR拉靴TS-BVani衰变）=0.1）（-gre0 25005000750010000125001500017500 20000时间步长5.1.3结果平均后悔程度如图3所示。从结果中，我们观察到我们的GuideBoot工作得很好。具体来说，GuideBoot的经验重放版本执行最好的，并显着优于经典的贝叶斯方法以及以前的基于引导程序的算法。为了更详细地分析基于引导程序的算法的结果，我们注意到，即使可以从整个历史中重新采样，vanilla bootstrap也运行得很差。Giro在历史记录中添加了固定比例的假样本，并优于vanilla bootstrap。接下来，我们发现GuideBoot带来了显着的性能改善，这表明伪样本生成以及指导功能对算法至关重要通过将GuideBoot与vanilla bootstrap和Giro进行比较，很明显，基于不确定性的指导有所帮助，这回答了问题Q3。另一方面，对于仅使用流数据学习的基于引导程序的方法，OBB作为香草图3：50次随机运行的合成任务的实验结果。报告了一段时间内的平均遗憾表2：腾讯广告模拟器统计数据数据集腾讯广告A腾讯广告B#时间步长4.5M14.7M广告数量（总计）8.9K6.5K#候选人（每一步）250 ~ 450100 ~ 200#上下文1313#候选人1212#context4.2K4.3K#广告12K9.4KTS-BLR：采用贝叶斯广义线性模型的汤普森采样[1，4]，这是常用的，并在最近的一项研究中显示出最先进的性能[29]。在GLM-UCB中，使用相同的广义线性模型学习奖励模型。Bootstrap：具有经验重放的标准bootstrap响应方法，其维护使用来自历史缓冲区的重采样数据训练的K个奖励模型OBB：在[31]中提出的在线引导Bandit算法，它可以使用重复的样本进行在线引导，其中重复数是从泊松分布中得出的Giro：Kveton等人最近提出的一种基于引导的方法。[20]，它在从扰动历史缓冲区重新采样的数据上训练K模型。当每个新样本被添加到缓冲区时，的伪样本也以概率α = 0添加。5.我 们 测 试 了 GuideBoot 的 体 验 重 播 版 本 和 在 线 版 本 （ 用GuideBoot和Online Guideboot，re-boot），其中α=1，ρ=1。（七）、对于所有基于自举的方法，我们将K设置为5，这对于自举模型是足够的，如以前的工作[20，31]所示。在基于引导的方法中，Vanilla Bootstrap、Giro和GuideBoot需要存储整个历史，而OBB和Online GuideBoot是不需要整个经验缓冲区的在线方法bootstrap遭受了巨大的损失。然而，我们的在线GuideBoot仍然工作得相当好，它相对于GuideBoot的损失很小，这表明了洗牌和分割步骤的有效性。当很难访问整个历史记录时，在线5.2在线广告接下来，我们在真实世界的在线广告环境中进行实验，其中涉及高维特征输入和非静态用户响应，这些特征具有复杂的依赖关系。由于在线A/B测试的不可行性，开发了基于在线广告平台历史日志的大规模模拟器5.2.1广告模拟设置。 我们从腾讯的在线广告系统中收集了五天的广告日志。具体来说，我们从腾讯展示广告和Feed广告的两个主要站点中抽取了两个日志数据集（分别写为腾讯广告A和腾讯广告B）。数据集的统计数据见表2。在日志中，每条记录都是一个真实的请求，由两部分组成：请求的上下文和候选池。上下文包括查询和用户特征，例如用户的性别、年龄和设备类型。候选池是一批具有其属性的广告（例如，广告ID和广告商ID）。模拟器具有由复杂的黑盒用户模型给出的每个（上下文，广告）对的点击率（CTR），该黑盒用户模型对于代理是未知的当代理选择广告时，模拟器使用用户模型对二进制反馈进行采样代理人的目标是达到高平均水平在学习过程中给予奖励。对于每个模拟器，我们构建了两组实验：一组使用经验重放，其中模型使用从整个历史中采样的小批量更新，另一组使用在线流数据而不存储所有历史。我们在10个随机种子上运行所有实验，并报告平均奖励。5.2.2模型结构和比较方法。奖励函数由具有嵌入层和两个隐藏层的神经网络建模。嵌入层将每个原始字段转换为8维稠密向量。所有输入字段的嵌入被连接到一个向量中，然后将其输入到ReLU中平均后悔2322、（）/（）[客户端]（ ）（）/（）（