Pandora's Box Problem Over Time

潘多拉魔盒问题模拟了在评估成本高昂的情况下寻找最佳选择的过程。在最简单的情况下，决策者面临$n$个盒子，每个盒子都有一个检查成本和一个隐藏奖励的分布。决策者依次检查这些盒子的一个子集，可能是自适应顺序，并获得的效用是发现的最大奖励与检查成本总和之间的差异。虽然这个经典版本的问题被很好地理解了（Weitzman 1979），但近年来该问题的变体文献蓬勃发展。在本文中，我们介绍了一个通用框架——潘多拉魔盒随时间问题——它涵盖了许多变体，其中时间起到了作用，例如，它可能限制了探索的时间表并影响成本和奖励。在潘多拉魔盒随时间问题中，每个盒子都由时间相关的奖励和成本所特征化，检查它可能需要特定于盒子的处理时间。此外，一旦检查了一个盒子，它的奖励可能会随时间而恶化，可能对每个盒子都不同。我们的主要结果是对最优策略的有效$21.3$近似，通常情况下计算是NP难的。我们进一步在自然特殊情况下获得了改进的结果，其中盒子没有处理时间，或者成本和奖励分布不依赖于时间（但奖励可能在检查后恶化）。

Pandora's Box Over Time问题

提出了一个通用的框架，可以捕捉时间在探索中的作用，为NP-hard问题提供了21.3的有效逼近算法

论文介绍了Pandora's Box Over Time问题，提出了有效的逼近算法，针对不同特殊情况给出了改进的结果。实验设计合理，结果表明算法的有效性。

Weitzman 1979的经典版本问题