Online Pandora's Boxes and Bandits
Online Pandora's Boxes and Bandits
复制标题
在线潘多拉魔盒和强盗
DOI：
10.1609/aaai.v33i01.33011885
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Mitzenmacher
中科院分区：
文献类型：
--
作者：
Hossein Esfandiari;M. Hajiaghayi;Brendan Lucier;M. Mitzenmacher
我们认为在线变化的潘多拉盒子问题（Weitzman 1979），一个标准的模型来理解与获取决策信息的成本有关的问题。我们的问题概括了经典的潘多拉盒子问题和先知不平等框架。盒子是在线呈现的，每个盒子都有一个随机的值和成本，这些值和成本是从一些已知的分布中联合得出的。Pandora在线选择是否打开每个盒子，然后选择是否保留显示的奖品或传递它。我们的目标是近似算法，以对抗可以选择任何打开的盒子的最大奖品的对手，并使用最佳离线策略来决定打开哪些盒子（不知道里面的价值）1。我们考虑的变化，潘多拉可以收集多个奖项的可行性约束，如基数，拟阵，或背包约束。我们还考虑了强化学习中与经典多臂强盗问题相关的变化。我们的研究结果使用了一个基于约简的框架，在这个框架中，我们将获取信息的成本问题与保留奖品的在线决策过程分开。我们的工作表明，在许多情况下，Pandora可以实现很好的近似最佳性能。
We consider online variations of the Pandora’s box problem (Weitzman 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both the classic Pandora’s box problem and the prophet inequality framework. Boxes are presented online, each with a random value and cost drawn jointly from some known distribution. Pandora chooses online whether to open each box given its cost, and then chooses irrevocably whether to keep the revealed prize or pass on it. We aim for approximation algorithms against adversaries that can choose the largest prize over any opened box, and use optimal offline policies to decide which boxes to open (without knowledge of the value inside)1. We consider variations where Pandora can collect multiple prizes subject to feasibility constraints, such as cardinality, matroid, or knapsack constraints. We also consider variations related to classic multi-armed bandit problems from reinforcement learning. Our results use a reduction-based framework where we separate the issues of the cost of acquiring information from the online decision process of which prizes to keep. Our work shows that in many scenarios, Pandora can achieve a good approximation to the best possible performance.
DOI：
10.1007/978-3-662-48350-3_42
发表时间：
2015-07
期刊：
ArXiv
影响因子：
--
作者：
H. Esfandiari;M. Hajiaghayi;Vahid Liaghat;M. Monemizadeh
通讯作者：
H. Esfandiari;M. Hajiaghayi;Vahid Liaghat;M. Monemizadeh