论文标题
最小值套装的在线学习和潘多拉的盒子
Online Learning for Min Sum Set Cover and Pandora's Box
论文作者
论文摘要
随机优化中的两个主要问题是最小总和集盖和潘多拉的盒子。在潘多拉（Pandora）的盒子中，我们有$ n $ box，每个盒子都包含一个未知的值，目标是按某种顺序打开盒子，以最大程度地减少搜索成本和最小值的总和。给定价值向量的分布，我们被要求确定近乎最佳的搜索顺序。最小总和集盖子对应于值为0或无穷大的情况。在这项工作中，我们研究了价值向量不是从分布中绘制而是以在线方式呈现给学习者的情况。我们提出了一种计算有效的算法，该算法是持续竞争力的，该算法竞争最佳搜索顺序的成本。我们将结果扩展到一个强盗设置，在每个回合后仅向学习者揭示了打开的盒子的值。我们还将结果推广到潘多拉盒子和最小总和集盖的其他经常研究的变体，这些变体涉及选择超过单个值，而受矩形约束。
Two central problems in Stochastic Optimization are Min Sum Set Cover and Pandora's Box. In Pandora's Box, we are presented with $n$ boxes, each containing an unknown value and the goal is to open the boxes in some order to minimize the sum of the search cost and the smallest value found. Given a distribution of value vectors, we are asked to identify a near-optimal search order. Min Sum Set Cover corresponds to the case where values are either 0 or infinity. In this work, we study the case where the value vectors are not drawn from a distribution but are presented to a learner in an online fashion. We present a computationally efficient algorithm that is constant-competitive against the cost of the optimal search order. We extend our results to a bandit setting where only the values of the boxes opened are revealed to the learner after every round. We also generalize our results to other commonly studied variants of Pandora's Box and Min Sum Set Cover that involve selecting more than a single value subject to a matroid constraint.
