Empirical Bernstein Inequality for Martingales : Application to Online Learning

In this article we present a new empirical Bernstein inequality for bounded martingale difference sequences. This inequality refines the one by Freedman [1975] and is then used in order to bound the average risk of the hypotheses during an online learning process. We show theoretical and empirical evidences of the tightness of our result compared with the state of the art bound provided by Cesa-Bianchi and Gentile [2008].