Lemma 7 strengthening — joint reward and cost convergence at positive limits
ProvedPandoraBO.Private20261023.monotone_multiplier_optimal_policy_limitbayesian-optimizationexpected-budgetgittins-indexpandoras-box
Let positive multipliers converge monotonically, in either direction, to a positive limit . There exist Gittins policies at and a Gittins policy at such that, for the same choices of policies,
By Theorem 1 these policies are penalized-optimal. Joint convergence implies convergence of their values at every fixed real evaluation multiplier, with the same witnesses, and gives convergence of slopes . This formalization strengthens Lemma 7 by tracking expected costs as well as rewards. It does not assert convergence of policy functions.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem monotone_multiplier_optimal_policy_limit {n : ℕ} (M : Instance n)
(multipliers : ℕ → ℝ) (limit : ℝ)
(hpos : ∀ k, 0 < multipliers k) (hlimitpos : 0 < limit)
(hmono : Monotone multipliers ∨ Antitone multipliers)
(hlim : Filter.Tendsto multipliers Filter.atTop (nhds limit)) :
∃ policies : ℕ → Policy n, ∃ π : Policy n,
(∀ k, isGittinsPolicy M (multipliers k) (policies k)) ∧
isGittinsPolicy M limit π ∧
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 7, and Appendix B.6, Lemma 13. This formalization tracks joint expected-cost and expected-reward limits, strengthening the policy-limit statement to supply the slopes used in the envelope argument.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.