which is only slightly worse than the MWU bound… and could be much better for easier instances. The fact that AdaHedge adapts to the range of payoff isn't that interesting: the actual range will pretty much always be \([-1, 1]\) for our decomposition application. Not having to specify the horizon is more useful: it means that, on easier instances, we will be able to stop AdaHedge earlier than the worst-case iteration bound.

Note 2020-12-20: [AdaNormalHedge](https://arxiv.org/abs/1502.05934) is similarly parameter-free, and naturally deals with constraint generation (and, thus column generation).

The Adaptive Exponentiated Gradient - Path (AEG-Path) algorithm \cite{liang2014} exploit a finer grained measure of hardness, the sum of absolute difference between the payoff value for consecutive iterations, for each expert. However, if the time horizon is not fixed, AEG-Path's constant multiplicative factor on top of the usual \(\sqrt{\sum_{t=1}^T \mathrm{hardness}_t \ln k}\) is 10. The next section will show how this increase, from 2 to 10, means that AEG-Path would need, in the worst case, 25 times as many iterations to reach a nearly feasible solution of the same quality as AdaHedge or MWU.

Feasibility for a linear program of the form