Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Gittins certificate bridge from greedy charge interleavings

Proved
BanditAlgorithm.gittins_ae_certificates_of_greedy_charge_interleaving

by Harry_Xu · Jul 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditsgittins-indexoptimal-stoppingprobability

Consider a discounted finite-armed Markov bandit with transition kernel PPP, measurable reward rrr, discount factor 0<α<10<\alpha<10<α<1, and an integrability assumption ensuring that discounted rewards are well defined. Assume the stated stopping-time calibration of the Gittins index, and let π∗\pi^*π∗ be a Gittins-index policy.

Assume also the deterministic charge-stack principle: for every family of nonincreasing stacks, every greedy interleaving has discounted sum at least that of any competing interleaving. Then for every competing policy π\piπ there is a common probability measure μ\muμ such that, for every ε>0\varepsilon>0ε>0, measurable finite lists xωx_\omegaxω​ and yωy_\omegayω​ satisfy almost surely that yωy_\omegayω​ is a nonincreasing permutation of xωx_\omegaxω​, both discounted list values are integrable, and

Vα(π,x)≤∫Dα(xω) dμ+ε,∫Dα(yω) dμ≤Vα(π∗,x)+ε.V_\alpha(\pi,x) \le \int D_\alpha(x_\omega)\,d\mu+\varepsilon, \qquad \int D_\alpha(y_\omega)\,d\mu \le V_\alpha(\pi^*,x)+\varepsilon.Vα​(π,x)≤∫Dα​(xω​)dμ+ε,∫Dα​(yω​)dμ≤Vα​(π∗,x)+ε.

This theorem isolates the probabilistic reward-stack coupling, prevailing-charge comparison, and infinite-horizon tail passage from the deterministic Hardy--Littlewood interleaving inequality.

Preamble
import Mathlib.MeasureTheory.Constructions.Polish.Basic
import Definitions.Def_GittinsIndex
import Definitions.Def_GittinsChargeInterleaving

open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittins_ae_certificates_of_greedy_charge_interleaving
    {k : ℕ} {S : Type*} [MeasurableSpace S]
    [StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
    {r : S → ℝ} (hr : Measurable r)
    {α : ℝ} (hα0 : 0 < α) (hα1 : α < 1)
    (hint : DiscountedRewardIntegrable P r α)
    (hcal : ∀ (y : S) (ε : ℝ), 0 < ε →
      ∃ τ : (ℕ → S) → ℕ∞,
        IsTrajStoppingTime τ ∧ (∀ ω, 1 ≤ τ ω) ∧
        gittinsIndex P r α y - ε <
          (∫ ω, discountedStoppedSum α r τ ω ∂markovChainMeasure P y) /
            (∫ ω, discountedStoppedSum α (fun _ ↦ 1) τ ω
              ∂markovChainMeasure P y))
    (πstar : MarkovBanditPolicy k S)
    (hπ : IsGittinsIndexPolicy P r α πstar)
    (x : Fin k → S) (π : MarkovBanditPolicy k S)
    (hinterleaving :
      ∀ {H : Fin k → ℕ → ℝ} {astar : ℕ → Fin k},
        (∀ i, Antitone (H i)) →
        IsGreedyChargeStackInterleaving H astar →
        ∀ (a : ℕ → Fin k),
          Summable (fun n ↦ α ^ n * chargeStackInterleaving H a n) →
          Summable (fun n ↦ α ^ n * chargeStackInterleaving H astar n) →
          (∑' n : ℕ, α ^ n * chargeStackInterleaving H a n) ≤
            ∑' n : ℕ, α ^ n * chargeStackInterleaving H astar n) :
    ∃ μ : Measure
        ((Fin k → ℕ → S) × ((ℕ → Fin k) × (ℕ → Fin k))),
      ∀ ε : ℝ, 0 < ε →
        ∃ xs ys :
            ((Fin k → ℕ → S) × ((ℕ → Fin k) × (ℕ → Fin k))) →
              List ℝ,
          (∀ᵐ ω ∂μ, (xs ω).Perm (ys ω) ∧
            (ys ω).Pairwise (· ≥ ·)) ∧
          Integrable
            (fun ω ↦ (xs ω).foldr (fun z acc ↦ z + α * acc) 0) μ ∧
          Integrable
            (fun ω ↦ (ys ω).foldr (fun z acc ↦ z + α * acc) 0) μ ∧
          markovBanditDiscountedValue P r α π x ≤
            (∫ ω, (xs ω).foldr (fun z acc ↦ z + α * acc) 0 ∂μ) + ε ∧
          (∫ ω, (ys ω).foldr (fun z acc ↦ z + α * acc) 0 ∂μ) ≤
            markovBanditDiscountedValue P r α πstar x + ε := by
  sorry
Source
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (free online edition), https://tor-lattimore.com/downloads/book/book.pdf, Section 35.4, printed pp. 451--453 / PDF pp. 459--461: Lemma 35.10 and the proof of Theorem 35.9, especially Part 1 (Prevailing Charge) and Part 2 (Interleaving Prevailing Charges).

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