Finite discounted interleaving inequality
ProvedBanditAlgorithm.discounted_list_value_le_of_perm_pairwisebanditsinequalitiesrearrangement
Let , and let and be finite lists of real charges containing the same multiset of entries. If is arranged in nonincreasing order, then its discounted value is at least that of :
This is the finite deterministic exchange inequality underlying the interleaving argument for prevailing charges.
Preamble
import Mathlib.Data.List.Perm.Basic import Mathlib.Tactic
Formal statement
theorem BanditAlgorithm.discounted_list_value_le_of_perm_pairwise
{α : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1)
{xs ys : List ℝ} (hperm : xs.Perm ys)
(hsorted : ys.Pairwise (· ≥ ·)) :
xs.foldr (fun z acc ↦ z + α * acc) 0 ≤
ys.foldr (fun z acc ↦ z + α * acc) 0 := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Lemma 35.10 and its use in the proof of Theorem 35.9, printed pp.451--453. This theorem is the finite permutation/exchange core of that lemma.