A state x can be picked before y by the index algorithm if and only if γ(x) ≥ γ(y)
ProvedTsitsiklisGittins.IndexTheorem.picked_before_iff_index_gebandit-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 be the indices produced by a run of the index algorithm. For distinct states ,
"Can be picked" refers to the freedom in step (a) of the algorithm when several states attain the maximal rate. Combined with the optimality of the picking orders, it shows that every priority order compatible with the indices is optimal (Theorem 2.2).
Formalization Note The runs on the right-hand side are required to produce the same index function on all of , which is the reading under which the claim yields Theorem 2.2; ties in are allowed.
Preamble
import Mathlib import Definitions.Def_TsitsiklisGittins_IndexTheorem_IndexRun
Formal statement
namespace TsitsiklisGittins.IndexTheorem
/-- Proof of Theorem 2.2 of Tsitsiklis (1994), p. 198: given the indices `γ` of a run of the index
algorithm, a state `x` can be picked before a state `y` by the index algorithm (in some run that
yields the same indices `γ`) if and only if `γ(x) ≥ γ(y)`. -/
theorem picked_before_iff_index_ge {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 γ)
(x y : Σ i, X i) (hxy : x ≠ y) :
γ y ≤ γ x ↔ ∃ seq' : List (Σ i, X i), B.IsIndexRun seq' γ ∧ seq'.idxOf x < seq'.idxOf y := 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, second sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.