Expected dominance from almost-sure discounted interleavings
ProvedBanditAlgorithm.le_of_ae_discounted_permutation_approximationsbanditsprobabilityrearrangement
Let random finite charge lists and be available for every . Assume almost surely that is a permutation of and that is nonincreasing. If their discounted values are integrable and approximate from below and from above in expectation, respectively, then .
This is the expectation-and-limit form of the deterministic discounted interleaving inequality used for random reward stacks.
Preamble
import Theorems.Thm_BanditAlgorithm_discounted_list_value_le_of_perm_pairwise import Mathlib.MeasureTheory.Integral.Bochner.Basic open MeasureTheory
Formal statement
theorem BanditAlgorithm.le_of_ae_discounted_permutation_approximations
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω)
{α u v : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1)
(hcert : ∀ ε : ℝ, 0 < ε →
∃ xs ys : Ω → List ℝ,
(∀ᵐ ω ∂μ, (xs ω).Perm (ys ω) ∧
(ys ω).Pairwise (· ≥ ·)) ∧
Integrable (fun ω ↦ (xs ω).foldr (fun z acc ↦ z + α * acc) 0) μ ∧
Integrable (fun ω ↦ (ys ω).foldr (fun z acc ↦ z + α * acc) 0) μ ∧
u ≤ (∫ ω, (xs ω).foldr (fun z acc ↦ z + α * acc) 0 ∂μ) + ε ∧
(∫ ω, (ys ω).foldr (fun z acc ↦ z + α * acc) 0 ∂μ) ≤ v + ε) :
u ≤ v := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), proof of Theorem 35.9, Part 2 on printed pp.452--453, applying Lemma 35.10 pathwise to the random prevailing-charge stacks and then taking expectations.