Online learning with dynamics: A minimax perspective

Understand

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.