Forced exploration keeps every count above
ProvedBanditAlgorithm.forced_exploration_sqrt_min_count_boundLet be counts on arms that start at zero and increase by exactly one coordinate per round, the coordinate played at round being , and let . Suppose the rule is forced to explore: whenever it must play a least-played arm, . Then for every ,
so : every arm is played at least of order times, whatever the rule does on the unforced rounds.
The proof is a potential argument, and the potential is what makes the constants explicit. Let be the number of coordinates attaining the minimum and set . Then never decreases, and it strictly increases on every forced round: if two or more coordinates are minimal, incrementing one leaves alone and drops by one; if only one is minimal, incrementing it raises by one, adding to the first term while the second loses at most . Since and , at most of the first rounds can have been forced. Hence every window of consecutive rounds before contains an unforced round, at which the threshold was already below the minimum; monotonicity of and of then transports that bound to the start of the window.
Stated for an abstract count sequence, with the minimum supplied as a function together with the two properties that characterise it, so that no lattice-valued definition is needed.
import Mathlib.Data.Finset.Lattice.Fold import Mathlib.Order.Interval.Finset.Nat
theorem BanditAlgorithm.forced_exploration_sqrt_min_count_bound {k : ℕ} (hk : 0 < k)
(N : ℕ → Fin k → ℕ) (arm : ℕ → Fin k) (m : ℕ → ℕ)
(hmle : ∀ t i, m t ≤ N t i) (hmatt : ∀ t, ∃ i, N t i = m t)
(hinit : ∀ i, N 0 i = 0)
(hstep : ∀ t i, N (t + 1) i = N t i + (if i = arm t then 1 else 0))
(hforced : ∀ t, m t < Nat.sqrt t → N t (arm t) = m t) (t : ℕ) :
t < (m t + 1) * (m t + 1) + k * m t + k := by
sorry