Any priority policy ordering the states as the index algorithm picks them is optimal
ProvedTsitsiklisGittins.IndexTheorem.pick_order_priority_optimalConsider the semi-Markov multi-armed bandit problem with finite nonempty state spaces, and let be the order in which a run of the index algorithm picks the states of . Let be a priority policy whose priority order agrees with the picking order: states picked earlier have strictly higher priority,
and always plays the bandit whose current state has the highest rank. Then 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.
import Mathlib import Definitions.Def_TsitsiklisGittins_IndexTheorem_IndexRun
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.