“多臂老虎机 ”—大型多选项试验的优化策略

在临床药物试验中，我们经常会通过将试验药物与安慰剂的治疗效果进行比较，来确定患者的最佳治疗方案。如果参与者足够的多，此类随机对照试验的确是确定因果关系的最佳标准：如果接受药物的组比接受安慰剂的组改善得更多，则可以安全地假设这种药物是有效的。凭借从试验中得到的结论，制药商可以自信地向数千甚至数百万患者推出药物。

但是，这种传统的试验方法其实有一个很大的缺点：接受安慰剂的参与者不可避免地会治疗失败。

药物试验与测试公司网页或广告版本的风险当然大不相同，但任何A/B测试的根本问题都是一样的。“我们需要以牺牲机会成本为代价获得知识。” 斯坦福商学院副教授Mohsen Bayati解释说。而且机会成本只会随着被测试的不同个体的数量而增加—例如，在化疗药物试验中，每种药物组合都需要有自己的治疗组和对照组。

最近，Bayati与斯坦福大学管理科学与工程教授Ramesh Johari以及斯坦福大学博士生Nima Hamidi和Khashayar Khosravi一起，着手研究了是否可以提高这些测试的效率并降低机会成本。在一篇新论文中，他们发现有一种被称为“多臂老虎机”的试验策略可以在多选项的试验中简化测试过程，但仍然能够产生决定性的结果。

“多臂老虎机”

这种可以降低机会成本的方法，其实早已为人所知，但仅在过去十年中才开始被运用到实践中—主要是在网络世界中，一些精通技术的公司需要快速比较多种变量组合的时候。这种试验—有时候会被称为连续性试验或是适应性试验—会使用一种被称为“多臂老虎机”的试验策略。每个“臂”代表着需要研究的选项之一，选项可以是产品、文章标题或是试验者想要测试的任何内容。

与传统试验中将所有参与者或用户平均分配到各个选项的做法不同，在这种“多臂老虎机”策略中，每次刚开始的时候，都只是分配少数几个用户到各个不同的选项，然后再根据哪个选项显示出最有希望的结果，来快速调整用户的后续分配。这样做的好处是，在试验结束时受到测试的次优版本影响的人相对减少了。例如，如果有人在药物试验中使用这种方法，Bayati解释说，“我们仍然会找出哪种药物是最好的，但更多的患者使用到的是效果好的药物。”

当然，这只是这种测试策略的基本思路。如何去优化“多臂老虎机”，才能让尽可能多的用户最终使用的是最好的选项，是对这种“多臂老虎机”策略研究的关键。该研究最早可以追溯到上世纪三十年代，那时人们就会通过模拟数据在“探索”未知回报的选项以及“利用”已知回报的选项之间进行权衡。对于这种“探索”和“利用”之间的两难困境，在不同情况下需要采取不同的策略才能达到最好的效果。Bayati和他的同事所研究的第一个问题就是，当选项数量远远多于两个（比如有10,000个选项，这种情况在网络世界中并不少见）时，什么才是最佳策略。

100个选项有时可以胜过10,000个选项

通过对真实数据进行数学分析和模拟，研究人员取得了多项发现，并在2020年神经信息处理系统会议上向大家做了介绍。首先，他们证明，对于包含大量选项的试验来说，最好的策略是使用二次抽样—例如，只尝试100个选项，而不是尝试所有10,000个选项。尽管尝试每个选项可以找出最佳选择，但与仅尝试子样本相比，这样做的好处并不足以抵消巨大的机会成本。“如果你可以采用随机子集，那就已经足够好了。” Bayati说，“我们的研究结果表明，100个（而不是10,000 个）选项中最好的那个就已经是非常好的了。”

Bayati解释说，A/B测试的根本问题是“我们需要以牺牲机会成本为代价来获取知识。”

那么，在选项较少时，我们又该如何处理呢？这个问题的答案正是研究人员的第二个发现：他们的模拟数据结果也同样显示了“多臂老虎机”策略的有效性。该方法在没有大量“探索”未知回报的选项的情况下就开始“利用”已知回报的选项：先将每个选项都尝试一次，然后就只选择其中回报最好的选项。

研究人员仍在试图理解为什么这种策略的效果会如此之好。但数据分析显示，至少部分答案似乎是，它在早期阶段就移除了大多数的次优选项，以后也不再去尝试它们，相反地，它将“探索”的范围缩小到了少数选项，并且只用这些选项进行后续的试验。正如Bayati所说：“这种方法虽然并没有非常积极地去“探索”那些未知回报的选项，但它仍然在学习，其实会受益于这种无成本的“探索”。这正是其中有趣的部分。”

最后，Bayati和他的团队还从理论上证明了这些问题中任何策略的最低界限，并证明了当选项数量至少与用户数的平方根一样多的时候，这种“多臂老虎机”策略的二次采样是最优的。

研究人员表示，这些研究成果对AI开发人员很重要，因为大多数强化学习算法都依赖于一定程度的“探索”，而“多臂老虎机”正是这些强化学习算法中的一个特例。

“最重要的是你可以减少试验的次数。” Bayati说。像亚马逊、Facebook、优步和许多其他公司，都经常需要对其众多用户进行广泛的试验。“我们告诉他们，即使你只是尝试迄今为止见过的最好的选择，可以学到的东西也比你想象的要多得多。”