Bandit Algorithms for Prophet Inequality and Pandora's Box. (arXiv:2211.08586v1 [cs.DS])

The Prophet Inequality and Pandora's Box problems are fundamental stochastic
problem with applications in Mechanism Design, Online Algorithms, Stochastic
Optimization, Optimal Stopping, and Operations Research. A usual assumption in
these works is that the probability distributions of the $n$ underlying random
variables are given as input to the algorithm. Since in practice these
distributions need to be learned, we initiate the study of such stochastic
problems in the Multi-Armed Bandits model.

In the Multi-Armed Bandits model we interact with $n$ …

algorithms arxiv inequality prophet