The finite Bellman recursion passes to the infinite-horizon retirement value
ProvedBanditAlgorithm.gittinsRetirementValue_bellman_of_finite_tendstobanditsbellman-equationgittins-indexoptimal-stopping
Let be the finite-horizon Bellman values of the discounted one-armed retirement game, and let be its infinite-horizon value. Assume that converges pointwise to and that both the finite values and the limit have the stated integrability against every transition measure.
For every state , the infinite-horizon value then satisfies the Wald--Bellman equation
This result isolates the analytic passage from finite-horizon dynamic programming to the infinite-horizon Bellman fixed point used in the proof of the Gittins index theorem.
Preamble
import Definitions.Def_GittinsFiniteRetirementValue import Mathlib.Topology.Instances.Real.Lemmas open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
theorem BanditAlgorithm.gittinsRetirementValue_bellman_of_finite_tendsto
{S : Type*} [MeasurableSpace S]
(P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} {α γ : ℝ} (hα0 : 0 ≤ α)
(hfin : ∀ n x,
Integrable (gittinsFiniteRetirementValue P r α γ n) (P x))
(hlim : ∀ x, Integrable (gittinsRetirementValue P r α γ) (P x))
(hconv : ∀ x,
Tendsto (fun n ↦ gittinsFiniteRetirementValue P r α γ n x)
atTop (𝓝 (gittinsRetirementValue P r α γ x)))
(x : S) :
gittinsRetirementValue P r α γ x =
max 0 (r x - γ +
α * ∫ y, gittinsRetirementValue P r α γ y ∂P x) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (Cambridge University Press, 2020), printed pp. 442-443, Theorem 35.3 (Wald--Bellman equation), specialized to the discounted retirement value used in printed p. 449, Lemma 35.7(a).