Online Learning with Continuous Variations: Dynamic Regret and Reductions

Ching-An Cheng, Jonathan Lee, Ken Goldberg, Byron Boots

Abstract

Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup fails to capture regularity that can exist in practice. Motivated by this observation, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function changes continuously across rounds with respect to the learner’s decisions. We show that COL appropriately describes many interesting applications, from general equilibrium problems (EPs) to optimization in episodic MDPs. Using this new setup, we revisit the difficulty of sublinear dynamic regret. We prove a fundamental equivalence between achieving sublinear dynamic regret in COL and solving certain EPs. With this insight, we offer conditions for efficient algorithms that achieve sublinear dynamic regret, even when the losses are chosen adaptively without any a priori variation budget. Furthermore, we show for COL a reduction from dynamic regret to both static regret and convergence in the associated EP, allowing us to analyze the dynamic regret of many existing algorithms.

Introduction

In classical online learning, a learner makes a sequence of decisions to minimize regret. While static regret—comparing performance against the best fixed decision in hindsight—is well-studied, many modern applications in robotics and reinforcement learning require minimizing dynamic regret. The goal is to remain nearly optimal at every round against a sequence of time-varying optima.

In a purely adversarial setting, sublinear dynamic regret is generally impossible without assuming a "variation budget" that limits how much the environment can change. However, in many real-world scenarios, the environment's change is not arbitrary; it is often a continuous response to the learner's own actions. This paper, presented at AISTATS 2020, introduces Continuous Online Learning (COL) to bridge this gap, modeling environments where small changes in decisions lead to small changes in loss functions.

The Continuous Online Learning (COL) Framework

The COL framework is defined by a "bifunction" $f(x, x')$, where $x$ represents the learner's current state or decision (the query) and $x'$ is the decision argument. In each round $n$, the learner selects $x_n$, and the environment reveals a loss function $l_n(\cdot) = f_{x_n}(\cdot)$.

To analyze this setting, the authors introduce $(\alpha, \beta)$-regularity:

  1. $\alpha$ (Strong Convexity): Measures the curvature of the loss function, facilitating the identification of a minimum.
  2. $\beta$ (Regularity Constant): Measures the sensitivity of the loss gradient to changes in the learner's decision.

The ratio $\beta/\alpha$ serves as a critical stability metric. When the environment is sufficiently stable ($\alpha > \beta$), sublinear dynamic regret becomes achievable.

Theoretical Insights and Reductions

A primary contribution of this work is the link between COL and Equilibrium Problems (EPs) and Variational Inequalities (VIs). The authors prove a fundamental equivalence: achieving sublinear dynamic regret in COL is as difficult as solving PPAD-complete problems, such as finding a Nash Equilibrium.

Despite this inherent complexity, the paper provides a powerful Reduction Principle. It demonstrates that dynamic regret can be bounded by a combination of static regret and the convergence rate to an equilibrium point. This allows for the application of standard online learning algorithms, like Mirror Descent, to continuous environments with guaranteed dynamic performance.

Unlike previous models that rely on exogenous variation budgets, COL treats variation as endogenous. The environment's change is a direct consequence of the interaction between the learner and the bifunction, making the resulting bounds more interpretable for adaptive scenarios.

Key Results

The framework demonstrates that common algorithms, including Greedy Updates and Mirror Descent, can achieve sublinear dynamic regret—ranging from $O(\sqrt{N})$ to $O(1)$—without prior knowledge of a variation budget. Furthermore, the COL setup is robust to stochastic or adversarial noise in the gradients, provided the underlying "true" loss function maintains its continuity properties. For "predictable" sequences where the environment has a non-stationary component, Mirror Descent remains effective at tracking the optimal path.

Conclusion and Future Directions

While COL provides a robust framework for analyzing adaptive environments, it relies on the assumption of $(\alpha, \beta)$-regularity, which may be challenging to verify in high-dimensional deep learning systems. Future work may explore "history-dependent bifunctions" to account for environments with memory, where losses depend on the full sequence of past decisions rather than just the current state. Additionally, establishing formal lower bounds for predictable online learning remains an open theoretical challenge.

Summary updated

Abstract

Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup fails to capture regularity that can exist in practice. Motivated by this observation, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function changes continuously across rounds with respect to the learner’s decisions. We show that COL appropriately describes many interesting applications, from general equilibrium problems (EPs) to optimization in episodic MDPs. Using this new setup, we revisit the difficulty of sublinear dynamic regret. We prove a fundamental equivalence between achieving sublinear dynamic regret in COL and solving certain EPs. With this insight, we offer conditions for efficient algorithms that achieve sublinear dynamic regret, even when the losses are chosen adaptively without any a priori variation budget. Furthermore, we show for COL a reduction from dynamic regret to both static regret and convergence in the associated EP, allowing us to analyze the dynamic regret of many existing algorithms.
BibTeX
@inproceedings{cheng2020online,
  author = {Ching-An Cheng and Jonathan Lee and Ken Goldberg and Byron Boots},
  title = {{Online Learning with Continuous Variations: Dynamic Regret and Reductions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=DaygboCkRiD},
}
Figure