BanditAlgorithm.gittins_index_theorem
Provedbanditsbayesiangittinsoptimal-stopping
(Gittins index theorem, L&S Theorem 35.9) For the infinite-horizon -discounted -armed Markov bandit on a Borel state space, assume the integrability Assumption 35.6:
(hence for all the Markov chains of the game). Then every Gittins index policy (activating an arm of maximal index each round, ties arbitrary) attains the supremum of the expected total discounted reward over all policies:
Preamble
import Mathlib.MeasureTheory.Constructions.Polish.Basic import Definitions.Def_GittinsIndex open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittins_index_theorem {k : ℕ} {S : Type*} [MeasurableSpace S]
[StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} (hr : Measurable r) {α : ℝ} (hα0 : 0 < α) (hα1 : α < 1)
(hint : DiscountedRewardIntegrable P r α)
(πstar : MarkovBanditPolicy k S) (hπ : IsGittinsIndexPolicy P r α πstar)
(x : Fin k → S) :
markovBanditDiscountedValue P r α πstar x =
⨆ π : MarkovBanditPolicy k S, markovBanditDiscountedValue P r α π x := by
sorry
Source
L&S Theorem 35.9, p.450
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.