Relation (21) — F̂ ≥ LᵢF̂, with equality if M ≤ Mᵢ and M₍ᵢ₎ ≤ Mᵢ
ProvedWhittleGittins.Retirement.relation21_L_lebandit-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), and let
be the extended operator (15), where lowers by one. Let be the index of project , and over the other active projects. Then for every project with ,
with equality if and , that is, if .
Relation (21) shows that engaging a project of maximal index is optimal in the dynamic programming equation (16) satisfied by .
Formalization Note The inequality is stated for active projects () only, since an exhausted project cannot be engaged. The condition is written as for every other active project . Projects are indexed by Fin N.
Preamble
import Mathlib import Definitions.Def_WhittleGittins_Retirement_BanditProcess
Formal statement
namespace WhittleGittins.Retirement
open MeasureTheory ProbabilityTheory
/-- Relation (21) (p. 148): for every active project `i`, `F̂ ≥ Lᵢ F̂`, with equality if
`M ≤ Mᵢ` and `M₍ᵢ₎ ≤ Mᵢ` (i.e. `Mᵢ` is maximal among the indices of the active projects). -/
theorem relation21_L_le {N : ℕ} {X : Fin N → Type*} [∀ i, MeasurableSpace (X i)]
(B : BanditProcess N X) (x : ∀ j, X j) (s : Fin N → ℕ) (M : ℝ) (i : Fin N) (hi : 0 < s i) :
LFhat B i x s M ≤ Fhat B x s M ∧
(M ≤ index B i (x i) (s i) →
(∀ j, j ≠ i → 0 < s j → index B j (x j) (s j) ≤ index B i (x i) (s i)) →
LFhat B i x s M = Fhat B x s 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, relation (21)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.