Unified method improves online learning and game theory results
A Simple and Unified Method for Gradient-Variation Regret
Machine Learning
Summary
Some computer programs learn better by adjusting their predictions based on how things change over time or how complicated the problem is. The authors propose a new, simple way to help these programs learn more effectively in two different settings: one where the situation changes, and one where the difficulty level is unknown. Their approach uses an extra part that gently limits how much the choices can jump between steps. This idea improves results in online decision-making and games, making learning strategies better without complicated adjustments.
What this means in practice
- •For machine learning engineers: Develop adaptive learning algorithms that handle changing data distributions with improved performance guarantees.
- •For game developers: Enhance automated strategies in online games by improving the theoretical guarantees of learning algorithms used for decision making.
Authors
Hang Yu, Peng Zhao
Abstract
Gradient-variation online learning has attracted increasing attention for its connections to game theory and optimization. It has been studied in both non-stationary online learning, which aims to minimize dynamic regret against time-varying comparator sequences, and universal online learning, which seeks to adapt to unknown loss curvature. Prior work obtained gradient-variation bounds using different techniques tailored to each setting. We propose a simple and unified method based on surrogate losses with a quadratic penalty on decision movement, yielding gradient-variation bounds in both settings. For non-stationary online learning, the method induces an optimistic-to-gradient-variation reduction, enabling a broad class of algorithms to match the rate established by Zhao et al. (2024). For universal online learning, it yields a simple algorithm that matches the optimal universal regret bounds of Yan et al. (2024) while relaxing the extended smoothness assumption. Finally, we apply our method to online games and improve on existing guarantees.