Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis
arXiv:2503.18607
The paper introduces a Switching Non-Stationary MDP framework where the environment alternates among a finite set of MDPs via a hidden Markov chain, and proves that standard TD learning, policy iteration, and Q‑learning converge to optimal solutions despite persistent non‑stationarity.
Abstract
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.
Extended version of a paper accepted at the 2026 IEEE Conference on Decision and Control (CDC). Contains complete proofs, background material, and full experimental details