Boundary lemma — Gittins policies as the multiplier decreases to zero
ProvedPandoraBO.Private20261023.zero_multiplier_gittins_limitbayesian-optimizationexpected-budgetgittins-indexpandoras-box
For any positive nonincreasing sequence , there exist positive-multiplier Gittins policies and a zero-multiplier Gittins policy , with indices in the extended reals, such that
The same policy sequence satisfies both limits along the full natural-number sequence. The conclusion is existential and permits choosing ties; it does not say arbitrary zero-index tie rules have minimal cost, or satisfy any prescribed budget.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem zero_multiplier_gittins_limit {n : ℕ} (M : Instance n)
(multipliers : ℕ → ℝ) (hpos : ∀ k, 0 < multipliers k)
(hmono : Antitone multipliers)
(hlim : Filter.Tendsto multipliers Filter.atTop (nhds 0)) :
∃ policies : ℕ → Policy n, ∃ π : Policy n,
(∀ k, isGittinsPolicy M (multipliers k) (policies k)) ∧
isZeroGittinsPolicy M π ∧
expectedReward M π = fullInformationReward M ∧
Filter.Tendsto (fun k => expectedCost M (policies k))
Filter.atTop (nhds (expectedCost M π)) ∧
Filter.Tendsto (fun k => expectedReward M (policies k))
Filter.atTop (nhds (expectedReward M π)) := 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 9 and its limiting-index argument. This supporting formalization lemma extends policy limits to essential-supremum indices at zero; it is not a verbatim numbered statement.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.