Cesàro averages forget a transient:
ProvedBanditAlgorithm.cesaro_average_forgets_transientLet follow a target sequence to within , in the sense that for every , and suppose for all and for all . Then for every
The transient before round contributes and nothing more: an average forgets a bad prefix at rate , whatever happens in it.
Read in the contrapositive — which is how it is used — the estimate says that if the average is not within of at round , then the target cannot have settled before round . That is what allows a weighted failure series for the average to be traded for a higher-moment failure series for the target: a single late failure of the target can spoil only the rounds below it, so exchanging the two sums replaces a linear weight by a quadratic one.
This is the deterministic step in the tracking half of Garivier and Kaufmann's Proposition 13, isolated from the bandit setting: , and are arbitrary reals.
import Definitions.Def_TrackAndStop open Finset
theorem BanditAlgorithm.cesaro_average_forgets_transient
{p N : ℕ → ℝ} {a C B δ : ℝ} {M : ℕ}
(hC : ∀ n : ℕ, |N n - ∑ s ∈ Finset.range n, p s| ≤ C)
(hB : ∀ s : ℕ, |p s - a| ≤ B) (hδ : 0 ≤ δ)
(htail : ∀ s : ℕ, M ≤ s → |p s - a| ≤ δ)
{n : ℕ} (hn : 0 < n) :
|N n / (n : ℝ) - a| ≤ (C + (M : ℝ) * B) / (n : ℝ) + δ := by
sorry