Dominance from finite discounted charge certificates
ProvedBanditAlgorithm.le_of_discounted_permutation_approximationsbanditsdiscounted-rewardinequalities
Let and let . Suppose that, for every , there are finite charge lists and such that: is a permutation of ; is nonincreasing; the discounted value of approximates from below up to ; and the discounted value of approximates from above up to . Then .
This packages the limiting step that converts finite prevailing-charge interleavings into a comparison of infinite-horizon policy values.
Preamble
import Theorems.Thm_BanditAlgorithm_discounted_list_value_le_of_perm_pairwise
Formal statement
theorem BanditAlgorithm.le_of_discounted_permutation_approximations
{α u v : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1)
(hcert : ∀ ε : ℝ, 0 < ε →
∃ xs ys : List ℝ,
xs.Perm ys ∧ ys.Pairwise (· ≥ ·) ∧
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, printed pp.452--453, using Lemma 35.10 on printed p.451. This is the epsilon/finite-certificate limiting form of that interleaving step.