Theorem 1 — Weitzman cost-per-sample optimality
ProvedPandoraBO.Private20261023.weitzman_optimalitybayesian-optimizationexpected-budgetgittins-indexpandoras-box
Consider finitely many mutually independent integrable real rewards with strictly positive deterministic opening costs. For every , a Gittins policy exists, and every such policy maximizes
over all measurable adaptive randomized policies. The first box must be opened. Afterward the rule selects an unopened maximal-index box and compares its index with the incumbent reward; it may randomize among tied boxes and between stopping and continuing at equality. This is the cost-per-sample result used as a prerequisite to the fixed expected-budget theorem.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem weitzman_optimality {n : ℕ} (M : Instance n)
(multiplier : ℝ) (hpos : 0 < multiplier) :
(∃ π : Policy n, isGittinsPolicy M multiplier π) ∧
∀ π : Policy n, isGittinsPolicy M multiplier π → optimal M multiplier π := 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. Section 3.2, Theorem 1 (attributed to Weitzman), applied to the positive scaled costs λc.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.