# Contextual Pandora's Box

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 76 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 30 of 32)

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration](https://mlsanity.com/paper/1807.00755/) (2018)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Pandora's Box Problem with Order Constraints](https://mlsanity.com/paper/2002.06968/) (2020)
- [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)
- [Pandora's Box with Correlations: Learning and Approximation](https://mlsanity.com/paper/1911.01632/) (2019)
- [Pandora's Problem with Nonobligatory Inspection](https://mlsanity.com/paper/1905.01428/) (2019)
- [The Markovian Price of Information](https://mlsanity.com/paper/1902.07856/) (2019)
- [Submodular Stochastic Probing on Matroids](https://mlsanity.com/paper/1310.4415/) (2013)
- [Online Pandora's Boxes and Bandits](https://mlsanity.com/paper/1901.10698/) (2019)
- [Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent](https://mlsanity.com/paper/2011.02817/) (2020)

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

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Optimal Stopping vs Best-of-N for Inference Time Optimization](https://mlsanity.com/paper/2510.01394/) (2025)
- [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)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)

## Abstract (arXiv)

Pandora's Box is a fundamental stochastic optimization problem, where the decision-maker must find a good alternative while minimizing the search cost of exploring the value of each alternative. In the original formulation, it is assumed that accurate distributions are given for the values of all the alternatives, while recent work studies the online variant of Pandora's Box where the distributions are originally unknown. In this work, we study Pandora's Box in the online setting, while incorporating context. At every round, we are presented with a number of alternatives each having a context, an exploration cost and an unknown value drawn from an unknown distribution that may change at every round. Our main result is a no-regret algorithm that performs comparably well to the optimal algorithm which knows all prior distributions exactly. Our algorithm works even in the bandit setting where the algorithm never learns the values of the alternatives that were not explored. The key technique that enables our result is a novel modification of the realizability condition in contextual bandits that connects a context to a sufficient statistic of each alternative's distribution (its "reservation value") rather than its mean.