# Approximating Pandora's Box with Correlations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 55 references that are in the map.
- First posted on arXiv 30 Aug 2021.

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

- [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)
- [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)
- [A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree](https://mlsanity.com/paper/1906.11385/) (2019)
- [Competitive Information Design for Pandora's Box](https://mlsanity.com/paper/2103.03769/) (2021)
- [Adaptive Submodular Ranking and Routing](https://mlsanity.com/paper/1606.01530/) (2016)

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

- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)

## Abstract (arXiv)

We revisit the classic Pandora's Box (PB) problem under correlated distributions on the box values. Recent work of arXiv:1911.01632 obtained constant approximate algorithms for a restricted class of policies for the problem that visit boxes in a fixed order. In this work, we study the complexity of approximating the optimal policy which may adaptively choose which box to visit next based on the values seen so far. Our main result establishes an approximation-preserving equivalence of PB to the well studied Uniform Decision Tree (UDT) problem from stochastic optimization and a variant of the Min-Sum Set Cover (MSSCf) problem. For distributions of support m, UDT admits a log m approximation, and while a constant factor approximation in polynomial time is a long-standing open problem, constant factor approximations are achievable in subexponential time (arXiv:1906.11385). Our main result implies that the same properties hold for PB and MSSCf. We also study the case where the distribution over values is given more succinctly as a mixture of m product distributions. This problem is again related to a noisy variant of the Optimal Decision Tree which is significantly more challenging. We give a constant-factor approximation that runs in time n tilde O( m2/varepsilon2 )  when the mixture components on every box are either identical or separated in TV distance by varepsilon.