Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — Vπ∗(x)−Vπ(x)≤Eπ[∑tβt(max⁡iGi(xi(t))−Gj(t)(xj(t)(t)))]V_{\pi^*}(x)-V_\pi(x)\le E_\pi[\sum_t\beta^t(\max_iG_i(x_i(t))-G_{j(t)}(x_{j(t)}(t)))]Vπ∗​(x)−Vπ​(x)≤Eπ​[∑t​βt(maxi​Gi​(xi​(t))−Gj(t)​(xj(t)​(t)))]

Proved
WeberGittins.IndexGap.theorem3_index_gap_bound

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

banditsgittins-indexp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1suboptimality

Consider kkk bandit processes, each a Markov chain on a standard Borel state space SSS with transition kernel PPP. In each round t=0,1,2,…t = 0, 1, 2, \dotst=0,1,2,… a gambler plays one bandit j(t)j(t)j(t), collects a reward with mean r(xj(t)(t))r(x_{j(t)}(t))r(xj(t)​(t)), and only the played bandit changes state. Rewards are nonnegative and uniformly bounded, rrr is measurable, and the discount factor satisfies 0<β<10<\beta<10<β<1. The value of a policy π\piπ from the initial state vector xxx is

Vπ(x)=Eπ[∑t=0∞βtr(xj(t)(t)) ∣ x(0)=x].V_\pi(x) = E_\pi\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].

Let γ(y)\gamma(y)γ(y) be the fair charge of state yyy (the supremum over stopping times τ≥1\tau \ge 1τ≥1 of expected discounted reward over expected discounted time) and G(y)=γ(y)/(1−β)G(y) = \gamma(y)/(1-\beta)G(y)=γ(y)/(1−β) the Gittins index.

Theorem 3. Let π∗\pi^*π∗ be a Gittins index policy (one that always plays a bandit of greatest Gittins index, ties broken arbitrarily), and let π\piπ be any policy. Then

Vπ∗(x)−Vπ(x)≤Eπ[∑t=0∞βt(max⁡iGi(xi(t))−Gj(t)(xj(t)(t))) | x(0)=x].V_{\pi^*}(x) - V_\pi(x) \le E_\pi\left[\sum_{t=0}^\infty \beta^t\Big(\max_i G_i\big(x_i(t)\big) - G_{j(t)}\big(x_{j(t)}(t)\big)\Big) \,\middle|\, x(0)=x\right].Vπ∗​(x)−Vπ​(x)≤Eπ​[t=0∑∞​βt(imax​Gi​(xi​(t))−Gj(t)​(xj(t)​(t)))​x(0)=x].

The suboptimality of an arbitrary policy is thus bounded by the expected discounted sum, along its own trajectory, of the amounts by which the index of the bandit it plays falls short of the greatest index. A policy that plays a bandit within ε\varepsilonε of the greatest index in every round therefore loses at most ε/(1−β)\varepsilon/(1-\beta)ε/(1−β).

Formalization Note "π∗\pi^*π∗ is the optimal (Gittins) policy" is read as: π∗\pi^*π∗ is any policy with IsGittinsIndexPolicy P r β πstar, as in the published Theorem 1. The expectation of the series is written as the series of round expectations, ∑tβtEπ[ ⋅ ]\sum_t \beta^t E_\pi[\,\cdot\,]∑t​βtEπ​[⋅], the convention of the published value; under bounded rewards the two agree. The index is Weber's GGG (weberIndex), not the fair charge γ\gammaγ (gittinsIndex); with γ\gammaγ the bound would be false by the factor 1−β1-\beta1−β. The hypothesis that γ\gammaγ is measurable is added so that the expectation is a genuine integral. The standing assumptions of Section 1 and the regularity hypotheses (measurable rrr, standard Borel SSS) are binders; Weber's bandits with separate state spaces are encoded on one state space (disjoint union).

Preamble
import Definitions.Def_GittinsIndex
import Definitions.Def_WeberGittins_IndexGap_SwitchPolicies

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace WeberGittins.IndexGap

theorem theorem3_index_gap_bound {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) (hγ : Measurable (gittinsIndex P r β))
    (πstar : MarkovBanditPolicy k S) (hπstar : IsGittinsIndexPolicy P r β πstar)
    (π : MarkovBanditPolicy k S) (x : Fin k → S) :
    markovBanditDiscountedValue P r β πstar x - markovBanditDiscountedValue P r β π x ≤
      ∑' t : ℕ, β ^ t * WeberGittins.Suboptimality.roundExpectation P π x t (fun h j =>
        (⨆ i : Fin k, WeberGittins.Suboptimality.weberIndex P r β (h.2 i)) - WeberGittins.Suboptimality.weberIndex P r β (h.2 j)) := by sorry

end WeberGittins.IndexGap
Source
Weber, On the Gittins index for multiarmed bandits, Ann. Appl. Probab. 2 (1992), p. 1029, Theorem 3, eq. (7)
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