Abstract
Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup sometimes fails to capture certain regularity in online problems in practice. Motivated by this, 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 covers and more appropriately describes many interesting applications, from general equilibrium problems (EPs) to optimization in episodic MDPs. In particular, we show monotone EPs admits a reduction to achieving sublinear static regret in COL. 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 standard online learning, a learner makes a sequence of decisions while an opponent chooses loss functions. Performance is traditionally measured by static regret, which compares the learner's cumulative loss to that of the single best fixed decision in hindsight. However, in dynamic environments like robotics or imitation learning, a more ambitious metric is required: dynamic regret. This metric compares the learner's decision at each round to the optimal decision for that specific round.
The primary challenge in minimizing dynamic regret is that in a purely adversarial setting, it grows linearly. Previous attempts to address this often relied on a "variation budget"—a predefined limit on how much the environment can change. However, in practice, environments are often adaptive, changing in response to the learner's actions. In such cases, the variation budget is unknown and impossible to bound a priori. This paper introduces Continuous Online Learning (COL) to model these interactions naturally and identify conditions where dynamic regret can be minimized without external budgets.
The Continuous Online Learning (COL) Framework
The authors propose COL as a bridge between theoretical online learning and practical iterative algorithms. In this setup, the loss function at each round $n$ is determined by a "bifunction" $f(x, x')$. When the learner chooses $x_n$, the opponent responds with a loss function $l_n(\cdot) = f(x_n, \cdot)$.
The "continuous" nature of the framework implies that small changes in the learner's decisions lead to only small changes in the resulting loss functions. This continuity allows for a more nuanced analysis of how learner-environment feedback loops affect regret.
Theoretical Equivalence and Complexity
A key methodological contribution of the paper is the proof of Equivalence Theorems. The authors demonstrate that achieving sublinear dynamic regret in COL is mathematically equivalent to solving:
- Equilibrium Problems (EPs)
- Variational Inequalities (VIs)
- Fixed-Point (FP) problems
This equivalence reveals the inherent complexity of the task. The paper shows that minimizing dynamic regret in the general COL setting is PPAD-complete. This implies that, in the worst case, finding an efficient algorithm is as difficult as finding a Nash equilibrium in a complex game, requiring polynomial dependency on the problem's dimension.
Algorithmic Guarantees: The $\alpha$ vs. $\beta$ Balance
To find tractable solutions, the authors define a class of "nice" problems characterized by $(\alpha, \beta)$-regularity. Here, $\alpha$ represents the strong convexity of the loss (how strongly the learner is pulled toward a local optimum), and $\beta$ represents the Lipschitz continuity of the environment's response (how much the environment "drifts" when the learner moves).
The feasibility of learning depends on the ratio between these two parameters:
- Stable Problems ($\alpha > \beta$): When the learner's optimization is stronger than the environment's drift, simple algorithms like Greedy Update or Online Mirror Descent can achieve constant ($O(1)$) dynamic regret in deterministic settings.
- Stochastic Settings: When feedback is noisy, the framework achieves a dynamic regret rate of $O(\sqrt{N})$, matching the gold standard for online learning.
Reductions and Practical Implications
The paper provides a formal reduction framework, showing that for regular problems, achieving sublinear dynamic regret is no harder than achieving sublinear static regret and ensuring convergence in the associated equilibrium problem.
This theoretical lens offers new explanations for the success of existing practical algorithms. For instance, the authors show that popular imitation learning algorithms like DAgger are essentially solving a COL problem. By framing these algorithms within the COL setup, their convergence properties can be more rigorously analyzed and understood.
Conclusion and Future Work
By bridging online learning and equilibrium problems, the COL framework provides a robust way to analyze dynamic regret in adaptive environments without requiring arbitrary variation budgets. While the current model assumes history-independence (the opponent responds only to the current decision), it sets the stage for future research into environments with memory. Additionally, the case where $\beta > \alpha$ (where the environment drifts faster than the learner can optimize) remains an open challenge, potentially requiring "optimistic" online learning methods that attempt to predict future loss functions.
Summary updated