{"ID":2829555,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.12325","arxiv_id":"2512.12325","title":"Eventually LIL Regret: Almost Sure $\\ln\\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data","abstract":"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 $\\ln^2(1/α)/V_T + \\ln (1/α) + \\ln \\ln V_T$ up to universal constants, where $V_T$ is a nonnegative, nondecreasing, cumulative variance process. (The bound reduces to $\\ln(1/α) + \\ln \\ln V_T$ if $V_T \\geq \\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 E_0$ of probability one, the regret on every path in $\\mathcal E_0$ is eventually bounded by $\\ln \\ln V_T$ (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.","short_abstract":"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 $\\ln^2(1/α)/V_T + \\ln (1/α) + \\ln \\ln V_T$ up to universal constants,...","url_abs":"https://arxiv.org/abs/2512.12325","url_pdf":"https://arxiv.org/pdf/2512.12325v3","authors":"[\"Shubhada Agrawal\",\"Aaditya Ramdas\"]","published":"2025-12-13T13:34:03Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.ST\",\"stat.ML\"]","methods":"[]","has_code":false}