REVIEW 1 major objections 4 minor 6 references
Pandora with Inaccurate Priors
T0 review · 1 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Treating estimated distributions within Kolmogorov distance ε as true priors costs the optimal Pandora's-box policy at most O(nε) in expected utility.
desk verdict First robustness result for Pandora's box under inaccurate priors, with a clean O(nε) bound and a real but easily repairable gap in the key lemma. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the reserve price $\sigma_i$, defined by $E[(X_i-\sigma_i)^+]=c_i$, together with the expected-utility functional $W_\sigma(D)$ of the algorithm that opens boxes in decreasing $\sigma$ and stops when the running maximum exceeds the next reserve price. The load-bearing identity is, for an opened box $i$, $$W_\$\sigma$(x_1,\ldots,x_{i-1},x,D_{i+1},\ldots,D_n)=E\left[\max\left\{B(x),\max_{j\ge i+1}\kappa_j\right\}\right]-c_{\le i},$$ where $B(x)=\max\{x_1,\ldots,x_{i-1},x\}$ and $\kappa_j=\min\{\sigma_j,X_j\}$. The identity is proved by shifting each future opening cost $c_j$ to an acceptance-time charge $[X_j-\sigma_j]^+$, whose expectation equals $c_j$. It makes the per-coordinate utility function $g(x)$ increasing and 1-Lipschitz, and that 1-Lipschitz property is what converts a Kolmogorov-distance bound on CDFs into the $O(\varepsilon)$ per-coordinate utility loss of Lemma 5.
What would settle it
Take a sequence of instances with continuous distributions on $[0,1]$ and $d_K(D_i,D'_i)\le\varepsilon$, compute the exact loss $W_\sigma(D)-W_{\sigma'}(D)$, and watch $\text{loss}/(n\varepsilon)$ as $\varepsilon\to0$. If that ratio is unbounded over any sequence, the $O(n\varepsilon)$ bound is false; the paper's proof predicts it stays bounded by a universal constant.
Extended reading notes
Core claim
The paper proves two statements. Theorem 2: for any two distribution vectors within Kolmogorov distance $\varepsilon$ coordinatewise, replacing the true distributions by the estimated ones changes the expected utility of the same reserve-price policy by at most $O(n\varepsilon)$. Corollary 3: computing reserve prices from the wrong distributions and running the classical algorithm is at most $O(n\varepsilon)$ worse than running the optimal algorithm with the true distributions. The proof decomposes the change coordinate by coordinate: Lemma 4 shows the utility viewed as a function of one revealed value is increasing and 1-Lipschitz, and Lemma 5 shows that replacing one coordinate's distribution by an $\varepsilon$-close one changes the expectation by at most $O(\varepsilon)$; summing over $n$ coordinates gives the theorem. The paper also frames itself as the first to study inaccurate priors for Pandora's box, following the analogous question for prophet inequalities.
Load-bearing premise
The proof assumes that when boxes are opened in reserve-price order, expected utility can be counted as the expected best value among all boxes minus the costs of opened boxes, with each opening cost shifted to a charge at acceptance time; if this accounting identity fails, the $O(n\varepsilon)$ bound does not follow.
Editorial extensions
If this is right
- Using reserve prices inferred from priors that are ε-close in Kolmogorov distance loses at most O(nε) in expected utility, so the classical policy is stable under small estimation error.
- The per-coordinate proof makes the loss additive across boxes: the total shortfall is at most a constant per box, not exponential in n and not dependent on a margin condition.
- The guarantee covers every continuous distribution on [0,1] and every nonnegative cost vector, with no regularity assumptions beyond continuity.
- In the descending-price-search view of Pandora's box, substituting ε-accurate estimated distributions preserves near-optimality of the search rule.
Reading between the lines
- A learning extension left implicit: if each D_i is replaced by an empirical distribution from m samples, standard concentration bounds put the empirical CDF within Kolmogorov distance O(1/√m) with high probability, so the plug-in policy should lose O(n/√m) expected utility; this is our inference, not a claim of the paper.
- The additive analysis does not use cancellation across boxes; whether adversarial errors can force a loss of Ω(nε) or whether the true worst case is smaller is an open question the paper does not address.
- The continuity assumption is used to guarantee exact reserve prices and a clean threshold-crossing argument; a discrete analogue with approximate reserve prices is a plausible extension, but nothing in the paper guarantees it.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the sensitivity of Weitzman's optimal algorithm for Pandora's box to inaccuracies in the prior distributions. It assumes each true distribution D_i and estimated distribution D'_i are within ε in Kolmogorov distance and are supported on [0,1]. Theorem 2 claims |W_σ(D) - W_σ(D')| ≤ O(nε), where σ is the vector of reserve prices for D; Corollary 3 then concludes that using reserve prices computed from the inaccurate distributions loses at most O(nε) in expected utility. The proof proceeds coordinate by coordinate: Lemma 4 shows that the value function is 1-Lipschitz in the value of a single box, and Lemma 5 bounds the per-coordinate loss by O(ε). The main issue is that the proof of Lemma 5 relies on an integral identity for E[|g(X)-g(X')|] that is not valid for the coupling implicitly used in the argument.
Significance. If the result holds, this is a clean and natural robustness statement for a classical optimal-stopping problem, paralleling the inaccurate-priors analysis of Dütting and Kesselheim for prophet inequalities. The O(nε) bound is explicit, the statement is falsifiable, and the high-level strategy is appropriate: decompose the total error into per-coordinate changes and exploit the Lipschitz property of the value function. The cost-shifting argument in Lemma 4 is a genuine technical contribution and, as far as I checked, correct. However, because the key identity in Lemma 5 is not justified as written, the proof of the main theorem is incomplete. The gap appears repairable by a standard quantile-coupling argument, but it is load-bearing for the central claim.
major comments (1)
- [Section 3, proof of Lemma 5, display after Eq. (6)] The identity E[|g(X)-g(X')|] = ∫_0^∞ |Pr[g(X) ≥ t] - Pr[g(X') ≥ t]| dt is not valid for an arbitrary coupling of X ~ D_i and X' ~ D'_i. The proof says only 'Sample the random variables X_i and X'_i from D_i and D'_i respectively', which does not specify the joint distribution. For the default independent coupling, the identity fails: if D_i = D'_i = Uniform[0,1] and g(x)=x, the left side is 1/3 while the right side is 0. The equality holds only under the quantile/comonotone coupling, or equivalently the right side is the W1 distance between the laws of g(X) and g(X'), which is a lower bound on E[|g(X)-g(X')|] for an arbitrary coupling. Since this is the only step converting the Kolmogorov error ε into the O(ε) utility loss, Theorem 2 is not established as written. The gap is repairable: choose the quantile coupling X' = F_{D'_i}^{-1}(F_{D_i}(X)); because g is 1-Lipschitz by Lemma 4, E[|g(X)-g(X')|] ≤ E[|X-X'|] = W1(D_i,D'_i) = ∫_0^1 |F_{D_i}(t)-F_{D'_i}(t)| dt ≤ ε, where the last inequality uses the fact that both distributions are supported on [0,1] and are within ε in Kolmogorov distance. This argument should be added to the proof.
minor comments (4)
- [Section 2, Lemma 1] The statement 'The expected utility of any algorithm for the Pandora's box problem is E[max_i κ_i]' is imprecise; it should say the optimal expected utility is E[max_i κ_i], or that the following algorithm achieves this bound. As written, the sentence is false for suboptimal algorithms.
- [Section 3, proof of Lemma 4] The sentence 'Therefore, box i is accepted' appears to contain a typo and should refer to box i′ (the first box whose value exceeds its reserve price). As written, this sentence is confusing because the index i was fixed at the start of the lemma.
- [Section 3, proof of Lemma 5] The definition of g(x) as W_σ(x_1, ..., X_{i-1}, x, D_{i+1}, ..., D_n) uses the random variable X_{i-1} where the proof has fixed the values x_1, ..., x_{i-1}; this should be x_{i-1}.
- [Throughout] There are several typographical errors: 'thie problem' and 'different settings including different settings' in Section 1, 'expected ulity' in Section 3, and inconsistent dashes in the abstract. A careful proofread is recommended.
Circularity Check
No circular reasoning: the sensitivity bound is derived from Weitzman's optimality lemma and standard probability arguments, not from fitted parameters or self-citation.
full rationale
The paper's central claim, Theorem 2 and Corollary 3, is proved from first principles using Weitzman's classical Pandora's box characterization (Lemma 1) and elementary properties of reserve prices. The authors do not fit any parameter to the target quantity, do not define the object of study in terms of the conclusion, and do not rely on their own prior work as load-bearing evidence. The proof of Lemma 4 establishes the 1-Lipschitz monotonicity of the utility as a function of a single realized value, and Lemma 5 attempts to convert Kolmogorov distance between distributions into a bound on the change in expected utility via the layer-cake integral representation. The flagged issue in Lemma 5—the asserted equality E[|g(X)-g(X')|] = ∫ |Pr[g(X)≥t]-Pr[g(X')≥t]| dt—is a mathematical correctness concern about the coupling of X and X', not a circularity: it does not reduce the theorem to its assumptions by construction, and it is in principle repairable by a Wasserstein/quantile coupling argument. Similarly, the proof of Corollary 3 uses only the optimality of each reserve-price vector for its own distribution and Theorem 2; this is a standard sandwiching argument, not circular. The self-citation to Esfandiari, HajiAghayi, Lucier, and Mitzenmacher appears only in the related-work discussion and is not used to justify any technical step. Therefore the paper's derivation chain is self-contained with respect to circularity; the observed weakness is a proof gap rather than a definitional or self-referential reduction.
Assumptions & free parameters
assumptions (2)
- standard math Weitzman's optimality lemma: expected optimal utility equals E[max_i min{sigma_i, X_i}] and the descending reserve-price algorithm achieves it.
- domain assumption Each value distribution D_i is continuous and supported on [0,1].
Cite this review
Pith. "Pith review of Pandora with Inaccurate Priors." pith.science (2026). https://pith.science/paper/IKEN6X4Y
@misc{pith2026250203574,
author = {Pith},
title = {Pith review of: Pandora with Inaccurate Priors},
year = {2026},
howpublished = {\url{https://pith.science/paper/IKEN6X4Y}},
note = {Machine review of arXiv:2502.03574}
}
read the original abstract
We investigate the role of inaccurate priors for the classical Pandora's box problem. In the classical Pandora's box problem we are given a set of boxes each with a known cost and an unknown value sampled from a known distribution. We investigate how inaccuracies in the beliefs can affect existing algorithms. Specifically, we assume that the knowledge of the underlying distribution has a small error in the Kolmogorov distance, and study how this affects the utility obtained by the optimal algorithm.
Reference graph
Works this paper leans on
-
[1]
H. Beyhaghi and L. Cai. Recent developments in pandora’s box problem: V ariants and applications. ACM SIGecom Exchanges, 21(1):20–34, 2024
work page 2024
- [2]
-
[3]
P . Dütting and T. Kesselheim. Posted pricing and prophet inequalities with inaccurate priors. In Proceedings of the 2019 ACM Conference on Economics and Comp utation, pages 111–129, 2019. 6
work page 2019
-
[4]
H. Esfandiari, M. HajiAghayi, B. Lucier, and M. Mitzenma cher. Online pandora’s boxes and bandits. In Proceedings of the AAAI Conference on Artificial Intelligen ce, volume 33, pages 1885–1892, 2019
work page 2019
-
[5]
R. Kleinberg, B. Waggoner, and E. G. Weyl. Descending pri ce optimally coordinates search. arXiv preprint arXiv:1603.07682, 2016
arXiv 2016
- [6]
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.