Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 3, p. 1029 — Vπ(t)(x)≤Vπ∗(t+1)(x)V_{\pi(t)}(x)\le V_{\pi^*(t+1)}(x)Vπ(t)​(x)≤Vπ∗(t+1)​(x): switching to Gittins after time ttt never lowers the value

Proved
WeberGittins.IndexGap.switch_to_gittins_after_t_optimal

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

banditsgittins-indexoptimalityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the discounted kkk-armed Markov bandit with state space SSS (a standard Borel space), transition kernel PPP, measurable mean reward rrr that is nonnegative and uniformly bounded, and discount factor 0<β<10 < \beta < 10<β<1. For a policy σ\sigmaσ and initial state vector xxx write

Vσ(x)=Eσ[∑t=0∞βtr(xj(t)(t)) ∣ x(0)=x]V_\sigma(x) = E_\sigma\Big[\sum_{t=0}^\infty \beta^t r\big(x_{j(t)}(t)\big) \,\Big|\, x(0) = x\Big]Vσ​(x)=Eσ​[t=0∑∞​βtr(xj(t)​(t))​x(0)=x]

for its expected total-discounted reward, as in (1).

Let σ\sigmaσ be any policy, t≥0t \ge 0t≥0, and let σ′\sigma'σ′ be a policy that is identical to σ\sigmaσ through time ttt (the same selection rule in every round n≤tn \le tn≤t) and is a Gittins index policy in every round n≥t+1n \ge t+1n≥t+1 (it plays, almost surely, an arm of greatest current fair charge, ties broken arbitrarily). Then

Vσ(x)≤Vσ′(x).V_\sigma(x) \le V_{\sigma'}(x).Vσ​(x)≤Vσ′​(x).

Weber uses this with σ=π(t)\sigma = \pi(t)σ=π(t) and σ′=π∗(t+1)\sigma' = \pi^*(t+1)σ′=π∗(t+1): "since π(t)\pi(t)π(t) and π∗(t+1)\pi^*(t+1)π∗(t+1) are identical through time ttt and π∗(t+1)\pi^*(t+1)π∗(t+1) is optimal thereafter, Vπ(t)(x)≤Vπ∗(t+1)(x)V_{\pi(t)}(x) \le V_{\pi^*(t+1)}(x)Vπ(t)​(x)≤Vπ∗(t+1)​(x)". It is the step that lets the bounds (8) for consecutive ttt telescope into Theorem 3. For ttt replaced by the start of play it is the optimality of the Gittins index policy (Theorem 1 of the paper, already on Prove2Me as BanditAlgorithm.gittins_index_theorem).

Formalization Note The statement is the general form of the sentence ("π∗(t+1)\pi^*(t+1)π∗(t+1) is optimal thereafter"): σ\sigmaσ is arbitrary, not only π(t)\pi(t)π(t). The hypothesis on σ′\sigma'σ′ is IsSwitchToGittinsAt P r β σ (t + 1) σ'. Weber's nnn bandits with their own state spaces are encoded as kkk chains on one state space with one kernel and one reward (take the disjoint union); rrr is the conditional mean of the random reward RjR_jRj​. The value is the series of discounted round expectations, the published convention. The standing assumptions of Section 1 (bounded nonnegative rewards, 0<β<10<\beta<10<β<1) are hypotheses; measurability of rrr and the standard Borel structure of SSS are regularity hypotheses the paper leaves implicit.

Preamble
import Definitions.Def_GittinsIndex
import Definitions.Def_WeberGittins_IndexGap_SwitchPolicies

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace WeberGittins.IndexGap

theorem switch_to_gittins_after_t_optimal {k : ℕ} {S : Type*} [MeasurableSpace S]
    [StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
    {r : S → ℝ} (hr : Measurable r) (hrb : WeberGittins.Suboptimality.RewardsNonnegBounded r)
    {β : ℝ} (hβ0 : 0 < β) (hβ1 : β < 1)
    (σ σ' : MarkovBanditPolicy k S) (t : ℕ) (hσ' : IsSwitchToGittinsAt P r β σ (t + 1) σ')
    (x : Fin k → S) :
    markovBanditDiscountedValue P r β σ x ≤ markovBanditDiscountedValue P r β σ' x := by sorry

end WeberGittins.IndexGap
Source
Weber, On the Gittins index for multiarmed bandits, Ann. Appl. Probab. 2 (1992), p. 1029, proof of Theorem 3, last paragraph ("Note that since π(t) and π*(t + 1) are identical through time t …")
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