Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — V_{π*}(x) − V_π(x) ≤ (1 − β)E_π[Σ_t β^t(max_i min_{s≤t} G_i(x_i(s)) − R_{j(t)}/(1 − β))]

Proved
WeberGittins.Suboptimality.theorem2_suboptimality_bound

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

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

Consider the discounted kkk-armed Markov bandit with state space SSS (a standard Borel space), Markov kernel PPP, measurable reward rrr that is nonnegative and uniformly bounded, and discount factor 0<β<10<\beta<10<β<1. Let γ\gammaγ be the fair charge and

G(y)=γ(y)1−βG(y) = \frac{\gamma(y)}{1-\beta}G(y)=1−βγ(y)​

the Gittins index of Weber's (3). Write xi(t)x_i(t)xi​(t) for the state of bandit iii at time ttt, j(t)j(t)j(t) for the bandit played at time ttt, and Vπ(x)V_\pi(x)Vπ​(x) for the expected total discounted reward (1) of a policy π\piπ from the initial states xxx.

Suppose π∗\pi^*π∗ is the optimal (Gittins) policy, i.e. a policy that in every round plays, with probability one, an arm of greatest Gittins index. Then for every policy π\piπ and every initial state vector xxx,

Vπ∗(x)−Vπ(x)  ≤  (1−β)∑t=0∞βt Eπ[max⁡imin⁡0≤s≤tG(xi(s))−r(xj(t)(t))1−β ∣ x(0)=x].V_{\pi^*}(x) - V_\pi(x) \;\le\; (1-\beta) \sum_{t=0}^\infty \beta^t\, \mathbb{E}_\pi\Big[\max_i \min_{0\le s\le t} G\big(x_i(s)\big) - \frac{r\big(x_{j(t)}(t)\big)}{1-\beta} \,\Big|\, x(0)=x\Big].Vπ∗​(x)−Vπ​(x)≤(1−β)t=0∑∞​βtEπ​[imax​0≤s≤tmin​G(xi​(s))−1−βr(xj(t)​(t))​​x(0)=x].

This is Theorem 2 of the paper, inequality (6), a bound first given by Glazebrook (1990). It measures how far an arbitrary policy falls short of the optimum by the expected discounted excess, along the policy's own trajectory, of the greatest prevailing charge over the reward actually collected.

Formalization Note Since G=γ/(1−β)G = \gamma/(1-\beta)G=γ/(1−β), the bound is equivalent to Vπ∗(x)−Vπ(x)≤∑tβtEπ[max⁡imin⁡s≤tγ(xi(s))−r(xj(t)(t))]V_{\pi^*}(x) - V_\pi(x) \le \sum_t \beta^t E_\pi[\max_i \min_{s\le t}\gamma(x_i(s)) - r(x_{j(t)}(t))]Vπ∗​(x)−Vπ​(x)≤∑t​βtEπ​[maxi​mins≤t​γ(xi​(s))−r(xj(t)​(t))]; the statement keeps the paper's form, with GGG inside and the factor 1−β1-\beta1−β outside. "The optimal (Gittins) policy" is any policy satisfying the published IsGittinsIndexPolicy (its optimality is the published Theorem 1, BanditAlgorithm.gittins_index_theorem); the statement does not assume one exists. Weber's Eπ[∑tβt(⋅)]E_\pi[\sum_t \beta^t(\cdot)]Eπ​[∑t​βt(⋅)] is written as the series of round expectations, which agrees with it for bounded rewards. At round ttt the integrand is evaluated on the history of the first ttt rounds and the current state vector x(t)x(t)x(t), so the minimum runs over s=0,…,ts = 0,\dots,ts=0,…,t; rrr is the mean of Weber's random reward RjR_jRj​. The hypotheses "rewards nonnegative and uniformly bounded" and 0<β<10<\beta<10<β<1 are the standing assumptions of Section 1; measurability of rrr and the standard Borel structure on SSS are added regularity. The bandits are indexed by Fin k\mathrm{Fin}\,kFink; when k=0k=0k=0 no policy exists, so the statement has content only for k≥1k \ge 1k≥1.

Preamble
import Definitions.Def_WeberGittins_Suboptimality_Model

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace WeberGittins.Suboptimality
theorem theorem2_suboptimality_bound {k : ℕ} {S : Type*}
    [MeasurableSpace S] [StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
    {r : S → ℝ} (hr : Measurable r) (hrb : RewardsNonnegBounded r)
    {β : ℝ} (hβ0 : 0 < β) (hβ1 : β < 1)
    (π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 ≤
      (1 - β) * ∑' t : ℕ, β ^ t * roundExpectation P π x t (fun h j =>
        (⨆ i : Fin k, currentHistoryPrevailingCharge (weberIndex P r β) t h i) -
          r (h.2 j) / (1 - β)) := by sorry
end WeberGittins.Suboptimality
Source
Weber, On the Gittins index for multiarmed bandits, Ann. Appl. Probab. 2 (1992), p. 1029, Theorem 2, eq. (6)
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