# Towards Minimax Online Learning with Unknown Time Horizon

arXiv: https://arxiv.org/abs/1307.8187 · HTML: https://mlsanity.com/paper/1307.8187/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2013.

## Built on by (most cited first, 6 of 6)

- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB](https://mlsanity.com/paper/2609.14892/) (2026)
- [Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant](https://mlsanity.com/paper/2609.27206/) (2026)
- [Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2510.22579/) (2025)
- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)
- [On prediction from expert advice with more than five experts](https://mlsanity.com/paper/2610.05186/) (2026)

## Abstract (arXiv)

We consider online learning when the time horizon is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some known distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which "pretends" that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen, the worst-case regret is of the optimal rate. Furthermore, our algorithm can be combined and applied in many ways, for instance, to online convex optimization, follow the perturbed leader, exponential weights algorithm and first order bounds. Experiments show that our algorithm outperforms many other existing algorithms in an online linear optimization setting.