Online learning with dynamics: A minimax perspective

Kush Bhatia, Karthik Sridharan

Introduction

In classical online learning, the environment is typically assumed to be "oblivious"—meaning the learner's past actions do not fundamentally alter the future state of the world. However, real-world systems, from autonomous drones navigating wind currents to recommendation engines shaping user preferences, are inherently dynamic. In these stateful environments, a single decision changes the trajectory of future states.

Standard metrics like "external regret" fail to capture the true cost of decisions in dynamic systems because they compare the learner to a fixed policy evaluated only on the states the learner actually encountered. To address this, researchers focus on Policy Regret, which measures the learner’s performance against the best fixed policy evaluated on the counterfactual states that would have occurred had that policy been used from the beginning.

This paper introduces a unified theoretical framework for online learning in stateful environments, utilizing a minimax perspective to establish the fundamental limits of learnability when dynamics are adversarial, time-varying, and potentially non-linear.

The Minimax Framework and The Dual Game

To characterize the fundamental limits of policy regret, the authors employ a minimax analysis. Instead of analyzing a specific algorithm, they analyze the problem's inherent difficulty by looking at a "reversed" interaction—the Dual Game. In this setup, the adversary first reveals a distribution over problem instances, and the learner responds. By leveraging minimax theorems, the authors can establish robust upper bounds on policy regret that apply regardless of the specific algorithm used.

To balance the tension between minimizing immediate loss and maintaining a stable state trajectory, the framework also analyzes a mini-batching strategy, where the learner commits to a single policy for a fixed window of time.

The Two Pillars of Learnability

A central contribution of the paper is proving that minimax policy regret can be upper-bounded by the sum of two distinct components. This two-term decomposition reveals that learnability in complex systems is dictated by:

  1. Sequential Rademacher Complexity: This term measures the "richness" or expressiveness of the policy class over time. A highly flexible policy class can adapt to many situations but is statistically harder to learn.
  2. Dynamic Stability: This term captures the deviation of the instantaneous loss from the counterfactual loss. It essentially quantifies the system's "memory" or state-evolution stability.

The paper formalizes the intuition that stability is a prerequisite for learning. If a system is highly chaotic—where a microscopic change in action leads to wildly divergent future states—policy regret cannot be minimized. The authors provide matching lower bounds, proving that both the complexity of the policy class and the stability of the dynamics are strictly necessary to guarantee learnability.

Unification and Key Results

Previously, problems like Online Linear Quadratic Regulators (LQR) and Online Markov Decision Processes (MDPs) were studied in isolation using disparate mathematical tools. This paper demonstrates that they are all special cases of a single minimax framework.

Key achievements of this unified approach include:

  • General Upper Bounds: The framework establishes a general rate for policy regret, recovering the optimal $\tilde{O}(\sqrt{T})$ regret rate for many standard problems.
  • Handling Non-Convexity: Unlike prior works that heavily rely on convex loss functions and linear dynamics, this minimax approach provides bounds for general, even non-convex functions, provided the complexity and stability terms remain bounded.
  • New Bounds for Non-Linear Systems: The authors derive tight regret bounds for the "Online Isotron with Dynamics," a novel problem featuring non-linear dynamics and non-convex losses that was previously unsolvable with existing techniques.
  • Robustness to Adaptive Adversaries: For the Online LQR problem, the framework provides guarantees against adaptive adversaries (who observe and react to the learner's past moves), a significant step up from previous works that only handled oblivious adversaries.

Limitations and Future Directions

While the paper provides a powerful theoretical foundation, it notes several limitations that pave the way for future research:

  • Non-Constructive Bounds: The primary upper bounds prove that a successful learning algorithm exists, but they do not inherently provide a computationally efficient recipe for implementing one.
  • Known Dynamics: The current framework assumes the transition function (the "physics" of the environment) is known to the learner. Extending this to "model-free" settings, where the learner must simultaneously learn the environment's dynamics and minimize regret, is a critical next step.
  • Noise Assumptions: The system assumes zero-mean additive noise. Exploring more complex, structured noise models will be necessary to apply these bounds to messier real-world scenarios.

Ultimately, this paper offers a vital theoretical stepping stone, proving that despite the chaos of dynamic, stateful environments, optimal learning is achievable when complexity and stability are properly balanced.

Summary updated

Abstract

We consider the problem of online learning with dynamics, where a learner interacts with a stateful environment over multiple rounds. In each round of the interaction, the learner selects a policy to deploy and incurs a cost that depends on both the chosen policy and current state of the world. The state-evolution dynamics and the costs are allowed to be time-varying, in a possibly adversarial way. In this setting, we study the problem of minimizing policy regret and provide non-constructive upper bounds on the minimax rate for the problem. Our main results provide sufficient conditions for online learnability for this setup with corresponding rates. The rates are characterized by: 1) a complexity term capturing the expressiveness of the underlying policy class under the dynamics of state change, and 2) a dynamics stability term measuring the deviation of the instantaneous loss from a certain counterfactual loss. Further, we provide matching lower bounds which show that both the complexity terms are indeed necessary. Our approach provides a unifying analysis that recovers regret bounds for several well studied problems including online learning with memory, online control of linear quadratic regulators, online Markov decision processes, and tracking adversarial targets. In addition, we show how our tools help obtain tight regret bounds for a new problems (with non-linear dynamics and non-convex losses) for which such bounds were not known prior to our work.
BibTeX
@inproceedings{bhatia2020online,
  author = {Kush Bhatia and Karthik Sridharan},
  title = {{Online learning with dynamics: A minimax perspective}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=gqV0R_TbPHt},
}
Figure