New method optimizes staged decisions for better search results
The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization
Machine Learning
Summary
Sometimes when looking for the best choice, you have to decide not only which option to check next but also when to stop searching. The authors study these decisions as a special kind of problem where some observations can be saved while others only help later. They develop a mathematical way to find the best strategy for advancing or stopping, improving on past methods by handling complex cases where the information changes during the search. Their approach also explains when saving intermediate results or continuing the search is useful and when it is not.
What this means in practice
- •For industrial engineers: Optimize sequential inspection processes by deciding when to continue or stop checking candidates for quality or defects.
- •For data-driven decision teams: Improve planning in complex searches where partial results can be saved or shared to maximize expected value.
Authors
Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu
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.