Existence of epsilon-optimal stopping times for the Gittins index
ProvedBanditAlgorithm.gittins_epsilon_optimal_stoppingbanditsoptimal-stoppingprobability
Let be a Markov chain with transition kernel , initial state , measurable reward , and discount factor . Assume the infinite discounted sum of absolute rewards has finite expectation. For every , there is an admissible stopping time whose discounted reward ratio is within of the Gittins index from below:
This epsilon-optimal form is the robust supremum-attainment principle needed to approximate the optimal stopping blocks in prevailing-charge proofs.
Formalization Note The theorem uses strict approximation rather than asserting that the supremum is exactly attained; this follows directly from the conditional supremum after proving nonemptiness and boundedness.
Preamble
import Theorems.Thm_BanditAlgorithm_gittins_stopping_ratio_le_index open MeasureTheory ProbabilityTheory ENNReal open BanditAlgorithm
Formal statement
theorem BanditAlgorithm.gittins_epsilon_optimal_stopping
{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)
{ε : ℝ} (hε : 0 < ε) :
∃ τ : (ℕ → S) → ℕ∞,
IsTrajStoppingTime τ ∧ (∀ ω, 1 ≤ τ ω) ∧
gittinsIndex P r α x - ε <
(∫ ω, discountedStoppedSum α r τ ω ∂markovChainMeasure P x) /
(∫ ω, discountedStoppedSum α (fun _ ↦ 1) τ ω
∂markovChainMeasure P x) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), §35.4.1, printed pp.448--449, Eq. (35.9) and the discussion immediately preceding Lemma 35.7(c).