algorithm - 设置优先队列值以优化找到 'gift' 的概率

Question

我有一个“门牌号”的优先队列。我从优先级队列中得到隔壁门号(即对应优先级值最低的门)，然后开门。门后可能有礼物，也可能没有。根据礼物的存在/不存在，更新此门号的优先级，并将其放回优先级队列。然后我重复一遍，打开隔壁的门号，依此类推。
假设每扇门都有不同的礼品补货率 (即有些人可能每天都会收到新礼物，而有些人则根本不会)，我应该如何更新优先级值以最大化我找到的礼物数量？ 也就是说，我想最大化我有礼物打开的门与没有礼物打开的门的比例。
我应该指出，补货率不能保证随着时间的推移而固定/存在随机变化。但我可以在这里简化假设。
这对我来说几乎像是一个蒙特卡洛问题，只是我探索一个节点(门)的次数越多，它的期望值就越低。 (当然，没有要构建的树；我们只需要计算 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 现在再次成为最佳选择，当然没有找到礼物，现在放回去在优先级较差的队列中)，这看起来很糟糕。作为引用，我使用了shrink = 0.9 和grow = 1.3。
是否有数学公式(如蒙特卡罗)表达探索门的最佳方式？

Answer 1

多臂强盗理论根深蒂固，不是我的专长，所以可能有一个我不知道的引用。话虽如此，我的第一直觉是:

使用球形奶牛假设简化数学计算，即对于每个门，补货时间呈指数分布，且某个未知速率随时间保持恒定。

将我们对补货率的估计与历史分开。

将每个门的优先级设置为 1 − exp(−λx)，其中 λ 是估计的补货率，x 是自我们上次打开门以来的时间。 (越高越好。)

多臂强盗通常必须在探索与剥削之间取得平衡，但我的直觉是，我们会从补给过程中自然而然地得到这一点。
大多数技术细节都在进行估算。我们有一堆例子 (x, b)，其中 x 是我们上次开门的时间，b 是是否有礼物。对于给定的速率 λ，上面的优先级公式给出了 b 的期望值。我会建议 λ 的最大似然估计量。这意味着最大化 log(exp(−λx)) = −λx 在所有 (x, 0) 示例上的总和加上 log(1 − exp(−λx)) 在所有 (x, 1) 示例上的总和。这个函数可以直接优化，但是有两个问题:

我们打开一扇门的次数越多，优化的成本就越高。

如果没有正例或反例，则解是退化的。可能我们应该要求 λ 至少是每月一次或某事，以避免完全放弃一扇门。

我实际上建议的是选择一小组 λ 值来使其成为离散优化问题。
(另一个潜在问题是优先级公式对于许多门来说可能效率低下。您可以做的是为优先级选择一个目标阈值，然后计算优先级何时会超过该阈值。)