Eventually LIL Regret: Almost Sure lnln T Regret for a sub-Gaussian Mixture on Unbounded Data

We prove that a classic sub-Gaussian mixture proposed by Robbins in a stochastic setting actually satisfies a path-wise (deterministic) regret bound. For every path in a natural ``Ville event'' mathcal Eα, this regret till time T is bounded by ln2(1/α)/VT + ln (1/α) + ln ln VT up to universal constants, where VT is a nonnegative, nondecreasing, cumulative variance process. (The bound reduces to ln(1/α) + ln ln VT if VT ≥ ln(1/α).) If the data were stochastic, then one can show that mathcal Eα has probability at least 1-α under a wide class of distributions (eg: sub-Gaussian, symmetric, variance-bounded, etc.). In fact, we show that on the Ville event mathcal E0 of probability one, the regret on every path in mathcal E0 is eventually bounded by ln ln VT (up to constants). We explain how this work helps bridge the world of adversarial online learning (which usually deals with regret bounds for bounded data), with game-theoretic statistics (which can handle unbounded data, albeit using stochastic assumptions). In short, conditional regret bounds serve as a bridge between stochastic and adversarial betting.