The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization

Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai FuarXiv 2026 · arXiv

TL;DR

This paper generalizes the classic "Pandora’s Box" search problem to a staged setting where candidates are advanced through multiple rungs of a ladder, and rewards can be collected at specific intermediate steps. The authors derive an exact, index-based optimal policy for independent candidates using a novel "covered-call" recursion and provide a robust regret bound for scenarios where candidates share information through a common surrogate model.

What Problem Does This Paper Address?

In fields like Bayesian Optimization (BO), we often face "multi-fidelity" problems. For example, when tuning a machine learning model, you might run a cheap proxy evaluation (low fidelity) before deciding whether to pay for a full training run (high fidelity).

The classic mathematical framework for this is Pandora’s Box, where you pay a cost to open a box and see its reward. However, the standard model assumes a one-shot "open and see" action. Real-world search is often staged: you might pause a training run at checkpoints, resume it later, or find that an intermediate result is actually "collectable" (usable) even if it isn't the final output.

The challenge is deciding:

  1. Which candidate to advance next?
  2. When to stop searching and keep the best result found so far?
  3. When is it worth resuming a candidate you previously paused?

Existing theories handled "terminal-only" collection (only the last step counts) or "all-collectable" settings, but this paper provides a unified theory for any arbitrary set of collectable stages.

Methods

The authors introduce the Staged Pandora’s Box model. Each candidate (arm) has a finite ladder of stages. Advancing a stage costs money and reveals a reading. Only readings at designated "collectable" stages can be kept as the final result.

Key Technical Innovations:

  • Covered-Call Recursion: The authors represent the value of an arm using a recursion inspired by finance. The "covered call" value ($Z$) accounts for the option to either stop with the current best value or continue to the next stage.
  • Reservation Index ($G$): They derive a unique index for each arm state. The optimal policy is simple: always advance the arm with the highest index, provided that index is higher than your current best result (the incumbent).
  • Loss Decomposition: They provide an exact formula for the "Bellman loss"—the cost of making a sub-optimal move—allowing researchers to price the error of any arbitrary search policy.
  • Information Sharing Robustness: When arms are not independent (e.g., they share a Gaussian Process surrogate), the index policy is no longer strictly optimal. The authors provide an approximate-planning bound that limits the regret based on how much a new observation changes the "local values" of other untouched candidates.

Datasets

Because this is a theoretical paper focused on exact optimality, the authors do not use standard "noisy" ML benchmarks. Instead, they use synthetic finite-law models to verify their math:

  • Independent Binary Trees: Randomly generated trees where every path and cost is known, used to verify the index optimality.
  • Staging Grids: A grid of 660 problem instances with varying costs and collection rights.
  • Shared-Law Audits: 453 cases involving shared latent variables to test the robustness bounds.
  • Exact Rational Arithmetic: Crucially, the numerical verification uses rational numbers (fractions) rather than floating-point decimals to ensure that every identity holds perfectly without rounding errors.

Key Insights and Ideas

  • Resumption is Stochastic: In deterministic settings, you never need to resume a paused arm—if it wasn't good enough to continue before, it won't be now. However, if rewards are stochastic, a change in your "incumbent" (the best value found elsewhere) can make a previously ignored arm worth resuming.
  • Collection Rights Matter: The paper proves that simply changing which stages are "collectable" can completely flip the optimal order of inspection, even if the underlying probability distributions remain identical.
  • Information Sharing Limits: The authors show that no policy looking only at an arm's own law can be universally optimal if there is information sharing. They quantify this "sharing penalty" using predictive total-variation dispersion, which measures how much one more reading moves your belief about the common components of the problem.

Key Results

  • Optimality Proof: The index policy is proven to be optimal for all independent, finite-stage search problems with positive costs.
  • Exact Loss Accounting: The difference between the optimal value and any sub-optimal policy's value is exactly equal to the sum of the one-step Bellman losses incurred along the path.
  • Numerical Validation: In thousands of test cases, the covered-call recursion matched direct Bellman optimization (the "gold standard" for solving MDPs) with zero error in exact arithmetic.
  • Robustness Guarantee: For shared laws, the regret of the recomputed index policy is bounded by $2H\bar{\epsilon}$, where $H$ is the number of stages and $\bar{\epsilon}$ is the maximum local-value change.

Limitations and Future Work

  • Complexity: The index computation involves a backward recursion that is exponential in the number of stages ($J^T$), making it difficult to scale to problems with very deep ladders or many possible outcomes per stage.
  • Continuous Distributions: The exact results assume finite, discrete outcomes. Applying this to continuous distributions (like standard Gaussian Processes) requires discretization, and the paper does not yet provide a formal error bound for that approximation.
  • Practical BO: The study focuses on "known laws." In real Bayesian Optimization, the model (surrogate) is learned and refitted. The authors acknowledge that their bounds don't yet account for posterior misspecification or the errors introduced by learning the law on the fly.

Summary updated

Abstract

A staged search must decide which candidate to advance next and when to stop. Some observations only inform later decisions; others can be kept as results. We formulate these choices as a staged Pandora's box with a designated set of collectable stages. For independent finite-stage candidates with bounded readings and positive bounded own-history costs, an exact covered-call recursion gives the reservation index, the optimal value and the loss of every advance or stop; advancing an index-maximal candidate while its index exceeds the incumbent is optimal. The representation recovers classical single-stage search, nested inspection and the all-collectable Markov setting, and prices changes in the problem: enlarging the collectable set or lowering costs raises the value by an explicit covered-call overshoot. Resumption can be valuable even when future reward laws do not change, but has no value for deterministic readings. With information sharing across candidates, no rule using only their separate remaining-reading laws is universally optimal, and making an intermediate reading collectable can change which candidate is inspected first. Under a coherent joint path law with own-history costs, an approximate-planning bound controls the recomputed index's regret by changes in untouched candidates' local values; a common-component specialization bounds those changes through predictive total-variation dispersion. Exact finite-law experiments check the representation, the loss accounting and the bounds.
BibTeX
@misc{vu2026staged,
  author = {Long Vu and Jongseong Brad Choi and Binoy Ravindran and Zhoulai Fu},
  title = {{The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization}},
  year = {2026},
  eprint = {2611.02722},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02722},
}
Figure