Finite prevailing-charge bound with terminal retirement potential
ProvedBanditAlgorithm.gittins_finite_reward_le_index_policy_add_terminalbanditsgittins-indexoptimal-stoppingprobability
Consider a -armed rested Markov bandit with measurable rewards, discount factor , and integrable discounted absolute rewards. Let be a policy that always selects an arm of maximal current Gittins index. For every competing policy , initial state vector , and horizon ,
where is the expected terminal retirement potential evaluated at the prevailing charges after rounds.
This is the finite-horizon accounting form of the prevailing-charge proof. It isolates the pathwise greedy interleaving comparison from the subsequent infinite-horizon tail passage.
Formalization Note The two finite discounted sums use the platform's round-reward marginals, while the final term uses markovBanditExpectedRetirementPotential.
Preamble
import Definitions.Def_GittinsTerminalPotential open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittins_finite_reward_le_index_policy_add_terminal
{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 : ℕ) :
(∑ n ∈ Finset.range N,
α ^ n * markovBanditRoundReward P r π x n) ≤
(∑ n ∈ Finset.range N,
α ^ n * markovBanditRoundReward P r πstar x n) +
α ^ N * markovBanditExpectedRetirementPotential
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, Parts 1–2, printed pp. 451–453 / PDF pp. 459–461; finite greedy comparison is Lemma 35.10.