Online Learning With Dynamics: A Minimax Perspective

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 complexi

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keybhatia2020online

Related papers

• Implications Of Regret On Stability Of Linear Dynamical Systems (2022)6.34
• Fast Rates For Online Learning In Linearly Solvable Markov Decision Processes (2017)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• Information-theoretic Minimax Regret Bounds For Reinforcement Learning Based On Duality (2024)3.58
• Solving Robust Mdps Through No-regret Dynamics (2023)0.00
• Live In The Moment: Learning Dynamics Model Adapted To Evolving Policy (2022)0.00
• Learning In Markov Games With Adaptive Adversaries: Policy Regret, Fundamental Barriers, And Efficient Algorithms (2024)0.00