  We study the online learnability of hypothesis classes with respect to
arbitrary, but bounded loss functions. No characterization of online
learnability is known at this level of generality. We give a new
scale-sensitive combinatorial dimension, named the sequential minimax
dimension, and show that it gives a tight quantitative characterization of
online learnability. In addition, we show that the sequential minimax dimension
subsumes most existing combinatorial dimensions in online learning theory.
