The Gittins retirement value is Lipschitz in the charge
ProvedBanditAlgorithm.gittinsRetirementValue_lipschitz_chargebanditsgittins-indexlipschitzoptimal-stopping
Fix a state in a discounted one-armed retirement game satisfying the discounted absolute-reward integrability assumption. Let denote the optimal value when each played round incurs charge .
For any two charges and ,
Thus the retirement value is uniformly Lipschitz in the charge, with constant equal to the full discounted duration. This controls the boundary case where the charge approaches the fair Gittins index.
Preamble
import Mathlib.MeasureTheory.Constructions.Polish.Basic import Definitions.Def_GittinsRetirementValue open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittinsRetirementValue_lipschitz_charge
{S : Type*} [MeasurableSpace S]
(P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} (hr : Measurable r) {α : ℝ}
(hα0 : 0 < α) (hα1 : α < 1)
(hint : DiscountedRewardIntegrable P r α)
(x : S) (γ δ : ℝ) :
|gittinsRetirementValue P r α γ x -
gittinsRetirementValue P r α δ x| ≤
|γ - δ| * ∑' t : ℕ, α ^ t := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (Cambridge University Press, 2020), printed p. 448, Eq. (35.7) and the observation immediately following Assumption 35.6 that the retirement value is decreasing in the charge; the quantitative bound follows directly from the discounted-duration bound used in printed p. 449, Lemma 35.7.