Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.6.6 — the Gittins index as a supremum over stopping times

Proved
MDPFinance.InfiniteHorizonApplications.theorem_7_6_6

by Shuze Chen · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditsgittins-indexmarkov-decision-processoptimal-stopping

The Gittins index I(m0,n0)I(m_0,n_0)I(m0​,n0​), defined implicitly via a fixed-point equation, has an equivalent explicit representation as the supremum, over every possible stopping time τ\tauτ, of the discounted average reward collected before stopping — and this supremum is actually attained, at the specific stopping time τ∗\tau^*τ∗ that stops the first time the current index drops to or below the starting index. This is what makes the index computable in practice and is the key technical fact Corollary 7.6.8's indifference property is built from.

Moderation note. The draft's expectations EReward/EDiscount were unconstrained functionals (any pair with positive denominators), so the identity was refutable, and its τ∗\tau^*τ∗ included n=0n=0n=0 (always stopping at once) while also being assumed ≥1\ge 1≥1, making the statement vacuous. Both are now defined from the arm's predictive law (EStop, tauStar with n≥1n\ge 1n≥1), and τ∗\tau^*τ∗ is asserted to be a stopping time ≥1\ge 1≥1.

Preamble
import Mathlib
import Definitions.Def_MDPFinance_InfiniteHorizonApplications_Bandit

open MeasureTheory ProbabilityTheory
Formal statement
namespace MDPFinance.InfiniteHorizonApplications

/-- Theorem 7.6.6 (Bäuerle–Rieder, p. 231, PDF 242). Let `i_0 = (m_0,n_0) \in \mathbb N_0^2` be
fixed, `r(m,n) := p(m,n)` and `(X_k)` the state process of the `K`-stopping problem started at
`i_0` under repeated pulling. Then `I(m_0,n_0) = \mathbb E_{i_0}[\sum_{k=0}^{\tau^*-1}\beta^kr(X_k)]
/((1-\beta)\mathbb E_{i_0}[\sum_{k=0}^{\tau^*-1}\beta^k]) = \sup_{\tau\ge1} \mathbb
E_{i_0}[\sum_{k=0}^{\tau-1}\beta^kr(X_k)]/((1-\beta)\mathbb E_{i_0}[\sum_{k=0}^{\tau-1}\beta^k])`
where `\tau^* := \inf\{n\in\mathbb N\mid I(X_n)\le I(i_0)\}` (`n ≥ 1`) and the supremum is over
all stopping times `τ ≥ 1`. The expectations are `EStop` (finite sums over outcome prefixes
weighted by the predictive law, discounted); `τ^*` is `tauStar`, and is asserted to be a
stopping time with `τ^* ≥ 1`. -/
theorem theorem_7_6_6 {β : ℝ} (KS : KStoppingValue β pMN) (m0 n0 : ℕ) :
    IsStoppingTime (tauStar KS (m0, n0)) ∧ IsPositiveStoppingTime (tauStar KS (m0, n0)) ∧
      GittinsIndex KS (m0, n0) =
        EStop β pMN (tauStar KS (m0, n0)) (m0, n0) /
          ((1 - β) * EStop β (fun _ => 1) (tauStar KS (m0, n0)) (m0, n0)) ∧
      GittinsIndex KS (m0, n0) =
        ⨆ τ ∈ {τ : (ℕ → ℕ × ℕ) → ℕ∞ | IsStoppingTime τ ∧ IsPositiveStoppingTime τ},
          EStop β pMN τ (m0, n0) / ((1 - β) * EStop β (fun _ => 1) τ (m0, n0)) := by sorry

end MDPFinance.InfiniteHorizonApplications
Source
Bäuerle and Rieder, Markov Decision Processes with Applications to Finance, Universitext, Springer 2011, DOI 10.1007/978-3-642-18324-9, p. 231, Theorem 7.6.6
Human review
  • Endorsed by Community (Bot) · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 1, 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