Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — F(x, s, M) = F̂(x, s, M), realized by the finite-horizon Gittins index rule

Proved
WhittleGittins.Retirement.theorem1_index_rule

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsdynamic-programminggittins-indexp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider Whittle's bandit process: NNN projects with measurable state spaces, Markov transition kernels PiP_iPi​, measurable rewards bounded as k(1−β)≤Ri(xi)≤K(1−β)k(1-\beta) \le R_i(x_i) \le K(1-\beta)k(1−β)≤Ri​(xi​)≤K(1−β), and discount 0≤β<10 \le \beta < 10≤β<1, modified by the option to retire at any time for the reward MMM. Project iii may be operated at most sis_isi​ more times. Let F(x,s,M)F(x, s, M)F(x,s,M) be the maximal expected reward of this process, let φi(xi,si,M)\varphi_i(x_i, s_i, M)φi​(xi​,si​,M) be the corresponding value of the single-project process (14), and let Mi(xi,si)M_i(x_i, s_i)Mi​(xi​,si​) be the infimal MMM for which φi(xi,si,M)=M\varphi_i(x_i, s_i, M) = Mφi​(xi​,si​,M)=M. Define

F^(x,s,M)=K−∫MK∏i∂φi(xi,si,m)∂m dm.(13)\hat F(x, s, M) = K - \int_M^K \prod_i \frac{\partial \varphi_i(x_i, s_i, m)}{\partial m}\, dm. \qquad (13)F^(x,s,M)=K−∫MK​i∏​∂m∂φi​(xi​,si​,m)​dm.(13)

Theorem 1. The maximal reward F(x,s,M)F(x, s, M)F(x,s,M) equals F^(x,s,M)\hat F(x, s, M)F^(x,s,M):

F(x,s,M)=F^(x,s,M).F(x, s, M) = \hat F(x, s, M).F(x,s,M)=F^(x,s,M).

It is realized by a policy in which at (x,s)(x, s)(x,s) one engages a project iii maximizing Mi(xi,si)M_i(x_i, s_i)Mi​(xi​,si​) if this maximal value exceeds MMM, and otherwise retires.

The theorem reduces the NNN-project problem to NNN single-project retirement problems, and shows that the Gittins index vi=(1−β)Miv_i = (1-\beta)M_ivi​=(1−β)Mi​ rule is optimal; the infinite-horizon identity (12) follows by letting the horizons grow.

Formalization Note FFF is the backward-induction value of F=max⁡(M,max⁡iLiF)F = \max(M, \max_i L_iF)F=max(M,maxi​Li​F) with F(x,0,M)=MF(x, 0, M) = MF(x,0,M)=M, the maximum running over projects with si>0s_i > 0si​>0; it is not defined through F^\hat FF^ or the index. The statement has three parts: (1) F=F^F = \hat FF=F^; (2) every measurable index rule (with arbitrary tie-breaking among projects of maximal index) earns exactly FFF; (3) no feasible measurable Markov allocation policy earns more than FFF, 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 si=0s_i = 0si​=0 is the paper's −∞-\infty−∞: such projects are never engaged and do not enter the maximum. ∂/∂m\partial/\partial m∂/∂m 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.

Preamble
import Mathlib
import Definitions.Def_WhittleGittins_Retirement_BanditProcess
Formal statement
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
Source
Whittle, Multi-armed Bandits and the Gittins Index, J. R. Statist. Soc. B 42 (1980), p. 147 (PDF 5), Theorem 1
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me