Dynamic Regret of Policy Optimization in Non-stationary Environments

Abstract

We consider reinforcement learning (RL) in episodic MDPs with adversarial full-information reward feedback and unknown fixed transition kernels. We propose two model-free policy optimization algorithms, POWER and POWER++, and establish guarantees for their dynamic regret. Compared with the classical notion of static regret, dynamic regret is a stronger notion as it explicitly accounts for the non-stationarity of environments. The dynamic regret attained by the proposed algorithms interpolates between different regimes of non-stationarity, and moreover satisfies a notion of adaptive (near-)optimality, in the sense that it matches the (near-)optimal static regret under slow-changing environments. The dynamic regret bound features two components, one arising from exploration, which deals with the uncertainty of transition kernels, and the other arising from adaptation, which deals with non-stationary environments. Specifically, we show that POWER++ improves over POWER on the second component of the dynamic regret by actively adapting to non-stationarity through prediction. To the best of our knowledge, our work is the first dynamic regret analysis of model-free RL algorithms in non-stationary environments.

References in corpus (22)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• RL${}^2$: Fast Reinforcement Learning via Slow Reinforcement Learning
• Learning to reinforcement learn
• A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environments
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Fast Convergence of Regularized Learning in Games
• Efficient Contextual Bandits in Non-stationary Worlds
• Weighted Linear Bandits for Non-Stationary Environments
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Dynamic Regret of Strongly Adaptive Methods
• A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
• Variational Regret Bounds for Reinforcement Learning
• Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits
• Learning to Collaborate in Markov Decision Processes
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously
• Bandit Convex Optimization in Non-stationary Environments
• Optimistic Policy Optimization with Bandit Feedback
• Multi-agent online learning in time-varying games
• Proximal Online Gradient is Optimum for Dynamic Regret
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• Understand Dynamic Regret with Switching Cost for Online Decision Making

Cited by in corpus (5)

• Nonstationary Reinforcement Learning with Linear Function Approximation
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Provable Fictitious Play for General Mean-Field Games
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Revisiting Clustering of Neural Bandits: Selective Reinitialization for Mitigating Loss of Plasticity