# On the optimality of the Hedge algorithm in the stochastic regime

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2018.

## Built on by (most cited first, 30 of 33)

- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [Multiplicative Reweighting for Robust Neural Network Optimization](https://mlsanity.com/paper/2102.12192/) (2021)
- [Contextual Active Model Selection](https://mlsanity.com/paper/2207.06030/) (2022)
- [Sequential Ski Rental Problem](https://mlsanity.com/paper/2104.06050/) (2021)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)
- [Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment](https://mlsanity.com/paper/2102.07929/) (2021)
- [Online Learning with Bounded Recall](https://mlsanity.com/paper/2205.14519/) (2022)
- [Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model](https://mlsanity.com/paper/2207.05437/) (2022)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [On the Universal Near Optimality of Hedge in Combinatorial Settings](https://mlsanity.com/paper/2510.17099/) (2025)
- [Best-Case Lower Bounds in Online Learning](https://mlsanity.com/paper/2106.12688/) (2021)
- [Single Trajectory Conformal Prediction](https://mlsanity.com/paper/2406.01570/) (2024)
- [Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy](https://mlsanity.com/paper/2502.10997/) (2025)
- [Detecting Suspicious Events in Fast Information Flows](https://mlsanity.com/paper/2101.02424/) (2021)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)
- [The Delusional Hedge Algorithm as a Model of Human Learning from Diverse Opinions](https://mlsanity.com/paper/2402.13927/) (2024)
- [The SMART approach to instance-optimal online learning](https://mlsanity.com/paper/2402.17720/) (2024)
- [OEUVRE: OnlinE Unbiased Variance-Reduced loss Estimation](https://mlsanity.com/paper/2510.22744/) (2025)
- [Block-Norm Geometries for Online Mirror Descent with Sparse Losses](https://mlsanity.com/paper/2602.13177/) (2026)

## Abstract (arXiv)

In this paper, we study the behavior of the Hedge algorithm in the online stochastic setting. We prove that anytime Hedge with decreasing learning rate, which is one of the simplest algorithm for the problem of prediction with expert advice, is surprisingly both worst-case optimal and adaptive to the easier stochastic and adversarial with a gap problems. This shows that, in spite of its small, non-adaptive learning rate, Hedge possesses the same optimal regret guarantee in the stochastic case as recently introduced adaptive algorithms. Moreover, our analysis exhibits qualitative differences with other variants of the Hedge algorithm, such as the fixed-horizon version (with constant learning rate) and the one based on the so-called "doubling trick", both of which fail to adapt to the easier stochastic setting. Finally, we discuss the limitations of anytime Hedge and the improvements provided by second-order regret bounds in the stochastic case.