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

Long Vu; Jongseong Brad Choi; Binoy Ravindran; Zhoulai Fu

cs.LGNov 2, 2026

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

Authors: Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu

Organizations: State University of New York Korea · Virginia Tech · Stony Brook University

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.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Instance family	Cases	Exact checks
Independent trees	192	Value representation, maximal-index actions, stop and advance losses
Staging grid	660	Index optimality and accumulated policy losses
Comparative pairs	$1763+60$	Coupled covered-call overshoot identity on grid and random pairs
Shared-law audit	453	Signed residual, policy telescoping, and local-value/path-TV envelopes
Concentration sweep	240	Policy accounting and sharing envelopes at five binary-component priors

Appendix

Table 1: All checks pass in exact arithmetic against direct Bellman calculations. Cases count starting instances, grid cells or problem pairs as indicated; they are verification coverage, not independent statistical observations.

Dominated transition	Pairs	Identity holds
Larger collectable set	440	440
Lower signal cost	495	495
Lower terminal cost	528	528
Constant for own-history costs	300	300
Collectable set	Cells	Zero loss / full rights value lost
$\{1,3\}$	220	133 / 50

Appendix

Table 2: Comparative statics and resumption on the 660-cell staging grid, in exact arithmetic. Top: dominated pairs of cells; the value difference equals the covered-call overshoot of Proposition 2 in every pair. Middle: terminal-only indices under intermediate collection; the loss lies in

[0,V^{\star\prime}-V^{\star}]

, and the last entry counts cells with positive rights value in which all of it is lost. Bottom: the no-return optimum; the gap

V^{\star}-V_{\rm NR}

is positive exactly where the index policy resumes, and

\rho

never exceeds it.

Prior $p$	$2p(1-p)$	Positive-regret cells	Max regret	Max call bound	Max path-TV bound
$1/2$	0.5000	4	0.00698	0.896	2.015
$1/4$	0.3750	0	0.00000	0.715	1.680
$1/10$	0.1800	0	0.00000	0.446	1.070
$1/40$	0.0488	0	0.00000	0.166	0.398
$1/160$	0.0124	0	0.00000	0.046	0.111

Appendix

Table 3: Concentration sweep over the prior of the binary component: the 12 base models at full contrast and all four collection choices, 48 cells per row. Regret and the uniform bounds are row maxima; each cell’s bounds maximize over all feasible histories. The factor

2p(1-p)

describes the root belief in Corollary 2 . Exact values are rounded.

Instance	Regret	Refined (oracle)	Call	Path-TV
Witness, $\lambda=1/10$	0.000024	0.000156	0.002142	0.012600
Witness, $\lambda=1$	0.001700	0.014900	0.214158	1.260000
Shared nuisance	0.000000	0.000000	0.000000	5.600000

Appendix

Table 4: Checks of the sharing bound under specified joint laws. Refined uses the true optimal policy occupancy in ( 6 ); Call and Path-TV are uniform

2H\bar{\varepsilon}

bounds. Values are rounded to six decimals. The nuisance control is outside the 453-cell audit.

Optimal Stopping

Optimal stopping studies when to act on sequential information rather than wait, balancing expected reward against delay, cost, and risk.

See all 39 papers

Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index
Jun 28, 2024Qian Xie, Raul Astudillo, Peter I. Frazier +2Bayesian Optimization
Cornell University · Caltech
Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization
May 31, 2026Shion TakenoBayesian Optimization Regret Minimization
Nagoya University
A Unified Information-Theoretic Approach to Constrained Multi-Fidelity Multi-Objective Bayesian Optimization
Oct 7, 2026Rikuto Matsumoto, Masanori Ishikura, Masayuki KarasuyamaBayesian Optimization Multi-Objective Optimization
Nagoya Institute of Technology

Jun 28, 2024J/K move · Enter open · S save

Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index

Qian Xie, Raul Astudillo, Peter I. Frazier, Ziv Scully+1

Cornell University · Caltech

Bayesian Optimization

Open paper AskPDF arXiv

Bayesian optimization is a technique for efficiently optimizing unknown functions in a black-box manner. To handle practical settings where gathering data requires use of finite resources, it is desirable to explicitly incorporate function evaluation costs into Bayesian optimization policies. To understand how to do so, we develop a previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's Box problem, a decision problem from economics. The Pandora's Box problem admits a Bayesian-optimal solution based on an expression called the Gittins index, which can be reinterpreted as an acquisition function. We study the use of this acquisition function for cost-aware Bayesian optimization, and demonstrate empirically that it performs well, particularly in medium-high dimensions. We further show that this performance carries over to classical Bayesian optimization without explicit evaluation costs. Our work constitutes a first step towards integrating techniques from Gittins index theory into Bayesian optimization.

Abstract

Optimal Stopping

Explore similar work

Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

A Unified Information-Theoretic Approach to Constrained Multi-Fidelity Multi-Objective Bayesian Optimization