5

我有一个“门号”的优先队列。我从优先级队列中得到下一个门号（即对应优先级值最低的门），然后开门。门后，可能有礼物，也可能没有。根据礼物的有无，我更新了这个门号的优先级，并将其放回优先级队列中。然后我重复，让下一个门号码打开，等等。

假设每扇门都有不同的礼物补充率（即有些可能每天都会收到新礼物，有些则根本不会），我应该如何更新优先级值以最大化我找到的礼物数量？也就是说，我想最大化我打开有礼物的门与我打开没有礼物的门的比例。

我应该注意，补货率不能保证随着时间的推移而固定/存在随机变化。但我可以在这里简化假设。

这对我来说几乎像是一个蒙特卡洛问题，除了我越经常探索一个节点（门），它的期望值越低。（当然，没有树要构建；我们只需要计算出 depth-1 节点的值。）

最简单的方法是跟踪最后优先级 (LP) 和当前优先级 (CP)，delta = CP - LP。如果我们找到礼物，设置下一个优先级 NP = CP + delta - 1；否则设置 NP = CP + delta + 1。我猜这是可行的，但它的优化似乎相当缓慢。

或者我们可以有一个乘法值：NP = CP + delta * shrink 或 NP = CP + delta * grow，其中 shrink < 1 并且 grow > 1。这就是我目前拥有的，而且几个月来似乎都可以正常工作，但是现在我遇到了一些门被背靠背打开的情况（即打开门 D，找到礼物，放回优先队列，D 现在再次成为最佳选择，当然没有找到礼物，现在放回去在优先级较低的队列中），这似乎很糟糕。作为参考，我使用了收缩 = 0.9 和增长 = 1.3。

是否有一个数学公式（如蒙特卡洛）来表达探索门的最佳方式？

4

1 回答 1

0

多臂老虎机理论深入人心，不是我的专长，所以可能有一个我不知道的参考。话虽如此，我的第一直觉是：

  • 使用球形奶牛假设简化数学，即对于每扇门，补货时间呈指数分布，且未知速率随时间保持不变。
  • 将我们对补货率的估计从历史中分离出来。
  • 将每扇门的优先级设置为 1 - exp(-λx)，其中 λ 是估计的补货率，x 是我们上次打开门后的时间。（越高越好。）

多臂强盗通常必须在探索与剥削之间取得平衡，但我的预感是，我们会从补给过程中自然而然地得到这一点。

大多数技术细节都在进行估算。我们有一堆示例 (x, b)，其中 x 是自我们上次开门以来的时间，b 是是否有礼物。对于给定的速率 λ，上面的优先级公式给出了 b 的期望值。我将建议 λ 的最大似然估计。这意味着最大化所有 (x, 0) 示例的 log(exp(-λx)) = -λx 的总和加上所有 (x, 1) 示例的 log(1 - exp(-λx)) 的总和。这个功能可以直接优化，但是有两个问题：

  • 我们打开一扇门的次数越多，优化的代价就越大。
  • 如果没有正面或负面的例子，那么解决方案是退化的。可能我们应该要求 λ 至少每月一次，或者避免完全放弃一扇门。

我实际上建议的是选择一小组 λ 值来使其成为离散优化问题。

（另一个潜在的问题是优先级公式对于许多门可能效率低下。您可以做的是选择优先级的目标阈值，然后计算优先级何时超过该阈值。）

于 2021-09-01T20:46:05.050 回答