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.

研究了在线随机环境下的 Hedge 算法行为，证明了降低学习率的任何时候版本，能够同时适应较容易的随机问题和顶峰问题，并与其他变体算法的表现有质的差异，最终讨论了该算法的局限性和 Stochastic 情况下双重遗憾边界带来的改进。