where \(m_\star^t\) is the payoff for the a posteriori best expert, at turn \(t\).
That's a strong non-asymptotic bound, which applies for any sequence of payoff functions, as long as the value for each expert is always in the range \([-1, 1]\). It's also pessimistic: the step size is fixed ahead of time, so the algorithm will hedge as defensively on "easy" inputs as it will against a worst-case adversary.
AdaHedge \cite{koolen2014} determines its step size adaptively, without knowing the time horizon (number of turns) nor the range of losses ahead of time. Assuming payoff are in the same range \([-1, 1]\), the regret for AdaHedge after \(T\) iterations is at most