  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.
