# Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2015.

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

- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Online Learning of Network Bottlenecks via Minimax Paths](https://mlsanity.com/paper/2109.08467/) (2021)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Continuous Prediction with Experts' Advice](https://mlsanity.com/paper/2206.00236/) (2022)
- [Data-Driven Subgroup Identification for Linear Regression](https://mlsanity.com/paper/2305.00195/) (2023)
- [On the Universal Near Optimality of Hedge in Combinatorial Settings](https://mlsanity.com/paper/2510.17099/) (2025)
- [Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant](https://mlsanity.com/paper/2609.27206/) (2026)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [A PDE approach for regret bounds under partial monitoring](https://mlsanity.com/paper/2209.01256/) (2022)

## Abstract (arXiv)

We prove non-asymptotic lower bounds on the expectation of the maximum of d independent Gaussian variables and the expectation of the maximum of d independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (asymptotically optimal) non-asymptotic lower bound on the minimax regret of online learning with expert advice.