我正在研究多臂强盗（MAB）问题，大约一百万武器。相反，迭代次数当然要大得多，大约为10到2000万。
大多数MAB算法都需要一个argmax运算符（动作空间的argmax），该运算符必须在每次迭代中执行才能选择当前的分支（最大化给定的选择标准）。无论选择哪种编程语言来实现，此过程/这个argmax运算符在整个动作空间（一百万个臂）中都是非常耗时的。
有人对如何以省时的方式实现MAB算法有任何想法吗？
在UCB1中，有两个术语确定接下来选择哪个分支-平均奖励和置信度。
average + sqrt(2 ln N / n_i)
到目前为止，不考虑平均奖励，第二项取决于样本总数（N），这对于所有分支都是相同的，以及给定分支的总数（n_i）。因此，对于所有已被采样相同次数的武器，第二项将是相同的。
一种简单的方法是按执行的样本数量来分配武器。然后，在每个存储桶中，您可以按奖励排序（从高到低）。当您要确定接下来要采样的手臂时，只需检查每个存储桶中收益最高的手臂，然后从UCB方程中选择具有最高价值的存储桶进行下一步采样。您只需要测试每个存储桶中的第一个条目即可。
可以在此基础上做进一步的改进，但这要比在每个时间步长遍历所有手臂要好得多。