# Bandit Algorithms for Prophet Inequality and Pandora's Box

arXiv: https://arxiv.org/abs/2211.08586 · HTML: https://mlsanity.com/paper/2211.08586/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 16 Nov 2022.

## Builds on (most cited first, 24 of 24)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [A Stochastic Probing Problem with Applications](https://mlsanity.com/paper/1302.5913/) (2013)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Descending Price Optimally Coordinates Search](https://mlsanity.com/paper/1603.07682/) (2016)
- [The Markovian Price of Information](https://mlsanity.com/paper/1902.07856/) (2019)
- [Learning Utilities and Equilibria in Non-Truthful Auctions](https://mlsanity.com/paper/2007.01722/) (2020)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Combinatorial Auctions via Posted Prices](https://mlsanity.com/paper/1411.4916/) (2014)
- [Online Pandora's Boxes and Bandits](https://mlsanity.com/paper/1901.10698/) (2019)
- [Online Contention Resolution Schemes](https://mlsanity.com/paper/1508.00142/) (2015)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Combinatorial Prophet Inequalities](https://mlsanity.com/paper/1611.00665/) (2016)
- [Beating Greedy for Stochastic Bipartite Matching](https://mlsanity.com/paper/1909.12760/) (2019)
- [Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models](https://mlsanity.com/paper/2002.09807/) (2020)
- [Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities](https://mlsanity.com/paper/2102.10261/) (2021)
- [Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark](https://mlsanity.com/paper/2206.01270/) (2022)
- [Beyond matroids: Secretary Problem and Prophet Inequality with general constraints](https://mlsanity.com/paper/1604.00357/) (2016)
- [Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection](https://mlsanity.com/paper/1807.05477/) (2018)

## Built on by (most cited first, 13 of 13)

- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Optimal Stopping vs Best-of-N for Inference Time Optimization](https://mlsanity.com/paper/2510.01394/) (2025)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Learning Markov Decision Processes under Fully Bandit Feedback](https://mlsanity.com/paper/2602.02260/) (2026)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Learning in Prophet Inequalities with Noisy Observations](https://mlsanity.com/paper/2604.01789/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

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 unknown distributions over T rounds: in round t we play a policy x(t) and receive a partial (bandit) feedback on the performance of x(t). The goal is to minimize the regret, which is the difference over T rounds in the total value of the optimal algorithm that knows the distributions vs. the total value of our algorithm that learns the distributions from the partial feedback. Our main results give near-optimal tildeO(mathsfpoly(n)√T) total regret algorithms for both Prophet Inequality and Pandora's Box. Our proofs proceed by maintaining confidence intervals on the unknown indices of the optimal policy. The exploration-exploitation tradeoff prevents us from directly refining these confidence intervals, so the main technique is to design a regret upper bound that is learnable while playing low-regret Bandit policies.