多臂抢劫机与缝合固定实验台

我们理解现在世界上正在发生很多事情。我们继续发布博客帖子，希望它们能在这些时间里提供一些智力刺激和一种连接感。关于种族正义和新冠肺炎，请看以下我们正在采取的行动。

在Stitch Fix的在线实验中，多武装土匪已经成为传统A/B测试的流行替代品。我们最近决定扩展我们的实验平台，将多武装强盗作为一流功能。这篇文章概述了我们的实验平台架构，解释了多武装强盗背后的一些理论，最后展示了我们如何将它们整合到我们的平台中。

在详细介绍多武装匪徒之前，您首先需要了解一下我们的实验平台是如何工作的。在我们上一篇关于构建集中式实验平台的文章中，我们解释了#One Way哲学，以及它如何使实验成本更低、影响更大。我们的想法是让#One Way在整个业务中运行和分析实验。前端工程师、后端工程师、产品经理和数据科学家使用相同的平台。而且它足够灵活，可以用于库存管理和预测、仓库运营、服装推荐、营销以及介于两者之间的所有方面的实验。要实现如此广泛的实验，我们依赖于两个关键概念：配置参数和随机化单元。

配置参数表示实验中正在变化的任何内容。它可以是任何东西，从登录页面上欢迎文本的选择，到造型师选择修复商品时我们向他们展示的商品数量，再到在我们的Shop Your Look页面上推荐商品的机器学习模型的超参数的值。这些参数不仅仅用于控制对现有系统的增量更改。它们还可以用来表示巨大的变化，比如为我们的采购订单平台部署一个新的后端，或者一个全新的库存策略。在这些情况下，参数值将表示正在测试的程序或算法的版本。

从平台的角度来看，配置参数只是一个名称和一组允许值。只有客户端应用程序才知道与值关联的行为。例如，在红/蓝按钮A/B测试中，StitchFix.com主页将注册front_page.button_color配置参数，允许的值为“red”和“Blue”，以及应该分配给每个值的流量比例。当访问者访问该页面时，会向实验平台发送一个请求，其中包含front_page.button_color配置参数，以及访问者id。分配引擎处理随机化，并将值传回页面。这样，任何想要进行实验的应用程序都可以将分配引擎用作随机化的键值存储。

当然，并不是所有的应用程序都希望随机化访问者id。在某些实验中，随机选择Shipping_id，甚至仓库ID可能是有意义的。为了扩大可能的实验范围，我们需要另一个抽象：随机化单元。

随机化单元定义在哪个实体上随机化实验。在上面的一个访问Stitch Fix主页的示例中，随机化单元是viewer_id。当测试用于向造型师推荐款式的算法的不同版本时，实验可能会随机选择Shift_id或styist_id。与配置参数一样，用户可以随时在平台中注册新的随机化单元。一个实验只有一个随机化单元，但可以同时随机化多个配置参数。通过混合和匹配随机单元和配置参数，我们的用户几乎可以创建他们能想象到的任何类型的实验！

分配引擎的一个关键功能是能够确定性地执行随机分配。例如，这保证了如果同一访问者多次访问同一页面，他们每次都会被分配到相同的实验单元，从而确保一致的体验。对于给定的实验和随机化单元，分配引擎每次将可靠地返回相同的小区选择。为了实现这一点，而不必将每个分配决策存储在数据库中并在分配时查找它们，小区的选择由散列函数确定。

首先，每个实验单元被映射到0到999之间的整数的排他子集。然后，对于每个分配，我们通过取模1000的test_id和随机化单元的SHA1散列在此范围内生成一个伪随机数。例如，如果实验是随机的，则随机数生成函数为：

此函数的结果将是介于0和999之间的整数，访问者将被分配到相应的单元格。分配给每个单元格的分配分数将与其映射到的整数数成比例。

现在您已经了解了我们的实验平台是如何处理A/B测试的，让我们花一点时间来介绍一下多武装土匪的话题。就像A/B测试一样，多臂盗贼需要将流量随机分配到网页或算法推荐的不同版本，以确定哪种变体会产生更好的结果。对于A/B测试，我们通常将这些不同的变种称为“细胞”，但在多武装匪徒的情况下，我们将其称为“武器”。与A/B测试不同的是，多臂匪徒学会将交通从表现不佳的武器转移到表现较好的武器上。多臂强盗实验通常比A/B测试更快地将更多的观测值分配给最佳手臂。因此，多臂土匪试验的机会成本可以低于A/B试验的机会成本。

在A/B测试中，在整个实验长度内，固定比例的流量被发送到次优小区，从而导致相对较高的机会成本。如果你的目标是了解哪个细胞是最优的，同时在实验过程中将机会成本降到最低，那么多臂强盗可能是更好的选择。当通信量很低时，或者当您要测试的小区数量很大时，情况尤其如此。在多武装匪徒的情况下，机会成本被称为后悔，并且存在各种算法来最小化后悔，同时学习哪个实验单元具有最好的结果。当然，这种效率并不是没有权衡的。在任何实验中，由于统计抽样的随机性，都有可能得出错误的结论。A/B测试允许直接控制这些错误率，并且在A/B测试之后计算置信区间也是一个相对简单的过程。对于多武装强盗来说，估计置信区间和控制错误率可能要困难得多。

强盗不仅可以用于固定期限的实验，还可以用来做更多的实验。它们可以作为长期优化的基础。随着不同ARM的性能变化，强盗算法可以改变发送到这些ARM的通信量。表现不佳的手臂甚至可以完全移除，取而代之的是新的变种。通过这种方式，可以不断地测试新的想法，同时仍然可以确保大多数流量被发送到表现最好的ARM。

多臂强盗模型是强化学习的简化版本，其中有一个Agent通过从有限的动作集合中选择并根据所采取的动作收集不确定的奖励来与环境交互。代理人的目标是随着时间的推移最大化收集的总奖励。

在离散时间步t，代理从可能动作的集合\(A\)中选择一个动作\(a_t\)。这导致观察结果\(y_t\)，该结果通过已知的奖励函数\(r_t}=f(y_{t})\)映射到奖励\(r_t\)。对应于每个动作的结果是一个随机变量\(Y_{a}\)，其分布对于代理是未知的。当然，如果代理人知道结果分布，最优策略将总是选择期望报酬最大的手臂：\(a_{t}=\arg\max\limits_{a\in A}(\mua})\)，其中\(\mua}=E[f(Y_{a})]\)。由于缺乏这方面的知识，代理人必须通过与环境互动并收集关于每一行动结果的证据来估计预期的回报。

澄清结果\(y_t\)和奖励\(r_t\)之间的区别是很重要的。通常，结果和奖励实际上是等量的。例如，如果要最大化的奖励是营销电子邮件的打开率，则奖励函数将是身份函数：\(r_t=f(Y_T)=y_t\)，其中结果\(y_t\)是指明电子邮件是否已打开的二元结果。但其他奖励功能也可能有用。为了测试我们的匹配分数算法的新版本，我们的数据科学家经常使用寿命值(LTV)作为奖励度量，该算法为造型师推荐添加到客户修复中的项目。当然，除非您准备运行一个非常长的实验，否则等到可以观察到实验中每个客户端的LTV是不可行的。取而代之的是，数据科学家使用LTV模型，该模型考虑了较短的时间

代理必须基于不完全信息做出决策，这导致了一个被称为探索与利用问题的两难境地。在过程的早期，奖励估计是高度不确定的，因此代理人被迫收集所有可用行动的证据，以便更确定哪个行动可能产生最高的平均奖励。获得这一证据的唯一方法是多次选择所有的行动，并观察结果。另一方面，代理的目标是最大化随着时间的推移收集的总回报，因此代理应该避免选择目前预测会产生较少回报的操作。有大量可用的算法试图基于从过去采取的操作中观察到的结果，在每个时间步自动平衡探索和利用。

遗憾最小化技术的一个经典例子是\(ε\)-贪婪算法。在该算法中，代理通常会选择当前估计平均报酬最大的动作\(HAT{\MU}_a\)，但概率为\(\ε\)会从集合\(A\)中选择一个随机动作。值较小的\(\epsilon\)表示代理将进行更多的利用，而值较大的\(\epsilon\)会导致更多的探索。参数\(\ε\)可以在实验期间固定，也可以随时间变化。通常情况下，人们会从较大的\(ε\)值开始，然后随着时间的推移而减小，因此代理在实验的早期阶段会做更多的探索，在后期阶段会做更多的开发。此算法的性能取决于\(\ε\)的选择以及它如何随时间变化。

最近，Stitch Fix的一些数据科学家转而倾向于使用汤普森采样来处理他们的多武装土匪。汤普森抽样有两个特性使其成为一种特别强大的遗憾最小化算法：收敛性和瞬时自校正。收敛意味着，在给定足够时间的情况下，算法最终总会选择最优的ARM。这一点很重要，因为这意味着算法不会因为早期的坏运气而陷入选择次优手臂的困境。即时自我纠正是一种更微妙的特性，但对于最大限度地减少后悔是非常重要的。如果当前平均奖励估计是对真实平均奖励的低估，则瞬时自校正的算法将倾向于更频繁地选择臂，并且如果当前奖励估计是高估，则将较不频繁地选择臂。这意味着算法不太可能被结果的随机性所愚弄，因此比那些不能自我修正的算法更快地收敛到最优的手臂上。不是即时自校正的算法仍然可以保证收敛，但是比汤普森采样收敛得更慢。

在未来的一篇博客文章中，我们将详细介绍Thompson采样的工作原理，并分享我们高效确定性在线Thompson采样的新解决方案。

我们的目标是在现有的实验平台上建立对多武装土匪的支持。我们希望实现一套标准的强盗策略，如\(\epsilon\)-贪婪和汤普森抽样，同时还支持喜欢实现自己策略的数据科学家。奖励模型由数据科学家自己实现，并通过每个土匪实验的专用微服务连接到分配引擎。

此设计的一个很好的特点是，它不需要更改依赖于配置参数值的分配引擎的工程应用程序。这些应用程序甚至不知道有一种新类型的实验-它们只是继续使用配置参数值并生成日志，就好像什么都没有改变一样。

数据科学家负责实施和更新他们自己的奖励模型，基于他们可以从我们的数据仓库中提取的数据。每个强盗实验都需要一个专用的微服务，分配引擎可以在分配时查询该服务以获得奖励估计。在Stitch Fix，我们有一些很棒的工具，可以帮助用户自动化设置这些微服务的过程，并使他们的数据保持最新。数据科学家不必担心正常运行时间、延迟和后备等问题。他们只需要提供一个Python函数来返回奖励模型估计，我们的“模型信封”工具(我们正在开发的新模型部署和跟踪系统)负责其余的工作。然后，数据科学家可以使用我们的工作流执行调度程序自动执行批处理ETL，并在每次ETL运行时使用新值更新奖励服务。

当分配引擎需要分配给多臂强盗实验时，它将向相应的奖励服务请求奖励估计。奖励估计以分布参数的形式出现。如果强盗是惯用的

每个强盗策略被实现为确定性函数，其接受ARM奖励估计集合并输出ARM选择概率分布。然后可以将这些概率插入到我们现有的分配引擎中，该引擎处理确定性随机分配。

盗贼策略必须能够根据奖励估计集计算手臂选择概率。对于\(\epsilon\)-贪婪算法，这是一个简单的计算。策略只需要知道每个手臂的点数估计\(\HAT{\MU}\)。回想一下，此算法的工作方式是在一定时间内选择一个均匀随机的手臂，其余时间选择具有最大\(HAT{\MU})的手臂，并随机打破平局。则选择ARM\(a\)的概率为：

其中\(K\)是臂的数目，\(M\)是具有最大\(HAT{\µ}\)的臂的集合，\(n_M\)是\(M\)中的单元数。

计算汤普森抽样的臂选择概率并非易事。与点估计不同，Thompson抽样要求每个臂的估计平均报酬(µ)的后验分布。在每个时间步长，从每个手臂的分布中随机抽取一个样本，并选择采样值最大的手臂。计算结果选择概率的一种方法是蒙特卡罗方法。这意味着使用同一组分布多次重复随机抽样，然后计算每个手臂被选中的次数。此方法太慢，不能用于在线分配，因此必须在预计算步骤中完成。然而，这将意味着计算作业激增，每个作业都与奖励微服务紧密耦合。它还会在对奖励模型的更新和对手臂选择概率的更新之间引入延迟。此外，对于大量的武器或较小的选择概率，该方法变得计算昂贵。如果有一种计算汤普森抽样概率的方法，这种方法足够确定、准确和有效，可以用于在线分配，而不需要任何预计算，那不是很好吗？事实证明，有一种方法可以做到这一点，但您必须等待我的下一篇博客文章才能了解如何做到这一点：)。

我们希望Thompson抽样和\(\epsilon\)-贪婪将覆盖大多数用例，但我们不想阻止我们的数据科学家使用我们尚未实现的策略。为此，我们添加了一个“比例”策略，它简单地将每个手臂的概率设置为其估计的平均奖励\(HAT{\µ}\)，并进行标准化，使所有手臂上的概率之和等于1。如果数据科学家想要实现他们自己的策略，他们可以将他们的奖励服务配置为返回概率而不是奖励分布参数，并选择比例策略让分配引擎直接使用他们的值。

到目前为止，在本讨论中，代理只知道可用操作和过去每个操作的观察结果。但是，通过在选择操作时使用有关环境的附加信息，代理可能会做得更好。此附加信息称为上下文。一般来说，上下文既依赖于环境又依赖于手臂。例如，如果工程师正在决定在客户访问StitchFix.com时向客户显示哪个横幅图像，则工程师可能需要考虑客户的风格或品牌偏好。在这种情况下，代理的奖励估计将取决于ARM和上下文。这种更为复杂的模型被称为“上下文强盗”。我们在这篇文章中忽略了细节，但我们的平台也是为支持上下文盗贼而构建的。

Stitch Fix的实验平台现在支持多臂强盗实验，将其作为A/B测试的一流功能。这为我们的数据科学家提供了一种新的实验工具，在某些情况下可以提供比标准A/B测试更有效的优化，以及更灵活的长期优化方法。我们的实现提供了两个标准化的盗贼策略，并允许用户提供自己的选项。用户负责开发、部署和更新他们自己的奖励模型。平台团队提供了数据科学家构建和调度ETL所需的所有工具，这些ETL用于训练他们的模型，并将Python模型转换为微服务。切克。

.