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⋆′−V⋆] , 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⋆−VNR is positive exactly where the index policy resumes, and ρ 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, λ=1/10
0.000024
0.000156
0.002142
0.012600
Witness, λ=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εˉ bounds. Values are rounded to six decimals. The nuisance control is outside the 453-cell audit.
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.
This paper studies theoretical guarantees of a one-step lookahead Bayesian optimization (BO) method. Although the empirical effectiveness of one-step lookahead BO methods, such as entropy search, has been studied extensively, they often rely on computationally intractable approximations, and their regret guarantees remain underdeveloped. Thus, this paper analyzes a one-step lookahead BO method, which we refer to as optimal-point variance reduction (OVR), that requires only posterior sampling and Monte Carlo approximations. We obtain a uniform Monte Carlo estimation error bound over an input domain in an acquisition function computation. Furthermore, we show that the regularized OVR, with a slight modification to facilitate exploration, achieves a vanishing Bayesian expected simple regret upper bound. Finally, we validate the performance of OVR and regularized OVR through numerical experiments.
Bayesian optimization often involves multiple objectives, constraints, and fidelity levels. We address the challenge of jointly selecting where and at which fidelity to evaluate to identify the highest-fidelity feasible Pareto frontier in this combined setting. From a unified information-theoretic perspective, we measure query utility by the information gain about this frontier, provided by an observation. Since this mutual information is intractable, we derive a variational lower bound using a mixture of under- and over-truncated approximations to the Pareto-consistent region. Multi-fidelity surrogate models propagate the information to arbitrary fidelities, yielding a cost-aware acquisition function without separate heuristics for fidelity selection or constraint handling. Experiments on synthetic, benchmark, and real-world problems demonstrate effectiveness across diverse objective, constraint, and fidelity settings.