Lemma 8 bridge — Gittins tie rules realize optimal cost extremes
ProvedPandoraBO.Private20261023.optimal_face_gittins_cost_extremabayesian-optimizationexpected-budgetgittins-indexpandoras-box
Fix . There exist two Gittins policies and whose expected costs bound the costs of every penalized-optimal policy:
For every , there also exists a Gittins policy with expected cost
By Theorem 1, the two witnesses and the interpolating policies are themselves penalized-optimal. This is an additional bridge required by the budget argument; it is not claimed to be a verbatim numbered lemma in the paper. It makes explicit both extreme-cost attainment within the Gittins class and randomization through admissible ties.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem optimal_face_gittins_cost_extrema {n : ℕ} (M : Instance n)
(multiplier : ℝ) (hpos : 0 < multiplier) :
∃ low high : Policy n,
isGittinsPolicy M multiplier low ∧ isGittinsPolicy M multiplier high ∧
(∀ π : Policy n, optimal M multiplier π →
expectedCost M low ≤ expectedCost M π ∧ expectedCost M π ≤ expectedCost M high) ∧
∀ a : ℝ, 0 ≤ a → a ≤ 1 → ∃ π : Policy n,
isGittinsPolicy M multiplier π ∧
expectedCost M π = a * expectedCost M low + (1 - a) * expectedCost M high := 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 and the conclusion of Theorem 2. This is a supporting formalization lemma for expected-cost extrema among optimal Gittins policies, not a separately numbered theorem in the paper.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.