Bounded tracking of a convergent target:
ProvedBanditAlgorithm.tendsto_div_atTop_of_bounded_trackingLet be reals with , and let be a sequence staying within a fixed distance of the partial sums,
Then .
This is the tracking half of Garivier & Kaufmann's Lemma 8, stripped of everything bandit-specific. A sampling rule maintains target allocations — in Track-and-Stop, , which converges once the empirical means do — and plays so that the realised count stays within a constant of the cumulative target . The conclusion is then immediate: the Cesaro average of the targets converges to , and the discrepancy contributes .
The two hypotheses are exactly the two halves of a tracking rule: convergence of the targets, which comes from convergence of the empirical means together with continuity of the allocation map, and the bounded discrepancy, which is what the greedy "play the arm furthest behind its target" step delivers.
import Mathlib.Analysis.Asymptotics.SpecificAsymptotics open Filter Topology
theorem BanditAlgorithm.tendsto_div_atTop_of_bounded_tracking {p : ℕ → ℝ} {a C : ℝ}
(hp : Filter.Tendsto p Filter.atTop (nhds a)) (M : ℕ → ℝ)
(hbd : ∀ t : ℕ, |M t - ∑ s ∈ Finset.range t, p s| ≤ C) :
Filter.Tendsto (fun t : ℕ ↦ M t / (t : ℝ)) Filter.atTop (nhds a) := by
sorry