Cover meets Robbins while Betting on Bounded Data: ln n Regret and Almost Sure lnln n Regret

arXiv:2604.20172v1 Announce Type: new Abstract: Consider betting against a sequence of data in [0,1], where one is allowed to make any bet that is fair if the data have a conditional mean m_0 in (0,1). Cover's universal portfolio algorithm delivers a worst-case regret of O(ln n) compared to the best constant bet in hindsight, and this bound is unimprovable against adversarially generated data. In this work, we present a novel mixture betting strategy that combines insights from Robbins and Cover, and exhibits a different behavior: it eventually produces a regret of O(ln ln n) on almost all paths (a measure-one set of paths if each conditional mean equals m_0 and intrinsic variance increases to infty), but has an O(log n) regret on the complement (a measure zero set of paths). 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 stochastic data and protection against adversarial data. We contrast our results to those inite{agrawal2025regret} for a sub-Gaussian mixture on unbounded data: their worst-case regret has to be unbounded, but a similar hedging delivers both an optimal betting growth-rate and an almost sure lnln n regret on stochastic data. Finally, our strategy witnesses a sharp game-theoretic upper law of the iterated logarithm, analogous toite{shafer2005probability}.

Related

• Eventually LIL Regret: Almost Sure lnln T Regret for a sub-Gaussian Mixture on Unbounded Data
• Swap Regret Minimization Through Response-Based Approachability
• A Modularized Framework for Piecewise-Stationary Restless Bandits

Source: arXiv cs.LG | 2026-04-23