PaperlayerView exact revision on arXiv

Source-linked AI summary

Batched Pandora's Box

Shaddin Dughmi, Yusuf Hakan Kalayci, Vasilis Livanos, Aditya Prasad

arXiv:2609.04059v1cs.DScs.GT

TL;DR

The paper studies Pandora’s Box when stochastic inspections must be launched in capacity-constrained batches with setup costs and simultaneous feedback. It analyzes reusable and non-reusable boxes, proves strong hardness for ordinary approximation, and obtains constant bi-criteria guarantees through LP relaxation and rounding.

  • Problem

    The paper asks how Pandora’s Box changes when costly stochastic inspections are parallelized into capacity-constrained batches with setup costs and delayed, simultaneous feedback.

  • Method

    The authors formulate reusable and non-reusable models, analyze their structure and hardness, and round linear-programming relaxations using randomized or Pipage-style techniques.

  • Results

    Ordinary approximation is NP-hard in key settings, while discounted-cost bi-criteria algorithms achieve constant-factor guarantees for both reusable and non-reusable models.

  • Takeaways & Limitations

    Batching changes which classical index and simple batching strategies remain valid, but discounted-cost benchmarks recover useful algorithmic guarantees.

  • Takeaways & Limitations

    Sort-and-merge policies over consecutive boxes in reservation-value order can fail to obtain positive utility, even when a non-consecutive batch is profitable.

Abstract

from arXiv · show

Motivated by numerous parallelizable stochastic search problems, most notable and timely among them being LLM inference-time scaling, we propose and study batched versions of the Pandora's Box problem of Weitzman. In particular, boxes are opened in capacity-constrained batches, each batch has a setup cost, and all rewards in a batch are revealed together. We consider two different variants, motivated by different application environments: one where boxes are reusable (i.e., can provide multiple i.i.d.~samples) and another where they are not. For both variants we rule out most ``simple'' natural heuristics, and also formally prove NP-hardness of approximation in the traditional sense. We then relax the problem to allow bi-criteria approximations, with respect to both rewards and setup costs, where we exhibit constant approximation algorithms for both the reusable and non-reusable settings. This is obtained through a linear-programming relaxation of Pandora's Box problem, followed by randomized or Pipage rounding.

1 Introduction

The paper formulates batched Pandora’s Box for parallel stochastic search, with capacity limits, setup costs, and simultaneous feedback. It characterizes structural and computational barriers, then develops discounted-cost constant approximations for reusable and non-reusable variants.

  • 1 Introduction: Batched Pandora’s Box groups costly inspections into capacity-limited batches whose rewards are revealed simultaneously, with a setup cost for each nonempty batch.The policy chooses each batch before observing its outcomes and may stop or continue after revelation.
  • 1 Introduction: The model distinguishes non-reusable boxes, which are consumed, from reusable boxes, which provide fresh i.i.d. samples across repeated openings.This distinction represents one-time opportunities versus repeatable experiments such as additional inference trials.
  • 1.1 Our Contributions: Adaptive non-reusable policies can outperform fixed menus, but every adaptive policy has a fixed-menu counterpart worth at least half as much; reusable policies recover a maximum-reservation-batch index structure.In the reusable case, an optimal policy repeatedly opens a maximum-reservation batch until its realized value exceeds the threshold.
  • 1.1 Our Contributions: Ordinary approximation is obstructed by NP-hardness, including a sign gap that makes distinguishing zero from positive optimum NP-hard when capacity is variable or unlimited.The reductions encode Subset Product through two-point reward distributions and calibrated costs.
  • 1.1 Our Contributions: A discounted-cost bicriteria benchmark enables constant-factor algorithms based on linear-programming relaxations followed by rounding.The non-reusable algorithm rounds fractional batch counts and partitions boxes into legal batches using dependent rounding; reusable instances use a feasibility LP and independent slot rounding.
  • 1.2 Related Work: Unlike delayed-feedback bandit work, this model studies a single-instance search objective where batching changes the economics and commitment structure of costly inspection.The related-work distinction is between statistical objectives such as regret or sample complexity and maximizing observed reward net of costs.

2 Preliminaries

The preliminaries define classical and batched Pandora’s Box, including non-reusable and reusable feasibility, reward and cost objectives, and finite-support representations. They also record the zero-setup-cost connection to the classical problem.

  • 2 Preliminaries: Classical Pandora’s Box opens independent boxes sequentially, paying individual costs and using reservation values to determine inspection order and stopping.Weitzman’s rule opens boxes in decreasing reservation-value order and stops when the best observed reward reaches the largest remaining reservation value.
  • 2 Preliminaries: The batched model limits each batch to k boxes, adds setup cost T, reveals all batch rewards together, and supports both consumed and reusable boxes.Non-reusable batches partition or consume boxes, whereas reusable batches are multisets of box types producing fresh samples.
  • 2 Preliminaries: In the reusable model, a batch is a nonempty multiplicity vector with at most k samples, and opening cost combines setup cost with positive per-sample costs.When k is unlimited, positive sampling costs exclude arbitrarily many zero-cost copies from a batch.
  • 2 Preliminaries: Policy performance is expected maximum observed reward minus expected total cost, while discounted-cost value replaces costs by λ times their amount.λ = 1 gives the original-cost objective; λ < 1 evaluates policies after discounting costs.
  • 2 Preliminaries: When setup cost is zero, batched models recover the classical singleton value because batches can be simulated through sequential openings while ignoring intermediate observations.For reusable instances with positive item costs, the same equality holds for every capacity k.
  • 2 Preliminaries: Approximation statements use finite-support reward distributions represented as value-probability pairs, while hardness reductions use two-point distributions.The nonzero support excludes the zero atom when constructing the relaxation.

3 Structural Observations

Batching breaks simple reservation-value ordering in the non-reusable setting, while adaptivity offers a bounded advantage over fixed menus. In the reusable setting, the problem regains an optimal index policy that repeatedly opens one highest-reservation batch.

  • 3.1 Failure of Simple Batching Rules: Separated boxes can form the only positive-utility batch, so consecutive batching in reservation-value order can fail completely.A deterministic decoy can lie between the useful boxes, making every feasible consecutive batch negative while the separated pair is positive.
  • 3.2 Non-Reusable Model: Adaptivity Gap: Adaptive non-reusable policies can outperform fixed menus because later batches may depend on earlier observations.In the supplied instance, adaptivity selects different groupings after observing box 2, whereas a fixed menu must commit beforehand.
  • 3.2 Non-Reusable Model: Adaptivity Gap: The adaptive non-reusable value is at most twice the best fixed-menu value.The proof samples a root-to-leaf path of the adaptive decision tree and converts it into a fixed path using a stochastic-probing-style argument.
  • 3.3 Reusable boxes: one repeated batch: Reusable boxes eliminate the adaptivity gap: an optimal policy repeatedly opens a feasible batch with the highest reservation value until its reward exceeds that threshold.This recovers a reusable analogue of Weitzman’s index rule under bounded values and positive opening costs.
  • 3.3 Reusable boxes: one repeated batch: Repeatedly opening a reusable batch until success attains its reservation value.The value calculation uses the success probability and the reservation-value identity E[(Xa − σ(a))+] = K(a).

4 Hardness Results

The paper proves strong computational hardness for batched Pandora’s Box: exact optimization is NP-hard even at fixed capacity, while sign-gap hardness rules out ordinary approximation when capacity is variable or unbounded.

  • Non-reusable boxes: Exact optimization is NP-hard for every fixed finite batch capacity k ≥3, even with positive setup costs and shared two-point rewards.The reduction is from Numerical 3-Dimensional Matching and uses common-prize boxes supported on {0, M}.
  • Non-reusable boxes: Finding a profitable batch is encoded as a product-matching problem: labels multiply to a target exactly when the corresponding items form a feasible tuple.The gadget assigns distinct class primes and size factors, so unique factorization enforces both class membership and the target-size condition.
  • Non-reusable boxes: The optimal value increases strictly with the maximum number of disjoint target tuples, allowing exact optimization to distinguish perfect numerical matchings.Target tuples share the same success probability and cost, while non-target batches are made unprofitable.
  • Sign-gap hardness: With variable or unbounded capacity, distinguishing zero value from positive value is NP-hard for non-reusable instances, even with common-prize two-point boxes and T > 0.If a target subset exists, one opening has positive value; otherwise every nonempty batch has negative one-shot surplus.
  • Reusable boxes: The same sign-gap hardness holds for reusable boxes, using private primes to prevent repeated use of one source item.The private-prime construction forces exactly one inclusion or exclusion choice for each source item while preserving the target-product condition.

5 Bi-criteria Approximation Results

The paper obtains constant-factor bicriteria guarantees by relaxing batched Pandora’s Box to linear programs and rounding fractional opening and batch-count decisions. The non-reusable and reusable variants use different structural reductions, but both achieve polynomial-time guarantees under discounted costs.

  • Non-reusable boxes: For non-reusable boxes, the LP tracks opening probabilities, expected batch count, and fractional winner assignments while upper-bounding adaptive-policy reward.Fractional z is essential because adaptive policies may use different integer batch counts across histories, producing a fractional expectation.
  • Non-reusable boxes: Independent sampling captures a (1−1/e)-fraction of the reward envelope, while pipage rounding enforces the batch-capacity constraint without reducing monotone submodular reward.The batch count is rounded to a neighboring integer, and the selected boxes can then be partitioned into legal batches.
  • Non-reusable boxes: For every finite-support non-reusable instance, a randomized polynomial-time algorithm solves the LP and rounds its solution to obtain the stated discounted-cost bicriteria guarantee.The algorithm returns the empty policy when the LP optimum is non-positive and otherwise applies the rounding procedure to an optimal solution.
  • Reusable boxes: For reusable boxes, an optimal original-cost policy repeats one maximum-reservation batch, reducing the problem to finding a certifying batch.A threshold certificate supports repeated opening until a realization exceeds the threshold, and certification is monotone in the threshold.
  • Reusable boxes: Binary search and conditional-expectation rounding yield a finite-support reusable algorithm with a (1, αR) discounted-cost bicriteria guarantee.The search returns a certified threshold within ε of the optimum, and the rounded batch is repeatedly opened until it exceeds that threshold.

6 Proofs of Hardness Results

The hardness proofs use product-separation gadgets whose profitable batches correspond exactly to solutions of NP-hard product or matching instances. Rational logarithm approximations preserve the gap and keep the reductions polynomially representable.

  • Product separation: The analytic separation function is minimized at z = 1 and is inverse-polynomially bounded away from zero at distinct integer ratios.For integer w ≠ Q, the proof establishes D(w/Q) ≥ 1/(16Q^2).
  • Representation: Rational approximations to logarithms preserve target and non-target surplus gaps while ensuring polynomial encoding length and positive setup costs.The approximation error is bounded by H/100, and the constructed instance remains rational and polynomial-size.
  • Fixed-capacity non-reusable hardness: The reduction encodes item labels with primes and powers of two, making target batches exactly feasible tuples satisfying the source matching constraints.Unique factorization enforces one item from each class and the required size sum; dummy classes extend the construction to k > 3.
  • Fixed-capacity non-reusable hardness: Target batches share cost, failure probability q = 1/Q, and positive surplus, whereas non-target batches are overpriced by analytic product separation.The separation bound D(w/Q) ≥ 1/(16Q^2) creates a strict surplus gap between target and non-target batches.
  • Fixed-capacity non-reusable hardness: Because the expected utility of opening target batches increases with each available batch, an optimal policy opens all disjoint target batches until success.Thus the optimum is determined by the maximum number ν of pairwise-disjoint target batches, distinguishing YES instances with ν = m from NO instances with ν ≤ m−1.
  • Sign-gap hardness: The resulting sign-gap reductions prove NP-hardness for both non-reusable and reusable models, including finite or unbounded capacity settings.In YES instances a positive-surplus batch exists; in NO instances every nonempty batch is overpriced, making the empty policy optimal.

7 Proofs of Bicriteria Approximation Results

The approximation proofs first show that adaptive policies induce feasible LP solutions, then compare fractional winner envelopes with independently sampled sets and round both batch counts and capacities. The reusable proof similarly converts threshold certificates into repeated policies and controls the rounding loss.

  • Non-reusable proof: The atomized winner envelope has a threshold representation and is a normalized, monotone, submodular reward function.This structure enables comparison between fractional opening marginals and independently sampled sets.
  • Non-reusable proof: Every adaptive non-reusable policy induces a feasible LP solution whose objective upper-bounds its original-cost value.The LP uses opening probabilities, expected batch count, and winner-event probabilities derived from the policy’s nonanticipatory decisions.
  • Non-reusable proof: The correlation-gap argument shows that independent sampling preserves a constant fraction of the fractional winner envelope.The proof integrates threshold-wise comparisons between the sampled-set reward and the fractional envelope.
  • Non-reusable proof: Two-point rounding of the fractional batch count controls its loss, after which pipage rounding produces a feasible set under the uniform capacity constraint.The rounded set has cardinality at most k times the integral batch count while preserving the required marginals and submodular-reward guarantee.
  • Non-reusable proof: Combining LP upper bounds, reward rounding, batch-count rounding, capacity rounding, and cost accounting proves the finite-support non-reusable guarantee.Polynomial solvability follows because the LP and multilinear-extension evaluations are polynomial in the finite-support representation.
  • Reusable proof: Monotone threshold certification lets binary search find a threshold within ε of the optimum, while fractional batch certificates are rounded into integral batches.The resulting algorithm provides the reusable discounted-cost bicriteria guarantee.
  • Reusable proof: For reusable boxes, every batch with reservation value at least τ yields a repeated policy whose discounted value is at least τ.The policy repeatedly opens the batch until its realization exceeds τ, using a geometric stopping argument.

A.1 A lower bound for consecutive batching

The section constructs an instance where reservation-value order separates two boxes that are profitable together, making every consecutive-batch policy unprofitable while a non-consecutive batch has positive value.

  • A.1 A lower bound for consecutive batching: A non-consecutive batch {A, B} is profitable, while every feasible consecutive batch in the order A ≻ D ≻ B is unprofitable.In the numerical instance, consecutive batches have utilities −1, −2, or −2, whereas {A, B} is profitable.
  • A.1 A lower bound for consecutive batching: For any α > 1/2, a finite-support instance exists in which every consecutive policy has α-discounted value at most zero while OPT1 > 0.Thus no algorithm restricted to consecutive batches in this order can guarantee an (α, α)-bicriteria approximation.
  • A.1 A lower bound for consecutive batching: The construction places k decoy boxes between useful boxes A and B, with reservation values between theirs but arbitrarily small total expected reward.A is a rare large prize, B is a moderate sure prize, and their maximum pays for one setup cost.
  • A.1 A lower bound for consecutive batching: Every consecutive policy can extract at most one useful box per opened batch, so setup costs prevent it from obtaining positive value.If both useful boxes are opened, at least two batches are required; decoy rewards contribute at most their total expected value.

A.2 Numerical details for the strict adaptivity-gap example

The numerical example exhibits a strict adaptivity gap: an adaptive policy achieves value 0.949535, whereas the best fixed menu achieves 0.796055, giving a gap of about 1.193.

  • A.2 Numerical details for the strict adaptivity-gap example: The best fixed-menu value is OPTfix(T, 2) = 0.796055, obtained by enumerating maximal disjoint menus and applying Weitzman’s rule.The three singleton menu has the largest listed value, 0.796055.
  • A.2 Numerical details for the strict adaptivity-gap example: The ratio 0.949535 / 0.796055 gives a strict adaptivity gap of about 1.193.For every k ≥ 3, the additional single-batch menu remains below 0.796055, so the same gap persists.

A.3 Capped-value reduction for non-reusable policies

The section reduces non-reusable adaptive policies to capped-value objectives and shows that overpriced batches can be omitted, while fixed disjoint menus become classical Pandora instances.

  • A.3 Capped-value reduction for non-reusable policies: An optimal non-reusable policy never opens an overpriced positive-cost batch, whose expected reward is below its cost.Skipping such a batch and continuing with the same policy is strictly better.
  • A.3 Capped-value reduction for non-reusable policies: For policies without overpriced positive-cost batches, net value is bounded by the expected maximum capped value among opened batches.The proof uses history-measurability, independence of unopened box values, and the fact that only the final maximum contributes.
  • A.3 Capped-value reduction for non-reusable policies: A fixed disjoint family of feasible batches induces independent Pandora boxes, so Weitzman’s rule is optimal for the resulting fixed-menu instance.Each induced box has reward X_B = max_{i∈B} V_i and opening cost K(B).

A.4 Proof of the non-reusable adaptivity gap

The proof uses random-path rounding to convert an adaptive decision tree into a fixed disjoint family whose expected maximum capped value is at least half as large.

  • A.4 Proof of the non-reusable adaptivity gap: A deterministic feasible path has expected maximum mark at least half the adaptive expected maximum mark.The argument first samples a path using an independent ghost instance, then probes that path on a fresh instance.
  • A.4 Proof of the non-reusable adaptivity gap: Threshold induction proves that the ghost-path policy reaches any mark threshold with probability at least half that of the adaptive tree.The proof compares root marks and continuation trees using independent ghost observations and disjoint supports.
  • A.4 Proof of the non-reusable adaptivity gap: Applying random-path rounding to feasible batches yields a fixed disjoint family with at least half the adaptive capped value.Non-reusability ensures that batch supports are disjoint along every realized path.
  • A.4 Proof of the non-reusable adaptivity gap: Because fixed disjoint families are classical Pandora instances, the reduction gives 1 ≤ 2 · OPTfix(T, k).Proposition A.4 identifies the fixed-family capped value with the corresponding fixed-menu Pandora value.

A.5 Proof of Theorem 3.3: Reusable reservation index

The proof establishes that W(m) = max{m, σ⋆} bounds every policy and is attained by threshold-based opening or stopping. For m < σ⋆, repeatedly opening a maximizing batch until a threshold crossing achieves the bound; for m ≥ σ⋆, stopping is optimal.

  • Existence: The maximizing reservation index σ⋆ is attained whenever it is positive because only finitely many non-overpriced batches remain relevant.Positive opening costs bound the feasible batch sizes, while the excess function arguments control overpriced batches.
  • Upper bound: W(m) = max{m, σ⋆} bounds every finite- and infinite-horizon policy, using backward induction, truncation, bounded convergence, and monotone convergence.Finite-horizon policies are bounded by backward induction; truncating admissible infinite-horizon policies preserves the bound in the limit.
  • Attainment: For m < σ⋆, repeatedly opening a batch a⋆ attaining σ⋆ until the first threshold crossing achieves W(m).The number of openings is geometric because the probability p = P[X_a⋆ > σ⋆] is positive.
  • Attainment: For m ≥ σ⋆, stopping attains W(m).Thus the stopping decision is optimal once the current reward reaches the reusable reservation index.
Loading 2609.04059v1…