Theorem 2.1 — for finite state spaces some priority rule is optimal
ProvedTsitsiklisGittins.IndexTheorem.theorem2_1_priority_rule_optimalbandit-algorithmsdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider the semi-Markov multi-armed bandit problem with bandits, discount rate and state spaces . If each , , is finite (and nonempty), then there exists a priority rule which is optimal:
This is the paper's basic result; Theorem 2.2 refines it by identifying an optimal priority order through indices computed bandit by bandit.
Formalization Note Finiteness is the Fintype instance on each state type. A priority rule is a policy that, for some injective ranking of , always plays the bandit whose current state has the highest rank. Optimality is over stationary deterministic policies and for every initial joint state. Bandits are indexed by Fin n.
Preamble
import Mathlib import Definitions.Def_TsitsiklisGittins_IndexTheorem_SemiMarkovBandit
Formal statement
namespace TsitsiklisGittins.IndexTheorem
/-- Theorem 2.1 of Tsitsiklis (1994), p. 196: if each `𝒳ᵢ` is finite, there exists a priority
rule which is optimal. -/
theorem theorem2_1_priority_rule_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) :
∃ π : Policy n X, IsPriorityRule π ∧ B.IsOptimal π := 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), Theorem 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.