Abstract: Classical online learning algorithms make a static assumption on the nature of the data generating process (either stochastic or adversarial) and the nature of the offline benchmark to measure performance. Neither of these assumptions are well-justified in practice. While assuming a probability model on the data could lead to suboptimal performance in practice, worst-case adversarially robust algorithms may be unnecessarily pessimistic.