© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons LicenseCEURWorkshopProceedings0一种具有臂级符合条件控制的非参数情境Bandit用于客户服务路由0Ruofeng Wen 1，*，Wenjun Zeng 1和Yi Liu 101. 亚马逊客户参与技术0摘要亚马逊客户服务（CS）每年为数百万客户联系提供实时支持。虽然机器人解决者有助于自动化一些流量，但我们仍然看到对人工代理的高需求，也称为实际主题专家（SME）。客户通过不同领域（退货政策、设备故障排除等）提出问题。根据他们的培训，不是所有的SME都有资格处理所有联系。将联系路由到有资格的SME变得非平凡，因为SME的领域资格取决于培训质量，并且随时间可能会发生变化。为了在同时学习真实资格状态的情况下最佳地推荐SME，我们建议使用非参数情境Bandit算法（K-Boot）加上资格控制（EC）算法来形式化路由问题。K-Boot使用核平滑器对过去选择的相似样本进行奖励建模，并使用Bootstrap ThompsonSampling进行探索。EC通过最初系统声明的资格来过滤臂（SME），并动态验证此信息的可靠性。所提出的K-Boot是一种通用的Bandit算法，EC适用于其他Bandit。我们的模拟研究表明，K-Boot的性能与最先进的Bandit模型相当，当存在随机资格信号时，EC提高了K-Boot的性能。0关键词 Bandit，客户服务路由，臂符合条件，非参数01.介绍0在亚马逊客户服务（CS）中，我们实时调度人工代理，也称为实际主题专家（SME），来处理数百万客户联系。SME路由自动化过程分为两步：首先是自然语言理解（NLU）模型，用于处理客户的输入并识别相关领域（退货政策、设备故障排除等）；然后是分派符合条件的SME。我们定义符合条件为SME通过培训掌握相关领域所需的技能。SME路由是一个非平凡的问题，原因有四：首先，NLU模型不太可能以完美的准确性对领域进行分类。其次，由运营团队确定的SME符合条件的可靠性取决于培训计划的质量和准备情况。第三，领域分类法和SME的符合条件状态可以以分散的方式发生变化。实际上，难以跟踪所有符合条件的更新，假设是正确的。最后，符合条件的SME并不保证客户满意度，导致嘈杂的反馈信号。所有这些不确定性使得SME路由成为一个具有挑战性的问题。为了解决这种复杂性，我们将CS路由问题形式化为一个推荐问题，并使用情境Bandit。0Knowledge-aware and Conversational RecommenderSystems（KaRS）研讨会第4版@RecSys2022年9月18-23日，2023年，美国华盛顿州西雅图。*通讯作者。�ruofeng@amazon.com（R. Wen）；zengwenj@amazon.com（W.Zeng）；yiam@amazon.com（Y. Liu）0ISSN 1613-0073 CEUR研讨会论文集（CEUR-WS.org）0图1：CS路由问题。推荐的目标是选择一个代理，这将导致此客户联系的最佳结果。0作为解决方案。Bandit是用于在线推荐的顺序决策框架，已经在亚马逊、谷歌、Netflix和雅虎等公司中使用[1]。在情境Bandit中，决策者根据可用的情境信息（联系记录嵌入、客户资料等）依次选择一个臂/动作（在我们的案例中是SME），并观察奖励信号（客户满意度、联系转移等）[2]。目标是在每个情境下推荐臂。0步骤是最大化随时间累积奖励的预期。我们将赌博应用于路由问题，因为它可以最优地探索不确定性并适应动态变化。特别是，SME资格的不确定性促使我们制定一种新类型的赌博，以利用基于手臂的资格信号。我们的贡献。我们提出了K-Boot，一种非参数上下文赌博算法，用于建模奖励和探索，以及一种EligibilityController（EC）算法，用于建模手臂级资格。K-Boot使用�-最近邻（�-NN）方法从过去找到相似的样本，对找到的样本应用Nadaraya-Watson核回归来估计奖励，并采用Bootstrap ThompsonSampling作为探索策略。EC组件基于其估计的Spearman's Rank CorrelationCoefficient来实现动态的顶级手臂过滤器。我们对这种端到端的非参数设置感兴趣，因为它具有实用性：性能稳健，解释性强，简单的非技术性维护对业务合作伙伴友好。例如，�-NN组件使得容易调查哪些历史联系支持SME推荐，然后通过修剪不需要的异常值来快速部署在线修复。虽然K-Boot和EC在这里被提出为一套，但每个都可以独立应用 -K-Boot是一种通用的赌博算法，EC可以控制其他赌博的手臂资格，例如LinUCB。在本文的其余部分中，我们将在第2节中回顾相关文献，第3节中设置正式问题，并在第4节中详细介绍所提出的算法。然后我们在第5节中呈现我们的模型结果，并在最后总结本文。02. 相关工作0在大多数赌博应用中，要推荐的项目是产品和网页内容（小部件，新闻文章等）。最近，我们看到了在对话中使用赌博进行路由推荐的研究工作。在[6]中，他们使用上下文赌博来利用查询和用户特征以及对话上下文，并构建一个编排来路由对话。在[5]中，他们构建了赌博模型，根据微软产品的客户查询分配解决方案给聊天机器人。这是与我们问题最相关的工作。然而，他们假设上游模型提供一组可行的动作来开始，并且赌博本身不处理手臂资格的不确定性。总的来说，与现有的产品和网页内容推荐的广泛赌博文献相比，用于路由推荐的赌博工作很少。ThompsonSampling（TS）是一种在赌博中平衡探索和开发的启发式方法。0参数化方式实现TS是通过从后验分布中绘制奖励函数参数�，使用采样的参数计算奖励，并选择最大化估计奖励函数的手臂来实现的。�通常被假定遵循共轭-指数族分布，从而产生封闭形式的后验分布。也有使用变分方法提供后验的解析近似并强制可追踪性的工作。BootstrapTS以一种不同的方式引入波动性：它以非参数方式从奖励历史中估计的最高bootstrap均值来选择手臂。该方法的一个缺点是训练每个Bootstrap训练集的赌博模型的计算成本对于大规模实时问题来说是困难的。[10]提出了一种通用的非参数赌博算法，但当存在上下文时，他们回到了参数化奖励函数的方法。[11]通过贝叶斯Bootstrap进一步提高了对于非上下文赌博的探索效率。我们将BootstrapTS与单个�-NN配对以进行非参数上下文探索。基于核的赌博使用核函数通过非参数奖励估计器，结合TS或UCB等探索策略。高斯过程（GP）在赌博领域有着广泛的应用，例如GP-UCB和GP-TS。然而，GP推断是昂贵的 -标准方法的复杂度为�（�3），其中�是训练样本的数量。最有效的稀疏或低秩GP方法仍然需要�（��2），其中�是指示感应变量数量的超参数 -有关的评论请参见[14]。我们使用�-NN使推断时间为�（�log�）。03. 公式: 具有臂资格的上下文赌博0我们定义了两种不同数据接口的资格设置类型。 (1) 资格分数: 对于给定的上下文 x，观察到每个臂 e = ( � 1 , � 2 , . . . ) 的资格分数列表，其中 � � ∈ [0 , 1] 代表臂 � �的分数。较大的分数意味着对于当前样本/迭代，对于臂的资格有更高的信心。一个直观的解释是臂在为自己竞标。这种分数设置假设每个臂（的所有者）能够以分布式和独立的方式适应性地评估动态环境，这可能对于赌博者来说是未知的。典型的例子包括广告竞标和语音助手的技能检测-每个广告/技能可能通过相同的API进行管理，但在动态竞争中由不同的客户端进行管理。(2) 资格状态:假设系统在任何时候都可以被分类为 �种可能的状态。每个臂声称在某个状态下是否有资格，用长度为 �的常数二进制向量 c � 代表臂 � � 。如果 c � 的第 � 个元素为 1 ，则臂 � � 声称在第 � 个状态下有资格，否则为 0 。给定一个上下文 x ，观察到一个长度为 �的状态的随机分布，用长度为 � 的概率向量 p代表。对于客服路由，状态是客户问题的类型，声称是SME的相应技能集，而 p是NLU的预测分布。注意，分数可以计算为声称的资格二进制向量和状态概率向量的内积: � � := c � � p，因此状态设置收敛到分数设置。两种接口之间的主要实际区别在于声称方的努力程度:状态接口简化了对有限状态集上的静态二进制投票的资格声称，而分数接口要求具有上下文意识的评分。考虑一个具有一组臂 { � 1 , � 2 , . . . } 的上下文赌博。在第 �轮，观察到上下文 x � ，资格分数 e �要么被观察到（分数接口），要么被推导出来（状态接口）。在拉动臂之后，揭示了奖励 � � ∈ [0 , 1] 。目标是在 � 轮上最小化预期遗憾: ∑� � � =1 ( E [ � | � � * , x � , e � ] − E [ � | � � , x � , e � ]) ，其中 � � * 是事后这一轮的最佳行动。4.1. K-Boot0在提出的算法中，按顺序运行资格控制器（EC）以过滤不合格的臂，然后运行K-Boot以在剩下的臂中找到最佳的。下面，我们首先介绍K-Boot来建立基础，然后介绍EC。04. 方法论0K-Boot是一种非参数赌博模型。对于给定的上下文 x，它将臂 � 的奖励估计为从所有历史样本中拉动臂 � 的 的 �个最近邻的观察奖励的Nadaraya-Watson核加权平均值。我们使用Bootstrap TS作为探索策略。已知 � -NN回归与Bootstrap-Aggregation很匹配，具有平滑条件均值估计的解析形式，不需要实际重采样 [ 15 , 16]。但是，从均值估计的置信分布中进行抽样的讨论很少。我们设计了一个技巧，将重采样范围从所有历史样本缩小到围绕 � -NN的局部包装器。K-Boot在算法1中详细说明。在第 �次迭代中，对于上下文 x � ，对于第 � 个臂 � � ，让 � 为拉动 � � 的所有历史样本的集合，而 � � = |� � | 。为零，我们从标准均匀分布中抽样奖励（第6行）。如果 � 大于 � ，我们首先构建一个包含 � � 的 � ′ -NN （ � < � ′）的 有影响力 的子集 � ′ � 。直观地， � ′ -NN作为一个缓冲区，覆盖了足够的样本方差，以便在 � -NN周围的有影响力的样本上进行Bootstrap，从而Bootstrap在有影响力的样本上进行。0对所有样本进行良好的近似。形式上，如果一个样本被认为对于推断 x � 有影响，那么它在 a Bootstrap on � �后被视为在 x � 的 � -NN 中的概率大于 �。这个概率是根据 [ 15 ] 中推导的方程式 (6) 在第 9行进行解析计算的。这里的容差超参数 �控制着错过有影响的样本的风险，从而控制了近似Bootstrap TS 的忠实度。在我们的实验中，当 � � ≤ 10 4且 � = 0 . 01 时， � ′ 被经验性地限制在 2 �。这个过程将所有后续的计算缩减到 � ′个样本，每个样本的开销邻居搜索成本为 � (log � � )（我们使用 Hnswlib [ 17 ] 进行近似搜索）。如果 � � 小于� ，则 � � 本身就是有影响的集合。然后我们在第 14-15行向 � ′ � 添加了两个伪样本，以扩展 Bootstrap探索的奖励的经验范围 [ 10]。为了给伪样本适当的上下文和核权重，我们将它们到 x的距离设置为 � ′ �中随机观察的距离，因此随着看到更多的数据，它的权重会缩小。在第 16-18 行，我们然后进行 Bootstrap重采样，并从中选择 � 个最近的样本来计算 � �的估计奖励，作为核加权平均值。我们将 � � ( ∙ , ∙ )实现为最简单的 � ( � ) Nadaraya-Watson核估计器，带有自动带宽选择 [ 20 ] -更高级的模型可以被插入。由于我们将每个手臂的奖励分别建模，因此 K-Boot可以灵活地添加和删除手臂。这有利于像我们这样具有分散和独立手臂管理的应用。此外，K-Boot具有简单的维护：（1）非参数模型在数据方面假设最小，并且只有一个重要的超参数 �来平衡精确度和计算。在我们的实验中， � = 0 . 01效果很好。（2）该算法在决策可解释性方面对业务友好，通过邻近的例子和允许直观地在线即时修改模型行为。例如，CS商家可以在特定时期隐藏具有不良趋势的联系人（例如在传统政策下），或者让新提供的 SMEs通过领域知识（例如重新雇用的代理商或额外的培训计划）“继承”过去的示例联系人或资格声明（下一节）。数据可见性的变化将立即且可预测地影响生产中的赌博模型，并具有明确的归因。这种数据驱动的同时人在循环中的可替代性对于像客户服务这样的快节奏运营业务至关重要。04.2. 资格控制0EC用于识别手臂资格和相关的不确定性，以优化赌博探索。在普通的上下文赌博模型中，资格信息可以被轻易地视为上下文 x 的一部分 - 假设它与 � 呈正相关，因此𝐾𝑘′𝑘′1𝑖0算法 1: K-Boot: 一个完全非参数化的上下文赌博0输入: 迭代次数 � , 手臂数量 � , 最近邻居数量 � , 具有带宽 � � ( ∙ , ∙ ) 的核函数，正则不完全贝塔函数 � �,� ( ∙ )，近似容差 � .01 初始化样本池 � � := � 和其大小 � � := 0 ，对于每个手臂 � = 1 , . . . , �02 对于 � = 1 , ∙ ∙ ∙ , � 执行03 观察上下文 x �04 对于 � = 1 , ∙ ∙ ∙ , � 执行05 如果 � � = 0 则06 估计奖励: � ˆ �,� � � (0 , 1)07 其他08 如果 � � > � 则010 找到有影响力的邻居 � ′ � := 在 � � 中的前 � ′ 个样本，具有最大的 � � ( x � , ∙ )011 其他012 设置 � ′ � := � �013 结束014 从 � ′ � 中随机抽取样本 ( x � , � � )015 添加伪样本: � ′ � := � ′ � ∪ { ( x � , 0) , ( x � , 1) }016 从 � ′ � 中抽取Bootstrap样本 � � �0 min( �, |� � � | ) 个样本，具有最大的 � � ( x � , ∙ )018 估计奖励: � ˆ �,� := ∑�0� � � ( x � , x � ) ，求和范围为 � � �,�019 结束021 拉动手臂 � � := arg max � � ˆ �,� ，并观察真实奖励 � � ∈ [0 , 1]022 更新 � � � := � � � ∪ { ( x � , � � ) } 和 � � � := � � � + 1023 结束0作为奖励估计器的纯输入进行预测。这假设奖励模型能够在足够的轮次后学习 � 和 �之间的关系。这种简单的方法并没有直接利用资格来限制手臂探索的范围，并且在冷启动期间可能不必要地探索不适当的行动而导致灾难性的后悔。另一个极端是严格遵循资格信息并忽略奖励反馈：对于资格分数接口，这可能只是拉动具有最高分数的手臂，就像它是一个预言；对于资格状态接口，这可能是找到概率最高的状态，然后删除没有声明该状态的手臂。因此，经验数据将永远不会用于验证和纠正潜在有偏的业务逻辑 -这是实践中的一个常见陷阱。EC的主要思想是在应用正常赌徒之前只留下最高资格分数的前 �个手臂，并根据资格分数和奖励之间的经验相关性定期调整 � 。我们使用Spearman等级相关系数，表示为 �。使用前 � 个手臂是 � = � (平凡情况； � 是手臂的总和 � = 1 (严格规则情况)之间的启发式权衡。直观地说，对于分数和奖励之间的完美相关性的情况 ( � = 1 )，0� = 1为最佳解。如果资格分数与奖励没有相关性或者呈负相关( � ≤ 0 )，则 � = � 是最佳解 -否则，手臂探索会受到对抗性或随机限制而无法获益。在无相关性的情况下，“奖励最佳手臂不在前 �名内”的概率，定义为泄漏，与 � 呈线性关系: � ( leak | �, � = 0) = 1 − �/� 。显然 � ( leak | �, 0 < � < 1) < � ( leak | �,� = 0) 。这一观察揭示了两个见解：(1) � := � ( leak | �, � )描述了在应用前 �名分数过滤到手臂时的一种风险类型；(2)当控制泄漏风险在某一水平时，例如 � = 0 . 01 ， � 是 �的函数。奖励 � 和资格分数 � 之间的真实相关性 �是未知的，但可以从历史观测中估计：{ ( � � , � � ) } �。因此，EC基本上计算 � ，以便控制 � ( leak | �, � ˆ)在给定水平上。与K-Boot配对，EC还以非参数方式对 � (leak | �, � ) 进行建模，以避免额外的假设。对于 �，虽然使用Spearman等级相关系数进行估计，但Kendall的 �或任何其他基于等级的相关度量也同样适用。在手臂和轮次之间，我们假设 � 的等级是 �等级的嘈杂扰动，并将这种扰动参数化为“执行 �随机邻居反转”。0算法2: 资格控制0输入: 迭代次数 � , 手臂数量 � , 风险水平 � , 分数初始阈值 � 0 , 预先计算的经验字典 � ( �, �, � ) → �01初始化阈值� := �0和观察池�� := �02对于� = 1，...，�执行03观察每个臂的上下文x�和资格分数{�1，∙∙∙，��}04找到得分中第�大的元素�[�]05如果��≥�[�]，则为每个臂抽样奖励(算法1，第5-18行)06拉动具有最高奖励估计的��臂(算法1，第21-22行)07观察真实奖励��，并更新�� := �� ∪ {(��,���)}08(定期)从��计算�ˆ并设置� := �(�,�,�ˆ)09如果�≥(1−�)�，则设置� := �010结束0简单地在序列中交换两个元素，而邻居反转则在相邻元素之间交换两个元素。注意� = 0表示� =1，因为扰动的秩序列与原始序列相同;�→∞实际上是一个随机排列，因此� =0。该设置提供了一个生成过程，用于模拟长度为�的秩序列的所有参数的联合分布:(1)对秩的排序序列进行�次随机邻居反转;(2)查看是否有泄漏，即如果元素1现在在或超过第�个位置;(3)计算原始序列和当前序列之间的�ˆ。可以多次复制这三个步骤，以获得最终的相关系数�ˆ和风险水平�ˆ，通过平个体�ˆ和计算泄漏的频率。对于不同的组合(�,�,�)，由于上程不依赖于任何实际数据，因此可以离线批处理执行，以获得相应的(�ˆ,�ˆ)。生成的经验字典�:(�,�,�)→�被存储，并在断期间进行查询。为了避免在资格分数被证明是纯噪声的边缘情况中进行不必要的控制，如果�输出大于平凡值(1−�)�的则将�重置为�(无EC)。最后请注意，随机邻居反转的生成分被假定在整个序列上是均匀的，即使观察到的数据点{ (��,��}�被顶-�过滤策略给屏蔽，也会产生估计器�ˆ的无偏性。完的在线EC过程在算法2中描述(不包括离线字典生成)。资格状态接口在EC之前转换为得分接口，因此得分是唯一的必需输入。该算法将K-Boot(算法1)作为赌博机对应部分仅用于演示，并适用于具有独立于臂的奖励模型的任何赌博机。EC具有单一超参数:泄漏的受控风险�。请注意�是错过最佳臂的风险，因此它对累积奖励的影响取决于臂奖励分布0分布，特别是第一和第二最佳臂之间的差距。我们将其他类型的风险控制机制与分布假设留给将来的工作。05.实验0在本节中，我们使用两个基准测试来评估K-Boot的性能:LinUCB [4]和NeuralUCB[21]。实验设置大部分遵循[21]中报告的方法，包括4个合成模拟和4个真实世界数据集。EC在具有资格分数设置的合成数据上进行测试，然后在亚马逊客户服务路由数据集上进行测试。数据集如下介绍。合成数据集。该赌博机有 �= 10 个臂，每轮运行 � = 5000 个样本/轮。它观察到具有 �= 20 个维度的上下文，每个维度都遵循独立的�(0,1)。测试了四种真实奖励函数-(1)线性: �0(x) = 0.1x�a;(2)二次: �1(x) = 0.05(x�a)2; (3)内积: �2(x) = 0.002x�A�Ax;(4)余弦: �3(x) =cos(3x�a);其中参数A∈R�×�和a∈R�的每个条目都是从独立的�(0,1)中抽取的，对于每个臂都是不同的。观察到的奖励有噪音: � :=�(x)+�，其中���(0,�2�)且��是从独立的�(0.01,0.5)中独立抽取的。通过随机种子复制20次。具有资格的合成数据集。给定上述，资格分数进一步通过扰动每个臂的反事实奖励来模拟: �:=��+�'，以诱导相关性。这里�是从�(−0.1,1)中抽取的特定于臂的缩放系数。它有很小的机会使�和�负相关，因为在整体正相关的系统中容忍资格索赔错误-EC的唯一假设。噪声项�'��(0,�2�)控制相关效应大小。通过设置适当的��，可以将奖励和资格分数之间的Spearman等级相关系数�固定为任意正值。0图2：基准测试K-Boot，LinUCB和NeuralUCB。左半部分：合成数据集；右半部分：UCI数据集。模型超参数设置为合成数据集上的最佳值。指标在10次运行中平均，置信度为80%。0UCI分类。从UCI机器学习库[22]中收集了四个真实世界的数据集：covertype，magic，statlog和mnist。这些多类分类数据集被转换为多臂上下文臂问题，遵循[4]中的方法：每个类别被视为一个臂，如果臂拉动了正确的臂（识别正确的类别），则奖励为1，否则为0。每个数据集都被洗牌并分成10个互斥的运行，每个运行有5000个样本，并在每一轮中馈送给一个臂（magic的样本少于50000个，因此进行重新采样）。具有资格的CS路由。考虑了代理技能级别路由：CS代理由运营团队分配到不同的技能组，并且路由系统根据客户资料、政策规则和自然语言理解来确定解决给定客户联系所需的技能。在进行任何在线实验之前，我们在历史观察中制定了一个离线臂数据集。收集了大约200万条亚马逊美国客户服务文本聊天记录，其中包括机器人到代理的路由。为了引入随机性，对历史路由策略进行了训练，使用95%的随机子集的客户-机器人转录，通过将路由操作之前的客户-机器人转录作为输入来预测系统选择了哪种技能。具体来说，模拟器由预训练的GPT-2变压器编码器[23]组成，带有多类序列分类器头部，用于预测前20个技能组。该模型使用学习率10^-4和批量大小32进行了一次训练（微调）。对于臂模拟，经过所有潜在的代理到代理转移后的最终实际解决技能作为地面真相-如果路由技能与最终技能一致，则认为该操作是准确的，并且避免了潜在的转移。在每一轮中，臂接收来自相同GPT-2编码器的256维文本嵌入，就像观察到的那样0上下文和模拟器的20维概率预测作为每个臂/技能的资格分数。如果臂选择与最终臂匹配的技能，奖励为1，否则为0。在这种情况下，累积遗憾是转移联系数量的上限，因为分配给不同技能的代理可能会解决联系（例如，数字订单代理通常能够解决零售订单问题，因此他们可能不会转移错误路由的联系）。其余5%的聊天记录用于生成10个包含8000个样本的臂运行。我们观察到跨运行的经验�为0.3492。我们将以下内容留给未来的工作：（1）在线实验，以测量实际转移和积极的客户评价作为奖励指标；（2）基于代理资料和比技能组更精细的资格定义的代理级别路由。05.1. K-Boot基准测试0我们在合成数据集和UCI分类数据集上将K-Boot与LinUCB和NeuralUCB进行比较。对于4个合成数据集，我们首先为感兴趣的每个臂算法选择以下超参数（1）最近邻居数�∈{20，50，100}对于K-Boot；（2）探索的权重参数�∈{0.1，1.0，10}对于LinUCB；（3）正则化参数�∈{0.1，0.01，0.001}和探索参数�∈{0.2，0.02，0.002}对于NeuralUCB-其他超参数，如学习率、批量设置和层数与原始代码库中设置相同。我们确定�=100，�=10，（�，�）=(0.001，0.002)具有在�0��3和10个复制运行中平均累积遗憾最低，并保留这些值0从另一个角度来看，这种离线老虎机与资格的模拟设置相当于"使用老虎机在线改进未知准确度的黑盒概率分类器"。2https://github.com/uclaml/NeuralUCB0图3：在不同的Spearman相关性�下，EC在不同风险水平�下的资格分数和奖励之间的关系，其中老虎机部分是K-Boot，资格分数不在上下文中。0比较在4个UCI数据集上的实际模型性能。我们认为这种设置更加现实，因为大多数老虎机应用由于样本量小或非静态环境而没有进行密集的超参数调整的奢侈条件。最后，本文中的所有实验都实现了在线、单样本模型更新。图2左侧显示了具有最终选择的超参数的模型的性能。除了线性奖励场景中LinUCB/NeuralUCB在正确/接近模型规范方面具有优势外，K-Boot和NeuralUCB之间没有显著的性能差异，而LinUCB较差。图2右侧显示了UCI真实世界数据集上的性能比较。K-Boot和NeuralUCB在每个数据集上都有一定的胜率，而LinUCB始终是最差的。通过检查80%的置信区间带（在10次运行中的P10-P90），我们发现NeuralUCB在真实数据上的性能波动较大（带宽较宽），这是由于在某些运行中的学习不稳定性造成的。05.2. 资格控制测试0对于合成数据，我们控制��来模拟资格分数中反映奖励的可靠性的不同水平，得到的�(�, �)∈{0.05, 0.15, 0.3, 0.45, 0.0.75}，对于每个真实奖励函数�0 -�3。在算法中，我们在EC中设置不同的风险水平�。注意�实际上不使用EC，我们滥用符号�→1来表示严格的top-1。0策略：拉动具有最高资格分数的手臂。图3显示了将EC应用于K-Boot的结果，其中只使用EC的资格分数（稍后解释）。当�中的信号较弱（低�）时，EC自适应地将顶部-�阈值提高到接近�，实现与无EC相同的性能。随着�的增长，优势显现出来-使用EC始终优于不使用。动态阈值可能在强资格信号下主导顶部-1策略，具有正确的�。在所有合成数据集中，�=0.5时，EC的性能最佳，并且相同的值被带入下一个在CSRouting数据上的实验中。EC可以应用于其他老虎机。图4显示了相同的合成数据结果，但使用了EC +LinUCB。这里资格分数也添加到了老虎机上下文中。之前的实验之所以没有将分数作为K-Boot输入，是因为�-NN没有本地特征选择机制。如果资格分数接近白噪声（低�），模型难以拟合奖励，从而分散了其他呈现的视觉模式。对于LinUCB，由于模拟噪声是高斯的，这种副作用是最小的，因此这是测试使用资格的平凡方式与EC方式之间的差异的更好条件。EC在大多数情况下仍然优于无EC。在线性真实奖励函数�0的几个例外情况中，�=0.5更糟，因为LinUCB学习得很好，以至于冒高风险错过最佳手臂是得不偿失的。有趣的观察是，尽管严格的top-1规则被K-Boot +EC（图3）所主导，但在�=0.15时，它实际上击败了LinUCB +EC，这表明老虎机模型的力量仍然是ML超越静态规则的关键驱动因素。图5显示了CSRouting数据的结果，EC显著提高了路由准确性。从仿真器中选择具有最高概率的技能进行路由服务，是现有政策的随机替代。仅有8000个样本，仿真器策略的平均准确性由K-Boot + EC从53.37%提高到57.78%。by K-Boot + EC (Figure 3), it actually beats LinUCB + ECfor nonlinear true reward functions even at 𝜌 = 0.15.This indicates the power of the bandit model is still a keydriver for ML to out-perform static rules.Figure 5 shows the result on CS Routing data, whereEC significantly improves routing accuracy. Routing tothe skill with the highest probability from the emulatorserves a stochastic surrogate of the existing policy. PureK-Boot result without knowing the emulator outputs isset as a baseline. With only 8000 samples, the averageaccuracy of the emulator policy is improved by K-Boot +EC from 53.37% to 57.78%.0图4：在不同的Spearman相关性�下，EC在不同风险水平�下的资格分数和奖励之间的关系，其中老虎机部分是LinUCB，资格分数是上下文的一部分。06. 结论0我们提出了一种非参数上下文赌博算法K-Boot，具有基于臂的资格控制（EC），用于实时将客户联系路由到合格的中小企业。虽然K-Boot和EC在这里作为一套提出，但每个都可以独立应用-K-Boot是一种通用的赌博算法，EC可以控制其他赌博的臂资格。我们将K-Boot与LinUCB和NeuralUCB进行了比较。在模拟运行中平均遗憾性能方面，K-Boot和NeuralUCB在获胜场景中并列，并且在不同数据分布的稳健性方面是可比的。两者均优于LinUCB。然而，与K-Boot相比，我们观察到NeuralUCB的性能变化更大。0图5：CS路由结果。指标在10次运行中平均，80%置信区间。0我们进一步发现，EC组件改善了K-Boot在合成数据集和CS路由模拟场景中的性能，当资格存在时。0参考文献0[1] G. Elena, K. Milos, I. Eugene,应用于推荐系统的多臂赌博算法调查，国际开放信息技术杂志9 (2021) 12–27.0[2] Y. Liu, L. Li,电子商务的赌博地图，arXiv预印本arXiv:2107.00680 (2021).0[3] T. Lattimore, C. Szepesvári,赌博算法，剑桥大学出版社，2020.0[4] L. Li, W. Chu, J. Langford, R. E. Schapire,个性化新闻文章推荐的上下文赌博方法，第19届国际万维网会议论文集，2010，pp. 661–670.0[5] S. Sajeev, J. Huang, N. Karampatziakis, M. Hall, S.Kochman, W. Chen,客户支持机器人中的上下文赌博应用，第27届ACMSIGKDD知识发现与数据挖掘会议论文集，2021，pp.0[6] S. Upadhyay, M. Agarwal, D. Bounneffouf, Y.Khaz- aeni,一种在预算下进行后续对话编排的赌博方法，arXiv预印本arXiv:1906.09384 (2019).0[7] O. Chapelle, L. Li,汤普森抽样的实证评估，神经信息处理系统24 (2011).0[8] T. Graepel, J. Quiñonero Candela, T. Borchert, R.Herbrich,微软必应搜索引擎中赞助搜索广告的基于贝叶斯的点击率预测，第27届国际机器学习大会ICML2010会议论文集，邀请应用专题（未评审，即将出版），2010.0[9] I. Osband, B. Van Roy,自举汤普森抽样和深度探索，arXiv预印本arXiv:1507.00300 (2015).0[10] B. Kveton, C. Szepesvari, S. Vaswani, Z. Wen, T.Lat- timore, M. Ghavamzadeh,垃圾进，奖励出：在多臂赌博机中引导探索，国际机器学习会议，PMLR，2019，pp. 3601–3610.0[11] C. Riou, J. Honda,基于汤普森抽样的有界奖励分布的赌博算法，算法学习理论，PMLR，2020，pp. 777–826.0[12] N. Srinivas, A. Krause, S. M. Kakade, M. Seeger,求解赌博机设置中的高斯过程优化：无遗憾和实验设计，arXiv预印本arXiv:0912.3995 (2009).0[13] S. R. Chowdhury, A. Gopalan,关于核化多臂赌博，国际机器学习会议，PMLR，2017，pp. 844–853.0[14] J. Hensman, N. Fusi, N. D. Lawrence,大数据的高斯过程，arXiv预印本arXiv:1309.6835 (2013).0[15] B. M. Steele, 精确的自举k最近邻学习器，机器学习74(2009) 235–255.0[16] G. Biau, F. Cérou, A. Guyader,关于袋装最近邻估计的收敛速度，机器学习研究杂志11(2010).0[17] Y. A. Malkov, D. A. Yashunin,使用分层可导航小世界图进行高效和稳健的近似最近邻搜索, IEEE模式分析和机器智能交易 42 (2018) 824–836.0[18] J. Johnson, M. Douze, H. Jégou,使用GPU进行十亿级相似性搜索, IEEE Transactions onBig Data 7 (2019) 535–547.0[19] R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simcha,F. Chern, S. Kumar,使用各向异性向量量化加速大规模推断, 在:机器学习国际会议, PMLR, 2020, pp. 3887–3896.0[20] B. W. Silverman, 统计和数据分析的密度估计,Routledge, 2018.0[21] D. Zhou, L. Li, Q. Gu, Neuralucb:基于神经网络的探索的上下文臂 (2019).0[22] D. Dua, C. Graff, UCI机器学习库, 2017. 网址:http://archive.ics.uci.edu/ml .0[23] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I.Sutskever, 等, 语言模型是无监督的多任务学习器,OpenAI博客 1 (2019) 9.
我的内容管理
展开
