Track trials, findings, and clinical evidence as it lands.
Search papers, labs, and topics across Lattice.
This paper introduces a novel mixture betting strategy that combines Cover's universal portfolio algorithm with insights from Robbins to achieve improved regret bounds. The strategy attains an $O(\ln \ln n)$ regret on almost all data paths when betting against a sequence of data in $[0,1]$ with conditional mean $m_0 \in (0,1)$, while maintaining an $O(\ln n)$ regret in the worst case. This hedging approach provides adaptivity to stochastic data while retaining protection against adversarial data, demonstrating a best-of-both-worlds performance.
By cleverly hedging between Cover's and Robbins' betting strategies, you can achieve almost-sure $O(\ln \ln n)$ regret without sacrificing the $O(\ln n)$ worst-case guarantee.
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 \emph{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 in~\cite{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 $\ln\ln n$ regret on stochastic data. Finally, our strategy witnesses a sharp game-theoretic upper law of the iterated logarithm, analogous to~\cite{shafer2005probability}.