Stopping-time reward ratios are bounded by the Gittins index
ProvedBanditAlgorithm.gittins_stopping_ratio_le_indexbanditsoptimal-stoppingprobability
Let be a Markov chain with transition kernel , started from state , measurable reward function , and discount factor . Assume the expected infinite discounted sum of absolute rewards is finite. For any stopping time , the expected discounted reward per expected discounted unit of time is at most the Gittins index:
This is the fundamental upper-bound direction of the stopping-time characterization of the Gittins index and is reusable in prevailing-charge arguments for discounted Markov bandits.
Formalization Note Stopping times take values in and are adapted to the natural coordinate filtration. The integrability assumption ensures the numerator is a genuine finite Bochner integral and the denominator is at least one.
Preamble
import Mathlib.MeasureTheory.Constructions.Polish.Basic import Mathlib.Analysis.Normed.Group.InfiniteSum import Mathlib.Analysis.SpecificLimits.Normed import Definitions.Def_GittinsIndex open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gittins_stopping_ratio_le_index
{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)
(τ : (ℕ → S) → ℕ∞) (hτ : IsTrajStoppingTime τ)
(hτ1 : ∀ ω, 1 ≤ τ ω) :
(∫ ω, discountedStoppedSum α r τ ω ∂markovChainMeasure P x) /
(∫ ω, discountedStoppedSum α (fun _ ↦ 1) τ ω
∂markovChainMeasure P x) ≤
gittinsIndex P r α x := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), §35.4.1, printed p.448, Eq. (35.9), under Assumption 35.6 on printed p.448.