Lemma 2.1 — some optimal policy always plays bandit i* when it is at a state s* of maximal reward rate
ProvedTsitsiklisGittins.IndexTheorem.lemma2_1_top_prioritybandit-algorithmsdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider the semi-Markov multi-armed bandit problem with bandits, finite nonempty state spaces and discount rate . Let satisfy
where is the reward rate (2.1), and let be such that . Then there exists an optimal policy that obeys the following rule: whenever bandit is at state , bandit 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.