In sequential decision-making, an algorithm must make a series of choices under uncertainty, receiving feedback and incurring losses step by step. To guarantee optimal performance—formulated as minimizing regret relative to the best fixed strategy in hindsight—traditional online learning algorithms require a crucial piece of information: the total number of rounds, or the time horizon $T$.
Knowing $T$ allows an algorithm to perfectly calibrate its learning rate. If the learning rate is too aggressive, the algorithm overcorrects to adversarial noise; if it is too conservative, it learns too slowly to minimize regret. Mathematically, the optimal learning rate typically scales inversely with the square root of the horizon ($\eta \propto 1/\sqrt{T}$).
But what happens when an algorithm runs indefinitely, or when the sequence length is dynamic and unpredictable? In real-world streaming applications, assuming a fixed, known horizon is impractical (György et al.; Zhang et al.). This has driven a core research direction: designing anytime algorithms that achieve optimal regret at every time step $t$ without prior knowledge of the final horizon.
The Inelegance of the Doubling Trick
Historically, the standard workaround for an unknown horizon has been the doubling trick. The core idea is simple: divide time into discrete epochs of exponentially increasing lengths (e.g., $1, 2, 4, 8, \dots$ rounds). At the start of each epoch, the algorithm pretends a new game is beginning, resets its parameters, and tunes its learning rate to the length of that specific epoch.
While the doubling trick successfully preserves the asymptotic rate of regret, it introduces several severe practical and theoretical drawbacks:
- Loss of History: Periodically resetting parameters forces the algorithm to discard valuable historical data, leading to a volatile "forgetting" phase at the start of each epoch (Stoltz et al.; Jenatton et al.).
- Suboptimality in Complex Environments: In high-dimensional settings or structured problems like online logistic regression, the doubling trick introduces unnecessary algorithmic complexity and suboptimal constant factors compared to horizon-aware variants (Shamir).
- Failure Under Constraints: In Online Convex Optimization (OCO) with long-term or adversarial constraints, resetting the algorithm disrupts the tracking of cumulative constraint violations. Formal proofs of the doubling trick's efficacy are often missing or invalid in control-theoretic or Lyapunov-based optimization contexts (Sinha et al.).
To move beyond this heuristic, researchers have developed truly adaptive, seamless strategies that eliminate discrete restarts entirely.
Mechanism 1: Parameter-Free Optimization via Coin Betting
One of the most elegant ways to eliminate the time horizon dependency is to reframe online optimization entirely. Instead of viewing the problem through the lens of gradient descent—which inherently requires a step-size parameter—Orabona et al. reframed optimization as a game of adversarial coin betting.
Imagine a gambler betting on the outcomes of coin flips, where the flips represent adversarial gradients. If the gambler makes a sequence of correct bets, their wealth grows exponentially. Conversely, if they bet poorly, their wealth shrinks, but it can never drop below zero.
By mapping the gambler's wealth to the objective function's value, the authors derived algorithms where the step size is automatically determined by the current accumulated wealth rather than a pre-allocated time budget. Because the betting fraction adapts dynamically based on performance rather than time, the resulting algorithms are completely parameter-free and inherently anytime, maintaining optimal regret bounds across indefinite horizons without discrete restarts.
Mechanism 2: Minimax Games with Randomized Horizons
Another foundational approach leverages game theory. Traditional minimax strategies compute the optimal move by backward induction from a fixed final round $T$. If $T$ is unknown, this backward induction chain breaks down (Koolen et al.).
To resolve this, Luo et al. proposed a minimax framework where the algorithm "pretends" the horizon is a random variable drawn from a specific probability distribution. Instead of optimizing for a fixed end date, the algorithm optimizes its choices against an adversary over the expected remaining duration of the game.
By carefully choosing a prior distribution over the horizon, the algorithm's objective function becomes time-independent. The resulting strategy naturally scales its caution based on the elapsed time $t$, achieving optimal minimax regret without ever needing to know when the sequence will terminate.
Mechanism 3: Lyapunov Optimization and Adaptive Step Sizes
For constrained online optimization, the challenge of an unknown horizon is doubled: the algorithm must minimize regret while ensuring that cumulative constraint violations grow sublinearly.
Sinha et al. solved this by combining control theory with adaptive online policies. They paired AdaGrad—which uses a running average of historical gradients to dynamically shrink the learning rate step-by-step—with Lyapunov optimization, a tool used to stabilize dynamical systems.
[Adversarial Environment]
│
▼ (Gradients & Constraints)
┌────────────────────────────────────────────────────────┐
│ Anytime Adaptive Learner │
│ │
│ ┌────────────────────────┐ ┌────────────────────┐ │
│ │ AdaGrad Step Sizes │ │ Lyapunov Function │ │
│ │ (Adapts to historical │ │ (Tracks cumulative │ │
│ │ gradient variance) │ │ violations over │ │
│ │ │ │ open-ended time) │ │
│ └───────────┬────────────┘ └─────────┬──────────┘ │
└──────────────┼───────────────────────────┼─────────────┘
▼ ▼
[Optimal Action] [Bounded Violations]
Because the AdaGrad step size updates continuously based on the variance of observed data rather than the total round count, and the Lyapunov function tracks cumulative violations over an open-ended timeline, this combination yields optimal $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ constraint violations simultaneously, bypassing the need for a known horizon or epoch-based scheduling.
The Fundamental Limits of Horizon Independence
Can we always expect to find an algorithm that performs just as well without a horizon as it does with one? The theoretical answer is nuanced.
Bartlett et al. investigated the boundaries of "horizon-independent" optimality. They discovered that for most statistical models, a forecaster cannot be perfectly optimal without prior knowledge of the data horizon. True horizon independence—where a myopic strategy that looks only one step ahead matches the performance of a strategy aware of the entire future—is exceptionally rare, proven to exist only within a few specific mathematical structures (such as Gaussian, Gamma, and Tweedie distributions).
This rarity highlights why the design of anytime algorithms is so critical. Because horizon independence does not occur naturally in most settings, practitioners cannot rely on simple myopic strategies. Instead, they must deploy sophisticated adaptive mechanisms—such as coin betting, randomized horizons, or cumulative noise processes (Devroye et al.)—to actively defend against the uncertainty of an open-ended future.
Key Foundational Work
Prediction strategies without loss (2011) — contributed 1 concept elements to this direction.
Strategies for prediction under imperfect monitoring (2008) — contributed 1 concept elements to this direction.