Open Problem: Is There an Online Learning Algorithm That Learns Whenever
  Online Learning Is Possible?
  This open problem asks whether there exists an online learning algorithm for
binary classification that guarantees, for all target concepts, to make a
sublinear number of mistakes, under only the assumption that the (possibly
random) sequence of points X allows that such a learning algorithm can exist
for that sequence. As a secondary problem, it also asks whether a specific
concise condition completely determines whether a given (possibly random)
sequence of points X admits the existence of online learning algorithms
guaranteeing a sublinear number of mistakes for all target concepts.
