Greedy tracking of a target has bounded discrepancy
ProvedBanditAlgorithm.greedy_tracking_discrepancy_boundLet be probability vectors on and let counts be generated by: start at zero, and at each round increment the coordinate of an arm of maximal shortfall
Then for every arm and every round, uniformly in the targets.
Sharper two-sided bounds hold and are what the proof produces: . The lower bound is an induction using two facts, that the shortfalls sum to zero (both the targets and the counts account for exactly rounds) and that a maximum of numbers summing to zero is nonnegative: an arm other than the one played only gains, and the arm played was at or above its target, so it ends the round at most one pull ahead. The upper bound is then free, since what one arm is owed the other are ahead by, and each by at most one.
Greediness is essential and not merely convenient. A rule that plays any arm currently behind its target admits an arm lagging arbitrarily far; the proof uses maximality only through , which is exactly where the zero-sum identity enters, and a threshold rule provides no such handle.
Divided by the bound gives , so a tracking rule inherits the Cesaro limit of its targets. This is the tracking lemma of Garivier and Kaufmann's Track-and-Stop.
import Mathlib.Data.Real.Basic import Mathlib.Algebra.BigOperators.Fin import Mathlib.Data.Fintype.BigOperators import Mathlib.Algebra.Order.BigOperators.Group.Finset
theorem BanditAlgorithm.greedy_tracking_discrepancy_bound {k : ℕ} [NeZero k]
(p : ℕ → Fin k → ℝ) (N : ℕ → Fin k → ℕ) (arm : ℕ → Fin k)
(hinit : ∀ i, N 0 i = 0)
(hstep : ∀ t i, N (t + 1) i = N t i + (if i = arm t then 1 else 0))
(hgreedy : ∀ t i, (∑ s ∈ Finset.range t, p s i) - (N t i : ℝ)
≤ (∑ s ∈ Finset.range t, p s (arm t)) - (N t (arm t) : ℝ))
(hnn : ∀ s i, 0 ≤ p s i) (hsum : ∀ s, ∑ i, p s i = 1) (t : ℕ) (i : Fin k) :
|(N t i : ℝ) - ∑ s ∈ Finset.range t, p s i| ≤ (k : ℝ) := by
sorry