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

arXiv: https://arxiv.org/abs/1805.10066 · HTML: https://mlsanity.com/paper/1805.10066/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2018.

## Built on by (most cited first, 30 of 30)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2006.16785/) (2020)
- [Dynamics-Adaptive Continual Reinforcement Learning via Progressive Contextualization](https://mlsanity.com/paper/2209.00347/) (2022)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions](https://mlsanity.com/paper/2305.17380/) (2023)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)
- [Dealing with Non-Stationarity in MARL via Trust-Region Decomposition](https://mlsanity.com/paper/2102.10616/) (2021)
- [Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems](https://mlsanity.com/paper/2111.03772/) (2021)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [Action Pick-up in Dynamic Action Space Reinforcement Learning](https://mlsanity.com/paper/2304.00873/) (2023)
- [Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes](https://mlsanity.com/paper/2304.00232/) (2023)
- [Provably Efficient Algorithm for Nonstationary Low-Rank MDPs](https://mlsanity.com/paper/2308.05471/) (2023)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [Time-Constrained Robust MDPs](https://mlsanity.com/paper/2406.08395/) (2024)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)
- [Achieve Performatively Optimal Policy for Performative Reinforcement Learning](https://mlsanity.com/paper/2510.04430/) (2025)
- [Online Reinforcement Learning in Periodic MDP](https://mlsanity.com/paper/2303.09629/) (2023)
- [Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2510.03181/) (2025)
- [Online Reinforcement Learning for Periodic MDP](https://mlsanity.com/paper/2207.12045/) (2022)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee](https://mlsanity.com/paper/2508.10804/) (2025)
- [DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees](https://mlsanity.com/paper/2604.16684/) (2026)

## 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.