Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
We introduce the Switching Non-Stationary Markov Decision Process (SNS-MDP) framework, in which the environment transitions among a finite set of MDPs governed by a latent Markov chain while the agent observes only the external state. We show that the long-term effect of this switching is equivalent to stationary dynamics parameterized by the stationary distribution of the hidden Markov chain. For fixed policies, we derive a closed-form expression for the SNS value function and prove that standard temporal-difference (TD) learning converges to it almost surely despite persistent non-stationarity. We further establish that policy iteration converges to the optimal policy of the equivalent averaged environment, and prove that tabular Q-learning converges almost surely to the optimal Q-function. The framework is validated on a wireless communication network with Markovian channel noise, demonstrating its practical efficacy for decision-making in rapidly time-varying systems.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 13 of its 34 references that are in the map. First posted on arXiv 24 Mar 2025.
Builds on
13 of 34 references.
References · 13
- 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
- 2020Gradient Surgery for Multi-Task Learningcited by 1,256
- 2019Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learningcited by 1,204
- 2021Multi-Task Reinforcement Learning with Context-based Representationscited by 174
- 2016Partially Observed Markov Decision Processes. Problem Sets and Internet Supplementcited by 34
- 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 33
- 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
- 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
- 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
- 2020Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Controlcited by 17
- 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
- 2022An Adaptive Deep RL Method for Non-Stationary Environments with Piecewise Stable Contextcited by 15
1 more
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.
- 2026Single or Multiple Policies for Phase-Structured Reinforcement Learning?2 Oct 2026
- 2026PriPG-RL: Privileged Planner-Guided Reinforcement Learning for Partially Observable Systems with Anytime-Feasible MPC9 Apr 2026
- 2025MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment12 Nov 2025
Similar, not cited
Close in wording, no citation either way
- 2025Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
- 2025Continuous-time reinforcement learning for optimal switching over multiple regimes
- 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
- 2026A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics
- 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
- 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
- 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments
- 2025Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration