Lemma 5 — an exact-budget Lagrangian certificate
ProvedPandoraBO.Private20261023.tight_lagrangian_certificatebayesian-optimizationexpected-budgetgittins-indexpandoras-box
Fix a budget and . If a policy maximizes over all policies and satisfies , then
Thus is expected-budget optimal. This states the certificate underlying Lemma 5 directly: no separate hypothesis that minimizes the dual is needed for this implication.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem tight_lagrangian_certificate {n : ℕ} (M : Instance n)
(B multiplier : ℝ) (hnonneg : 0 ≤ multiplier) (π : Policy n)
(hopt : optimal M multiplier π) (htight : expectedCost M π = B) :
budgetOptimal 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: the Lagrangian budget-optimality argument with exact expected expenditure. This milestone isolates a proof step.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.