Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.1 — some optimal policy always plays bandit i* when it is at a state s* of maximal reward rate

Proved
TsitsiklisGittins.IndexTheorem.lemma2_1_top_priority

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

bandit-algorithmsdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the semi-Markov multi-armed bandit problem with n≥1n\ge1n≥1 bandits, finite nonempty state spaces X1,…,Xn\mathcal X_1,\dots,\mathcal X_nX1​,…,Xn​ and discount rate β>0\beta>0β>0. Let s∗∈Xs^*\in\mathcal Xs∗∈X satisfy

r(s∗)=max⁡x∈Xr(x),r(s^*)=\max_{x\in\mathcal X}r(x),r(s∗)=x∈Xmax​r(x),

where rrr is the reward rate (2.1), and let i∗i^*i∗ be such that s∗∈Xi∗s^*\in\mathcal X_{i^*}s∗∈Xi∗​. Then there exists an optimal policy π\piπ that obeys the following rule: whenever bandit i∗i^*i∗ is at state s∗s^*s∗, bandit i∗i^*i∗ is played.

The lemma says that a state of maximal reward rate can be given top priority; it is the first step of the induction proving Theorem 2.1.

Formalization Note Optimality is over the paper's class of stationary deterministic policies and for every initial joint state; the existence of an optimal policy is part of the conclusion, not a hypothesis. Bandits are indexed by Fin n.

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

/-- Lemma 2.1 of Tsitsiklis (1994), p. 196: if `s = ⟨i*, s*⟩` has maximal reward rate (2.1),
`r(s*) = max_{x ∈ 𝒳} r(x)`, then there exists an optimal policy that plays bandit `i*` whenever
bandit `i*` is at state `s*`. -/
theorem lemma2_1_top_priority {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)
    (s : Σ i, X i) (hmax : ∀ q : Σ i, X i, B.rate q ≤ B.rate s) :
    ∃ π : Policy n X, B.IsOptimal π ∧ ∀ z : JointState n X, z s.1 = s.2 → π z = s.1 := by sorry

end TsitsiklisGittins.IndexTheorem
Source
Tsitsiklis, A Short Proof of the Gittins Index Theorem, Ann. Appl. Probab. 4 (1994), p. 196 (PDF p. 3), Lemma 2.1
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