Online learning with dynamics: A minimax perspective

Kush Bhatia, Karthik Sridharan

Abstract

We study 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.

Introduction

In classical online learning, a learner makes a prediction, suffers a loss, and moves to the next round in a stateless environment. However, real-world applications—ranging from recommendation engines to autonomous robotics—rarely operate in a vacuum. Decisions form a feedback loop: the action taken today fundamentally alters the state of the environment tomorrow. This paper addresses the challenge of "online learning with dynamics," where the learner's decisions actively change the future state of the world.

To evaluate performance in these stateful environments, researchers utilize policy regret. Unlike standard regret, which compares a learner to the best fixed action in hindsight, policy regret compares the learner to the best fixed policy in hindsight. This comparison is evaluated against the counterfactual states that would have been visited had that optimal policy been deployed from the start. While policy regret has been explored in specific contexts like linear dynamical systems, this work seeks to establish the general, information-theoretic conditions for learnability across arbitrary policy classes, adversarial losses, and complex state dynamics.

Theoretical Framework: The Minimax Perspective

This research employs a non-constructive minimax analysis to identify the fundamental limits of learning. The goal is to determine the policy regret of the optimal learning algorithm against a worst-case adversary.

By applying von Neumann’s minimax theorem, the problem is transformed into a "Dual Game." In this reformulated setting, the adversary reveals a distribution over instances first, allowing the learner to respond. The authors analyze the performance of Empirical Risk Minimization (ERM) strategies—specifically regularized and mini-batched ERM—within this dual game. This lens allows for the mathematical decomposition of the minimax policy regret into two essential components:

  1. Sequential Rademacher Complexity: A measure that captures the statistical expressiveness or capacity of the policy class within a sequential context.
  2. Dynamic Stability: A novel metric measuring how much the algorithm's instantaneous loss deviates from the counterfactual loss it would have incurred had it committed to its current policy from the beginning of the interaction.

The Two Pillars of Learnability

The core contribution of this work is the proof that learnability in dynamical systems requires a delicate balance between these two tensions. A learner must utilize a policy class that is not overly complex (bounded Sequential Rademacher complexity), while the algorithm itself must ensure it does not perturb the environment's state too drastically (bounded Dynamic Stability).

By establishing these pillars, the framework serves as a "grand unifier" for the field. The authors demonstrate that several previously distinct problems are special cases of this broader theory, including:

  • Online Markov Decision Processes (MDPs)
  • Online Linear Quadratic Regulators (LQR)
  • Online Learning with Memory

Furthermore, because this framework does not rely on the mathematical conveniences of linear systems or convex losses, it successfully provides tight regret bounds for problems involving non-linear dynamics and non-convex losses—areas where previous theoretical approaches often failed.

Key Results and Rates

The authors established a general upper bound on minimax policy regret based on the sum of the Sequential Rademacher complexity and the Dynamic Stability term. Matching lower bounds confirm that both terms are strictly necessary for guaranteed learnability.

Using this framework, the research derives specific $\tilde{O}(\sqrt{T})$ regret bounds (where $T$ is the number of time steps) for several settings:

  • Online Isotron with dynamics: A semi-parametric model.
  • Online MDPs: Recovering known rates even under stronger, adaptive adversaries.
  • Online LQR: Covering both standard and adversarial disturbance scenarios.
  • Online Non-linear Control: Providing novel, non-degenerate regret bounds for a previously unsolved problem class.

Limitations and Future Directions

While the paper establishes a robust theoretical foundation, it faces two primary limitations. First, the analysis is non-constructive; it proves that an algorithm with a specific regret rate exists but does not provide a computationally efficient method to implement it in all primal settings. Second, the generalized framework currently yields a $O(\sqrt{T})$ bound for certain problems, such as tracking adversarial targets, where specialized algorithms are known to achieve "fast rates" of $O(\log^2 T)$. Refining the minimax framework to capture these accelerated rates remains a significant open challenge for future research.

Summary updated

Abstract

We study 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},
}

Loading related content...

Figure