A Gittins-index policy dominates every competing policy
ProvedBanditAlgorithm.gittins_index_policy_dominatesConsider a discounted -armed Markov bandit on a standard Borel state space. All arms evolve according to the same Markov kernel , yield measurable reward , and are discounted by . Assume the expected discounted absolute reward of each single-arm chain is finite. If always activates an arm whose current state has maximal Gittins index, then for every competing policy and every initial state vector ,
This is the pointwise policy-dominance form of the Gittins index theorem. It isolates the prevailing-charge and interleaving argument from the order-theoretic final step that identifies the optimal value with the supremum over policies.
Formalization Note Policies may be randomized Markov kernels on the complete observed history. The integrability assumption is the formal version of Assumption 35.6.
import Mathlib.MeasureTheory.Constructions.Polish.Basic import Definitions.Def_GittinsIndex open MeasureTheory ProbabilityTheory ENNReal
theorem BanditAlgorithm.gittins_index_policy_dominates
{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) :
∀ π : MarkovBanditPolicy k S,
markovBanditDiscountedValue P r α π x ≤
markovBanditDiscountedValue P r α πstar x := by
sorry