Theorem 2: Existence of an Optimal Generalized Gittins Policy for Budgeted Pandora's Box
ProvedPandoraBO.Private20261023.budgeted_pandora_gittins_optimalityConsider a finite nonempty set of boxes . Box has an independent, integrable real reward and a deterministic opening cost . Policies are measurable and choose actions using only observed rewards and independent randomization. They must open at least one box, may open each box at most once, and cannot resume after stopping.
For a policy , let be the random set of boxes it opens. Define its expected terminal reward and expected total opening cost by
The expectation is over the box rewards and the policy's randomization. A fixed expected budget means that a feasible policy satisfies . The actual total cost in an individual run may exceed ; the constraint bounds its expectation.
Assume
For a nonnegative cost multiplier , define the dual objective
where the supremum ranges over all admissible policies, without imposing the budget constraint. Then there exist a multiplier minimizing over and a generalized Gittins policy such that
Thus maximizes expected reward among all policies satisfying the expected-budget constraint.
For , the index is the unique finite solution of , where , and the policy spends exactly in expectation. For , the index is , possibly , and unused budget is permitted. The index policy first opens a maximal-index box, then opens an unopened maximal-index box when its index exceeds the best observed reward, and stops when the best observed reward exceeds every remaining index. Equality permits either action; ties may be randomized.
Source: Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index, NeurIPS 2024, Theorem 2 and Appendix B.5. The formal statement and all its proof dependencies have been verified by Prove2Me's Lean 4 server.
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
namespace PandoraBO.Private20261023
theorem budgeted_pandora_gittins_optimality {n : ℕ} (M : Instance n)
(B : ℝ) (hslater : ∃ i : Box n, M.cost i < B) :
∃ multiplier : ℝ, dualMinimizer M B multiplier ∧ ∃ π : Policy n,
isGeneralizedGittinsPolicy M multiplier π ∧ optimal M multiplier π ∧
complementarySlackness M B multiplier π ∧ budgetOptimal M B π := by sorry
end PandoraBO.Private20261023
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.