Finite prevailing-charge accounting identities
ProvedBanditAlgorithm.gittins_finite_prevailing_charge_accountingbanditsgittins-indexoptimal-stoppingprobability
Under discounted absolute-reward integrability, compare finite reward and prevailing charge over a horizon . For every policy , finite discounted reward is at most its finite discounted prevailing-charge value. If is a Gittins-index policy, its charge accounting is exact up to the terminal retirement potential:
This is Part 1 of the prevailing-charge proof and is reusable independently of the greedy interleaving argument.
Formalization Note Both assertions are bundled so the arbitrary-policy Bellman inequality and the fair-charge identity share the same horizon and initial state.
Preamble
import Definitions.Def_GittinsPrevailingChargeValue open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittins_finite_prevailing_charge_accounting
{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) ≤
markovBanditFinitePrevailingChargeValue P r α π x N ∧
markovBanditFinitePrevailingChargeValue P r α πstar 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, Part 1 “Prevailing Charge”, printed pp. 451–452 / PDF pp. 459–460.