Lemma 8 — exact expected-cost matching at an interior minimum
ProvedPandoraBO.Private20261023.interior_dual_minimum_matches_budgetbayesian-optimizationexpected-budgetgittins-indexpandoras-box
Fix a strictly feasible expected budget . If minimizes over the nonnegative half-line, then some policy is optimal for the penalized objective and satisfies
Randomized policies are included. The separate Gittins cost-extrema milestone supplies the additional bridge needed to choose a budget-matching policy inside the index-policy class.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem interior_dual_minimum_matches_budget {n : ℕ} (M : Instance n)
(B multiplier : ℝ) (hslater : ∃ i : Box n, M.cost i < B)
(hmin : dualMinimizer M B multiplier) (hpos : 0 < multiplier) :
∃ π : Policy n, optimal M multiplier π ∧ expectedCost M π = B := by sorry
end PandoraBO.Private20261023
Source
Qian Xie, Raul Astudillo, Peter I. Frazier, Ziv Scully, and Alexander Terenin. [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://arxiv.org/abs/2406.20062). NeurIPS 2024. Appendix B.5, Lemma 8: budget matching at a strictly positive dual minimizer.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.