Index monotonicity — along a run of the index algorithm, γ(s*) ≥ γ(q*) for consecutive picks s*, q*
ProvedTsitsiklisGittins.IndexTheorem.index_antitonebandit-algorithmsgittins-indexp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider the semi-Markov multi-armed bandit problem with finite nonempty state spaces and a run of the index algorithm with indices . Then for every with defined,
For this is the claim that if is the first state picked and the next one, then : if is in the bandit of , by (2.3), and otherwise .
The indices are thus non-increasing in the picking order, which is the first half of the characterization "x can be picked before y if and only if ".
Formalization Note The page proves the case of the first two picks and invokes "the recursive nature of the algorithm" for the rest; the Lean statement is the resulting claim for every pair of consecutive picks.
Preamble
import Mathlib import Definitions.Def_TsitsiklisGittins_IndexTheorem_IndexRun
Formal statement
namespace TsitsiklisGittins.IndexTheorem
/-- Proof of Theorem 2.2 of Tsitsiklis (1994), p. 198: along a run of the index algorithm the
indices do not increase; a state picked next never has a larger index than the state picked
before it, `γ(s*) ≥ γ(q*)`. -/
theorem index_antitone {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 γ)
(k : ℕ) (hk : k + 1 < seq.length) :
γ seq[k + 1] ≤ γ seq[k] := 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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.