Anytime Algorithms for Horizon Independent Online Learning

This direction is split into other directions: unknown time horizon. Its last version stays readable and citable here.

Version 1 of 138 papers39 conceptsfrozen 2026-10-04

In the standard formulation of online learning, an agent makes a sequence of decisions over $T$ rounds, aiming to minimize "regret"—the difference between their cumulative loss and the loss of the best fixed strategy in hindsight. Most classical algorithms, however, harbor a secret: they need to know the value of $T$ before the first round begins.

This requirement, often called the horizon problem, is a significant hurdle for real-world deployment. Whether in online advertising, high-frequency trading, or network routing, we rarely know exactly when a process will end. If an algorithm assumes a short horizon but the game continues, it may "over-exploit" early and fail to adapt later. Conversely, if it prepares for a long horizon that never materializes, it may "over-explore" and suffer unnecessary losses.

The research direction of Anytime Algorithms seeks to eliminate this dependence, creating learners that achieve optimal performance at every time step $t$ without ever knowing the final $T$.

The Failure of Fixed Horizons

To understand why the horizon matters, consider the learning rate in Online Gradient Descent. To achieve the optimal $O(\sqrt{T})$ regret, the step size must typically be scaled by $1/\sqrt{T}$. Shipra Agrawal and Yinyu Ye note that in online linear programming, knowing the total number of arrivals is crucial for calibrating "threshold prices" that balance resource consumption. Without this knowledge, an algorithm might exhaust its budget prematurely or leave valuable resources unutilized (Agrawal et al.).

Historically, researchers bypassed this using the "doubling trick"—running the algorithm in epochs of size $2^k$ and resetting. However, as Moise Blanchard points out, this adds complexity and often results in sub-optimal constants or "hiccups" in performance at the boundaries of epochs (Blanchard).

Universal Adaptation to Curvature

A key facet of anytime learning is universality. Different loss functions (convex, strongly convex, or exp-concave) allow for different regret bounds ($O(\sqrt{T})$ vs $O(\log T)$). Yibo Wang and Tianbao Yang developed frameworks that use meta-algorithms to track "experts" with different learning rates. By using second-order regret bounds, these meta-algorithms can automatically adapt to the curvature of the loss function without knowing the horizon or the function type in advance (Wang et al.).

Similarly, Lijun Zhang introduced the Universal Strategy for Online Convex Optimization (USC), which treats off-the-shelf solvers as black boxes. The challenge here is that even the "expert grid"—the set of candidate learning rates—usually depends on $T$. Transitioning these to an anytime framework requires dynamically growing the expert pool as time progresses (Zhang et al.).

Managing Constraints in the Dark

In many practical scenarios, we don't just want to minimize loss; we must also satisfy cumulative constraints (e.g., a total budget). Víctor Valls and Leandros Tassiulas highlight that most primal-dual algorithms for constrained optimization fail when the duration is unknown (Valls et al.).

Recent breakthroughs by Abhishek Sinha and Rahul Vaze have bridged this gap by merging Lyapunov optimization with adaptive policies. Their work achieves optimal regret and constraint violation simultaneously without prior knowledge of $T$, effectively treating the constraint violation as a "debt" that the algorithm must manage over an indefinite timeline (Sinha and Vaze).

The Search for "Goldilocks" Distributions

Is it always possible to be horizon-independent? Peter L. Bartlett and colleagues investigated this by looking for cases where a "greedy" strategy (looking only one step ahead) is mathematically equivalent to a strategy that knows the entire future.

They discovered that for one-dimensional exponential families, this perfect horizon-independence is rare, occurring only for Gaussian, Gamma, and Tweedie distributions (Bartlett et al.). For other distributions, some loss in optimality is inevitable if the horizon is unknown, which motivates the search for algorithms that minimize this "anytime penalty."

Why Anytime Algorithms Work

The intuition behind modern anytime algorithms lies in scale-invariance and parameter-free updates. Instead of picking a learning rate based on $T$, algorithms like those proposed by Andrew Jacobsen and Francesco Orabona use the history of observed gradients to set the learning rate dynamically. By embedding the problem into Reproducing Kernel Hilbert Spaces (RKHS), they show that dynamic regret can be handled in a way that is naturally horizon-independent (Jacobsen et al.).

By shifting from "fixed-time" planning to "adaptive-response" mechanisms, this research direction makes online learning robust enough for systems that operate indefinitely, ensuring that the learner is always ready for the next round, no matter how many have passed.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_anytime_algorithms_for_horizon_independe_1e45b95d,
  title = {Anytime Algorithms for Horizon Independent Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/anytime-algorithms-for-horizon-independent-online-learning/rdr_1e45b95d5b184b1f9830a8951090d7b8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_anytime_algorithms_for_horizon_independe_1e45b95d_v1,
  title = {Anytime Algorithms for Horizon Independent Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/anytime-algorithms-for-horizon-independent-online-learning/rdr_1e45b95d5b184b1f9830a8951090d7b8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}