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

• URL: http://arxiv.org/abs/2512.12325v1
• Date: Sat, 13 Dec 2025 13:34:03 GMT
• Title: Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data
• Abstract summary: We prove that a classic sub-Gaussian mixture satisfies a pathwise (deterministic) regret bound.<n>We explain how this work helps bridge the world of adversarial online learning.
• Score: 39.04174642330437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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'' $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 $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 $E_0$ of probability one, the regret on every path in $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.

Related papers

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret [39.04174642330437]
  We present a novel mixture betting strategy that combines insights from Robbins and Cover.<n>Our paper appears to be the first to point out the value in hedging two very different strategies to achieve a best-of-both-worlds adaptivity to data.
  arXiv  Detail & Related papers  (2026-04-22T04:27:54Z)
• Stochastic Linear Bandits with Parameter Noise [36.09200986359924]
  We show a regret upper bound of $widetildeO (sqrtd T log (K/) 2_max)$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $2_max$ is the maximal variance of the reward for any action.<n>Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.
  arXiv  Detail & Related papers  (2026-01-30T16:47:42Z)
• Prior Diffusiveness and Regret in the Linear-Gaussian Bandit [25.66105507730649]
  We prove that Thompson sampling exhibits $tildeO(d sqrtT + d r sqrtmathrmTr(_0))$ Bayesian regret in the linear-Gaussian bandit.<n>We establish these results via a new elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.
  arXiv  Detail & Related papers  (2026-01-05T11:30:08Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical $tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$.
  arXiv  Detail & Related papers  (2025-03-15T07:09:36Z)
• How Does Variance Shape the Regret in Contextual Bandits? [59.8472760881411]
  We consider contextual bandits with general function approximation.<n>We show that the eluder dimension $d_textelu$$-$plays a crucial role in variance-dependent bounds.
  arXiv  Detail & Related papers  (2024-10-16T16:20:07Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  We consider a contextual bandit problem with $S$ contexts and $K$ actions. We give an algorithm that outputs an $epsilon$-optimal policy after using at most $widetilde O(r (S +K )/epsilon2)$ samples. In the regret setting, we give an algorithm whose cumulative regret up to time $T$ is bounded by $widetilde O(sqrtr3(S+K)T)$.
  arXiv  Detail & Related papers  (2023-06-22T17:20:30Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  Worst-case minimax regret for sparse linear bandits is $widetildeThetaleft(sqrtdTright)$. In the benign setting where there is no noise and the action set is the unit sphere, one can use divide-and-conquer to achieve an $widetildemathcal O(1)$ regret. We develop a general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits.
  arXiv  Detail & Related papers  (2022-05-26T15:55:44Z)
• No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
  We show that the expected discounted ergodic distribution of play converges to the set of coarse correlated equilibrium (CCE) if the algorithms have "no discounted-regret" For a zero-sum game, we show that no discounted-regret is sufficient for the discounted ergodic average of play to converge to the set of Nash equilibria.
  arXiv  Detail & Related papers  (2021-03-08T05:15:31Z)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  We study differentially private online learning problems in a environment under both bandit and full information feedback. For differentially private bandits, we propose both UCB and Thompson Sampling-based algorithms that are anytime and achieve the optimal $O left(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right right)$ minimax lower bound. For the same differentially private full information setting, we also present an $epsilon$-differentially
  arXiv  Detail & Related papers  (2021-02-16T02:48:16Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.