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

2018/05/25 by Pratik Gajane, Gajane, Pratik, Ronald Ortner +3 · 11 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Smart Grid Energy Management #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1805.10066

arxiv created 2018/05/25 · openalex publication_date 2018/05/25 · arxiv updated 2018/05/28 · openalex created_date 2022/09/11 · openalex updated_date 2026/07/28

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.

Citations

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

Cited by

• Achieve Performatively Optimal Policy for Performative Reinforcement Learning
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Large Scale Markov Decision Processes with Changing Rewards
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Age-of-information minimization under energy harvesting and non-stationary environment
• Natural Policy Gradient for Average Reward Non-Stationary RL

Related

• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Markov Decision Processes under External Temporal Processes
• Variational Regret Bounds for Reinforcement Learning
• On Reward Structures of Markov Decision Processes
• Logarithmic regret bounds for continuous-time average-reward Markov decision processes