Proof of Theorem 1, retirement case — if maxⱼ Mⱼ ≤ M then F̂(x, s, M) = M ≥ LᵢF̂
ProvedWhittleGittins.Retirement.retirement_casebandit-algorithmsdynamic-programminggittins-indexp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In Whittle's bandit process with per-project horizons , let be defined by (13), by (15) and be the index of project . If
the maximum being over the projects with , then
and for every project with . Thus satisfies the dynamic programming equation (16) with , corresponding to adoption of the retirement option.
Together with (21) this covers both branches of the index rule in the inductive proof of Theorem 1.
Formalization Note Projects with (index ) impose no condition. Projects are indexed by Fin N.
Preamble
import Mathlib import Definitions.Def_WhittleGittins_Retirement_BanditProcess
Formal statement
namespace WhittleGittins.Retirement
open MeasureTheory ProbabilityTheory
/-- Retirement case of the proof of Theorem 1 (p. 148): if `maxⱼ Mⱼ ≤ M` (over the active
projects) then `F̂(x, s, M) = M`, and `M ≥ Lᵢ F̂` for every active `i`, so `F̂` satisfies (16)
with the retirement option. -/
theorem retirement_case {N : ℕ} {X : Fin N → Type*} [∀ i, MeasurableSpace (X i)]
(B : BanditProcess N X) (x : ∀ j, X j) (s : Fin N → ℕ) (M : ℝ)
(hM : ∀ j, 0 < s j → index B j (x j) (s j) ≤ M) :
Fhat B x s M = M ∧ ∀ i, 0 < s i → LFhat B i x s M ≤ M := by sorry
end WhittleGittins.Retirement
Source
Whittle, Multi-armed Bandits and the Gittins Index, J. R. Statist. Soc. B 42 (1980), p. 148 (PDF 6), Section 4, proof of Theorem 1, retirement case
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.