Relation (16) — F̂(x, 0, M) = M and F̂ = max(M, maxᵢ LᵢF̂)
ProvedWhittleGittins.Retirement.relation16_dp_equationbandit-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 by the extended operator (15). Then , and satisfies the dynamic programming equation
where the inner maximum runs over the projects with , and when no project can be operated.
Since lowers by one, (16) is recursive in ; together with the base case it identifies with the maximal reward by induction, which is the first half of Theorem 1.
Formalization Note The maximum over is restricted to active projects, since a project with may not be operated; when none is active the right-hand side is . Projects are indexed by Fin N.
Preamble
import Mathlib import Definitions.Def_WhittleGittins_Retirement_BanditProcess
Formal statement
namespace WhittleGittins.Retirement
open MeasureTheory ProbabilityTheory
/-- Relation (16) (p. 147) with the base case: `F̂(x, 0, M) = M`, and `F̂` satisfies the dynamic
programming equation `F̂ = max(M, maxᵢ Lᵢ F̂)`, the inner maximum over the active projects (and
`F̂ = M` when no project is active). -/
theorem relation16_dp_equation {N : ℕ} {X : Fin N → Type*} [∀ i, MeasurableSpace (X i)]
(B : BanditProcess N X) (x : ∀ j, X j) (M : ℝ) :
Fhat B x 0 M = M ∧
∀ s : Fin N → ℕ, Fhat B x s M = bellmanMax s M (fun i => LFhat B i x s M) := by sorry
end WhittleGittins.Retirement
Source
Whittle, Multi-armed Bandits and the Gittins Index, J. R. Statist. Soc. B 42 (1980), pp. 147–148 (PDF 5–6), Section 4, relation (16) and the base case F̂(x, 0, M) = M
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.