# On the Universal Near Optimality of Hedge in Combinatorial Settings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 20 Oct 2025.

## Builds on (most cited first, 15 of 15)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice](https://mlsanity.com/paper/1511.02176/) (2015)
- [Tight Bounds for Bandit Combinatorial Optimization](https://mlsanity.com/paper/1702.07539/) (2017)
- [Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries](https://mlsanity.com/paper/2504.00461/) (2025)
- [From Duels to Battefields: Computing Equilibria of Blotto and Other Games](https://mlsanity.com/paper/1603.00119/) (2016)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [Online Dynamic Programming](https://mlsanity.com/paper/1706.00834/) (2017)
- [Combinatorial Bandits for Sequential Learning in Colonel Blotto Games](https://mlsanity.com/paper/1909.04912/) (2019)
- [On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games](https://mlsanity.com/paper/2410.23398/) (2024)

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

- [On the Power of Adaptivity for varepsilon-Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2605.15663/) (2026)
- [Truthful Online Preference Aggregation for LLM Fine-Tuning in Mobile Crowdsourcing](https://mlsanity.com/paper/2605.24052/) (2026)

## Abstract (arXiv)

In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector boldsymbolxt from a set X subseteq 0,1d, observes a full loss vector boldsymbolyt ∈ ℝd, and incurs a loss langle boldsymbolxt, boldsymbolyt rangle ∈ [-1,1]. This setting captures several important problems, including extensive-form games, resource allocation, m-sets, online multitask learning, and shortest-path problems on directed acyclic graphs (DAGs). It is well known that Hedge achieves a regret of Obig(√T log |X|big) after T rounds of interaction. In this paper, we ask whether Hedge is optimal across all combinatorial settings. To that end, we show that for any X subseteq 0,1d, Hedge is near-optimal--specifically, up to a √log d factor--by establishing a lower bound of Omegabig(√T log(|X|)/log dbig) that holds for any algorithm. We then identify a natural class of combinatorial sets--namely, m-sets with log d ≤ m ≤ √d--for which this lower bound is tight, and for which Hedge is provably suboptimal by a factor of exactly √log d. At the same time, we show that Hedge is optimal for online multitask learning, a generalization of the classical K-experts problem. Finally, we leverage the near-optimality of Hedge to establish the existence of a near-optimal regularizer for online shortest-path problems in DAGs--a setting that subsumes a broad range of combinatorial domains. Specifically, we show that the classical Online Mirror Descent (OMD) algorithm, when instantiated with the dilated entropy regularizer, is iterate-equivalent to Hedge, and therefore inherits its near-optimal regret guarantees for DAGs.