The paper introduces an optimal online learning algorithm for the non-parametric class of total-variation bounded sequences. Moreover, it shows that a class of well-known existing methods cannot be optimal, and that there is a separation between the achievable rates for estimation and prediction in terms of regret. These are all fundamental results, and the paper clearly discusses their connections to important developments in non-parametric statistical estimation. Comments for the final version: Please carefully consider the reviews, and take the (updated) comments into account when preparing the final version of the paper. In particular, please consider the dependence on B mentioned by reviewer #1. Note that there is already a well-known online learning algorithm called AROW (Crammer, Kulesza, Dredze, NeurIPS 2009), so please change the algorithm name from ARROWS to something else.