Finite prevailing-charge comparison for a Gittins policy
ProvedBanditAlgorithm.gittins_finite_prevailing_charge_interleavingbanditsgittins-indexinterleavingprobability
Let be a Gittins-index policy in a finite-armed rested Markov bandit. For every competing policy and finite horizon , the expected discounted prevailing-charge value of is at most that of :
This is the finite probabilistic form of Part 2 of the Gittins proof. It combines the common independent reward-stack coupling with the deterministic fact that greedily interleaving nonincreasing charge stacks maximizes every discounted finite prefix.
Formalization Note The statement exposes only the finite charge-value interface; reward-stack sample spaces and action likelihoods remain internal proof machinery.
Preamble
import Definitions.Def_GittinsPrevailingChargeValue open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittins_finite_prevailing_charge_interleaving
{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πstar : IsGittinsIndexPolicy P r α πstar)
(x : Fin k → S) (N : ℕ) :
markovBanditFinitePrevailingChargeValue P r α π x N ≤
markovBanditFinitePrevailingChargeValue P r α πstar x N := by
sorrySource
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (free online edition), https://tor-lattimore.com/downloads/book/book.pdf, §35.4, proof of Theorem 35.9, Part 2, printed pp. 452–453 / PDF pp. 460–461, using Lemma 35.10 on printed p. 451 / PDF p. 459.