Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Any priority policy ordering the states as the index algorithm picks them is optimal

Proved
TsitsiklisGittins.IndexTheorem.pick_order_priority_optimal

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

bandit-algorithmsgittins-indexp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the semi-Markov multi-armed bandit problem with finite nonempty state spaces, and let s0,s1,…,sN−1s_0,s_1,\dots,s_{N-1}s0​,s1​,…,sN−1​ be the order in which a run of the index algorithm picks the states of X\mathcal XX. Let π\piπ be a priority policy whose priority order agrees with the picking order: states picked earlier have strictly higher priority,

a<b ⟹ rank⁡(sb)<rank⁡(sa),a<b\ \Longrightarrow\ \operatorname{rank}(s_b)<\operatorname{rank}(s_a),a<b ⟹ rank(sb​)<rank(sa​),

and π\piπ always plays the bandit whose current state has the highest rank. Then π\piπ is optimal.

This is what the proof of Theorem 2.1 shows when the induction always removes the state picked by the index algorithm; together with the characterization of the picking orders through the indices it gives Theorem 2.2.

Formalization Note The statement holds for every run of the index algorithm, whatever the tie choices in its step (a). Optimality is over stationary deterministic policies and for every initial joint state.

Preamble
import Mathlib
import Definitions.Def_TsitsiklisGittins_IndexTheorem_IndexRun
Formal statement
namespace TsitsiklisGittins.IndexTheorem

/-- Proof of Theorem 2.2 of Tsitsiklis (1994), p. 198: any priority policy that orders the states
in the same order as they are picked by (a run of) the index algorithm is optimal. -/
theorem pick_order_priority_optimal {n : ℕ} [NeZero n] {X : Fin n → Type} [∀ i, Fintype (X i)] [∀ i, DecidableEq (X i)]
    [∀ i, Nonempty (X i)] [∀ i, MeasurableSpace (X i)] [∀ i, MeasurableSingletonClass (X i)]
    (B : SemiMarkovBandit n X)
    (seq : List (Σ i, X i)) (γ : (Σ i, X i) → ℝ) (hrun : B.IsIndexRun seq γ)
    (rank : (Σ i, X i) → ℕ)
    (hord : ∀ (a b : ℕ) (ha : a < seq.length) (hb : b < seq.length), a < b → rank seq[b] < rank seq[a])
    (π : Policy n X) (hπ : FollowsRank rank π) :
    B.IsOptimal π := by sorry

end TsitsiklisGittins.IndexTheorem
Source
Tsitsiklis, A Short Proof of the Gittins Index Theorem, Ann. Appl. Probab. 4 (1994), p. 198 (PDF p. 5), Section 2, proof of Theorem 2.2, first sentence
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