2019/02/19 by Ching-An Cheng, Cheng, Ching-An, Jonathan Lee +5 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Adaptive Dynamic Programming Control #Advanced Bandit Algorithms Research #COVID-19 epidemiological studies #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.1902.07286
openalex publication_date 2019/02/19 · openalex created_date 2020/07/02 · openalex updated_date 2026/07/28
Online learning is a powerful tool for analyzing iterative algorithms.\nHowever, the classic adversarial setup sometimes fails to capture certain\nregularity in online problems in practice. Motivated by this, we establish a\nnew setup, called Continuous Online Learning (COL), where the gradient of\nonline loss function changes continuously across rounds with respect to the\nlearner's decisions. We show that COL covers and more appropriately describes\nmany interesting applications, from general equilibrium problems (EPs) to\noptimization in episodic MDPs. In particular, we show monotone EPs admits a\nreduction to achieving sublinear static regret in COL. Using this new setup, we\nrevisit the difficulty of sublinear dynamic regret. We prove a fundamental\nequivalence between achieving sublinear dynamic regret in COL and solving\ncertain EPs. With this insight, we offer conditions for efficient algorithms\nthat achieve sublinear dynamic regret, even when the losses are chosen\nadaptively without any a priori variation budget. Furthermore, we show for COL\na reduction from dynamic regret to both static regret and convergence in the\nassociated EP, allowing us to analyze the dynamic regret of many existing\nalgorithms.\n