2016/08/29 by Ian Gemp, Sridhar Mahadevan, Gemp, Ian +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1608.07888
openalex publication_date 2016/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a new framework for analyzing and designing no-regret algorithms for dynamic (possibly adversarial) systems. The proposed framework generalizes the popular online convex optimization framework and extends it to its natural limit allowing it to capture a notion of regret that is intuitive for more general problems such as those encountered in game theory and variational inequalities. The framework hinges on a special choice of a system-wide loss function we have developed. Using this framework, we prove that a simple update scheme provides a no-regret algorithm for monotone systems. While previous results in game theory prove individual agents can enjoy unilateral no-regret guarantees, our result proves monotonicity sufficient for guaranteeing no-regret when considering the adjustments of multiple agent strategies in parallel. Furthermore, to our knowledge, this is the first framework to provide a suitable notion of regret for variational inequalities. Most importantly, our proposed framework ensures monotonicity a sufficient condition for employing multiple online learners safely in parallel.