A linear function eventually exceeds a logarithmic threshold
ProvedBanditAlgorithm.linear_exceeds_log_threshold_sharpLet , , , . If
then .
The point is the coefficient of . Splitting into two equal halves, one to absorb the logarithm and one to absorb , gives the same conclusion under ; but in the application is the term that grows as , so a factor there is a factor in the sample complexity, turning the constant of Theorem 33.6 into .
A logarithm needs only an asymptotically negligible share of a line, so the split can be made instead of : writing , the first summand absorbs from a round depending on but not on , and the second absorbs from . The loss is now multiplicative- on and purely additive elsewhere, which is exactly what a statement with an -slack in the leading constant tolerates.
The first threshold uses rather than the sharper : the linear term has to dominate a logarithm, not a linear function, so a crude square-root bound is the right tool.
import Mathlib.Analysis.SpecialFunctions.Log.Basic open Real
theorem BanditAlgorithm.linear_exceeds_log_threshold_sharp {K r ε β₀ t : ℝ}
(hK : 0 ≤ K) (hr : 0 < r) (hε : 0 < ε) (hβ₀ : 0 ≤ β₀) (ht1 : 1 ≤ t)
(ht2 : (8 * K * (1 + ε) / (ε * r)) ^ 2 ≤ t)
(ht3 : 2 * K * Real.log 2 * (1 + ε) / (ε * r) ≤ t)
(htβ : (1 + ε) * β₀ / r ≤ t) :
K * Real.log (t ^ 2 + t) + β₀ ≤ r * t := by
sorry