Lemma 5 extension — feasibility and complementary slackness
ProvedPandoraBO.Private20261023.complementary_lagrangian_certificatebayesian-optimizationexpected-budgetgittins-indexpandoras-box
For any real budget and nonnegative multiplier , suppose a policy maximizes over all measurable adaptive randomized policies. If
then is budget-optimal: every policy with satisfies . Unlike exact-budget matching, this sufficient condition includes and unused budget. This is an explicit extension of Lemma 5, not a verbatim source statement.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem complementary_lagrangian_certificate {n : ℕ} (M : Instance n)
(B multiplier : ℝ) (hnonneg : 0 ≤ multiplier) (π : Policy n)
(hopt : optimal M multiplier π) (hfeasible : budgetFeasible M B π)
(hcomp : complementarySlackness M B multiplier π) :
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 complementary slackness, including the zero-multiplier case. This milestone isolates a proof step.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.