mlsanityData to 7 Oct 2026

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

arXiv 1805.10066 ↗First posted 25 May 2018cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 May 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 5; 2022: 5; 2023: 9; 2024: 4; 2025: 4; 2026: 1.

29 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2022Performative Reinforcement Learningcited by 25
  4. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  5. 2020Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learningcited by 15
  6. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  7. 2022Dynamics-Adaptive Continual Reinforcement Learning via Progressive Contextualizationcited by 13
  8. 2023Smooth Non-Stationary Banditscited by 13
  9. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  10. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  11. 2023Decision-Making Under Uncertainty: Beyond Probabilitiescited by 8
  12. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
17 more
  1. 2021Dealing with Non-Stationarity in MARL via Trust-Region Decompositioncited by 5
  2. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  3. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  4. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  5. 2023Action Pick-up in Dynamic Action Space Reinforcement Learningcited by 3
  6. 2023Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processescited by 2
  7. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  8. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  9. 2024Time-Constrained Robust MDPscited by 2
  10. 2024Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Informationcited by 2
  11. 2025Achieve Performatively Optimal Policy for Performative Reinforcement Learningcited by 2
  12. 2025Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learningcited by 1
  13. 2022Online Reinforcement Learning for Periodic MDPcited by 0
  14. 2023Online Reinforcement Learning in Periodic MDPcited by 0
  15. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  16. 2025Non-Stationary Restless Multi-Armed Bandits with Provable Guaranteecited by 0
  17. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0