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

arXiv: https://arxiv.org/abs/2512.12325 · HTML: https://mlsanity.com/paper/2512.12325/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 13 Dec 2025.

## Builds on (most cited first, 16 of 16)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Hypothesis testing with e-values](https://mlsanity.com/paper/2410.23614/) (2024)
- [There are natural scores: Full comment on Shafer, "Testing by betting: A strategy for statistical and scientific communication"](https://mlsanity.com/paper/2102.05569/) (2021)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)
- [A composite generalization of Ville's martingale theorem using e-processes](https://mlsanity.com/paper/2203.04485/) (2022)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Matrix-Free Preconditioning in Online Learning](https://mlsanity.com/paper/1905.12721/) (2019)

## Built on by (most cited first, 2 of 2)

- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)
- [Cover meets Robbins while Betting on Bounded Data: ln n Regret and Almost Sure lnln n Regret](https://mlsanity.com/paper/2604.20172/) (2026)

## Abstract (arXiv)

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.