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

1. Problem Statement

The paper addresses the problem of sequential betting (or online portfolio selection) against a stream of data $X_1, X_2, \dots$ taking values in the bounded interval $[0, 1]$.

• Setup: A bettor aims to maximize wealth $W_n$ by betting a fraction $\lambda$ of their current capital at each step. The bet is "fair" if the data has a conditional mean $m_0 \in (0, 1)$.
• Objective: Minimize regret $R_n$, defined as the difference between the log-wealth of the best fixed betting fraction $\lambda^*$ chosen in hindsight ($W_n^*$) and the log-wealth of the betting strategy ($W_n$):
  $$R_n = \ln W_n^* - \ln W_n$$
• The Tension:
  1. Cover's Universal Portfolio: Uses a uniform prior over $\lambda$. It guarantees a worst-case regret of $O(\ln n)$ for all data sequences but fails to achieve the tighter $O(\ln \ln n)$ regret on "typical" stochastic paths.
  2. Robbins' Mixture: Uses a heavy-tailed prior concentrated near zero. It achieves $O(\ln \ln n)$ regret on typical stochastic paths (where the Law of Iterated Logarithm holds) but can suffer linear regret ($O(n)$) on adversarial or atypical paths, and may have suboptimal asymptotic growth rates in stochastic settings.

The core question is whether one can simultaneously achieve the $O(\ln n)$ worst-case guarantee (protection against adversarial data) and the $O(\ln \ln n)$ typical-path guarantee (optimal performance on stochastic data), while also maintaining optimal asymptotic growth rates.

2. Methodology

The authors propose a novel mixture betting strategy that aggregates two distinct classical strategies via a simple convex combination.

A. The Two Component Strategies

1. Uniform Mixture ($W_n^{(1)}$):
   • Uses a uniform prior $\pi(\lambda)$ over the admissible betting range $[-\frac{1}{m_0}, \frac{1}{1-m_0}]$.
   • Performance: Guarantees $R_n = O(\ln n)$ for every sequence. However, on typical stochastic paths, the regret does not improve to $O(\ln \ln n)$.
2. Modified Robbins' Mixture ($W_n^{(2)}$):
   • Uses a specific prior $\pi(\lambda)$ (Equation 7) that is heavy near zero and decays rapidly, scaled to the bounded domain. This is a modification of the Robbins-Siegmund prior.
   • Performance: Achieves $R_n = O(\ln \ln n)$ on paths where the wealth remains bounded (a set of measure 1 under stochastic assumptions). However, on paths where the wealth explodes (e.g., adversarial sequences), the regret can be linear ($O(n)$), and the asymptotic growth rate is suboptimal for distributions far from the mean $m_0$.

B. The Aggregation Strategy

The authors define an aggregate wealth process $W_n$ as a convex combination of the two:
$$W_n = s_0 W_n^{(1)} + (1 - s_0) W_n^{(2)}$$
where $s_0 \in (0, 1)$ is a fixed split of the initial capital.

• Key Insight: By simply averaging the wealths, the resulting strategy inherits the best properties of both parents. If one strategy suffers high regret, the other likely performs well, keeping the aggregate wealth high and the regret low.

3. Key Contributions

1. Best-of-Both-Worlds Regret Guarantees

The paper proves that the aggregated strategy achieves a path-wise regret bound that is the minimum of the two components (up to an additive constant):
$$R_n \leq \min(R_n^{(1)}, R_n^{(2)}) + C$$

• Worst-Case: Since $W_n^{(1)}$ has $O(\ln n)$ regret everywhere, the aggregate strategy guarantees $O(\ln n)$ regret for all sequences.
• Typical-Case: On the set of paths where $W_n^{(2)}$ performs well (specifically, the "Ville event" where wealth is controlled), the regret is $O(\ln \ln n)$.
• Significance: This resolves the apparent trade-off where previous works suggested one must choose between worst-case safety and typical-path optimality.

2. Optimal Asymptotic Growth Rates

The authors analyze the asymptotic growth rate ($\liminf \frac{1}{n} \ln W_n$) and the self-normalized growth rate ($\liminf \frac{1}{V_n} \ln W_n$).

• They show that the uniform mixture achieves the optimal growth rate but has higher regret.
• They show that the Robbins mixture has suboptimal growth rates for distributions far from $m_0$ due to its linear regret in those regimes.
• Result: The aggregated strategy achieves a growth rate at least as large as the maximum of the two components:
  $$G \geq \max(G^{(1)}, G^{(2)})$$
  Thus, the aggregate strategy achieves optimal growth rates while maintaining the superior regret bounds.

3. Game-Theoretic Law of the Iterated Logarithm (LIL)

The analysis yields a sharp, explicit game-theoretic version of the Law of the Iterated Logarithm.

• The paper establishes a dichotomy: Either the self-normalized sum of deviations satisfies the LIL ($\limsup \frac{|S_n|}{\sqrt{2V_n \ln \ln V_n}} \leq 1$), OR the wealth process $W_n$ diverges to infinity.
• The mixture wealth process acts as an explicit witness for the violation of the SLLN and LIL. If the data violates these laws, the wealth explodes; if the wealth remains bounded, the laws hold.

4. Key Results

• Theorem 3.1 (Uniform Mixture): Establishes a deterministic path-wise regret bound of $R_n \leq \ln(1+n) + 1$ for the uniform mixture.
• Theorem 4.1 & 4.2 (Robbins' Mixture): Establishes that for the modified Robbins prior, $R_n = O(\ln \ln V_n)$ on the event $E_\alpha$ (where wealth is bounded). It further proves that on the set where $V_n \to \infty$ and wealth is bounded, the regret is eventually $O(\ln \ln V_n)$, implying the SLLN and LIL hold.
• Proposition 5.1 (Aggregation):
  • Regret: $R_n \leq \min(R_n^{(1)}, R_n^{(2)}) + \ln(1/\min(s_0, 1-s_0))$.
  • Growth: The aggregate growth rate is $\geq \max(G^{(1)}, G^{(2)})$.
  • This confirms the "best-of-both-worlds" property: $O(\ln n)$ worst-case regret, $O(\ln \ln n)$ typical-path regret, and optimal growth rates.

5. Significance and Impact

1. Resolution of Trade-offs: The paper fundamentally challenges the notion that one must sacrifice worst-case guarantees for typical-path performance (or vice versa) in bounded betting. It demonstrates that a simple convex combination of two classical strategies resolves these tensions.
2. Bounded vs. Unbounded Data: The authors contrast their results with their previous work on sub-Gaussian (unbounded) data. In the unbounded setting, achieving $O(\ln n)$ worst-case regret is impossible for mixtures that achieve $O(\ln \ln n)$ typical regret. However, in the bounded setting, the geometry of the problem allows for this simultaneous achievement.
3. Game-Theoretic Probability: The work strengthens the link between online learning (regret minimization) and game-theoretic statistics (martingale betting). The explicit construction of a wealth process that witnesses the LIL provides a concrete, finite-time, path-wise interpretation of probabilistic limit theorems without assuming a specific underlying probability measure (non-parametric).
4. Practical Implications: The proposed strategy offers a robust algorithm for sequential decision-making under uncertainty that is adaptive to stochastic data (learning the mean efficiently) while remaining safe against adversarial manipulation.

In summary, this paper presents a theoretically rigorous and practically simple solution to the problem of sequential betting on bounded data, unifying the strengths of Cover's universal portfolio and Robbins' mixture to achieve optimal performance across both adversarial and stochastic regimes.