Vanishing discounted terminal retirement potential
ProvedBanditAlgorithm.tendsto_gittins_terminal_retirement_potential_zerobanditsgittins-indexintegrabilityprobability
Consider a finite-armed rested Markov bandit with measurable rewards and discount factor . Under discounted absolute-reward integrability, the expected retirement potential at the prevailing charges grows slowly enough that its discounted terminal contribution vanishes:
for every policy and every initial state vector.
This theorem supplies the uniform-integrability tail step needed to pass from the finite prevailing-charge inequality to infinite-horizon Gittins optimality.
Formalization Note The conclusion is convergence in along Filter.atTop; no bounded-reward assumption is imposed beyond the platform's formalization of Assumption 35.6.
Preamble
import Definitions.Def_GittinsTerminalPotential open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.tendsto_gittins_terminal_retirement_potential_zero
{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 α)
(π : MarkovBanditPolicy k S) (x : Fin k → S) :
Filter.Tendsto (fun N ↦ α ^ N *
markovBanditExpectedRetirementPotential P r α π x N)
Filter.atTop (nhds 0) := by
sorrySource
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (free online edition), https://tor-lattimore.com/downloads/book/book.pdf, Assumption 35.6 and §35.4 proof of Theorem 35.9, terminal passage after Parts 1–2, printed pp. 447 and 451–453 / PDF pp. 455 and 459–461.