Finite prevailing-charge interleaving certificates
ProvedBanditAlgorithm.gittins_discounted_value_interleaving_certificatesConsider a discounted rested Markov bandit with finitely many arms, common transition kernel , measurable reward , discount factor , and initial state vector . Assume discounted absolute rewards are integrable and that every single-arm Gittins index admits arbitrarily accurate stopping-time calibration. Let be any policy that always selects an arm of maximal current Gittins index.
For every competing policy and every , there are finite real lists and such that the two lists contain the same multiset, the second is nonincreasing, and
The lists are finite certificates for the prevailing-charge proof: the first ordering represents the competing interleaving, while the sorted ordering represents the greedy Gittins interleaving. This form isolates the model-specific probabilistic coupling from the reusable finite Hardy--Littlewood permutation inequality.
Formalization Note The discounted sums are encoded by a right fold ; list permutation expresses equality of multisets and Pairwise (· ≥ ·) expresses nonincreasing order.
import Mathlib.MeasureTheory.Constructions.Polish.Basic import Definitions.Def_GittinsIndex open MeasureTheory ProbabilityTheory ENNReal
theorem BanditAlgorithm.gittins_discounted_value_interleaving_certificates
{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 α)
(hcal : ∀ (y : S) (ε : ℝ), 0 < ε →
∃ τ : (ℕ → S) → ℕ∞,
IsTrajStoppingTime τ ∧ (∀ ω, 1 ≤ τ ω) ∧
gittinsIndex P r α y - ε <
(∫ ω, discountedStoppedSum α r τ ω ∂markovChainMeasure P y) /
(∫ ω, discountedStoppedSum α (fun _ ↦ 1) τ ω
∂markovChainMeasure P y))
(πstar : MarkovBanditPolicy k S)
(hπ : IsGittinsIndexPolicy P r α πstar)
(x : Fin k → S) (π : MarkovBanditPolicy k S) :
∀ ε : ℝ, 0 < ε →
∃ xs ys : List ℝ,
xs.Perm ys ∧ ys.Pairwise (· ≥ ·) ∧
markovBanditDiscountedValue P r α π x ≤
xs.foldr (fun z acc ↦ z + α * acc) 0 + ε ∧
ys.foldr (fun z acc ↦ z + α * acc) 0 ≤
markovBanditDiscountedValue P r α πstar x + ε := by
sorry