A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions

Abstract

We consider reinforcement learning in changing Markov Decision Processes where both the state-transition probabilities and the reward functions may vary over time. For this problem setting, we propose an algorithm using a sliding window approach and provide performance guarantees for the regret evaluated against the optimal non-stationary policy. We also characterize the optimal window size suitable for our algorithm. These results are complemented by a sample complexity bound on the number of sub-optimal steps taken by the algorithm. Finally, we present some experimental results to support our theoretical analysis.

References in corpus (1)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

Cited by in corpus (14)

• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Optimizing for the Future in Non-Stationary MDPs
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimation
• Non-Stationary Delayed Bandits with Intermediate Observations
• Large Scale Markov Decision Processes with Changing Rewards
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting