Weitzman's Rule for Pandora's Box with Correlations
Authors: Evangelia Gergatsouli
Christos Tzamos
Venue: NeurIPS 2023 poster (2023)
Keywords: pandora's box
stochastic optimization
discrete optimization
learning from samples
algorithms under uncertainty

Abstract: Pandora’s Box is a central problem in decision making under uncertainty that can model various real life scenarios. In this problem we are given n boxes, each with a fixed opening cost, and an unknown value drawn from a known distribution, only revealed if we pay the opening cost. Our goal is to find a strategy for opening boxes to minimize the sum of the value selected and the opening cost paid.
In this work we revisit Pandora’s Box when the value distributions are correlated, first studied in [CGT+20]. We show that the optimal algorithm for the independent case, given by Weitzman’s rule, directly works for the correlated case. In fact, our algorithm results in significantly improved approximation guarantees compared to the previous work, while also being substantially simpler. We also show how to implement the rule given only sample access to the correlated distribution of values. Specifically, we find that a number of samples that is polynomial in the number of boxes is sufficient for the algorithm to work.

Weitzman's Rule for Pandora's Box with Correlations
Evangelia Gergatsouli University of Aasconsin-Madison evagergůcs wisc.
Christos Tzamos University Aaeconsin-Madisonn & University of Athens tzamosQwisc. edu
Abstract
PANDORA'S BOX is a central problem in decision making under uncertainty that can model various real life scenarios. In this problem we are given n boxes, each with a fixed opening cost, and an unknown value drawn from a known distribution, only revealed if we pay the opening cost. Our goal is to find a strategy for opening boxes to minimize the sum of the value selected and the opening cost paid.
In this work revisit PANDORA'S BOX when the value distributions are correlated, first studied in Chawla et al. [2020]. We show that the optimal algorithm for the independent case, given by Weitzman's 's rule, directly works for the correlated case. In fact, our algorithm results in significantly improved approximation guarantees compared to the previous work, while also being substantially simpler. We also show how to implement the rule given only sample access to the correlated distri- bution of values. Specifically, we find that number of samples that polynomial in the number of boxes is sufficient for the algorithm to work.
Introduction
In various minimization problems where uncertainty exists in the input, we are allowed to obtain information to remove this uncertainty by paying extra price. Our goal is to sequentially decide which piece of information to acquire next, order to minimize the sum of the search cost and the value of the option we chose.
This family of problems is naturally modeled by PANDORA'S Box, first formulated by Weitzman [1979] in an economics setting, with multiple application in consumer search, housing markets and job search (see [McCall and McCall, 2007] for more applications). In this problem where we are given boxes, each containing a value drawn from known distribution and each having fixed known opening cost. We can only see the exact value realized in a box we open it and pay the opening cost. Our goal is to minimize the sum of the value select and the opening costs of the boxes we opened.
In the original work of Weitzman, an optimal solution was proposed when the distributions on the values of the boxes were independent [Weitzman, 1979]. This algorithm was based on calculating a reservation value (a) for each box, and then choosing the box with the lowest reservation value to open at every step. Independence, however, is an unrealistic assumption in real life: in housing market neighboring houses' price are affected the same way, or in job search setting, candidates might share qualifications that affect them similarly. Wanting to tackle a more realistic setting, Chawla et al. [2020] first studied the problem where the distributions are correlated, and designed an algorithm giving a constant approximation guarantee. This algorithm is quite involved, it requires solving an LP to convert the PANDORA'S Box instance to a MIN SUM SET COVER one, and then solving this instance to obtain an ordering opening the boxes. Finally, reduces the problem of deciding when to stop to online algorithm question corresponding to SKI-RENTAL.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Our Contribution
In this work we revisit PANDORA'S Box with correlations, and provide simpler, learnable algorithms with better approximation guarantees, that directly generalize Weitzman's reservation values. More specifically, our results are the following.
Generalizing: first show how the original reservation values given by Weitzman [1979] can be generalized to work in correlated distributions, thus allowing us to use a version of their initial greedy algorithm.
we give two different variants of our main algorithm, that each uses different updates on the distribution D> after every step.
Better approximation:
Variant 1: partial updates. We condition on the algorithm not having stopped yet.
2. Variant 2: full updates. We condition on the exact value e revealed in the box opened.
Both variants improve the approximation given by Chawla et al. [2020] from 9.22 to 4.428 for Variant and to 5.828 for Variant 2. is worth noting that our result for Variant I is almost tight, since the best possible approximation factor by Feige [1998]. We include more details on the lower bound in Section A.4 of the Appendix.
obtain is 4, implied
Simplicity: our algorithms are greedy and only rely on the generalized version of the reservation value, while the algorithms in previous work rely solving linear program, and reducing first to MIN SUM SET COVER then to SKI-RENTAL, making them not straightforward implement. A 9.22 approximation was also given in Gergatsouli and Tzamos [2022], which followed the same approach but bypassed the need to reduce to MIN SUM SET COVER by directly rounding the linear program via randomized rounding.
Learnability: we show how given sample access to the correlated distribution DD we are able to still maintain the approximation guarantees. Specifically, for Variant 1 only poly(n, 1/E, log(1/))) samples are enough to obtain 4.428 + approximation with proba- bility at least 1 ó. Variant 2 is however impossible to learn.
Our analysis is enabled by drawing similarities from PANDORA'S A Box to MIN SUM SET COVER, which corresponds to the special case of when the values inside the boxes 0 or co. For MIN SUM SET COVER a simple greedy algorithm was shown to achieve the optimal 4-approximation [Feige al., 2002]. Surprisingly, Weitzman's algorithm can be seen direct generalization of that algorithm. Our analysis follows the histogram method introduced in Feige et al. [2002], for bounding the approximation ratio. However, we significantly generalize handle values in the boxes and work with tree-histograms required to handle the case with full-updates.
1.2 Related Work
Since Weitzman's 's initial work [Weitzman, 1979] on PANDORA'S BOx there has been a renewed interest in studying this problem in various settings. Specifically Doval [2018]. Beyhaghi and Kleinberg [2019], Beyhaghi and Cai [2023a], Fu et al. [2023] study PANDORA'S Box when we can select box without paying for it (non-obligatory inspection), in Boodaghians et al. [2020] there are tree or line constraints on the order in which the boxes can be opened. In Chawla et al. [2020, 2021] the distributions on the values inside the boxes are correlated and the goal is to minimize the search and value cost, while finally in Bechtel et al. [2022] the task of searching over boxes is delegated by an agent to a principal, while the agent makes the final choice. The recent work of Chawla et al. [2020] is the first one that explores the correlated distributions variant and gives the first approximation guarantees. The recent survey by Beyhaghi and Cai [2023b] summarizes the recent work on Pandora's 's Box and its variants.
This problem can be seen as being part of the "price of information" literature [Charikar et al., 2000, Gupta and Kumar, 2001, Chen et al., 2015b,a], where we can remove part of the uncertainty of the problem hand by paying price. In this line of work, more recent papers study the structure of approximately optimal rules for combinatorial problems [Goel et al., 2006, Gupta and Nagarajan, 2013, Adamezyk et al., 2016, Gupta et al., 2016, 2017, Singla, 2018, Gupta al., 2019].
For the special case of MIN SUM SET COVER, since the original work of Feige et al. [2002], there has been many follow-ups and generalizations where every set has requirement of how many elements

---

contained in it we need to choose [Azar et al., 2009, Bansal et al., 2010, Azar and Gamzu, 201 1, Skutella and Williamson, 2011, Im al., 2014].
Note also that multiple results on problems related to Pandora's box have been published MI.- related conferences, as this is problem that encompasses both algorithmic and learning aspects (e.g. Esfandiari et al. [2019], Gergatsouli and Tzamos [2022], Bhaskara et al. [2020], Cesa-Bianchi et al. [2021], Guo et [2021]).
2 Preliminaries
In PANDORA'S Box (PB) we are given a set of n. boxes B, each with known opening cost C E IR+, and distribution over vector of unknown values box b E B, once it is opened, reveals the value up. The algorithm can open boxes sequentially, by paying the opening cost each time, and observe the value instantiated inside the box. The goal of the algorithm is to choose a box of small value, while spending as little cost as possible "opening" boxes. Formally, denoting by O B the set of opened boxes, we want to minimize
(UI,..., Un) R inside the boxes. Each
E
min Ub +
Σ Ch DEO
BEO
A strategy for PANDORA'S Box is an algorithm that in every step decides which is the next box to open and when to stop. We measure the performance of our algorithm usign the competitive (or approximation) ratio; strategy A is a-approximation if E [A] S aOPT, where OPT is the optimal online algorithm'
A strategy can pick any open box to select at any time. To model this, we assume without loss of generality that after a box is opened the opening cost becomes 0, allowing us select the value without opening it again. In its full generality, strategy can make decisions based on every box opened and value seen so far. We call this the Fully-Adaptive (FA) strategy.
Different Benchmarks. As it was initially observed in Chawla et al. [2020], optimizing over the class of fully-adaptive strategies is intractable, therefore we consider the simpler benchmark of partially-adaptive (PA) strategies. In this case, the algorithm has to fix the opening order of the boxes, while the stopping rule can arbitrarily depend on the values revealed.
2.1 Weitzman's Algorithm
When the distributions of values in the boxes are independent, Weitzman [1979] described a greedy algorithm that is also the optimal strategy. In this algorithm, first calculate index for every box b, called reservation value db. defined as the value that satisfies the following equation
EnwD [ vb) Cb.
where (a b)+ max(0, a b). Then, the boxes are ordered by increasing ar and opened until the minimum value revealed is less than the next box in the order. Observe that this is partially-alattive strategy.
Competing with the Partiall--Aaaptiv
We begin by showing how Weitzman's 's algorithm can be extended to correlated distributions. Our algorithm calculates a reservation value for every box each step, and opens the box b E B with the minimum db We stop if the value is less than the reservation value calculated, and proceed in making this box free; we can re-open this for no cost, to obtain the value just realized at any later point. The formal statement is shown in Algorithm 1.
We give two different variants based on the type of update we do after every step on the distribution D. In the case of partial updates, we only condition on Vú > ob, which is equivalent to the algorithm
'The optimal online has the exact same information as our algorithm A but has infinite computation time to solve the problem.

---

not having stopped. On the other hand, for full updates we condition on the exact value that was instantiated in the box opened. Theorem 3.1 gives the approximation guarantees for both versions of this algorithm.
Algorithm 1: Weitzman's 's algorithm, for correlated DD
Input: Boxes with costs & E RR distribution over scenarios An unknown vector of values V ~ D is drawn
repeat
Calculate d for each box b B by solving:
EenD [(o0 - [b)+] -1b)+]
cb.
Open box argmin
Stop if the value the observed Vi tb S
eb f- 0 // Box is always open now or can be reopened
Update the prior distribution
Variant D D Mi (partial updates)
Variant 2: D <- D Vg=o, (full updates)
until termination;
Theorem 3.1. Algorithum I is ..22-apprrxxmmation for Variant and 5.828-approximation for Variant of PANDORA'S Box against the partially-ddapiee optimal.
Proof. We seperately show the two components of this theorem in Theorems 3.2 and 3.3.
Observe that for independent distributions this algorithm exactly the same as Weitzman's 's [Weitzman, 1979], since the product prior D remains the same, regardless of the values realized. Therefore, the calculation of the reservation values does not change in every round, and suffices to calculate them only once at the beginning.
Scenarios To proceed with the analysis of Theorem 3.1, we assume that D is supported on collection of m vectors, (v") which we call scenarios, and sometimes abuse notation to say that scenario is sampled from the distribution D. We assume that all scenarios have equal probability. The general case with unequal probabilities follows by creating more copies of the higher probability scenarios until the distribution is uniform.
scenario is covered when the algorithm decides to stop and choose a value from the opened boxes. For specific scenario E S we denote by c(s) the total opening cost paid by an algorithm before this scenario covered and by vss) the value chosen for this scenario.
To analyze Theorem 3.1, introduce new way of defining the reservation values of the boxes that is equivalent to (1). For a box b, we have that
Reservation Values
C6 E.EA
PRo [s] ug
min ACS
E.EA
Pro [s]
The equivalence (1), follows since ar defined as the root of the expression
EnED [aa - -]])+]
Σ Pro (a) - vz²++ Cb
cs
max ACS
Σ
Pro [s] (ab vt) cb.
we divide the above expression by any positive number, the result will not be affected since we require the root of the equation; σy being the root is equivalent σ6 being the root of the numerator.

---

Thus, dividing by ExEA Prp [s] we get that is also the root of
Esen Pro (s] (ob - -
Cb
ExEA Pro [s
max
56
min AÇS
(2)
AÇS
ExEA Prp
E.EA Prp
This, gives our formula for computing ob, which we can further simplify using our assumption that all scenarios have equal probability, In this case, Prp [s] = 1/ S| which implies that
0o|S + >.EA ACS
min
|4|
3.1 Conditioning on V/ >>00
We start by describing the simpler variant of our algorithm where after opening each box we update the distribution by conditioning on the event V,, order for each scenario does not depend on actual value that is realized every time. At every step the algorithm will either stop continue opening boxes conditioned on the event "We have not stopped yet" which does not differentiate among the surviving scenarios.
This algorithm is partially adaptive, since
Theorem 3.2. Algorithm a -4288-pproximation for PANDORA'S s Box against the partially- adaptive optimal, when conditioning on Vo db.
In this section show simpler proof for Theorem 3.2 that gives 33+2222 5.828 ap.2xxapproxiiatioon The full proof for the ..42--aprrxximation is given in section A.2 of the Appendix. Using the equivalent definition of the reservation value (Equation (3)) rewrite Algorithm follows.
Algorithm 2: Weitzman's 's rule for Partial Updates
Input: Boxes with costs & E R, set of scenarios S.
t <<-0 0
Ro < the set of scenarios still uncovered
while RG + 0 do
Let o. < AAC
[A]
Let b, and A, be the box and the set of scenarios that achieve the minimum
Open box by and pay co2 Stop and choose the value Ub, at box b, if it is less than o, (see also Fact 3.2.1)
8
Set Cb, +- 0
R. R4 \ A
10
t t
t ++1
11 end
Structure of the solution. An important property note is that by the equivalent definition of the reservation value (3) the set of scenarios that stop at each step are the ones that give value at most for the box opened, as we formally state in the following fact.
Fact 3.2.1. The value at box is less than ot if and only if E Ar.
In equation (8) the set A, that maximizes the expression contains all the scenarios with value most σr for the box b. Therefore, the set A, are exactly the scenarios covered at each step of the algorithm, and can be removed from consideration.
Before showing our result, observe that this algorithm is partially adaptive; the order of the boxes does not depend on the scenario realized. This holds since only condition "not having stopped" (i.e. ov.) and therefore each scenario either stops or uses the same updated prior as all other surviving scenarios to calculate the next reservation values. If we were to draw solution, it would look like a line, (see also Figure in Appendix A.2), which as we observe in Section 3.2 differs from Variant
Moving on to show the proof, we first start by giving a bound on the cost of the algorithm. The cost can be broken down into opening cost plus the value obtained. Since at any time t, all remaining
5

---

scenarios RG pay the opening cost ob,, we have that the total opening cost is Ee Cb2 Rel. Moreover, the chosen value is given as E, Σ EEE, V/. Overall, we have that
ALG Σ
Cb. [2, +
Σ Ax
ob
Σ
Ael Cb.
R +
E.EA, vi
Σ Acloo
[A,
Defining og to be the reservation value of scenario s the time it covered, i.e. when s A,, we get ALG = _ se a=². We follow a histogram analysis similar to the proof of Theorem 4 in Feige al. [2004] for MIN SUM SET COVER and construct the following histograms.
The OPT, histogram: put the scenarios on the x-axis on increasing opening cost order c according to OPT, the height each scenario is the opening cost paid.
The oPT, histogram: put the scenarios on the x-axis on increasing covering value order oPP according to OPT, the height of each scenario is the value with which it was covered.
The ALG histogram: put scenarios on the x-axis in the order the algorithm covers them. The height of each scenario a. Observe that the area of the ALG histogram is exactly the cost of the algorithm.
Proof of Theorem 3.2. Initially, observe that the algorithm will eventually stop; every time open a box we cover at least one scenario (since line 3 cannot be oo while scenarios are left uncovered).
To show the approximation factor, we scale the histograms as follows; OPT, scale horizontally by 1/a, and vertically by 1/(8 7)) and OPT, scale by 1/a, horizontally, for some constants Co, Ove 8 E (0, 1) to be determined later?. We align the ALG histogram with OPT, and OPT, so that all of them have the same nght-hand side. Observe that the optimal opening cost is the area below the histogram OPT, and has increased by B .y aoo and similarly the area below OPT, has increased by ag as a result of the scaling.
To conclude the proof it suffices to show that any point in the ALG histogram is inside the sum of the rescaled OPT, and OPT, histograms. Consider any point p in the ALG histogram, and let be its corresponding scenario and t be the time this scenario is covered. We have that the height of the ALG histogram
0, = Cb. Bel + EoEA, VG.
cb|Rel + EeEA of
|Ad
[A]
where the last inequality holds for all A S R2 and any b e B.
Denote by e* the opening cost such that Re of the scenarios in R3 have opening cost less than e", and by Rko = {s E R₂ .PPT I c²) the set of these scenarios. Similarly denote by s" the value of scenarios in Rlow such that R of the scenarios have value less than v" and by
= {s E Roo ooPr < v²} these scenarios. This split shown in Figure I, and the constants 8, 7 E (0, 1) will be determined at the end of the proof.
(1- 1-B)y(Ba c*
Ry
By e*
? Rg
R1
Figure 1: Split of scenarios in R.-
Let By be the set of boxes that the optimal solution uses to cover the scenarios in L. Let L, S L C Re be the subset of scenarios in that choose the value at box in OPT. Using inequality (4) with
Throughout this proof omit the uormalization term 1/1S¹ both the algorithms cost and the optimal cost, without loss of generality, since our guarantee multiplicative.
'Scaling horizontally means that we duplicate every scenario and scaling vertically we just multiply the height every point by the scale factor.

---

b E BL and = Lo. we obtain T. o,|Lo| S <co|Ril + EsEL, U and by summing up the inequalities for all b E Br we get
Re EbEBL cb + EEL OPP |R/l + E.EL U
OPT
c² EBEL OPT
0, 5
(5)
[L]
L
8.7
[
where for the second inequality we used that the cost for covering the scenarios in L is at most c* by construction, and in the last inequality that |L] = [ 7). We consider each term above separately, to show that the point p is within the histograms.
Bounding the opening cost. By the construction of c", the point in the OPT. histogram that has cost at least c* is at distance at least (1 - 7) [), from the right hand side. This means that in the rescaled histogram, the point that has cost least c* /(3 7) is distance at least (1 - Rel/ from the right hand side.
On the other hand, in the ALG histogram the distance of from the right edge of the histogram is at most Rg), therefore for the point to be inside the OPT, histogram we require
Og S 1 7.
(6)
Observe that throughout the proof we did not use the fact that we change the opening cost to 0, therefore the bound on our cost works even if re-pay the boxes that are reopened.
The fact that the opening cost becomes 0 not directly used in the analysis (i.e. inequalities (4) and
(5) ). Our analysis gives upper bound the cost of the algorithm, even if the algorithm never changes the cost of an opened box to O. That is the reason in (4) and (5) the cost appears unchanged but the analysis still works for the algorithm since just want upper bound (and if we changed the cost to 0 this would only lower the cost of the algorithm).
Bounding the values cost. By the construction of v², the point in the OPT, histogram that has value v" is at distance at least [1,(( - B)y from the right hand side. This means that in the rescaled histogram, the point that has value at least v² is at distance at least (1 Rala /a,, from the right hand side.
On the other hand, in the ALG histogram the distance of from the right edge of the histogram is at most [Rl, therefore for the point p to be inside the OPT, histogram we require
Ogp < (1 B)y-
We optimize the constants (ka, Chn, 3,,,,,7 by ensuring that inequalities (6) and (7) hold. We set 0s =
1 y and Or (1 - 3)7, and obtain that ALG < OPT./(B y (1 (1-7)) + OPT,:/(1 3) Requiring these to be equal we get 8 1/(2- 7),, which is minimized for 3 1/v2 and 2- V2
for value of 3 + 2/2.
3.2 Conditioning on Vi =
In this section we switch gears to our second variant of Algorithm 1, where in each step we update the prior D conditioning on the event V,, We state our result in Theorem 3.3. In this case, the conditioning on D implies that the algorithm at every step removes the scenarios that are inconsistent with the value realized. In order to understand better the differences of the two variants and their conditioning we included an example and a discussion in section A. of the Appendix.
Theorem 3.3. Algorithm I a 2v2 5.828-approsiie appraxipaxaiiinnnaoomma for PANDORA'S Box against the purtially-adaptive optimal, when conditioning on Vn_
The main challenge was that the algorithm's solution is now tree with respect to scenarios instead of a line as in the case of D Vi Specifically, in the Dlvi variant at every step all scenarios that had V/ σb were covered and removed from consideration. However in the D Dlv,=e variant the remaining scenarios are split into different cases, based on the realization of V, as shown in the example of Figure 4, which is deferred Section A.3 of the Appendix due to space constraints.
This results into the ALG histogram not being well defined, since there no unique order covering the scenarios. We overcome this by generalizing the histogram approach to trees.
7

---

Proof of Theorem 3.3. The proof follows similar steps to that of Theorem 3.2, thus we only highlight the differences. The algorithm presented below, the only change is line where we remove the inconsistent with the value revealed scenarios, which also leads to our solution branching out for different scenarios and forming tree.
Algorithm 3: Weitzman's rule for Full Updates
Input: Boxes with costs q E R. set of scenarios S. Define root node u corresponding the set
Ry <- S the set of scenarios still uncovered
while R., * ) do
Let TT ACC c.IRul+E..dd
Let by and A, be the box and the set of scenarios that achieve the minimum Open box bu paying cb, and observe value v Stop and choose the value at box by it is less than ogt this holds iff' s E Au Set Cb. f- 0
Let u' vertex corresponding to the set of consistent scenarios with
R & Ry, \. (A, Us R., o% # b}} // Remove inconsistent scenarios Set u t u
10
11 end
Bounding the opening cost Consider the tree T of ALG where every node set A, of scenarios is covered. We associate this tree with node weights, where at every node u, we assign |A, weights (ou, -.,, O.). Denote, the weighted tree by TALG. As before, the total cost of ALG is equal to the sum of the weights of the tree.
We now consider two alternative ways of assigning weights to the the nodes, forming trees TOPT.. TOPT, using the following process.
TOPT.. At every node u we create a vector weights w WOPT. (cOPT) (cOPT) OPT is the opening cost that scenario E A., has in the optimal solution.
AE where each
TOPT... At every node create vector of weights W.PT, (2:PT) )EE, where each 1 is the value the optimal uses to cover scenario A..
We denote by cost(TALG) the sum all weights in every node the tree T. We have that cost(T) is equal to the total cost of ALG, while cost(ToPT.) and cost (ost(Tor,,)) is equal to the optimal opening cost OPT, and optimal value OPT, respectively. Intuitively, the weighted trees correspond to the histograms in the previous analysis of Theorem 3.2.
We want to relate the cost of ALG, that of TOPT.. and TOPT To this, we define an operation similar to histogram scaling, which replaces the weights of every node u in tree with the top p-percentile of the weights in subtree rooted at u. As the following lemma shows, this changes the cost of tree by bounded multiplicative factor.
Lemma 3.3.1. Let T be a tree with a vector of weights ww at each node u E T, and let T(e) be the tree we get when substitute the weights of every node with the top p-percentile of all the weights in the subtree of T rooted at u. Then
p ((P)( cost(T).
We defer the proof of Lemma 3.3.1 to Section A.3 of the Appendix. To complete the proof of Theorem 3.3, and bound cOst(TALG), we show as before that the weights at every node u, are bounded by the weights of (T(-"") scaled by 3y plus the weights of OPT. chosen in the proof of Theorem 3.2. This implies that
((118))) for the constants 8, E (0,
cost(ToPT.) < 1 -cost(T -cost(TofT.)) + cost(T/(1-
By
8

---

By((1 cost(Torr, +
cost(Torr.)
(1-3)y
which gives ALG S 5.828 OPT for the choice of 33 and The details of the proof are similar to the one of Theorem 3.1, and are deferred to section A.3 of the Appendix.
Note on the approximation factors. Observe that Variant 2, where we condition on V has worse approximation factor than Variant 1 where we only condition on V,, > ob. Intuitively someone might expect that with more information the approximation factor will improve. However, it is challenging to argue about this formally. It is also plausible that such monotonicity may not hold as more information might lead the greedy algorithm to make wrong decisions. Instead of making any such claims, we analyze this case directly by showing that our proof approach extends to the full update variant with a generalization of the histogram method to work on trees. Our technique for improving the approximation for the partial updates variant could not be generalized however and thus we only obtain the worse approximation guarantee.
4 Learning from Samples
In this section we show that our algorithm also works when we are only given sample access to the correlated distribution D.
We will mainly focus on the first variant with partial updates Dl The second variant with full Bayesian updates Dl requires full knowledge of the underlying distribution and can only work with sample access if one can learn the full distribution. To see this consider for example an instance where the values are drawn uniformly from [0, 1jé. No matter how many samples one draws, it is impossible to know the conditional distribution DIv vo after opening the first box for fresh samples v, and the Bayesian update not well defined'.
Variant does not face this problem and can be learned from samples if the costs of the boxes are polynomially bounded by n, i.e. if there is constant > 0 such that for all 6 B, c [L, nL. If the weights are unbounded, it is impossible to get a good approximation with few samples. To see this consider the following instance. Box has cost 1/ H - 0, while every other box has cost H for a very large H > O. Now consider a distribution where with probability 1 1 # + 1, the value in the first box is O, and with probability 1/H is +00. In this case, with a small number of samples we never observe any scenario where 0i * O and believe the overall cost is near O. However, the true cost least H 1/H 2 and is determined by how the order of boxes is chosen when the scenario has U1 * O. Without any such samples it is impossible to pick good order.
Therefore, we proceed to analyze Variant I with D Pl in the case when the box costs similar. We show that polynomial, in the number of boxcs, samples suffice to obtain an approximately-opting algorithm, as we formally state in the following theorem. We present the case where all boxes have cost but the case where the costs are polynomially bounded easily follows.
Theorem 4.1. Consider an instance of Pandora's 's Box with opening costs equal to 1. For any given parameters E, 8 > O, using m = poly(n, 1/e, 1og(1/5) samples from DD Algorithm (Variant I) obtains 4.428 e approximation policy against the partially optimal, with probability at least 1 - 8.
To prove the theorem, we first note that variant of Algorithm I takes a surprisingly simple form, which we call a threshold policy. It can be described by a permutation x of visiting the boxes and vector of thresholds that indicate when to stop. The threshold for every box corresponds to the reservation value the first time the box is opened. To analyze the sample complexity of Algorithm 1, we study broader class of algorithms parameterized by a permutation and vector of thresholds given in Algorithm 4.
Our goal now is to show that polynomially many samples from the distribution D suffice to learn good parameters for Algorithm 4. We first show a Lemma that bounds the cost of the algorithm calculated in the empirical D instead of the original D (Lemma 4.1.1), and a Lemma 4. 1.2 that shows how capping the reservation values by n/e can also be done with negligible cost.
Forr a discrete distribution example Section A.5 of the appendix.

---

Algorithm 4: General format of PANDORA'S Box algorithm.
Input: Set of boxes, permutation x, vector of thresholds E R
best < 20
foreach i [n] do
if' best > T; then
Open box ni, see value eq
best + min(best, vi))
else
Accept best
end
Lemma 4.1.1. Let s, > 0 and let D' be the empirical distribution obtained from poly(n, 1/E, log(1/6)) samples from D. Then, with probability 6, it holds that
D ALG(T,T)
- min 4b ED ALG(T, - min Vb
8
BEB
BEB
for any permutation a and any vector of thresholds e E [1
We defer the proof of Lemmas 4.1.1, 4.1.2 and that of Theorem 4.1 to Section A.5 of the Appendix. Lemma 4.1.2. Let be any distribution of values. Let >> and consider a permutation and thresholds T. Moreover, let T' be the thresholds capped to n/e. i.e. setting Ti = min min(To,n/E) for all boxes b. Then,
EnnD AL) +')] (1 E)EED (AGG(T,T))
Note on Continuous Discrete Distributions. The results of Section 4 apply for general distribu- tions (discrete or continuous) and show that the partial updates variant leads to good approximation when run the empirical distribution obtained just with polynomially many samples. In contrast, the full updates variant requires a complete description of the distribution. However, as the approximation factor does not depend on the support size, It can also apply even for continuous distributions with arbitrary large support by taking limit over a very fine discretization
Conclusion
We present summary of results with a comparison previous work Table 1. Our main contribution was to improve the approximation factor for Pandora's Box with correlations given by Chawla al. [2020], while also greatly simplifying their approach. Our algorithm also directly extends the independent case algorithm, giving us a unified way to solve this problem. An interesting open question is to try and improve their results for more complex combinatorial constraints, like selecting & boxes (instead of one) or for selecting a basis of size k, when the boxes are part of matroid.
Approx. Factor
Learnable from Samples
Algorithm of Chawla et al. [2020]
9.22
Yes
Variant (Dv,>a))
4.428 (Thm 3.2)
Yes (Thm 4.1)
Variant 2 (Dvy=u)
5.828 (Thm 3.3)
No (Sec.
Table Summary of results (in bold) and comparison previous work.
Observe also that the more natural Variant seems worse than Variant even though the algorithm has more accurate information through the update of the prior. Intuitively we would expect better factor, however since the algorithm is greedy approximation, and not the optimal, the factor may not necessarily be monotone on the amount of information given. We leave as open problem whether our analysis Variant tight this greedy algorithm cannot perform better under full information.
10

---

References
Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. Math. Oper. Res., 41(3):1022-1033 2016. doi: 10. 10.1287/moo:20115.07777 URL https: //doi.
org/10. 1287 /moor.
Yossi Azar and Iftah Gamzu. Ranking with submodular valuations. In Proceedings of the Twenty- Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 201 pages 1070-1079, 2011. doi: 9711133717811119991179 URL attps://dol: org/10. /00. 1137 / www.9981111997989 81.
Second Annual ACM-SIAM Symposium
Yossi Azar, Iftah Gamzu, and Xiaoxin Yin. Multiple intents re-ranking. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD. USA, May 31 June 2009, pages 669-678, 2009. doi: 10.1145/1536414.553350 URL https://doi. org/ 10. 1145/ 1536414. 1536505.
Nikhil Bansal, Anupam Gupta, and Ravishankar Krishnaswamy. A constant factor approximation algorithm for generalized min-sum set cover. Proceedings of the Twenty-First Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1539-1545, 2010. doi: 091177/1.9781111177777 1137/1-998866119730755 125.
URL https://doi.orr
Curtis Bechtel, Shaddin Dughmi, and Neel Patel. Delegated pandora's box. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder. CO, USA, July 11 15, 2022, pages 1666693. ACM, 2022. doi: 10.1145/ 3490486.3538267. URL wwttt::tss//ootooo org/ /115/33494420 3538267.
Hedyeh Beyhaghi and Linda Cai. Pandora's problem with nonobligatory inspection: Optimal structure and PTAS. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FI., USA, June 20-23, 2023, pages 803-816. ACM, 2023a. doi: 10. 10.1145/3564246.55885 0164246.3585211
URL https://doi. org/ 10/g//0.211 1..11..5... 1145/
Hedyeh Beyhaghi and Linda Cai. Recent developments in pandora's 's box problem: Variants and applications. SIGecom Exch., 20(1), 2023b.
Hedyeh Beyhaghi and Robert Kleinberg. Pandora's 's problem with nonobligatory inspection. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 131-132, ACM, URL htt.h:tt///ooo org/ 1145/3328526 3329626.
2019. doi: 10. 10.1145 141314433222263332000
Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, and Kamesh Munagala. Adaptive probing policies for shortest path routing. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL htttttp::/pproceedingg www.eeeiiinnnnn.nss...... wwtpcccpppppp////eeeee /200/ haath/eddsaad44776002900.0.. www.ee/aaaa777777aaaaaaaaaa Abstract. html.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapmik-chervonenkiis dimension. J. ACM, 36(4):929-965, 1989. doi: 10.1145/77355.76377..
URL. httt::::/doo..rrg//// 1145/763599 76371.
Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. Pandora's box problem with order constraints. In Péter Biró. Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 21st ACM Conference on Economics and Computation. Virtual Event, Hungary, July 13-17, 2020, pages 439 458. ACM, 2020. doi: 10.1145/33914033339901 URL nttps://doi. org/10 10. 1145/134510 3055//3914400 1403. 3399501.
Nicolò Cesa-Bianchi, Tommaso Cesari, Yishay Mansour, and Vianney Perchet. A new theo- retical framework for fast and accurate online decision-making. In Mare Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edi- tors, Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual,
11

---

pages 9152-9166, 2021. URL https://proceedinges 4c4ea5258efffosf wttp://fwwfofffffeeeeeooooe w wew.eeedddinnnn.nni...... cc/pappr/2021/has//
html.
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, and Amit Sahai. Query strategies for priced information (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA. pages 582-591, 2000. doi: 10.1145/335305.33533 URL https://doi. org/ 10. 1145/ 335305. 335382.
Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pandora's box with correlations: Learning and approximation. In Sandy Irani, editor, 61 IEEE Annual Symposium Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November URL
16-19, 2020, pages 1214-1225. IEEE, 2020. doi: 10.1 001109//FCS44700.200..000 https:/ attts://doi.co oewoi.oor//0// 10. 1t..0...199/91 1109 1109/F0CS46000 2020. 00016.
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating pandora's 's box with correlations. CoRR, abs/2108. 12976, 2021. URL https://arxiv org/abs/ 2108. 12976.
Yuxin Chen, S. Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information maximization: When greedy near-optimal? In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 338-363, 2015a. URL http:// proceedings mlr www.s/resssvvv Satpsss//v////enn1/e/ee Chenn/henn1b html.
Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew Bagnell, Siddhartha S. Srinivasa, and Andreas Krause. Submodular surrogates for value of information. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 3511-3518, 2015b. URL http: //ww:///wwwww.w. aaai. org//cs/iideeeeeeeeeeeeereeeeeoe www.ddee.pppppeeee /AAA///AAAI/pppppe/////////e///
Laura Doval. Whether or not to open pandora's box. J. Econ. Theory, 175:127-158, 2018. doi: je1.18.00 .055. URL https: wo. jet 2018. 01.005.
Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Brendan Lucier, and Michael Mitzenmacher. Online pandora's boxes and bandits. In The Thirty-Third AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 2019, pages 1885 1885-1892.0 AAAI Press, 2019. doi: 10. N0.1660/aaii.v3366 333001.33110011 1885. URL https: //tp::://doi.. org/ / 10. 1609 wwa.://aaaa.... ww3.aivvv33.11111 33011885.
Uriel Feige. A threshold of In n for approximating set cover. ACM, 45(4))43(44)4) 652, July 1998. ISSN 0004-5411. doi: 10. 10.1145/285055.2855 285059.
URL:tp:://doo acm. http://:....aaa.....o........... 11tp:///0..14/288555.
Uriel Feige, László Lovász, and Prasad Tetali. Approximating min-sum set cover. In Approximation Algorithms for Combinatorial Optimization, 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21. 2002, Proceedings, pages 94-107, 2002. doi: 10.1007/3-540-4555--4 URL https: orgooo///// 1007 -000733-440-4773--4111
Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40 (4):219-234, 2004.
Hu Fu, Jiawei Li, and Daogao Liu. Pandora box problem with nonobligatory inspection: Hardness and approximation scheme. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 789 802.8002.44 ACM, 2023. doi: 10. 10.1145/35642463355222 URL https: //doi. org 100. /1144///642466..1 3585229.
Evangelia Gergatsouli and Christos Tzamos. Online learning for min sum set cover and pandora's 's box. In Kamalika Chaudhuri, Stefanie Jegelka, Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 7382-7403. PMLR, 2022. URL attpp::/pproceet
mlr, wwwss/vve222 wwtpe//ogggttttteeeeeeeaa html.
12

---

Ashish Goel, Sudipto Guha, and Kamesh Munagala. Asking the right questions: model-driven optimization using probes. Proceedings of the Twenty-Fiine Fifth ACM SIGACT-SIGMEN SIGAOSSSRI Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA, pages 203-212, 2006. doi: 10. 14445/1443311142222355 URL https: //doi. org/10. 10. 1441111 1142380.
Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora's 's problem. In Mikhail Belkin and Samory Kpotufe, editors, Conference Learning Theory, COLT 2021, 15- 19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2248 2288. PMLR, 2021. URL httt::/pproceedingg/ mlr prwss/vessvs vv34/ guo21a. html.
Anupam Gupta and Amit Kumar. Sorting and selection with structured costs. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 416-425, 2001. doi: (..10099SFCS.220).959999 URL https://doi: org/ 10. 1109/SFCSCC 2001 959916.
Anupam Gupta and Viswanath Nagarajan. stochastic probing problem with applications. In Integer Programming and Combinatorial Optimization 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings, pages 205-216, 2013. doi: 10.1007/ 10. 10010000///11 9978-/99932222 3- 142-36694 9_18.
978-3-642-36694- 11 URL https: /doii org/10.
Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing- Proceedings of the Twenty-Sevente Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1731-1747, 2016. doi: 10.1137/1.978161 1974331.ch1222 URL hathhttp////ol org/ 9711/11.978111197333111 ch120.
Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic prob- ing: Submodular and XOS functions. In Proceedings of the Sventy-Eighuti Anmual ACM- SIAM Symposiun on Discrete Algorithms,, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1688-1702. 2017. doi: 10.1137/1.9781111977772... //toi..rg///// 1117/1 978111199111111788888 111.
URL https:
Anupam Gupta, Haotian Jiang. Ziv Scully, and Sahil Singla. The markovian price information. In Integer Programming and Combinatorial Optimization 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings, pages 233-246. 2019. doi: 10.1007/ 978-3-030-17953-31 URL https: / /ttp///oi..oooo org/10 10. 1007 1007/970 0007//978333 9-8-3-7380- 17953- 1_153-3118..
Sungjin Im, Maxim Sviridenko, and Ruben Van Der Zwaan. Preemptive and non-preemptive generalized min sum set cover. Mathematical Programming, 145(1-2)3377-41, 2014
Brian McCall and John McCall. The economics of search. Routledge, 2007.
Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Januury 7-10, 2018, pages 2523-2532, 2018. 10. https://doi org/ 10. 1137/1 11117/11.771111177565000 97811119771111 161.
URL
Martin Skutella and David Williamson. A note on the generalized min-sum set cover problem. Oper. Res. Lett., (9(6) 2011. doi: 10.1016/..or..0111.08 1.0...00000000.........000 URL https://doi. org/ 10. 1016/o.oooooo orl. 2011.08. 08. 002.
orl.
Martin L Weitzman. Optimal Search for the Best Alternative, Econometrica, 47(3):641-654 May 1979.
13

---

A Appendix
A.1 Supplemental Preliminaries
Updating the prior. We include an example showing the process of updating the prior for our two different updating rules. The (correlated) distribution is set of vectors size n, where each is drawn with some probability. When we open a box and see value, some scenarios are not "possible" anymore, i.e. we know they cannot be the ones realized. We illustrate in the following example. Assume there are 3 of these vectors (scenarios).
b1
b2
b3
S
3
4
7
S
6
Sg
7
7
2
Table 2: Example with scenarios and boxes.
The rows in the matrix above are the scenarios, and the columns are the boxes. For example, if scenario S2 the one realized (i.e. drawn from the distribution) then the values inside boxes b,. b2 and by are 6, 4 and 2 respectively. The distribution D is essentially drawing one of the scenarios with some probability.
To see what the conditioning means: assume we open box b and we see the value (and assume for the sake of the example that the reservation value of box is 5).
we condition on 6 = V 01 = 5 meaning that scenario S1 is not possible anymore (because S1 was the one drawn from D, then would have seen a value less than 01 = 5 when opening the box), and is removed from the set S the algorithm considers
Variant 1:
(line 9, Alg 2)
Variant 2: condition on Vi 6, which means that scenarios S1 and S3 both removed (similarly, because if any of these were drawn, we would not have seen 6 upon opening the box)
Differences in the variants. As a result of the different conditioning, the solution for the V > a variant partially adaptive meaning that the next box the algorithm opens, only depends the scenarios that remain. However, for the Vi = o variant the solution is fully adaptive (meaning that the next box opened, depends the exact value seen). This is illustrated in Figures and 4 in the Appendix, where Variant I's solution can be represented by line graph (Figure 2), while Variant 2's solution tree (Figure 4).
A.2 Proofs from Section 3
Open by
Open bj
Open box b
Stop
$1, 82, $3
$2, 83
$3
0
V
8 abs
V Tbs
Figure 2: Algorithm's solution when D Dv for an instance with scenarios S {81, 82, 8a}. and boxes B = {bi, b2, ba, ba). The circles contain the scenarios that have not stopped at each step. Scenario 81 stopped at box by, scenario 82 stopped box by and 83 at box by.
Theorem 3.2. Algorithm a app28iaaproiniation for PANDORA'S BOx against the partially- adaptive optimal, when conditioning on Vo >> db.
14

---

The tighter guarantee proof follows the steps of the proof in section 3.1 for the opening cost, but provides a tighter analysis for the values cost.
Tight proof of Theorem 3.2. Denote by ds the reservation value for scenario when it was covered by ALG and by T the set boxes opened i.e. the steps taken by the algorithm. Then we can write the cost paid by the algorithm as follows
1 ALG
Σ SES
1
Σ PET
Addop.
(8)
S
S
We use the same notation section 3.1 which we repeat here for convenience. Consider any point p in the ALG histogram, and let its corresponding scenario and the time this scenario covered.
Rg set of uncovered scenarios at step
A, set of scenarios that ALG chooses to cover at step
ct: the opening cost such that y/RRe of the scenarios in R, have opening cost less than c*
Ryow {s R4 C. S ) the set of these scenarios
v²: the value of scenarios in Rlow such that b/ R of the scenarios have value less than et
L = {s E Rlow
DPPT S v²) the set of scenarios with value at most e²
Br: set of boxes the optimal uses to cover the scenarios in L of step t
The split described in the definitions above is again shown in Figure 3, and the constants 1 1> 1,,7 > 0 will be determined the end of the proof.
(1 B,
By|Rel v*
c*
Rd
R2
(I Rd
Figure 3: Split of scenarios in R.
Continuing from equation (8) obtain the following.
Re Enen, Cb + ExEr.
OPT
ALG <
AA
Inequality 5
S
[T]
1E
C*
ESEL OPT
[Ael
Ineq. 5 and [T]] 7 Re
S
By
L
OPT.
Agl
Al
E.ET. OPT
Since e" <PPTo/(1- -
3y(1
S
S
TT
IET
OPT.
A
Σ
OPT
+
Since Σ |Ag = |S]
By(1-7)
S
L
PET
Where in the second to last inequality we used the same histogram argument from section 3.1, to bound et by OPT./(1 7).
To bound the values term, observe that if we sorted the optimal values OPT that cover each scenario by decreasing order, and denote ja the index of OPT in this ordering, we add oPT multiplied by
15

---

the length of the interval every time js E [(1 7) This implies that the length of the intervals we sum up for U ranges from Je/7 to js/ ja/((1 - -8)7), therefore the factor for each e is
1 1
Σ
S log
7
1 B
We want to balance the terms 1/(3y(1 - 7)) and 1/7 log 1og(11(11-)))) 3)) which gives that
1
7 log
1-3
Since we balanced the opening cost and value terms, by substituting the expression for y we get that the approximation factor is
Blog
1-3
By 7)
3 log
1-3 -1
Numerically minimizing that ratio for 3 and ensuring that 0 < B,, < we get that the minimum is 4.428 obtained = 0.91 and 0.55.
A.3 Proofs from Section 3.2
Open b2
81, 82,
V = 2
V 5
Stop
Open bj
81
V
V=1
Stop
Stop
Figure 4: Algorithm's solution when conditioning on V v, for an instance with scenarios S {81, $2, s3). and boxes B {b,, b2 The nodes contain the consistent scenarios at each step, and the values V are revealed once open the corresponding box.
Theorem 3.3. Algorithum 1 is a 2 5.828-appprsee a118-ppprxxiiaiionnnee for PANDORA'S ' Box against the partially-adaptive optimal, when conditioning on V1, t.
Continued proof of Theorem 3.3. We now proceed give the bound on the weights of the nodes of TALG- Consider any node u. We have that the weights at this node are equal to
Tv Cb., Rul + E.EA, of
Co Rul + E.EA Ug
[Ag
|A|
where the last inequality holds for all A R, and any b B.
Let et be the opening cost such that 7 R., the scenarios R. have opening cost less than e and by Riw {s E Rr CPP < <; } the set of these scenarios. Similarly denote by ve the value of scenarios in Rio such that Rtow| of the scenarios have value less than o and by
L {s E RP OPT < e these scenarios. This split is shown in Figure 1.
16

---

Note that, e corresponds to the weights of node in TOPT." while the weights of node u at T(1-9) are at least V.
Let Br be the set of boxes that the optimal solution uses to cover the scenarios in L. Let La S L S Rs be the subset of scenarios in that choose the value box in OPT. Using inequality (4) with b E Bg and A = Lt. we obtain LalL I Ral + ESEL, U and by summing up the inequalities for all b E Br. we get
Ry EbEB, Ob + E.Er OPT
|Rlle + E.SEL OPT
Cu 8.7
0u
1.u
[T]]
[T.
where for the second inequality used that the cost for covering the scenarios in L is at most ct by construction, and in the last inequality that [L] = RRl/(B -)) We consider each term above separately, to show that the point p is within the histograms.
Lemma 3.3.1. Let T be tree with a vector of weights ww each node E T, and let T(e) be the tree we get when we substitute the weights of every node with the top p-percentile of all the weights in the subtree of T rooted u. Then
p. c(s)(((p)) S cT).(T).
Proof of Lemma 3. We denote by Tn the subtree rooted u, by W(7) {w w wy for T) the (multi)set of weights in the tree T. Denote, by (T) be the top p percentile of all the weights in T. Finally, define (pl for any tree T as follows:
We create a histogram (x) of the weights WTT) in increasing order.
We calculate the area enclosed within
(T) until [W(T)):
(W(T)
Q (piT)
H())dr
(1-DIW(TT
This is approximately equal to the sum all the values greater than (T) with values
exactly (T) taken fractionally so that exactly fraction of values selected.
We show by induction that for every node u, it holds that p. cos)((T.")) s (plT)
For the base case, for all leaves u, the subtree T, only has one node and the lemma holds as pq s Q (T)
Now, let be any node of the tree, and denote by child(r) the set of the children nodes of
p -..co((T.()) = p (Tx)) w, +
cOst(T!()))
Definition of cost
vEchild(r)
S p 9l (T,) w + Σ
Q(p(T.)
From induction hypothesis
vEchild(r)
[W
|
$ pp. | +
Tr
Since To C T
(TT))
(Q(PTT))
The second-to-last inequality follows since Q is defined as the area of the largest weights of the histogram. Including more weights only increases and keeping the length of the integration range the same (equal to p([W (Tx) - (w,l) can only increase the value Q.
The last inequality follows by noting that if H(x) is the histogram corresponding to the values of T then
(pITT)) - ( [(T.)
( -|wrl Tr =
WW(T.)
W(T-M
[W
(1-0) (a-o) W(T)))
H(x) dx
H(x)dr
17

---

(1 (---l((T))tple
(1 (1-p)l
Hxx)de 2
ol (T. (d
(1-p) W(T.)
(1-))I((T)
(T+(T)))ux)
where the inequality follows since (x) 2 (T,) for a 2 (1-10 (1-p) (T.) by the definition of (Tr) as the top-r quantile of the weights in Tr.
(T,)
Q [T)] 1w
Tr
[xr(T.]
pa (Tr((Tr))))))) (wpl
p w
p((we(T) 100,))
Figure 5: Picture depicting the proof above.
A.4 Lower Bound
To show that our algorithm is almost tight, we observe that the lower bound of Min Sum Set Cover presented in Feige et al. [2004] also applies to PANDORA'S S Box. In MIN SUM SET COVER we are given elements 6; and m sets 8, where each 8 S [n]] We say a set 8j covers an element e, e E 8j. The goal is to select elements in order to minimize the sum of the covering times of all the sets, where covering time of a is the first time an element e; E 8j is chosen. This lower bound is also mentioned in Chawla et al. [2020], but we include it here with more details for the sake of completeness.
In Feige et al. [2004] the authors show that MIN SUM SET COVER cannot be approximated better than even in the special case where every set contains the same number of elements". We restate the theorem below.
Theorem A.1 (Theorem 13 of Feige et al. [2004]). For every > NP-hard to approximate min sum set cover within a ratio of 4
uniform hypergraphs.
Our main observation that MIN SUM SET COVER a special case of PANDORA'S Box. When the boxes all have the same opening cost c and the values inside are ve (0, oo), we are required to find for each scenario; equivalent to covering a scenario. The optimal solution of MIN SUM SET COVER is algorithm that selects elements one by one, and stops whenever all the sets are covered. This exactly the partially adaptive optimal we defined for PANDORA'S S BOx. The thcorem restated above results in the following Corollary.
Corollary A.1.1. For every > 0 it is NP-Hard to approximate Pandora's 's Box against the partially- adaptive within a ratio better than 4 E.
A.5 Proofs from Section 4
We first present an example of a discrete distribution that shows that one needs exponentially many samples in the number of boxes to learn Dy
Discrete Distribution Example Consider a distribution that only takes values 0, H. + for some very large H > 0. The scenario is drawn by choosing random bit b, E (0, 1} for every box
'Eqivalenttly forms uniform hypergraph, where sets are hyperedges, and elements vertices.
18

---

and depending on the realized sequence b single box f(b) E [n] is chosen for an unknown and arbitrary function f. The value box is then chosen to H + b, unless i the box f(b) in which case it is 0. In this case learning the probability DV=p would require learning the unknown function on all inputs which are exponentially many. In particular, we only take << 2n samples, for any order of choosing boxes after R log steps, none of the samples in our collection will match the observed sequence of bits, therefore will not be possible to compute a posterior distribution.
We continue by giving the omitted proofs.
Lemma 4.1.1. Let e, 5 > 0 and let D' be the empirical distribution obtained from poly(n, 1/e, log(1/6) samples from D. Then, with probability - 6, it holds that
Bn ALG(T,
min 2/b bEB
ED ALG(TT min Ub
E
BEB
for any permutation π and any vector of thresholds E [0. 2]"
Proof of Lemma 1.1.I We first argue that we can accurately estimate the cost for any vector of thresholds when the order of visiting boxes is fixed.
Consider any fixed permutation
T1, T22 ... Ty be any permutation of the boxes, we relabel the boxes without loss of generality so that TT is box i.
Denote by V = minggr Uj, and observe that VÚ is a random variable that depends on the distribution D. Then we can write the expected cost of the algorithm as the expected sum of the opening cost and the chosen value: Ep [ALG] = ED [ALG,] + ED [ALG,]- We have that:
1-1
Ep ALG.
Σ i=1
Prp freach 1 = Pro
Σ
A > Ts+2)
j=1
Moreover, we denote by V² = Ni=1 V2 > T++1) and we have
ED ALG. - Vill = Σ Ep (V/ - Vn)) 1 at o)
Ep (V, - Vn2) -D(V ^
Ep Ti+1 Pr+1Pr,-U00.T41 r <<v;= V.l -lv's a (ii (Mi
V V=n r+ v. (( TH
Tit PrD
In order to show our result, we use from Blumer et al. [1989] that for a class with VC dimension d < oo that we can learn it with error at most E with probability 8 using m poly(1/e, d, log (1/8)) samples.
Consider the class Fr, = | This defines an axis parallel rectangle in Rí, therefore its VC-dimension is 2i. Using the observation above we have that using poly(1/e,n, n, log (1/8)) samples, with probability at least 8, holds
Pro [F)( Pro [Fr(..))
SE
for all T E R".
Similarly, the class (V = No (i, > m (r+ Vv S v, - T441) has VC-dimension
((n) since it is an intersection of most (sparse) halfspaces. Therefore, the same argument as before applics and for m = poly(1/E, n, log (1/8)) samples, we get
Prp. (C
Pr ProDrru0o..mm) (c((V,)) Se
19

---

for all T E IR", with probability at least 1 1-dd 8.
Putting it all together, the enror still be unbounded if the thresholds too large. However, since we assume that T; S n/e for all i E [n], poly(n, 1/e, log(1/)) samples suffice to get error overall, by setting <-
While we obtain the result for fixed permutation, we can directly obtain the result for all n! permutations through a union bound. Setting n! only introduces additional factor of log(n!) = n log in the overall sample complexity.
Lemma 4.1.2. Let be any distribution of values. Let & > and consider a permutation n and thresholds T. Moreover, let T' be the thresholds capped to n/e, i.e. setting To = min [Tb, n/e) for all boxes Then,
EvnD [TL (1++))EUND [ALG(TT, r)].
Proof of Lemma 4. 1.2. We compare the expected cost of ALG with the original thresholds and the transformed one ALG' with the capped thresholds. For any value vector v D, either (1) the algorithms stopped at the same point having the same opening cost and value, or (2) ALG stopped earlier at threshold 7 > n/E, while ALG' continued. In the latter case, the value that ALG gets is greater than n/e, while the value r' that ALG' gets is smaller, r' < v. For such a scenario, the opening cost of ALG, and the opening cost c' of ALG' satisfy c' S + Thus, the total cost is + v' & + - n S (1 + (c + v) Overall, we get that
ED [ALG'] I ED [ALG] (1 (1+
Theorem 4.1. Consider an instance of Pandora's 's Box with opening costs equal to 1. For any given parameters E, 5 >> using m poly(n, 1/e, log(1/8) samples from D, Algorithm (Variant I) obtains 4. 4.428 + approximation policy against the anriplly-adaptive optimal, with probability at least 1 8.
Proof of Theorem 4.1. With poly(n, e, log(1/0) samples from D, we obtain an empirical distribu- tion D.
From Lemma 4.1.1, we have that with probability least 1 de/ log(L/)), the following holds
E E ALG(T, 7)
min Ub
E
ALG((T
min 8b BEB
S
(10)
be
for any permutation π and any vector of thresholds v E the cost of a threshold policy accurately.
[0, n ".
This gives us that we can estimate
To compare with the set of all partially adaptive policies that may not take the form of threshold policy, we consider the set scenario aware policies (SA). These are policies SA(T) parameterized by a permutation æ of boxes and are forced to visit the boxes in that order. However, they are aware of all values in the boxes in advance and know precisely when to stop. These are unrealistic policies introduced in Chawla et al. [2020] which serve as upper bound the set of all partially adaptive policies.
As shown in Chawla et al. [2020] (Lemma 3.3), scenario-aware policies are also learnable from samples. With probability at least - /z/ log(1/6) it holds that for any permutation π
E
G D SA(T) min
EDND
(A((T) min 2b beB
S
(11)
heB
The a-approximation guarantees (with x 4.428) of Algorithm hold even against scenario aware policies as there is no restriction on how the partially-adaptive policy may choose stop. for the empirical distribution, we can compute permutation á and thresholds 7 such that:
ED [ALG((it +)] & a min E. [s)()))
Clipping the thresholds to obtain 3' min n//e), and letting A E,-D [minng mi] Ey-D [minges vy), we have that:
ED [ALG +')] ED ALG +'] A +e
20

---

< (1 (1+ ( +)] + 4
(1+ min B, [SA(T) + "
(1+ minEp [TA(T)) + 0(4 +
By Markov's inequality, we have that Pr [ [minses V/} S (1 + E [minGeB e/2.
ua]]
2 I+e
Thus, repeating the sampling process 1/5) times and picking the empirical distribution with
minimum E.D.D [minses vib satisfies A EEE,, iininee 2b) with probability least 5 and simultaneously satisfies equations (10) and (11).
This shows that ED [ALG +]] S (1 + O()))a min, ED [SA(T)) which completes the proof by rescaling by a constant.
21


Reviews:
[{"review_id": "DpyQWoJD1b", "reviewer": "Reviewer_6o9F", "summary": "This paper studies the Pandora’s box problem with correlation. The problem is as follows: a decision maker is presented with $n$ boxes to explore, and each box $b_i$ is associated with a hidden value $v_i$ and a known cost $c_i$ that needs to be paid to reveal the value. The values in the boxes are drawn from a known correlated distribution. The decision maker opens the box one after the other in an arbitrary order that may depend on the realized values uncovered and, when it decides to stop, pays the total cost of exploration (the sum of the costs of the boxes it opened) plus the smallest uncovered value. The goal of the problem is to design a strategy that minimizes the cost paid by the agent. \n\nThe authors present two algorithms and a learnability result. A first algorithm yields a constant factor approximation (4.428) to the best non-adaptive strategy when the only information the decision maker uses to update its strategy is whether the exploration stopped or not, according to some stopping rule. The second algorithm yields another constant factor approximation (5.828) to the same benchmark in a full update model (the decision maker updates its prior distribution according to the exact realized values). Both approximations improve on the state of the art.", "questions": "1. Why consider the richer update model? It gives a worse approximation guarantee. The decision-maker should ignore it\n\n2. Is there any lower bound on the approximation factor? How far are the proposed results from the optimal poly-time algorithm?\n\n3. Please explain why the second to last display of page 3 implies the last one. Why is it safe to make the sum_s \\in A P_D(s) term appear at the numerator without affecting the maximization problem?\n\n-----------------------\n\nRaised my score after rebuttal", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The Pandora’s Box problem is an exciting and challenging model for exploration under uncertainty that has received much attention in recent years (see, e.g., the recent papers at STOC and EC). The correlated version of the problem is interesting and overcomes the unnatural assumption of independent valuations made in the original model by Weitzman. \n\nStrengths:\n- The algorithms proposed by the authors are uncomplicated and enjoy the desirable property of extending Weitzman’s notion of reservation value. This fills a gap in understanding the correlated version of the problem, as previous works used different techniques, achieving worse results.\n- The learnability result is interesting and useful in overcoming the natural limitation of not knowing the underlying distribution. The result complements its analogous for the independent scenario (COLT 21, ‘‘Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and Pandora’s problem’’).", "weaknesses": "- It is unnatural to obtain weaker results (against the same benchmark) when the decision-maker employs a richer update rule. The main weakness of the paper is not providing a convincing explanation of this fact. Moreover, it is impossible to understand from the main body what is the technicality that allows the improved approximation factor. \n- Removing the abstract from the manuscript to fit into the 9 pages limit is a borderline practice. \n\n\nMinor comments:\n- Please be consistent in the use of \\citet and \\citep. Use \\citet when the article cited is part of the sentence (e.g., in the abstract), and \\citep otherwise. \n- Please explain why the second to last display of page 3 implies the last one. Why is it safe to make the sum_s \\in A P_D(s) term appear at the numerator without affecting the maximization problem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments, we are going to fix the citation inconsistencies, and add more intuition on the difference between the two algorithms versions. Also apologies for the abstract, the author who submitted the paper was careless with copying everything to the NeurIPS template. Space was not an issue, since we could have moved more proofs to the appendix. To answer the reviewer’s questions:\n\n1. When we initially started considering the richer update model (Variant 2), we were not sure whether it would give a better approximation or not. It is however a more natural variant: we don’t keep scenarios that are clearly not possible anymore (which variant 1 does). Intuitively we would expect a better factor. However since the algorithm is a greedy approximation, we soon realized that the factor may not necessarily be monotone on the amount of information given. The richer update model led us to a generalization of the histogram proof on trees, which might be of independent interest, and therefore we decided to include it as well. Additionally our analysis is not necessarily tight, and a better factor might be possible for the richer updates variant (even though even the worse approximation for the richer update variant is close to the lower bound --> see below)\n\n2. The best possible for a polynomial-time algorithm is a $4$-approximation, and this is a result from the Min Sum Set cover problem [FLT04], which means our algorithm is almost tight. We have already included a discussion on the lower bound in the Appendix (supplementary material, section A.3). We will however mention it in the main text too, for completeness.\n\n3. The maximization problem is not affected because we need the max over subsets $A\\subseteq S$ such that the expression is equal to $0$; i.e. the expression is the following:  \n{ Find $\\sigma $ that is the solution to $\\max_{A\\subseteq S} { f(A,\\sigma) } = 0$} where $f(A,\\sigma)= \\sum_{s\\in A} Pr_D[s] (\\sigma_b-v_b^s)-c_b$  \nTherefore, by dividing with something positive (i.e. $\\sum_{s \\in A} Pr_{\\mathcal{D}}[s]$), we still need the numerator to be $0$ for this to be satisfied, which is not affected by dividing by any positive number. Note also that $S$ is not empty (since if it was, the algorithm would have stopped), so this is a well defined division.\n"}, {"review_id": "Sd4tFQl0XF", "reviewer": "Reviewer_ktwT", "summary": "This paper studies the problem of Pandora's boxes with the values of the boxes correlated. The authors extend the classical algorithm Weitzman’s Rule for independent values of boxes to the correlated case, and propose new algorithms with better approximation than previous works that are learnable from samples. ", "questions": "Justify the major motivation of the correlated case for its practical or theoretical importance. \n", "limitations": "As written in Weakness", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Novelty: The major novelty of this paper is to extend the Weitzman’s Rule algorithm to the cases of correlated boxes' values, and simplify the problems greatly. Though none of the correlated case or the algorithm are new, this extension does have its unique value by making simplicity and improving the approximation guarantee. \n\nQuality: This paper's result is sound and the analysis looks good. The results are strong as well. ", "weaknesses": "Clarity: This paper is not very clear in some places. For instance, it does not give the definition of \\epsilon-approximation before first using it, which may make some readers hard to understand this paper. The proofs are also too simplified without enough intermediate steps to make readers easy to follow. \n\nSignificance. This is a minor weakness, where the authors need to better justify why the correlated case is important. What is the major motivation in practice, or is is a theoretical fundamental problem that can solve a series of dependent problems?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments, and we will clarify and define the notions that aren’t currently clear. To answer the question: on the theoretical side, removing the strong assumption of independence generalizes the problem, and gave rise to new techniques that may be used to solve similar problems with correlation (e.g. prophet inequalities [1]).\nOn the practical side, in real life  independence is an assumption that usually does not hold. For example:\n1. *Housing market*: we are looking to buy a house and we have a list of potential properties in mind, and have to decide on some order to visit them, learn more information and finally buy one. The houses are the boxes, we have to spend time/gas driving to each property (i.e. pay the opening cost) in order to learn the actual price (i.e. the house might need more repairs, therefore the price is not as low as we thought). The houses’ prices however are not independent: \n    1. Location affects nearby houses the same way (e.g. if a neighborhood is bad, all houses near there will be affected the same way)\n    2. Having the same property manager (e.g. a potentially dishonest property manager hides the issues with the house, meaning that houses with the same property manager are potentially affected the same way)\n\n2. *Acquiring an item*: we want to buy an item that many different shops sell. We have a prior belief for every shop (e.g. if it’s generally expensive or not) but we have to spend time inquiring about the price. However, some shops will use the same supplier, meaning that if the supplier is low on some part used for the item, these shops will sell it at higher price, compared to the ones using different suppliers.\n\n3. *Job Search*: we are a company interviewing candidates for a job position. Each candidate is a box, we have some prior for each (e.g. their cv) but until we spend time to interview them (i.e pay the opening cost) we don’t know their exact value (i.e. how close they match the position). Our goal is to select the best candidate without interviewing too many. Correlations arise since some of them have common qualifications in their cv that affect their value (e.g. they have graduated the same university, which happens to offer a program that matches very well the position)\n\nThese examples are the motivation that started this area of research in economics (consumer search, housing market, job search), where optimal search problems (like Pandora’s Box) arise [see [2] for more details].\n\n[1] Prophet Inequalities with Linear Correlations and Augmentations [Immorlica, Singla, Waggoner] EC 20\n\n[2] The Economics of Search [Brian McCall, John McCall], Routledge, 2007]\n"}, {"review_id": "UxoONnxAW5", "reviewer": "Reviewer_coaw", "summary": "This paper provides an exploration of Pandora's box problem with correlations. The authors innovatively modify the computation of reservation values within Weitzman's algorithm. They further solidify their contribution by proving the approximation ratio of the proposed algorithms under various distribution updating schemes.", "questions": "I would greatly appreciate further explanations to deepen my comprehension. Specifically, it remains unclear what it means to update the value distribution $\\mathcal{D}$ conditional on $V_b > \\sigma_b$ and $V_b = \\sigma_b$. Why even we could have both different updating? I am also uncertain how this conditional updating of $\\mathcal{D}$ gives rise to Algorithms 2 and 3.\n\nProviding additional insights into these elements would undoubtedly clarify the understanding for readers like myself and further enhance the value of your work.", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper provides an exploration of Pandora's box problem with correlations. The authors innovatively modify the computation of reservation values within Weitzman's algorithm. They further solidify their contribution by proving the approximation ratio of the proposed algorithms under various distribution updating schemes. The algorithms presented are intriguing and succinct, which I find very appealing. \nThe whole paper also reads very well except skipping of some technical parts. ", "weaknesses": "However, I admit that some aspects of the algorithms and their details elude my understanding. I would greatly appreciate further explanations to deepen my comprehension. Specifically, it remains unclear what it means to update the value distribution $\\mathcal{D}$ conditional on $V_b > \\sigma_b$ and $V_b = \\sigma_b$. Why even we could have both different updating? I am also uncertain how this conditional updating of $\\mathcal{D}$ gives rise to Algorithms 2 and 3.\n\nProviding additional insights into these elements would undoubtedly clarify the understanding for readers like myself and further enhance the value of your work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments, we can add the appropriate clarifications in the final version. We answer the question below.\n\n The (correlated) distribution is a set of vectors of size $n$ (described end of page 3), where each is drawn with some probability. When we open a box and see a value, some scenarios are not “possible” anymore, i.e. we know they cannot be the ones realized. We illustrate in the following example. Assume there are 3 of these vectors (scenarios).\n\n|    | B1 | B2 | B3 |\n|:--:|:--:|:--:|----|\n| **S1** |  3 |  4 | 7  |\n| **S2** |  6 |  4 | 2  |\n| **S3** | 7  | 7  | 2  |\n\nThe rows in the matrix above are the scenarios, and the columns are the boxes. For example, if scenario S2 is the one realized (i.e. drawn from the distribution) then the values inside boxes B1,B2 and B3 are 6, 4 and 2 respectively. The distribution $D$ is essentially drawing one of the scenarios with some probability.\n\nTo see what the conditioning means: assume we open box 1 and we see the value 6 (and assume for the sake of the example that the reservation value of box 1 is $\\sigma_1 = 5$).\n\n* Variant 1: we condition on $6=V_b> \\sigma_1 = 5$, meaning that scenario S1 is not possible anymore (because if S1 was the one drawn from D, then we would have seen a value less than $\\sigma_1 = 5$ when opening the box), and is removed from the set S the algorithm considers (line 9, Alg 2)\n\n* Variant 2: we condition on $V_b = 6$, which means that scenarios 1 and 3 are both removed (similarly, because if any of these were drawn, we would not have seen 6 upon opening the box)\n\nThe second way these variants differ, is that due to this conditioning, the solution for the $V_b> s$ variant is “partially adaptive” meaning that the next box the algorithm opens, *only* depends on the *scenarios that remain*. However, for the $V_b=v$ variant the solution is “fully adaptive” (meaning that the next box opened, *depends on the exact value seen*). This is illustrated in Figures 2 and 4 of the appendix (supplementary material), where variant’s 1 solution can be represented by a line graph (Fig 2), while Variant’s 2 solution is a tree (Fig 4).\n"}, {"review_id": "TXPMxm4L0m", "reviewer": "Reviewer_1WDf", "summary": "This paper considers the Pandora's box problem with correlated values. In each step, the algorithm chooses an unopened box and observes its value generated from the known distribution. The goal is minimizing the sum of the minimum value among the opened boxes and the total opening cost. The distribution is given as a uniform distribution over finite possible scenarios. This paper shows simple greedy algorithms based on reservation values achieve improved approximation ratios. The existing algorithms for this problem are based on more complicated techniques. This paper also proposes an algorithm that uses samples from the distribution instead of its explicit representation.\n", "questions": "What is the formal treatment of the opening cost $c_b$ in the analysis?\n", "limitations": "Yes, it is adequate.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The Pandora's box problem is an interesting problem that has been extensively studied in TCS and algorithmic game theory. Its correlated version is regarded as a noteworthy technical challenge. This paper improves and simplifies the existing results. This is a significant theoretical advancement.\n", "weaknesses": "I have a concern regarding the soundness of the proofs. The proofs sometimes appear informal, making it challenging to verify their validity. For example, the description of the algorithm is not always clear. In Algorithm 2, the opening cost of the already opened boxes are set to 0 (line 8). Then their reservation value might become the minimum, which is selected in line 4-5. The algorithmic behavior in this case is not clearly specified. This issue is relevant to the analysis around the inequalities (4) and (5). The opening cost $c_b$ appears in these inequalities, but it is not constant during the execution of the algorithm.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments, and we will clarify that a box can be opened many times during the run of the algorithm. \n\n* Regarding the algorithm’s behavior: a box can be opened many times, therefore after we open it once (and make the cost 0) it could be re-opened at a later stage of the algorithm. This is similar to what happens in the independent case algorithm (Weit79) where we could stop at any point and “go back” to pick a value seen in a box opened before. This is the same behavior: we can go back and select a box previously opened with no extra cost. \n\n* The fact that the opening cost becomes 0 is not directly used in the analysis (i.e. inequalities (4) and (5) ). This means that our analysis gives an upper bound on the cost of the algorithm, *even if* the algorithm *never* changes the cost of an opened box to 0. That is the reason in inequalities (4) and (5) the cost appears unchanged but the analysis still works for the algorithm since we just want an upper bound (and if we changed the cost to 0 this would only lower the cost of the algorithm).\n\nTherefore, our analysis shows that we can bound the algorithm’s cost even without setting costs to 0. However, setting them to 0 this makes it easier to see how it directly generalizes the independent case (since it mimics the “going back to pick a box opened earlier” behavior).\n"}, {"review_id": "EhNhO93tCT", "reviewer": "Reviewer_PoqM", "summary": "This paper considers Pandora’s Box problem with correlated values. Previous work gives a 9.22 approximation for this problem. This problem considers two variants, depending on whether the algorithm updates based on exact values or on the event that the value is large, with approximation factors of 5.828 and 4.428, respectively. The latter approach can be extended to the case of unknown distributions that the algorithm has sample access to. An interesting feature of the main algorithmic blueprint is that it is a direct extension of Weitzman’s original rule for this problem (in the independent value case).", "questions": "Why are both variants considered? It seems like variant 1 is better under every aspect considered (approximation ratio, simpler proof, learnable).", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper makes a major contribution to optimal stopping theory, by giving a clean answer to a very natural and important problem.", "weaknesses": "The technical writing can definitely be improved. For example, it is very difficult to follow the histogram argument in the proof of Theorem 3.2 without figures. \n\n(\nSome typos/writing notes since there is nowhere else to put them: \n- Typo in line 41: “are are”\n- I believe the notation (x)^+ is not defined anywhere.\n- It’d be nice to do some of the math slower. E.g., in 154, it’d be useful for the reader to write ALG first as an expectation, and then slowly open it up and use the uniform fact, etc\n- Typo in line 274: the \\geq sign should not be there\n)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and typos caught; we will add a figure in the final version showing how the histogram method works, to better illustrate the proof. \n\nTo answer the question: when we initially started considering variant 2, we were not sure whether it would give a better approximation or not. It is however a more natural variant: we don’t keep scenarios that are clearly not possible anymore (which variant 1 does). \n\nAs other reviewers pointed out, intuitively we would expect a better factor. However since the algorithm is a greedy approximation, we soon realized that the factor may not necessarily be monotone on the amount of information given. Variant 2, led us to a generalization of the histogram proof on trees, which might be of independent interest, and therefore we decided to include it as well. Additionally our analysis is not necessarily tight, and a better factor might still be possible.\n"}]

Author rebuttal:

Meta-review: This paper considers a well-motivated extension of the Pandora's box problem that allows for correlations. The reviewers agree that the setting considered is natural, that the results are strong, and that the techniques are interesting. I recommend that this paper be accepted.

Multiple reviewers found that the clarity of certain parts of the paper could be improved, please address these comments in the camera-ready version of the paper.
Decision: Accept (poster)