Theorem 1 — F(x, s, M) = F̂(x, s, M), realized by the finite-horizon Gittins index rule
ProvedWhittleGittins.Retirement.theorem1_index_ruleConsider Whittle's bandit process: projects with measurable state spaces, Markov transition kernels , measurable rewards bounded as , and discount , modified by the option to retire at any time for the reward . Project may be operated at most more times. Let be the maximal expected reward of this process, let be the corresponding value of the single-project process (14), and let be the infimal for which . Define
Theorem 1. The maximal reward equals :
It is realized by a policy in which at one engages a project maximizing if this maximal value exceeds , and otherwise retires.
The theorem reduces the -project problem to single-project retirement problems, and shows that the Gittins index rule is optimal; the infinite-horizon identity (12) follows by letting the horizons grow.
Formalization Note is the backward-induction value of with , the maximum running over projects with ; it is not defined through or the index. The statement has three parts: (1) ; (2) every measurable index rule (with arbitrary tie-breaking among projects of maximal index) earns exactly ; (3) no feasible measurable Markov allocation policy earns more than , which records the meaning of "maximal reward" for such policies and is the standard backward-induction fact rather than something the paper proves. The index of a project with is the paper's : such projects are never engaged and do not enter the maximum. is the right derivative; policies are required to have measurable decision sets so that their expected rewards are well defined. Projects are indexed by Fin N.
import Mathlib import Definitions.Def_WhittleGittins_Retirement_BanditProcess
namespace WhittleGittins.Retirement
open MeasureTheory ProbabilityTheory
/-- Theorem 1 (p. 147): the maximal reward `F(x, s, M)` equals `F̂(x, s, M)` of (13); it is
realized by every (measurable) index rule, which at `(x, s)` engages a project maximizing
`Mᵢ(xᵢ, sᵢ)` if this maximal value exceeds `M` and otherwise retires; and no feasible measurable
Markov allocation policy earns more than `F`. -/
theorem theorem1_index_rule {N : ℕ} {X : Fin N → Type*} [∀ i, MeasurableSpace (X i)]
(B : BanditProcess N X) (x : ∀ j, X j) (s : Fin N → ℕ) (M : ℝ) :
F B x s M = Fhat B x s M ∧
(∀ σ : Policy N X, IsMeasurablePolicy σ → IsIndexRule B σ →
polValue B σ x s M = F B x s M) ∧
(∀ σ : Policy N X, IsFeasible σ → IsMeasurablePolicy σ →
polValue B σ x s M ≤ F B x s M) := by sorry
end WhittleGittins.Retirement
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.