Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis

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.