The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization
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.
Related
- MF-SCBO : Multi-fidelity Scalable Constrained Bayesian Optimization
- Reduced-Space Multi-Fidelity Bayesian Optimization of Process Simulation Models
- Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices
- Elastic Multi-Fidelity Bayesian Model Calibration
- Bayesian Emulation of Multi-fidelity Earth System Modelling Using Hierarchical Gaussian Processes
BibTeX
@misc{vu2026staged,
title = {{The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization}},
author = {Long Vu and Jongseong Brad Choi and Binoy Ravindran and Zhoulai Fu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02722},
eprint = {2611.02722},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02722},
}
RIS
TY - UNPB
TI - The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization
AU - Long Vu
AU - Jongseong Brad Choi
AU - Binoy Ravindran
AU - Zhoulai Fu
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02722
UR - https://arxiv.org/abs/2611.02722
AB - 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.
ER -