Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.8: any index for the class of bandit processes with discount factor a is strictly increasing in ν(B, x)

Proved
AllocationIndices.index_unique_up_to_increasing

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

gittins-indexstandard-bandituniqueness

Theorem 4.8. Any index for Ba\mathcal B_aBa​ (0<a<10 < a < 10<a<1), if there is one, must be a strictly increasing function of ν(B,x)\nu(B, x)ν(B,x).

Formally: let μ\muμ assign a real number to every bandit process and state (an IndexFunction), and suppose μ\muμ is an index for every SFABP {B,Λ}\{B, \Lambda\}{B,Λ} formed by a bandit process on a countable state space with bounded reward and a standard bandit process: every policy that continues an arm of maximal μ\muμ-value at each decision time is optimal for that family. Then for any two bandit processes B=(P,r)B = (P, r)B=(P,r) on TTT and B′=(P′,r′)B' = (P', r')B′=(P′,r′) on T′T'T′ (countable, bounded rewards) and states x,x′x, x'x,x′,

ν(B,x)<ν(B′,x′)  ⟹  μ(B,x)<μ(B′,x′).\nu(B, x) < \nu(B', x') \implies \mu(B, x) < \mu(B', x').ν(B,x)<ν(B′,x′)⟹μ(B,x)<μ(B′,x′).

The hypothesis is weaker than the book's "index for Ba\mathcal B_aBa​" (optimality for every finite SFABP), since the proof only uses the two-member families {B,Λ(λ)}\{B, \Lambda(\lambda)\}{B,Λ(λ)}, so the statement is slightly stronger than printed; the conclusion compares processes on different state spaces, as the book's does.

The conclusion is the order form of "a strictly increasing function of ν\nuν". The printed form also says that μ\muμ is a function of ν\nuν, i.e. equal indices get equal μ\muμ-values, and that part is not true. An index may break the ties within one level of ν\nuν in any way: μ=ν\mu = \nuμ=ν with a different value on some of the bandit processes of index exactly 000 still orders every family as ν\nuν does, up to ties, which Theorem 2.1 allows to be broken arbitrarily.

Preamble
import Definitions.Def_AllocationIndices_Superprocess

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices

theorem index_unique_up_to_increasing (μ : IndexFunction) {a : ℝ} (ha0 : 0 < a) (ha1 : a < 1)
    (hμ : IsIndexForStandardPairs μ a)
    {T : Type} [MeasurableSpace T] [Countable T] [MeasurableSingletonClass T]
    (P : Kernel T T) [IsMarkovKernel P] {r : T → ℝ} (hr : BoundedReward r) (x : T)
    {T' : Type} [MeasurableSpace T'] [Countable T'] [MeasurableSingletonClass T']
    (P' : Kernel T' T') [IsMarkovKernel P'] {r' : T' → ℝ} (hr' : BoundedReward r') (x' : T')
    (hlt : gittinsIndex P r a x < gittinsIndex P' r' a x') :
    μ T P r x < μ T' P' r' x' := by sorry

end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §4.5.2 p. 96, Theorem 4.8 with its proof (the SFABP {B, Λ})
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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