Weitzman's Rule for Pandora's Box with Correlations

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).

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. ( Some typos/writing notes since there is nowhere else to put them: - Typo in line 41: “are are” - I believe the notation (x)^+ is not defined anywhere. - 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 - Typo in line 274: the \geq sign should not be there )

Questions

Why are both variants considered? It seems like variant 1 is better under every aspect considered (approximation ratio, simpler proof, learnable).

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

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.

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.

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.

Questions

What is the formal treatment of the opening cost $c_b$ in the analysis?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Yes, it is adequate.

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.

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. The 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. Providing additional insights into these elements would undoubtedly clarify the understanding for readers like myself and further enhance the value of your work.

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. Providing additional insights into these elements would undoubtedly clarify the understanding for readers like myself and further enhance the value of your work.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

NA

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.

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. Quality: 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. Significance. 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?

Questions

Justify the major motivation of the correlated case for its practical or theoretical importance.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

As written in Weakness

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. The 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.

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. Strengths: - 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. - 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. - Removing the abstract from the manuscript to fit into the 9 pages limit is a borderline practice. Minor comments: - 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. - 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?

Questions

1. Why consider the richer update model? It gives a worse approximation guarantee. The decision-maker should ignore it 2. Is there any lower bound on the approximation factor? How far are the proposed results from the optimal poly-time algorithm? 3. 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? ----------------------- Raised my score after rebuttal

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above

Comment

Thank you for addressing my concerns in your response. The clarification provided regarding the opening cost is appreciated. To enhance the clarity of this aspect, I recommend considering a revision of the pseudocode and the proofs. Given that there is room for improvement in the writing, my score is still on the borderline.