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

2025/03/24 by Mohsen Amiri, Sindri Magnússon, Amiri, Mohsen +1 · 1 citation
#cs.LG #cs.AI

paper · pdf · doi:10.48550/arxiv.2503.18607

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.

Cited by

• MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment

Related

• Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
• Markov Decision Processes under External Temporal Processes
• Continuous-time reinforcement learning for optimal switching over multiple regimes
• A Sliding-Window Algorithm for Markov Decision Processes with\n Arbitrarily Changing Rewards and Transitions
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism