Online Learning for Min Sum Set Cover and Pandora’s Box

Evangelia Gergatsouli, Christos Tzamos
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:7382-7403, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-gergatsouli22a, title = {Online Learning for Min Sum Set Cover and Pandora’s Box}, author = {Gergatsouli, Evangelia and Tzamos, Christos}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {7382--7403}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/gergatsouli22a/gergatsouli22a.pdf}, url = {https://proceedings.mlr.press/v162/gergatsouli22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Online Learning for Min Sum Set Cover and Pandora’s Box %A Evangelia Gergatsouli %A Christos Tzamos %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-gergatsouli22a %I PMLR %P 7382--7403 %U https://proceedings.mlr.press/v162/gergatsouli22a.html %V 162 %X 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.
APA
Gergatsouli, E. & Tzamos, C.. (2022). Online Learning for Min Sum Set Cover and Pandora’s Box. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:7382-7403 Available from https://proceedings.mlr.press/v162/gergatsouli22a.html.

Related Material