1 Introduction↩︎

Reinforcement Learning (RL) is a powerful framework for training agents to make sequential decisions by learning from interactions with their environment. In standard RL settings, the environment is often assumed to be stationary, meaning that the transition dynamics and reward functions remain unchanged over time. This assumption simplifies analysis and algorithm design, allowing for the application of well-established techniques for policy optimization and convergence guarantees. However, many real-world problems are non-stationary, where the environment’s dynamics and reward structures evolve over time, potentially changing at every iteration.

Non-stationarity in reinforcement learning introduces significant challenges, as the evolving nature of the environment can make it difficult for agents to maintain effective policies over time. If the environment changes in an unconstrained or arbitrary manner, it becomes impossible for the agent to learn an optimal policy, or even estimate the value of a policy, since past experiences may no longer be relevant for future decision-making. To enable learning in non-stationary settings, either the changes in the environment must occur gradually, allowing the agent enough time to adapt to the new dynamics, or there must be some underlying structure in the non-stationarity that can be exploited.

In this paper, we propose a novel structured form of non-stationarity that both realistically models real-world challenges and can be exploited for analysis and algorithm development. Specifically, we introduce the framework of SNS-MDPs. In this setting, the environment can change at each iteration, switching among a finite set of distinct environments, each characterized by its own transition probabilities and reward functions. The differences between these environments can be arbitrarily large, capturing a wide range of scenarios. A key feature is that the agent does not know, and cannot measure or observe which environment it is currently in. Instead, the switches between environments follow a Markov chain, providing a systematic way to model the transitions and allowing for more tractable analysis and algorithm design.

This structure captures many real-world scenarios where the underlying conditions change based on recent history, even though the agent cannot directly observe the current environment. For instance, in communication networks, the quality of the network can shift between different modes, such as high congestion during peak hours and smoother operation during off-peak hours, depending on factors like time of day and recent traffic patterns [1], [2]. Although the agent does not know the exact congestion state, the likelihood of changes in network conditions follows a predictable pattern based on prior states, making the transitions Markovian. Similarly, in financial markets, shifts between regimes of low and high volatility or bull and bear markets occur in response to economic indicators, recent trends, or market events [2], [3]. While an investor cannot observe the true state of the market regime directly, the changes exhibit a form of structure that depends on recent conditions, following a Markov process. The main contributions of this paper are as follows:

1. We introduce the novel framework of SNS-MDP, which models non-stationary environments by allowing the underlying dynamics and rewards to change according to a Markov chain.

2. For the case of fixed policies or Markov Reward Processes (MRPs), we define an SNS value function that remains invariant to the environmental state and show that it has a closed-form expression determined by the statistical properties of the Markov chain.

3. We prove that, despite the non-stationarity, TD-learning algorithms converge with probability one to the SNS value function defined in bullet 2 under a fixed policy.

4. We demonstrate that policy improvement can be implemented within this framework, and prove that the policy iteration algorithm converges to the optimal policy for SNS-MDPs.

5. We prove that, even in the presence of non-stationarity, Q-learning converge probability one to an on optimal SNS-MDP Q-table, provided a properly fixed behavioral policy is used.

6. Finally, we illustrate the practicality of SNS-MDPs through an example in communication networks, where channel noise follows a Markov chain, demonstrating the framework’s effectiveness in optimizing decision-making in non-stationary settings.

A shortened version of this paper has been accepted for publication at the 2026 IEEE Conference on Decision and Control (CDC) [4]. This manuscript is the extended version, containing the complete proofs of all results, the supporting background on Markov chains and MRPs, and the full experimental details in the supplementary sections.

2 Related Work↩︎

Reinforcement learning in non-stationary Markov Decision Processes (MDPs) has been explored in previous research. Here, we review the most relevant studies and approaches that relate to our work.

Partially Observable Markov Decision Processes (POMDPs) involve scenarios where the agent cannot fully observe the underlying state [5], [6]. Although the core dynamics may be stationary, non-stationarity can arise through variations in the observable components, which provide only partial information about the true state of the environment. While POMDPs share some similarities with our SNS-MDPs, they typically rely on the agent’s ability to use observable information to infer the hidden states and adapt accordingly. In contrast, our work diverges from this paradigm by considering scenarios where the agent cannot infer the latent modes of the environment, making it necessary to develop alternative strategies for dealing with evolving dynamics without assuming access to a structured latent representation.

Another line of research in reinforcement learning focuses on non-stationary environments where the dynamics and rewards can change freely over time, with the impact of these changes reflected in the regret [7]–[14]. Specifically, the regret is often bounded by the total variation in the transition probabilities and rewards across different MDPs. While these approaches are valuable, they differ significantly from our model due to the lack of structure in the changes; the MDPs can evolve arbitrarily, leading to increased regret. In contrast, our work on SNS-MDPs assumes that changes in the environment follow a Markov chain, which allows us to study the convergence of value and Q-functions under a fixed policy and to characterize these functions based on the statistical properties of the environmental Markov chain. Such analysis is not feasible with more unstructured changes, where value functions may not converge, although regret can still be bounded by the total variation. Additionally, these prior works typically address episodic tasks, whereas our focus is on continuing (infinite horizon) tasks.

Meta-RL and multi-task RL address non-stationarity by learning strategies for rapid adaptation across a distribution of tasks, typically assuming episodic settings [15]–[19]. Their goal is to optimize for quick adaptation based on prior task experience, focusing on task-specific adaptation rather than long-term dynamics. In contrast, our setup is fundamentally different, as we focus on continual tasks where the transitions can change at each time step, not just between tasks, requiring the agent to adapt continuously to evolving dynamics.

The most relevant papers to our work are probably [20]–[23]. Specifically, the study in [20], where their term "context" aligns with what we refer to as the "environment," differs primarily in terms of the observability of this context. Indeed, they assume that the context is known to the agent, is influenced by the algorithm’s history, and can be directly incorporated into decision-making. This assumption represents a fundamental distinction from our work. On the other hand, the study in [21] assumes full knowledge of the MDP dynamics and rewards, focusing on average reward MDPs. Consequently, this differs from our setting, where such information is unavailable, and the agent must learn and make decisions under uncertainty. The key difference between our work and [22] lies in their assumption that certain information about the context (environment) is available, such as partial knowledge of the environment and the segment length (the duration for which the context remains constant), which they use to infer the latent state of the context. However, this information may not always be accessible, especially when it is only available during training. In contrast, our framework assumes that the context is entirely unobservable, with no direct or indirect access to it. Furthermore, while [22] considers the context to either change abruptly or remain constant for a known number of time steps, occurring probabilistically, we model context transitions using a Markov chain, where each state can persist or transition based on predefined probabilities. Thus, their framework can be viewed as a special case of the more general Markov chain model used in our work. In [23], the setup is similar to ours, particularly in considering a scenario where the reward function changes at each iteration, though the transition probabilities are stationary. Therefore, this scenario is a special case of our work. Generally, in MDPs, dealing with changing reward functions is more straightforward than handling varying transition probabilities, as the latter directly alters the stochastic process. Moreover,  [23] is limited to policy evaluation and does not consider other RL tasks.

3 Notation↩︎

We represent non-random vectors using lowercase bold letters and non-random matrices using uppercase bold letters. For example, a vector \(\mathbf{v} \in \mathbb{R}^n\) and a matrix \(\mathbf{A} \in \mathbb{R}^{n \times m}\) are typical representations. The expression \(\mathbf{v}(i)\) indicates the \(i\)-th component of the vector \(\mathbf{v}\), and \(\mathbf{A}(i, j)\) refers to the element located at the \(i\)-th row and \(j\)-th column of the matrix \(\mathbf{A}\). For vectors, \(\mathbf{x} \in \mathbb{R}^n\), the function \(\texttt{Diag}(\mathbf{x})\) denotes the \(n \times n\) diagonal matrix with the elements of \(\mathbf{x}\) along its diagonal. Sets are denoted using a calligraphic typeface. We use the notation \(X \sim p(\cdot)\) to denote that \(X\) is a random variable sampled from the probability distribution \(p(\cdot)\). The probability of \(X\) being in \(\mathcal{X}\) is expressed as \({\mathbf{Pr}\left[X \in \mathcal{X}\right]}\).

4 Markov Decision Processes (MDPs)↩︎

This paper considers reinforcement learning algorithms in MDPs. A stationary MDP is defined by the tuple \((\mathcal{S}, \mathcal{A}, p(\cdot), \mathbf{r}(\cdot), \gamma)\), where \(\mathcal{S}\) denotes the set of states, \(\mathcal{A}\) is the set of actions, \(p(s' \mid s, a)\) represents the transition probability of moving to state \(s'\) from state \(s\) after taking action \(a\), \(\mathbf{r}(s, a)\) is the reward received in state \(s\) and action \(a\), and \(\gamma \in [0, 1)\) is the discount factor that determines the importance of future rewards.

A policy \(\mu: \mathcal{S} \rightarrow \Delta(\mathcal{A})\) defines a distribution over the action set \(\mathcal{A}\) for a given state \(s\), where \(\mu(a \mid s)\) specifies the probability of taking action \(a\) in state \(s\). The agent’s interaction with the environment produces a sequence of states \(S_k\), actions \(A_k\), and reward \(R_k = \mathbf{r}(S_k, A_k)\). The value function of a policy \(\mu\), denoted as \(\mathbf{v}^\mu(s)\), describes the expected cumulative discounted reward when starting from a state \(s\) and following the policy \(\mu\):

\[\mathbf{v}^\mu(s) = \mathbb{E}\left[ \sum_{k=0}^{\infty} \gamma^k R_k \,\middle|\, S_0 = s \right].\]

Similarly, the Q-function of a policy \(\mu\) (the behavior policy), denoted as \(\mathbf{Q}^\mu(s, a)\):

\[\mathbf{Q}^\mu(s, a) = \mathbb{E}\left[ \sum_{k=0}^{\infty} \gamma^k R_k \,\middle|\, S_0 = s, A_0 = a \right].\]

The value function has a closed-form solution. Specifically, defining the transition matrix \(\mathbf{P}^{\mu}\in \mathbb{R}^{|\mathcal{S}|\times |\mathcal{S}|}\) of the Markov chain induced by policy \(\mu\) as \(\mathbf{P}^{\mu}(s,s')=\sum_{a\in\mathcal{A}}p(s'|s,a)\mu(a|s)\). Then the value of the policy \(\mu\) can be expressed in closed form as: \[\label{eq:Value95Closed95Form} \mathbf{v}^{\mu}=(\mathbf{I}-\gamma \mathbf{P}^{\mu})^{-1} \mathbf{r}^{\mu},\tag{1}\] where \(\mathbf{I}\) is the identity matrix and \(\mathbf{r}^{\mu}(\cdot)\) is defined as \(\mathbf{r}^{\mu}(s) = \sum_{a \in \mathcal{A}} \mathbf{r}(s,a)\mu(a|s)\). The optimal policy \(\mu^{\star}\) maximizes the value function for all states, resulting in the optimal value function \(\mathbf{v}^{\star}(s) = \max_{\mu}\mathbf{v}^{\mu}(s)\).

Among the key tasks in reinforcement learning are policy evaluation, which involves estimating the value function \(\mathbf{v}^{\mu}\) for a given policy \(\mu\), and policy iteration, which aims to find an optimal policy by iteratively performing policy evaluation followed by policy improvement to reach the optimal policy \(\mu^{\star}\). Additionally, off-policy learning methods, such as Q-learning, play an important role, as they enable learning about one policy (the target policy) while following a different policy (the behavior policy) to collect data. These tasks are well-established in the context of stationary MDPs. However, in non-stationary MDPs, where the transition probabilities \(p_k(s'|s,a)\) and rewards \(\mathbf{r}_k(s,a)\) change at each time step \(k\), the algorithms may not converge, especially if the dynamics change too rapidly or in an unconstrained manner. Even when they do converge, it is often unclear to what solution they converge. Without additional structure on the non-stationary MDP, reliable convergence is not guaranteed.

We provide one such structure on the non-stationarity that is useful for modeling practical problems and introduces regularities that can be leveraged to analyze and understand the convergence behavior of RL algorithms.

5 Switching Non-Stationary Markov Decision Process↩︎

In many real-world decision-making problems, the environment evolves over time, making stationary MDPs inadequate for capturing the complexity of these systems. For example, in autonomous driving, traffic conditions, such as congestion, weather, and road closures, may change in ways that affect optimal decision-making. Similarly, in communication networks, transmission quality can shift due to interference, signal degradation, or network congestion, all of which affect how agents should adapt their strategies. In these settings, the agent must make decisions without directly knowing the underlying state of the environment, which switches dynamically between different regimes.

We introduce SNS-MDP, a non-stationary MDP where the environment alternates between multiple latent states (or "modes"). Crucially, the agent cannot observe or measure the current latent mode and must make decisions solely based on its direct interactions with the environment. The switching between environments is governed by a Markov chain, meaning that the environment transitions probabilistically between modes depending on the current mode, though the agent remains unaware of these transitions.

Formally, SNS-MDPs are defined over a state space \(\mathcal{S} = \{1, \dots, |\mathcal{S}|\}\) and an action space \(\mathcal{A} = \{1, \dots, |\mathcal{A}|\}\), similar to traditional MDPs. However, unlike stationary MDPs, the environment, specifically the transition probabilities and rewards, changes at each time step. The environment can be in one of a finite number of environmental states, represented by the set \(\mathcal{E}=\{1,\dots, |\mathcal{E}|\}\), where each state corresponds to a distinct configuration of the system. Each environmental state \(e \in \mathcal{E}\) is associated with a unique transition probability function \(p_e: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0,1]\) and a reward function \(\mathbf{r}_e: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}\).

The dynamics of the environmental states is captured by a Markov chain \((\mathcal{E}, q(\cdot))\), where \(\mathcal{E}\) denotes the set of environment states, and \(q(\cdot)\) defines the transition probabilities between them, formalized in this definition.

Given a realization of an SNS-MDP, we get a trajectory of the measurable states, actions, and rewards: \[\begin{align} \label{eq:ORtrajectory95MDP} S_0, A_0, R_0, S_1, A_1, R_1, \ldots, S_k, A_k, R_k, \ldots, \end{align}\tag{2}\] where the reward is \(R_k = \mathbf{r}_{E_k}(S_k, A_k)\). At the same time, the unmeasurable environmental states evolve according to the following trajectory: \[\begin{align} \label{eq:Etrajectory95MDP} E_0, E_1, \ldots, E_k, \ldots. \end{align}\tag{3}\] The key point is that the environmental states determine which transition function and reward structure are applied at each time step. Specifically, if at time \(k\) the system is in environmental state \(E_k = e\), then the next state follows the distribution \(S_{k+1} \sim p_e(\cdot ~| S_k = s, A_k = a)\), and the reward is given by \(\mathbf{r}_{E_k}(S_k, A_k)\). However, since the environmental state is unmeasurable, the agent must act without direct knowledge of \(E_k\), relying only on the observable state \(S_k\) and the history of its interactions.

This type of non-stationarity appears in many real-world applications. Consider, for example, wireless communication. At each time step, a transmitting node must decide on a communication protocol (the action) to maximize data throughput or minimize latency. The choice of protocol can include options like modulation schemes, power levels, or channel access methods. However, the wireless environment is non-stationary due to factors such as interference, network congestion, or signal fading. These factors represent the unmeasurable environmental states that influence both the success of the transmission and the quality of the communication link. Importantly, these environmental factors often follow Markovian dynamics, which means that they evolve according to a Markov chain, as modeled by \((\mathcal{E},q(\cdot))\). While the transmitting node cannot mesure or observe the environmental state \(E_k\), it must still adapt its actions based on observable system states and past experience.

5.1 Impossibility of Inferring the Latent Environmental State↩︎

Although the SNS-MDP can be cast syntactically as a POMDP with hidden state \((S_k, E_k)\) and observation \(S_k\), POMDP methods are inapplicable in our setting. Such methods require forming a belief over the latent state, which in turn requires knowledge of \(q(e' \mid e)\) and \(\{p_e(s' \mid s,a)\}_{e \in \mathcal{E}}\), neither of which is available to the agent. More fundamentally, the latent environmental state is non-identifiable: distinct latent processes and model families can generate identical distributions over observable trajectories, making recovery of \(E_k\) from data ill-posed regardless of the estimation strategy. The following proposition formalizes this.

Since the agent also does not know \(|\mathcal{E}|\), different latent processes and mode-dependent dynamics can generate identical observed distributions. Belief-state estimation and POMDP-based RL techniques are therefore inapplicable, which motivates applying standard tabular RL algorithms directly to the observable trajectory and characterizing their limits.

6 Policy Evaluation in SNS-MDPs↩︎

A central problem in reinforcement learning is policy evaluation, where the objective is to estimate the value of a given policy. Once a policy is fixed, the problem essentially reduces to determining the value in a corresponding reward process. Therefore, to simplify notation, we consider the reward process in this section, abstracting away actions. However, when performing policy evaluation for a specific policy, these results and algorithms directly apply to the reward process induced by that policy, we investigate this in the next section.

We consider Switching Non-Stationary Markov Reward Process (SNS-MRP) formally defined as follows.

We make the following assumption on the SNS-MRPs.

Our goal is to characterize the value function of SNS-MRPs. Given a measurable trajectory \(S_k, R_k\) [cf. Eq. 2 ] and a corresponding unmeasurable trajectory of environmental states \(E_k\) [cf. 3 ], a natural definition of the value function is \[\begin{align} \label{eq:value95s95e} \mathbf{v}(s, e) = \mathbb{E} \left[ \sum_{k=0}^{\infty} \gamma^k R_k \mid S_0 = s, E_0 = e \right]. \end{align}\tag{4}\] However, since the environmental state \(E_k\) is unmeasurable, we do not know the current value under this definition. This makes it impractical, especially, for reinforcement learning algorithms. We need a definition of the value function that relies only on the observable state \(S_k\), making it more applicable in practice. By Assumption 1, we know that the environment Markov chain has a stationary distribution \(\boldsymbol{\pi}_{\mathcal{E}}(\cdot)\). Since the stationary distribution describes the long-run behavior of \(E_k\) once it has stabilized, it provides a reasonable basis for defining the value function. We thus propose the following value function for SNS-MRPs: \[\begin{align} \label{eq:value95s} \mathbf{v}^{\texttt{SNS}}(s) = \mathbb{E}_{E \sim \boldsymbol{\pi}_{\mathcal{E}}(\cdot)} \left[ \mathbf{v}(s, E) \right], \end{align}\tag{5}\] where the expected value is taken over the stationary distribution \(E \sim \boldsymbol{\pi}_{\mathcal{E}}(\cdot)\). This definition allows us to capture the expected accumulated reward based solely on the observable state \(S_k\), while accounting for the environmental uncertainty through the stationary distribution.

We now demonstrate that, surprisingly, the value in Eq. 5 has a closed form expression that can be characterized by the statistical properties of the SNS-MRP. This is unexpected because, although the value function in stationary MRPs has a closed-form solution, as shown in Eq. 1 , the value function in non-stationary MRPs typically does not.

The theorem establishes that the value function for the SNS-MRP has a closed-form expression. It is insightful to compare this expression with the closed-form solution for a stationary MRP. In the stationary case, given a transition matrix \(\mathbf{P}\in {\mathbb{R}}^{|\mathcal{S}|\times|\mathcal{S}| }\) and reward vector \(\mathbf{r}\in {\mathbb{R}}^{|\mathcal{S}|}\) then the value function is \[\begin{align} \label{eq:v95for95stationary95MRP} \mathbf{v}= (\mathbf{I}-\gamma \mathbf{P})^{-1} \mathbf{r}. \end{align}\tag{6}\] Interestingly, the closed-form expression for the SNS-MRP has a similar structure, but with key differences in the transition matrix and the reward vector.

1. Transition Matrix: Instead of the transition matrix \(\mathbf{P}\), the SNS-MRP involves the expression: \[\begin{align} \label{eq:} \sum_{e\in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e . \end{align}\tag{7}\] This is a weighted average of the transition matrices \(\mathbf{P}_e\) corresponding to the different environmental states \(e\in \mathcal{E}\). The weights \(\boldsymbol{\pi}_{\mathcal{E}}\) are given by the stationary distribution of the underlying environmental Markov chain \((\mathcal{E},q(\cdot))\). Therefore, instead of a single transition matrix \(\mathbf{P}\), we have a weighted combination of the transition matrices across the different environmental states.

2. Reward Vector: Similarly, the reward vector \(\mathbf{r}\) in the stationary MRP is replaced by \(\mathbf{r}_{\mathcal{E}}=\mathbf{R}\boldsymbol{\pi}_{\mathcal{E}}\) in the SNS-MRP case. This represents the weighted mean of the rewards for the different environmental states, where the weights are again given by the stationary distribution \(\boldsymbol{\pi}_{\mathcal{E}}\).

In reinforcement learning, we aim to estimate the reward function from data without having prior knowledge of the transition probabilities or rewards. This estimation is typically performed using observed trajectories. A common approach for this is TD-learning. However, in the case of a non-stationary environment, it is uncertain whether TD-learning will converge, or if it does, to what point it will converge, since the environment’s underlying dynamics are continually changing. Nonetheless, one might implement the TD update directly on the observed states \(S_k\), adapting the learning process to the measurable components of the system. To that end, we consider the following TD-learning algorithm. At each time step \(k\) we perform the TD-update \[\label{Equ:TDlearning-adopted} \mathbf{v}_{k+1}(s) {=} \mathbf{v}_k(s) {+} \alpha_k \left(R_k {+} \gamma \mathbf{v}_k(S_{k+1}) {-} \mathbf{v}_k(s)\right)\tag{8}\] if \(s = S_k\) and for all other states \(s\neq S_k\), we set \(\mathbf{v}_{k+1}(s)=\mathbf{v}_{k}(s)\). The algorithm starts with an initial value vector \(\mathbf{v}_0 \in \mathbb{R}^{|\mathcal{S}|}\), where \(\alpha_k\) is the learning rate.

Our next result demonstrates that the TD-learning algorithm in Eq. 8 converges in probability. Moreover, we establish that it converges specifically to the SNS-MRP value \(\mathbf{v}^{\texttt{SNS}}\) in Eq. ?? .

The theorem ensures that, under the SNS structure, TD-learning converges to a fixed point, and this fixed point corresponds the SNS-MRP value function in Eq. 5 . This guarantees that, despite the non-stationarity of the environment, the algorithm reliably captures the long-term value of states as they evolve.

7 Policy Iteration in SNS-MDPs↩︎

We now focus our attention to learning the optimal policy in SNS-MDPs. The goal is to learn the optimal policy, i.e., the one that optimizes the value function.

In a SNS-MDP, we must constrain ourselves to policies that are based only on the measurable states \(S_k\), but not based on the environment states \(E_k\), since they are not known to the agent. Therefore, we focus on policies of the form \(\mu:\mathcal{S}\rightarrow \Delta(\mathcal{A})\), where the policy \(\mu\) maps each state \(S_k\) to a probability distribution over actions, without relying on the unknown environmental state \(E_k\). We denote the probability of selecting action \(a\) given state \(s\) under policy \(\mu\) as \(\mu(a|s)\).

When searching for the optimal policy, it is often helpful to consider the state-action value function, or Q-function. Given a policy \(\mu\), the Q-function is \[\begin{align} \mathbf{Q}^{\mu}(s, e, a) = \mathbb{E} \left[ \sum_{k=0}^{\infty} \gamma^k R_k \,\middle|\, S_0 = s,\, E_0 = e,\, A_0 = a \right]. \end{align}\] However, since the environmental state \(E_k\) is unmeasurable, we cannot directly condition the action-value function on it. Instead, we must rely on a Q-function that depends solely on the observable state \(S_k\) and the actions taken, ignoring any direct information about the underlying environmental state. Similarly as before, we consider the expected value taken over the stationary distribution \(E\sim \boldsymbol{\pi}(\cdot)\). In particular, we consider the following state-action value: \[\begin{align} \mathbf{Q}^{\texttt{SNS},\mu}(s, a) = \mathbb{E}_{E \sim \pi_{\mathcal{E}}(\cdot)} \left[ \mathbf{Q}^{\mu}(s, E, a) \right]. \label{eq:Qvalue95s95a} \end{align}\tag{9}\] We can connect this Q-table to the SNS-MRP value function associated with the policy \(\mu\); specifically, for each environment state \(e \in \mathcal{E}\), we define the transition matrix \(\mathbf{P}_e^{\mu} \in \mathbb{R}^{|\mathcal{S}|\times |\mathcal{S}|}\) by \(\mathbf{P}_e^{\mu}(s,s') = \sum_{a \in \mathcal{A}} p_e(s'|s,a)\mu(a|s)\). Then, by Theorem 1, the SNS-MRP value under the fixed policy \(\mu\) is \[\mathbf{v}^{\texttt{SNS},\mu} = \left(\mathbf{I} - \gamma\left( \sum_{e\in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e^{\mu}\right)\right)^{-1} \mathbf{r}^{\mu}_{\mathcal{E}}\] where \(\mathbf{r}^{\mu}_{\mathcal{E}} = \mathbf{R}^{\mu}\mathbf{\pi}_{\mathcal{E}}\), and \(\mathbf{R}^{\mu}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{E}|}\) is the reward matrix defined as \(\mathbf{R}^{\mu}(s,e) = \mathbf{r}_{e}^{\mu}(s) = \sum_{a \in \mathcal{A}}\mathbf{r}_e(s,a)\mu(a|s)\). We can now establish the relationship between the SNS value function \(\mathbf{v}^{\texttt{SNS},\mu}\) and the SNS Q-function \(\mathbf{Q}^{\texttt{SNS},\mu}\) as follows.

This lemma establishes the relationship between the SNS state-value function, \(\mathbf{v}^{\texttt{SNS},\mu}\), and the SNS Q-function, \(\mathbf{Q}^{\texttt{SNS},\mu}\). In Section 6, we have already demonstrated how to estimate \(\mathbf{v}^{\texttt{SNS},\mu}\). To connect it with \(\mathbf{Q}^{\texttt{SNS},\mu}\) we need the transition probabilities \(p_e(s'|s,a)\). In deterministic environments, such as Grid-World or shortest-path problems, these transitions are explicitly known for each action, making this connection straightforward. In more general settings, \(\mathbf{Q}^{\texttt{SNS},\mu}\) can still be estimated using TD learning for policy evaluation, similarly as in Section 6, under the fixed policy \(\mu\).

If we can estimate or recover the SNS Q-table, \(\mathbf{Q}^{\texttt{SNS},\mu}\), then it plausible to perform Policy Iteration. We begin with an initial policy, \(\mu^0\), and then, at each iteration \(n\), estimate the SNS state-action values for the current policy \(\mu^n\), i.e., \(\mathbf{Q}^{\texttt{SNS},\mu^n}\). The policy is subsequently updated according to \[\begin{align} \label{eq:monotonic95improvement95PI95eq951} \mu^{n+1}(s) = \arg\max_{a \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS},\mu^n}(s, a) \end{align}\tag{10}\] ensuring that \[\begin{align} \label{eq:monotonic95improvement95PI95eq952} \mathbf{Q}^{\texttt{SNS},\mu^n}\big(s, \mu^{n+1}(s)\big) = \max_{a \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS},\mu^n}(s, a). \end{align}\tag{11}\] We now establish that the Policy Iteration algorithm works in SNS-MDPs.

The theorem establishes that \(\mu'\) is at least as good a policy as \(\mu\), ensuring that the Policy Iteration algorithm improves the policy at each step. We will now demonstrate that this improvement continues until a fixed point is reached, at which point the algorithm converges to the optimal policy.

8 Q-learning in SNS-MDP↩︎

The Policy Iteration algorithm discussed in the previous section has a drawback: at each iteration \(k\), we must estimate the Q-table \(\mathbf{Q}^{\texttt{SNS},\mu^k}\) for the corresponding policy \(\mu^k\). In contrast, Q-learning often provides a more efficient alternative, as it directly estimates the optimal Q-table without requiring explicit policy evaluation at each step. However, the convergence of Q-learning is generally not guaranteed outside of stationary environments. We now show that in SNS-MDPs, under certain conditions, Q-learning does converge to a stationary Q-table.

In Q-learning, the goal is to learn the optimal Q-table from sampled interaction. In SNS-MDPs, we observe two types of sample trajectories: the measurable trajectory [see Eq. 2 ] \(S_k,A_k,R_k\) and the unmeasurable trajectory [see Eq. 3 ] \(E_k\). Our goal is to learn an optimal Q-table, \(\mathbf{Q}^{\texttt{SNS}} \in {\mathbb{R}}^{|\mathcal{S}|\times|\mathcal{A}|}\), using only the observable trajectory. In particular, if we let \(\mathbf{Q}^{\texttt{SNS}}_k\) be the Q-table at iteration \(k\), with \(\mathbf{Q}^{\texttt{SNS}}_0\) initialized arbitrarily, i.e., as a zero matrix, then we may perform the following update: \[\begin{align} \label{eq:QL} \mathbf{Q}^{\texttt{SNS}}_{k+1}(s, a) &= (1 {-} \alpha_k)\,\mathbf{Q}^{\texttt{SNS}}_{k}(S_k, A_k) {+} \alpha_k \Bigl(\mathbf{r}_{e}(S_k,A_k) {+} \gamma \,\max_{a \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(S_{k+1}, a)\Bigr) \end{align}\tag{12}\] if \(s{=}S_k\) and \(a{=}A_k\) and \(\mathbf{Q}^{\texttt{SNS}}_{k+1}(s, a){=} \mathbf{Q}^{\texttt{SNS}}_{k}(s, a)\) otherwise. Since the environment mode changes at each iteration according to \(E_k\), it is unclear whether Q-learning converges and, if so, to what value. We now establish that Q-learning does converge in SNS-MDPs. To characterize the limit of this convergence, we define \(\mathbf{v}^{\texttt{SNS},\star}(s) = \max_{\mu} \, \mathbf{v}^{\texttt{SNS},\mu}(s).\) We then show that, under certain conditions, Q-learning converges to \[\begin{align} \label{eq:QFunc95ValueFunc95optimal} \mathbf{Q}^{\texttt{SNS},\star}(s, a) = \mathbf{r}_{\mathcal{E}}(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \mid s,a)\,\mathbf{v}^{\texttt{SNS},\star}(s'), \end{align}\tag{13}\] Before proving this result, we first define the optimal Bellman operator for SNS-MDPs. The following lemma establishes the uniqueness of the optimal Q-table as the fixed point of this operator.

We now establish the convergence of the Q-learning algorithm in SNS-MDPs.

This result establishes that, under appropriate step-size conditions and sufficient exploration, Q-learning in SNS-MDPs converges almost surely to the optimal Q-table. The requirement that every state-action-environment triplet \((s,a,e)\) is visited infinitely often ensures that the learning process adequately samples the entire state space, allowing the algorithm to correctly estimate the value function despite the underlying non-stationarity. Without this condition, the algorithm may fail to learn optimal Q-values for underexplored regions, potentially leading to suboptimal policies.

9 Experimental Results↩︎

We now demonstrate our theoretical results in the context of wireless communication systems, which often experience dynamic channel conditions due to factors such as fading, interference, and user mobility. To enhance performance under such fluctuating conditions, Adaptive Modulation (AM) techniques are employed, where transmission parameters are dynamically adjusted [24], [25]. To show the effectiveness of the proposed framework, we model an adaptive communication system using the SNS-MDP framework, which effectively captures the stochastic nature of wireless environments.

We consider a scenario where the transceiver, functioning as an agent, selects a frequency band for data transmission by observing the current modulation. This selection is the agent’s action, i.e., the action space is \(\mathcal{A}=\{\texttt{FB}_1,\texttt{FB}_2,\ldots \texttt{FB}_A\},\) where the agent can select between \(A\) frequency bands. The states, on the other hand, corresponding to different Modulation Schemes, i.e., \(\mathcal{S}=\{\texttt{MS}_1,\texttt{MS}_2,\ldots \texttt{MS}_S\},\) where \(S\) represents the number of available modulation schemes in the system. Each modulation scheme offers a unique trade-off between data rate and noise tolerance. Lower-order schemes, like BPSK, are more resilient to noise but provide lower data rates, whereas higher-order schemes, such as 1024-QAM or 2048-QAM, offer higher data rates but require better channel conditions. The environmental states represent the channel conditions, and for our study we consider the following 4 environments, \(\mathcal{E}=\{ \text{Excellent (E)}, \text{Good (G)}, \text{Fair (F)}, \text{Poor (P)} \}.\) The channel conditions are usually not known to the transceiver, but still they can have much influence on the dynamics of the communication system. Moreover, channel conditions are often modelled by Markovian dynamics, i.e., governed by a transition matrix \(q(e'|e)\). This is because the stochastic nature of wireless environments, influenced by factors such as fading, interference, and user mobility, inherently introduces dependencies across time steps.

The probability of successful transmission depends on several factors, including the channel condition, the chosen modulation scheme, and the selected frequency band [26], [27]. We define \(P_{\text{success}}(s, e, a)\) as the probability of successful transmission under a given channel condition (environmental state \(e\)), modulation scheme (system state \(s\)), and action (frequency band \(a\)). The probability of a successful transmission, \(P_{\text{success}}(\cdot)\) for each combination of modulation schemes, selected frequency bands, and channel conditions dictates the transition probabilities \(p_e(s'|s, a)\), as detailed in the Supplementary Materials, see also, e.g., [28].

The reward function \(\mathbf{R}(s, e)\) indicates system performance by considering both data throughput and the cost associated with using higher-order modulation schemes in poor channel conditions. It is defined as: \[\begin{align} \mathbf{R}(s, e) =& \alpha \cdot \text{Rate}(s) \cdot \text{Decay}(e) - \beta \cdot \text{Decay}(e) \end{align}\] where \(\alpha\) represents a weight that controls the contribution of the data rate to the overall reward, while \(\beta\) serves as a penalty factor for selecting higher-order modulation schemes in suboptimal channel conditions. The term \(\text{Rate}(s)\) refers to the data transmission rate associated with a given modulation scheme, and \(\text{Decay}(e)\) captures the degradation of system performance based on the current channel condition. Together, these parameters influence the balance between maximizing data throughput and mitigating the risks of poor channel quality. The introduced reward function and state transition probability are only used to make a setting for simulation and are not inferred from the literature.

The agent aims to determine the optimal frequency band for each modulation scheme by taking into account the system’s priority of maximizing data throughput while minimizing the impact of channel low quality. The SNS-MDP framework is well-suited for modeling this adaptive communication scenario, where unobservable environment changes occur following a Markov chain. This framework enables algorithms to estimate policy values and apply policy improvement techniques effectively. We illustrate this with a problem involving \(S = 11\) modulation schemes and \(A = 11\) frequency bands. The detailed model parameters used in the simulations are provided in the Supplementary Material. Figure 1 (a) illustrates the performance of the TD-learning algorithm for policy evaluation in Eq 8 with a fixed policy, using a constant learning rate of \(\alpha = 0.01\) and \(\gamma=0.97\). The red curve represents the average performance across 10 independent runs (\(M=10\)), while the black line indicates the true SNS value \(\mathbf{v}^{\texttt{SNS}}\) as derived in Theorem 1. The results show that the algorithm converges close to the true value. However, because a fixed learning rate is used rather than a diminishing one as specified in Theorem 2, the algorithm stabilizes within a small region around the fixed point and remains there, which is consistent with the expected behavior of stochastic algorithms with a constant step size.

Figure 1 (b) illustrates the performance of the Policy iteration algorithm in Eq. 10 . In this experiment, the agent can evaluate the true SNS Q-table \(\mathbf{Q}^{\texttt{SNS},\mu}\) for a fixed policy. The red curve represents the performance of the Policy iteration algorithm, while the black line indicates the optimal value. The results show that the Policy Improvement algorithm converges to the optimal policy in only a few iterations, thus establishing its efficiency and effectiveness in rapidly finding the optimal solution. This affirms the results in Theorem 3 and Theorem 4 that establish the convergence and optimally of the Policy Improvement in SNS-MDPs. Figure 1 (c) demonstrates the performance of the Q-learning algorithm. To compute the optimal Q-function, we first determine the optimal value function using policy iteration and then apply Eq. ?? . The red curve represents the Euclidean distance between the Q-function estimated by the proposed algorithm and the derived optimal Q-function, thereby confirming the convergence results established in Theorem 5 within the SNS-MDP framework.

10 Conclusion↩︎

In this paper, we introduced the SNS-MDP, a novel framework for modeling non-stationary environments driven by an underlying Markov chain. We defined an SNS value function for fixed policies or MRPs and derived a closed-form expression explicitly linked to the Markov chain’s statistics. We proved the almost sure convergence of TD-learning algorithms to the SNS value function under fixed policies, despite environmental non-stationarity. Furthermore, we demonstrated policy improvement feasibility and proved the convergence of the policy iteration algorithm toward optimal policies. Additionally, we established the almost sure convergence of Q-learning to an optimal SNS-MDP Q-function under a fixed behavioral policy. The practicality of the framework was validated through application to communication network problems with Markovian channel noise. Future work includes examining additional on-policy and off-policy algorithms, applying the SNS-MDP to multi-task learning, and extending it to multi-agent reinforcement learning.

11 Acknowledgment↩︎

This work was partially supported by the Sweden’s Innovation Agency (Vinnova) and the Swedish Research Council (VR).

12 Proof of Theorem 1↩︎

The following lemma will be useful for proving the theorem.

To prove Theorem 1, we first show that \[\begin{align} \label{eq:bellman95new95vectorwise} \mathbf{v}^{\texttt{SNS}} = \mathbf{r}_{\mathcal{E}} + \gamma \left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right) \mathbf{v}^{\texttt{SNS}}. \end{align}\tag{16}\] To that end, recall the definition \[\begin{align} \label{eq:bellman95new95elementwise} &\mathbf{v}^{\texttt{SNS}}(s) = \mathbb{E}_{E \sim \boldsymbol{\pi}_{\mathcal{E}}(\cdot)} \left[ \mathbf{v}(s, E) \right] = \sum_{e \in \mathcal{E}}\mathbf{v}(s, e)\boldsymbol{\pi}_{\mathcal{E}}(e), \end{align}\tag{17}\] where \(\boldsymbol{\pi}_{\mathcal{E}}(e)\) is the stationary distribution of the Markov chain \((\mathcal{E},q(\cdot))\), which exists by Assumption 1 (see discussion in Section 19 below).

To expand the expression in Eq. 17 we note that by Lemma 3 we have that \[\begin{align} \mathbf{v}(s, e) =& \mathbb{E} \left[\sum_{k=0}^{\infty} \gamma^k R_k \mid S_0 = s, E_0 = e \right] \\ =& \mathbb{E} \left[ R_0 + \gamma \sum_{k=1}^{\infty} \gamma^{k-1} R_k \mid S_0 = s, E_0 = e \right] \\ =& \mathbf{R}(s,e) \\ +&\gamma \sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E} } \mathbb{E} \left[ \sum_{k=1}^{\infty} \gamma^{k-1} R_k \mid S_1 = s', E_1 = e' \right] {\mathbf{Pr}\left[S_1=s', E_1=e' \mid S_0=s, E_0=e\right]} \\ =& \mathbf{R}(s,e) + \gamma \sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E} } \mathbf{v}(s', e') {\mathbf{Pr}\left[S_1=s', E_1=e' \mid S_0=s, E_0=e\right]} \\ =& \mathbf{R}(s,e) + \gamma \sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E} } \mathbf{v}(s', e') {\mathbf{Pr}\left[S_1=s' \mid S_0=s, E_0=e\right]} {\mathbf{Pr}\left[E_1=e' \mid E_0=e\right]} \\ \end{align}\] where in the last equations we utilized the Markov chain property in Lemma 3 and the structure of the transition function in Eq. ?? . Therefore, by expanding Eq. 17 we get that \[\begin{align} \label{eq:vSNSeq2} \mathbf{v}^{\texttt{SNS}}(s) =& \sum_{e\in \mathcal{E}} \mathbf{R}(s,e) \boldsymbol{\pi}_{\mathcal{E}}(e) + \gamma P' = \mathbf{r}_{\mathcal{E}}(s) + \gamma P'. \end{align}\tag{18}\] where we recall the definition \(\mathbf{r}_{\mathcal{E}}=\mathbf{R}\boldsymbol{\pi}_{\mathcal{E}}\) and have defined \[\begin{align} \label{eq:AA} &P'=\sum_{e \in \mathcal{E}} \sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E} } \mathbf{v}(s', e') {\mathbf{Pr}\left[S_1=s' \mid S_0=s, E_0=e\right]} {\mathbf{Pr}\left[E_1=e' \mid E_0=e\right]}{\mathbf{Pr}\left[E_0=e\right]}. \end{align}\tag{19}\] We can further manipulate \(P'\) to express it in a more favorable form. To do that, note that \[\begin{align} {\mathbf{Pr}\left[E_1=e' \mid E_0=e\right]} =& {\mathbf{Pr}\left[E_1=e' \mid S_0=s, E_0=e\right]} \tag{20}\\ {\mathbf{Pr}\left[E_0=e\right]} =& {\mathbf{Pr}\left[E_0=e \mid S_0=s\right]} \tag{21} \\ {\mathbf{Pr}\left[S_1=s' \mid S_0=s, E_0=e\right]} =& {\mathbf{Pr}\left[S_1=s' \mid E_1=e', S_0=s, E_0=e\right]}, \tag{22} \end{align}\] where we obtain Eq. 20 and Eq. 21 by the fact that \(E_0\) and \(E_1\) do not depend on \(S_0\) and we obtain Eq. 21 by the fact that \(S_1\) only depends on \(E_0\) and \(S_0\) and not on \(E_1\). Moreover, by using the chain rule, we have \[\begin{align} \label{eq:1D} &{\mathbf{Pr}\left[S_1=s', E_1=e', E_0=e \mid S_0=s\right]} = {\mathbf{Pr}\left[S_1=s'\mid S_0=s, E_0=e\right]} \\ & {\mathbf{Pr}\left[E_1=e' \mid S_0=s, E_0=e\right]}{\mathbf{Pr}\left[E_0=e \mid S_0=s\right]}. \end{align}\tag{23}\] By applying first Eq. 20 22 and then Eq. 23 in Eq 19 we get that \[\begin{align} P'&=\sum_{s' \in \mathcal{S} } \sum_{e' \in \mathcal{E} }\mathbf{v}(s', e') \sum_{e \in \mathcal{E}} {\mathbf{Pr}\left[S_1=s' \mid S_0=s, E_0=e\right]}{\mathbf{Pr}\left[E_1=e' \mid S_0=s, E_0=e\right]}{\mathbf{Pr}\left[E_0=e \mid S_0=s\right]} \notag \\ & = \sum_{s' \in \mathcal{S} } \sum_{e' \in \mathcal{E} } \mathbf{v}(s', e') \sum_{e \in \mathcal{E}} {\mathbf{Pr}\left[S_1=s', E_1=e', E_0=e \mid S_0=s\right]} \notag \\ & = \sum_{s' \in \mathcal{S} } \sum_{e' \in \mathcal{E} } \mathbf{v}(s', e') {\mathbf{Pr}\left[S_1=s', E_1=e' \mid S_0=s\right]} \notag \\ & = \sum_{s' \in \mathcal{S} } \sum_{e' \in \mathcal{E} } \mathbf{v}(s', e') {\mathbf{Pr}\left[E_1=e' \mid S_0=s\right]}{\mathbf{Pr}\left[S_1=s' \mid E_1=e', S_0=s\right]} , \label{eq:1E} \end{align}\tag{24}\] where the third equation is obtained by the fact that the inner most sum is over all \(e\in\mathcal{E}\) and the final equation is obtained by using the chain rule. By noting that \(S_1\) does not depend on \(E_1\), it only depends on \(E_0\), we further get \[{\mathbf{Pr}\left[S_1=s' \mid E_1=e', S_0=s\right]}= {\mathbf{Pr}\left[S_1=s' \mid S_0=s\right]}\] which allows us to reduce 24 to the following form (after rearranging the terms) \[\begin{align} P' =& \sum_{s' \in \mathcal{S}} {\mathbf{Pr}\left[S_1=s' \mid S_0=s\right]} \left( \sum_{ e' \in \mathcal{E} } \mathbf{v}(s', e'){\mathbf{Pr}\left[E_1=e'\right]} \right). \end{align}\] Note that since \(E_0\sim \boldsymbol{\pi}_{\mathcal{E}}(\cdot)\), where \(\boldsymbol{\pi}_{\mathcal{E}}(e)\) is the stationary distribution, and because the stationary distribution is invariant under the transition dynamics, we also have that \(E_1\sim \boldsymbol{\pi}_{\mathcal{E}}(\cdot)\). This means that \[\begin{align} P' =& \sum_{s' \in \mathcal{S}} {\mathbf{Pr}\left[S_1=s' \mid S_0=s\right]} \left( \sum_{ e' \in \mathcal{E} } \mathbf{v}(s', e')\boldsymbol{\pi}_{\mathcal{E}}(e')\right) \notag \\ =& \sum_{s' \in \mathcal{S}} {\mathbf{Pr}\left[S_1=s' \mid S_0=s\right]} \mathbf{v}^{\texttt{SNS}}(s'), \label{eq:2A} \end{align}\tag{25}\] where we have used the definition of \(\mathbf{v}^{\texttt{SNS}}(s)\) in Eq. 17 to obtain the second equality. Moreover, we have that \[\begin{align} {\mathbf{Pr}\left[S_1=s' \mid S_0=s\right]} =& \sum_{e \in \mathcal{E}} {\mathbf{Pr}\left[S_1=s', E_0=e \mid S_0=s\right]} \\ =& \sum_{e \in \mathcal{E}} {\mathbf{Pr}\left[S_1=s' \mid E_0=e, S_0=s\right]}{\mathbf{Pr}\left[E_0=e\right]} \\ =& \sum_{e \in \mathcal{E}} p_e(s'|s) \boldsymbol{\pi}_{\mathcal{E}}(e) = \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e(s,s'), \end{align}\] where we have used the chain rule in the second equality and the definition of the transition matrix \(\mathbf{P}_e\) in the final equality. Plugging this into Eq. 25 we get \[\begin{align} P'= \sum_{s' \in \mathcal{S}} \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e(s,s')\mathbf{v}^{\texttt{SNS}}(s') = \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \sum_{s' \in \mathcal{S}} \mathbf{P}_e(s,s')\mathbf{v}^{\texttt{SNS}}(s') . \end{align}\] It is easily checked that this is entry \(s\) in the matrix \[\sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) (\mathbf{P}_e \mathbf{v}^{\texttt{SNS}})= \left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right) \mathbf{v}^{\texttt{SNS}} .\] Now going back to Eq. 18 , we get that \[\begin{align} \mathbf{v}^{\texttt{SNS}}(s) =& \mathbf{r}_{\mathcal{E}}(s) + \gamma P' \\ =& \mathbf{r}_{\mathcal{E}}(s) + \gamma \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \sum_{s' \in \mathcal{S}} \mathbf{P}_e(s,s')\mathbf{v}^{\texttt{SNS}}(s') \end{align}\] or in matrix form we get the desired result that \[\begin{align} \label{eq:vSNS95linear95system} \mathbf{v}^{\texttt{SNS}} = \mathbf{r}_{\mathcal{E}} + \gamma \left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right) \mathbf{v}^{\texttt{SNS}}. \end{align}\tag{26}\] Since \[\sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e\] is a convex combination of stochastic matrices and \(\gamma\in[0,1)\) we know that \[\mathbf{I}- \gamma \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e\] is non-singular matrix and thus the linear system in Eq. 26 has the unique solution \[\mathbf{v}^{\texttt{SNS}} = \left(\mathbf{I} - \gamma\left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right) \right)^{-1} \mathbf{r}_{\mathcal{E}} .\]

13 Proof of Theorem 2↩︎

To prove Theorem 2 we draw on the following classic result for stochastic systems, see, e.g., Proposition 4.8 in [29].

To prove Theorem 2, we construct a Markov chain \((\mathcal{X},z(\cdot))\) along with \(\mathbf{A}\) and \(\mathbf{b}\), as in Proposition [Prop:Bertsekas], so that the algorithm in Eq. 28 is equivalent to the TD-learning algorithm in Eq. (9). We then verify that all the conditions of Proposition [Prop:Bertsekas] are satisfied, thereby confirming that the fixed-point is the unique solution to the system, ensuring convergence of the algorithm to the desired value.

In particular, we let the Markov chain sequence in Eq. 27 be such that \(X_k=(S_k,S_{k+1},E_k)\). The state space is \[\begin{align} \label{eq:Ki95def} \mathcal{X} = \{(s, s', e) \in \mathcal{S} \times \mathcal{S} \times \mathcal{E} \mid p_{e}(s'|s) > 0\}, \end{align}\tag{29}\] where the condition \(p_{e}(s'|s) > 0\) is included since we only consider states \(X_k=(S_k,S_{k+1},E_k)\) where transition from \(S_k\) to \(S_{k+1}\) is possible. This sequence is indeed a Markov chain.

For a given sample \(X_k = (S_k, S_{k+1},E_k)\), define: \[\begin{align} \mathbf{A}(X_k) &= \gamma \mathbf{e}_{\mathcal{S}}(S_k) \mathbf{e}_{\mathcal{S}}(S_{k+1})^{\mathrm{T}} - \mathbf{e}_{\mathcal{S}}(S_k) \mathbf{e}_{\mathcal{S}}(S_k)^{\mathrm{T}} \tag{30}\\ \mathbf{b}(X_k) &= \mathbf{e}_{\mathcal{S}}(S_k)\mathbf{e}_{\mathcal{S}}(S_K)^{\mathrm{T}} \mathbf{R} \mathbf{e}_{\mathcal{E}}(E_k) \tag{31} \end{align}\] where \(\mathbf{e}_{\mathcal{S}}(s) \in \mathbb{R}^{|\mathcal{S}|}\) and \(\mathbf{e}_{\mathcal{E}}(e) \in \mathbb{R}^{|\mathcal{E}|}\) are unit vectors with a 1 in the \(s\)-th and \(e\)-th position. It is easy to verify that with this definition of \(\mathbf{A}(\cdot)\) and \(\mathbf{b}(\cdot)\), the algorithm in Eq. 28 of Proposition [Prop:Bertsekas] is equivalent to TD algorithm as described in Eq. (9).

In subsections 13.1 and 13.2, we establish that \((\mathcal{X}, z(\cdot))\) possesses an invariant distribution \(\boldsymbol{\pi}\) and confirm that \[\begin{align} \mathbf{A} &= \mathbb{E}_{X \sim \boldsymbol{\pi}(\cdot)}[\mathbf{A}(X)] = \gamma \mathbf{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right) - \mathbf{D}_{\boldsymbol{\pi}_{\mathcal{S}}}, \tag{32}\\ \mathbf{b} &= \mathbb{E}_{X \sim \boldsymbol{\pi}(\cdot)}[\mathbf{b}(X)] = \mathbf{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \mathbf{r}_{\mathcal{E}} . \tag{33} \end{align}\] where \(\mathbf{D}_{\boldsymbol{\pi}_{\mathcal{S}}} = \text{Diag}(\boldsymbol{\boldsymbol{\pi}}_{\mathcal{S}})\) and \(\boldsymbol{\pi}_{\mathcal{S}}\) is defined in subsection 13.2. Therefore, if we verify that conditions (a)-(e) of Proposition [Prop:Bertsekas] are satisfied, then the TD-learning algorithm converges with probablity one to the fixed-point \[\begin{align} \lim_{k\rightarrow \infty} \mathbf{v}_k =&-\mathbf{A}^{-1}\mathbf{b} =\left(\mathbf{D}_{\boldsymbol{\pi}_{\mathcal{S}}}\left(\mathbf{I} - \gamma \left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right)\right)\right)^{-1} \mathbf{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \mathbf{r}_{\mathcal{E}} \\ =& \left(\mathbf{I} - \gamma \left( \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e \right)\right)^{-1} \mathbf{r}_{\mathcal{E}}, \end{align}\] and the proof of Theorem 2 is complete. We note that condition (a) holds trivially; the step-sizes are already assumed to satisfy this condition. The subsequent subsections are devoted to the validation of conditions (b)-(e).

13.1 Condition [Condition:C2])↩︎

We now demonstrate that the Markov chain \((\mathcal{X},z(\cdot))\) possesses an invariant distribution \(\boldsymbol{\pi}\). According to Proposition [Prop:invariantDist] in subsection 19.1, it suffices to establish that \((\mathcal{X},z(\cdot))\) is irreducible and aperiodic.

13.2 Conditions [Condition:C3]) and [Condition:C4])↩︎

We start by proving that Equations 32 and 33 hold true. Note that for states \(s,s'\in \mathcal{S}\) then \(\mathbf{e}_{\mathcal{S}}(s) \mathbf{e}_{\mathcal{S}}(s)^{\rm{T}}\) is a \(n \times n\) matrix that is everywhere zero except it has \(1\) on the diagonal element corresponding to state \(s\). Similarly, \(\mathbf{e}_{\mathcal{S}}(s) \mathbf{e}_{\mathcal{S}}(s')^{\rm{T}}\) is a \(n \times n\) matrix that is everywhere zero except it has \(1\) on the row and column corresponding, respectively, to the states \(s\) and \(s'\).

Consider the tuple \(x = (s, s', e) \in \mathcal{X}\). As established in subsection 13.1, the Markov chain \((\mathcal{X}, z(\cdot))\) has a stationary distribution \(\boldsymbol{\pi}(x) = {\mathbf{Pr}\left[s, s', e\right]}\), which represents the probability of being in state \((s, s', e)\) at equilibrium. It is also useful to define a marginal stationary distribution over the state space \(\mathcal{S}\), denoted by \(\boldsymbol{\pi}_{\mathcal{S}}\), which captures the marginal probability of being in state \(s \in \mathcal{S}\) by summing over the remaining variables \(s' \in \mathcal{S}\) and \(e \in \mathcal{E}\). Formally, we define \(\boldsymbol{\pi}_{\mathcal{S}}\) as: \[\boldsymbol{\pi}_{\mathcal{S}}(s) = \sum_{e \in \mathcal{E}, s' \in \mathcal{S}} \boldsymbol{\pi}(s, s', e).\] Additionally, we define the aggregated state transition matrix, denoted by \(\boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}}\), which represents the expected transition dynamics between states in \(\mathcal{S}\) after averaging over the environmental variable \(e \in \mathcal{E}\). This matrix is defined as: \[\boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} = \sum_{e \in \mathcal{E}} \boldsymbol{\pi}_{\mathcal{E}}(e) \mathbf{P}_e,\] where \(\boldsymbol{\pi}_{\mathcal{E}}(e)\) is, again, the stationary distribution of the environmental Markov chain \((\mathcal{E},q(\cdot))\), and \(\mathbf{P}_e\) is the transition matrix for a fixed environmental state \(e\). It can now be established that: \[\begin{align} \label{eq:eeT95identity} \mathbb{E}_{X\sim \boldsymbol{\pi}(\cdot)} [ \mathbf{e}_{\mathcal{S}}(s) \mathbf{e}_{\mathcal{S}}(s)^{\rm{T}} ]=& \texttt{Diag}(\boldsymbol{\pi}_{\mathcal{S}}) = \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \\ \mathbb{E}_{X\sim \boldsymbol{\pi}(\cdot)} [ \mathbf{e}_{\mathcal{S}}(s) \mathbf{e}_{\mathcal{S}}(s')^{\rm{T}} ]=& \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}}. \end{align}\tag{38}\]

Equation 32 now follows directly from the definition of \(\mathbf{A}(\cdot)\) in Equation 30 . In the same manner, Equation 33 is derived by combining Equation 38 and the definition in Equation 31 , considering the independence between the current state and the current environmental state. According to the definition of \(\mathcal{X}\), the current environmental state influences the next state, not the current state. Additionally, \(\mathbb{E}_{X \sim \boldsymbol{\pi}(\cdot)} [\mathbf{e}_{\mathcal{E}}(e)]= \boldsymbol{\pi}_{\mathcal{E}}\).

We next prove that \(\mathbf{A}\) is negative definite. To that end, we show that \(\mathbf{w}^{\rm{T}}\mathbf{A}\mathbf{w}<0\) for all \(\mathbf{w}\in {\mathbb{R}}^{|\mathcal{S}|}\setminus \{0\}\). In particular, we have that \[\begin{align} \notag \mathbf{w}^{\rm{T}}\mathbf{A}\mathbf{w}=& \mathbf{w}^{\rm{T}} \left( \gamma \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} - \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \right) \mathbf{w} \\ =& \gamma \mathbf{w}^{\rm{T}} \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} \mathbf{w} - \mathbf{w}^{\rm{T}} \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \mathbf{w}. \label{eq:wAw} \end{align}\tag{39}\] Let \(\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}^{1/2}\in {\mathbb{R}}^{|\mathcal{S}|\times |\mathcal{S}|}\) be the diagonal matrix whose entries are the element-wise square roots of the corresponding elements in \(\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}\). Then, by the Cauchy–Schwarz inequality, we obtain \[\begin{align} \notag \mathbf{w}^{\rm{T}} \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}\boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} \mathbf{w} &= \left( \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}^{1/2} \mathbf{w} \right)^{\rm{T}} \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}^{1/2}\boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} \mathbf{w} \\ &\leq ||\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}^{1/2} \mathbf{w}||_2 ||\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}^{1/2}\boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} \mathbf{w} ||_2. \label{eq:wDPw} \end{align}\tag{40}\] By considering the norm \[||\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}=\sqrt{\mathbf{w}^{\rm{T}}\boldsymbol{D}_{\pi_{\mathcal{S}}}\mathbf{w}}\] and using that \(||\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}^{1/2} \mathbf{w}||_2=||\mathbf{w}||_{\boldsymbol{D}_{\pi_{\mathcal{S}}}}\) for all \(\mathbf{w}\) we have that \[\mathbf{w}^{\rm{T}} \boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}} \boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}} \mathbf{w} \leq ||\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}} ||\Pi_{\mathcal{S}, \mathcal{S}}\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}.\] It is easily verified that \(||\boldsymbol{\Pi}_{\mathcal{S}, \mathcal{S}}\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}\leq ||\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}\) for all \(\mathbf{w}\in {\mathbb{R}}^{|\mathcal{S}|}\), see, e.g., Lemma 7.1 in [30]. This, together with Equations 39 and 40 ensures that \[\begin{align} \mathbf{w}^{\rm{T}}\mathbf{A}\mathbf{w}\leq \gamma ||\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}^2 - ||\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}^2 = (\gamma-1) ||\mathbf{w}||_{\boldsymbol{D}_{\boldsymbol{\pi}_{\mathcal{S}}}}^2. \end{align}\] Since \(\gamma<1\), it follows that \(\mathbf{w}^{\rm{T}}\mathbf{A}\mathbf{w}<0\) for all \(\mathbf{w}\in {\mathbb{R}}^{|\mathcal{S}|}\).

Finally, we establish that there exists \(M\in {\mathbb{R}}\) such that \(||\mathbf{A}||\leq M\) and \(||\mathbf{b}||\leq M\). To that end, note that the state space \(\mathcal{X}\) is finite, thus \(\mathbf{A}(x)\) and \(\mathbf{b}(x)\) can only take finite values, and must thus be bounded for all \(x\in \mathcal{X}\), i.e., there exists \(M\in {\mathbb{R}}\) such that \(\mathbf{A}(x)\leq M\) for all \(x\in \mathcal{X}\). This means that \(||\mathbf{A}||=||\mathbb{E}_{X\sim \boldsymbol{\pi}} [\mathbf{A}(X)]||\leq M\) and \(||\mathbf{b}||=||\mathbb{E}_{X\sim \boldsymbol{\pi}} [\mathbf{b}(X)]||\leq M\), so \(\mathbf{A}\) and \(\mathbf{b}\) are bounded.

13.3 Condition [Condition:C5])↩︎

From Lemma 5 proved above, the Markov chain \((\mathcal{X},z(\cdot))\) is both irreducible and aperiodic. Therefore, by the Convergence Theorem for Markov chains, see, e.g., Theorem 4.9 in Chapter 4 in [31], there exist \(\lambda \in (0,1)\) and \(D > 0\) such that for all \(x\in \mathcal{X}\) we have \[\begin{align} &\max_{x \in \mathcal{X}} ||z^{k}(\cdot|x)-\boldsymbol{\pi}||_{\rm{TV}} \leq D\lambda^{k} \quad \text{ for all} \quad n \in \mathbb{N}. \end{align}\] Therefore, recalling from above that there exists \(M\in {\mathbb{R}}\) such that \(||A(x)||\leq M\) for all \(x\in \mathcal{X}\), we have \[\begin{align} &\|\mathbb{E}[\mathbf{A}(X_{k})|X_{0}{=}x_{0}]{-}\mathbf{A} \| = \left\|\sum_{x \in \mathcal{X}}\mathbf{A}(x)(z^k(x|x_{0}){-}\boldsymbol{\pi}(x)) \right\| \\ &\leq \sum_{x \in \mathcal{X}}\|\mathbf{A}(x) \| |z^{k}(x|x_{0})-\boldsymbol{\pi}(x)| \\ &\leq M \sum_{x \in \mathcal{X}} |z^{k}(x|x_{0})-\boldsymbol{\pi}(x)| = 2 M ||z^{k}(\cdot|x_0)-\boldsymbol{\pi}||_{\rm{TV}} \\ &\leq 2 M D \lambda^k. \end{align}\] Therefore, the first inequality in part [Condition:C5]) of Proposition [Prop:Bertsekas] is established. The second inequality follows similarly \[\begin{align} \|\mathbb{E}[\mathbf{b}(X_{k})|X_{0}=x_{0}]-\mathbf{b} \| \leq& M \sum_{x\in \mathcal{X}} |z^k(x|x_0)-\boldsymbol{\pi}(x)| \\ \leq& 2MD \lambda^k. \end{align}\] As a result, both inequalities of part [Condition:C5]) are established, which concludes the proof.

14 Proof of Lemma 1↩︎

To prove the Lemma, first we use the Eq. (11), \[\begin{align} \mathbf{Q}^{\texttt{SNS},\mu}(s, a) = \mathbb{E}_{E \sim \pi_{\mathcal{E}}(\cdot)} \left[ \mathbf{Q}^{\mu}(s, E, a) \right]. \end{align}\]

Thus, from the definition of \(\boldsymbol{Q}^{\texttt{SNS},\mu}(s, e, a)\) we have

\[\begin{align} \boldsymbol{Q}^{\mu}(s, e, a) &= \mathbb{E} \left[ \sum_{k=0}^{\infty} \gamma^k \boldsymbol{R}_k \, \middle| \, S_0 = s, E_0 = e, A_0 = a \right] \\ &= \boldsymbol{R}(s, e, a) + \gamma \mathbb{E} \left[ \sum_{k=1}^{\infty} \gamma^{k-1} \boldsymbol{R}_k \, \middle| \, S_0 = s, E_0 = e, A_0 = a \right] \\ &= \boldsymbol{R}(s, e, a) + \gamma \sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E}} \mathbf{v}^{\text{SNS},\mu}(s', e'){\mathbf{Pr}\left[ S_1 = s', E_1 = e' \, \middle| \, S_0 = s, E_0 = e, A_0 = a \right]} . \end{align}\]

Therefore, it is only necessary to substitute \(\boldsymbol{Q}^{\mu}(s, e, a)\) into Eq. (11). To achieve this, note that \(E_0 \sim \boldsymbol{\pi}_{\mathcal{E}}(\cdot)\), where \(\boldsymbol{\pi}_{\mathcal{E}}(e)\) represents the stationary distribution. Consequently, we have: \[\begin{align} \mathbf{Q}^{\texttt{SNS},\mu}(s, a) =& \mathbb{E}_{E \sim \pi_{\mathcal{E}}(\cdot)} \left[ \mathbf{Q}^{\mu}(s, E, a) \right]=\sum_{e \in \mathcal{E}}\mathbf{Q}^{\mu}(s, e, a){\mathbf{Pr}\left[E_0=e\right]} \\ =&\sum_{e \in \mathcal{E}}\boldsymbol{R}(s, e, a){\mathbf{Pr}\left[E_0=e\right]} \\ +& \gamma \sum_{e \in \mathcal{E}}\sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E}} \mathbf{v}^{\mu}(s', e'){\mathbf{Pr}\left[ S_1 = s', E_1 = e' \, \middle| \, S_0 = s, E_0 = e, A_0 = a \right]}{\mathbf{Pr}\left[E_0=e\right]} \\ =&\boldsymbol{r}_{\mathcal{E}}(s, a) \\ +& \gamma \sum_{e \in \mathcal{E}}\sum_{s' \in \mathcal{S}} \sum_{e' \in \mathcal{E}} \mathbf{v}^{\mu}(s', e'){\mathbf{Pr}\left[ S_1 = s', E_1 = e' \, \middle| \, S_0 = s, E_0 = e, A_0 = a \right]} {\mathbf{Pr}\left[E_0=e\right]}. \end{align}\] Here, \(\mathbf{v}^{\mu}(s', e')\) denotes the value function, as defined in Eq. (4), under the fixed policy \(\mu\). Since the environmental state \(E_0\) is independent of both \(S_0\) and \(A_0\), we can express the following equivalence: \[\begin{align} {\mathbf{Pr}\left[E_0=e\right]}={\mathbf{Pr}\left[E_0=e|S_0=s, A_0=a\right]}. \end{align}\] Thus, we have, \[\begin{align} \mathbf{Q}^{\texttt{SNS},\mu}(s, a)&=\boldsymbol{r}_{\mathcal{E}}(s, a) \\ &+ \sum_{s' \in \mathcal{S}}\sum_{e' \in \mathcal{E}}\sum_{e \in \mathcal{E}} \mathbf{v}^{\mu}(s',e') {\mathbf{Pr}\left[S_1=s', E_1=e'| S_0=s, A_0=a, E_0=e\right]}{\mathbf{Pr}\left[E_0=e| S_0=s, A_0=a\right]} \\ &=\boldsymbol{r}_{\mathcal{E}}(s, a) + \sum_{s' \in \mathcal{S}}\sum_{e' \in \mathcal{E}} \mathbf{v}^{\mu}(s',e') \sum_{e \in \mathcal{E}}{\mathbf{Pr}\left[S_1=s', E_1=e', E_0=e| S_0=s, A_0=a\right]} \\ &=\boldsymbol{r}_{\mathcal{E}}(s, a) + \sum_{s' \in \mathcal{S}}\sum_{e' \in \mathcal{E}} \mathbf{v}^{ \mu}(s',e') {\mathbf{Pr}\left[S_1=s', E_1=e'| S_0=s, A_0=a\right]}\\ &=\boldsymbol{r}_{\mathcal{E}}(s, a) \\ &+ \sum_{s' \in \mathcal{S}}\sum_{e' \in \mathcal{E}} \mathbf{v}^{\mu}(s',e') {\mathbf{Pr}\left[E_1=e'| S_0=s, A_0=a\right]}{\mathbf{Pr}\left[S_1=s'| S_0=s, A_0=a, E_1=e'\right]} \\ &\quad \text{(Using chain rule)}\\ &=\boldsymbol{r}_{\mathcal{E}}(s, a) \\ &+ \sum_{s' \in \mathcal{S}} \left(\sum_{e'\in \mathcal{E}} \mathbf{v}^{\mu}(s',e') {\mathbf{Pr}\left[E_1=e'\right]} \right){\mathbf{Pr}\left[S_1=s'| S_0=s, A_0=a\right]} \\ &\quad \text{(Using SNS-MDP property)}\\ &=\boldsymbol{r}_{\mathcal{E}}(s, a) + \sum_{s' \in \mathcal{S}} \mathbf{v}^{\texttt{SNS}, \mu}(s') {\mathbf{Pr}\left[S_1=s'| S_0=s, A_0=a\right]} \quad \text{(Using Eq.~(5))} \\ &=\boldsymbol{r}_{\mathcal{E}}(s, a) + \sum_{s' \in \mathcal{S}} \mathbf{v}^{\texttt{SNS}, \mu}(s') p(s'| s, a). \end{align}\]

In the equation above, the transition probability \(p(s'| s, a)\) exists and can be derived as follows: \[\begin{align} p(s'| s, a)&=\sum_{e \in \mathcal{E}} \pi_{\mathcal{E}}(e)p_e(s'| s, a). \end{align}\]

15 Proof of Theorem 3↩︎

To prove this Theorem, we utilize Lemma 1 to compute \(\boldsymbol{Q}^{\texttt{SNS}, \mu}(s, \mu')\) as follows: \[\begin{align} \label{eq:QFunc95new95policy} \boldsymbol{Q}^{\texttt{SNS}, \mu}(s, \mu') =& \mathbb{E}_{A_0 \sim \mu'(.|s)}[\boldsymbol{Q}^{\texttt{SNS}, \mu}(s, A_0)] \\ =& \mathbb{E}_{\mu'} \left[ \boldsymbol{r}_{\mathcal{E}}(S_0, A_0) +\gamma \mathbf{v}^{\texttt{SNS}, \mu}(S_1) |S_0=s \right], \end{align}\tag{41}\] where \(\mathbb{E}_{\mu'}\) denotes the expected value when we follow the policy \(\mu'\). Note that by the assumption of the theorem, \(\forall s \in \mathcal{S}\) we have, \[\begin{align} \label{eq:QFunc95new95policy95geq95value} \mathbf{v}^{\texttt{SNS}, \mu}(s) \leq \boldsymbol{Q}^{\texttt{SNS}, \mu}(s, \mu') . \end{align}\tag{42}\] We can now derive the result by recursively applying Eq. 41 and Eq. 42 as follows \[\begin{align} \mathbf{v}^{\texttt{SNS}, \mu}(s) \leq& \mathbf{Q}^{\texttt{SNS},\mu} (s,\mu') \\ =& \mathbb{E}_{\mu'} \left[ \mathbf{r}_{\mathcal{E}}(S_0, A_0) + \gamma \mathbf{v}^{\texttt{SNS},\mu}(S_1) \mid S_0=s \right] ~~~~~~~~~~~~~~~~~~~~~~~~\text{(Using \eqref{eq:QFunc95new95policy})} \\ \leq& \mathbb{E}_{\mu'} \left[ \mathbf{r}_{\mathcal{E}}(S_0, A_0) + \gamma \mathbf{Q}^{\texttt{SNS},\mu}(S_1,\mu') \mid S_0=s \right] ~~~~~~~~~~~~~~~~~~~~\text{(Using \eqref{eq:QFunc95new95policy95geq95value})} \\ =& \mathbb{E}_{\mu'} \left[ \mathbf{r}_{\mathcal{E}}(S_0, A_0) + \gamma \mathbf{r}_{\mathcal{E}}(S_1, A_1) + \gamma^2 \mathbf{v}^{\texttt{SNS},\mu}(S_2) \mid S_0=s \right] ~~~~~~~~~\text{(Using \eqref{eq:QFunc95new95policy})} \\ \leq& ~~~\cdots \\ =& \mathbb{E}_{\mu'} \left[ \sum_{k=0}^{\infty} \gamma^k \mathbf{r}_{\mathcal{E}}(S_k, A_k) \mid S_0=s \right] = \mathbf{v}^{\texttt{SNS}, \mu'}(s) \end{align}\]

16 Proof of Theorem 4↩︎

Since \(\mu^{n+1}=\mu^n\) we also have that \(\mathbf{v}^{\mu^{n+1}}(s) = \mathbf{v}^{\mu^n}(s)\) for all \(s \in S\). From the monotonic improvement Theorem 3, this implies that \[\mathbf{v}^{\texttt{SNS}, \mu^n}(s) = \mathbf{v}^{\texttt{SNS}, \mu^{n+1}}(s) = \boldsymbol{Q}^{\texttt{SNS}, \mu^n} \big(s, \mu^{n+1}(s)\big), \quad \forall s \in S.\] But from equations (13) and (14), we have \[\boldsymbol{Q}^{\texttt{SNS}, \mu^n}\big(s, \mu^{n+1}(s)\big) = \max_{a \in A} \boldsymbol{Q}^{\texttt{SNS}, \mu^n}(s, a) = \mathbf{v}^{\texttt{SNS}, \mu^n}(s).\] This means that for all \(s \in S\), \[\begin{align} & \mathbf{v}^{\texttt{SNS}, \mu^n}(s) = \max_{a \in A} \boldsymbol{Q}^{\texttt{SNS}, \mu^n}(s, a) = \max_{a \in A} \boldsymbol{r}_{\mathcal{E}}(s, a) + \gamma \max_{a \in A} \mathbb{E} \left[ \mathbf{v}^{\texttt{SNS}, \mu^n}(s') \,\middle|\, S_0 = s,\, A_0 = a \right]. \end{align}\] Therefore, \(\mathbf{v}^{\texttt{SNS}, \mu^n}\) satisfies the Bellman optimality equation. Since the optimal value function \(\mathbf{v}^{\texttt{SNS}}\) is the unique fixed-point of the Bellman optimality equation, we conclude that \[\mathbf{v}^{\texttt{SNS}, \mu^k}(s) = \max_{\mu} \mathbf{v}^{\texttt{SNS},\mu}(s),\] for all \(s\in \mathcal{S}\). Consequently, \(\mathbf{v}^{\texttt{SNS}, \mu^k}\) is an optimal policy.

17 Proof of Lemma 2↩︎

Suppose \(\mathbf{Q}^{\texttt{SNS}}(s, a)\) is any function that satisfies Eq. (17). Then the vector formed by \(\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}(s', a')\) also satisfies Bellman’s equation. By the uniqueness of Bellman solutions, it follows that \[\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}(s', a') = \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS},\star}(s', a') \quad \text{for all } s' \in \mathcal{S}.\] Since \(\mathbf{Q}^{\texttt{SNS}}(s,a)\) also satisfies Eq. (17), we conclude that \(\mathbf{Q}^{\texttt{SNS}}(s,a) = \mathbf{Q}^{\texttt{SNS},\star}(s,a)\). Hence, the solution is unique.

18 Proof of Theorem 5↩︎

First of all, to leverage Proposition 4.4 in [29], we bring it here again:

We define the operator \(\mathcal{T}\) as follows: \[\begin{align} \label{eq:Operator} (\mathcal{T}\mathbf{Q}^{\texttt{SNS}})(s, a) = \mathbf{r}_{\mathcal{E}}(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}(s', a'), ~~~ \forall s \in \mathcal{S}, a \in \mathcal{A} \end{align}\tag{43}\]

Then, the Q-learning is defined in Eq. (15) can be shown as: \[\begin{align} \label{eq:Q-learing-algorithm} \mathbf{Q}^{\texttt{SNS}}_{k+1}(s, a) = (1-\alpha_k)\mathbf{Q}^{\texttt{SNS}}_{k}(s, a) + \alpha_k \left((\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a) + \mathcal{N}_k(s,a)\right) \end{align}\tag{44}\] where, \[\begin{align} \mathcal{N}_k(s,a) = \mathbf{r}_{\mathcal{E}}(s,a) + \gamma \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') - (\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a) \end{align}\]

To demonstrate the convergence of the algorithm in Eq. 44 , it is necessary to verify that it satisfies the conditions outlined in Proposition [Thm:Bertsekas-Prop4464]. The step-size conditions are met by choosing appropriate values for \(\alpha_k\) and adopting a suitable behavioral policy that ensures each state-action pair is visited infinitely often. For the third condition, it must be shown that the noise term \(\mathcal{N}_k(\cdot)\) has zero mean and bounded variance. We can show that the noise term has zero mean as follows:

\[\begin{align} \mathbb{E} \left[\mathcal{N}_k(s,a) \mid \mathcal{H}_k \right] = \mathbf{r}_{\mathcal{E}}(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \mid s, a) \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') - (\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a) = 0 \end{align}\]

For variance of the noise term, we have:

\[\begin{align} \mathbb{E} \left[\left(\mathcal{N}_k(s,a)\right)^{2} \mid \mathcal{H}_k \right] &= \mathbb{E} \left[ \left(\mathbf{r}_{\mathcal{E}}(s,a) + \gamma \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') - (\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a) \right)^{2} \mid \mathcal{H}_k \right] \\ &= \mathbb{E} \Bigg[ \left(\mathbf{r}_{\mathcal{E}}(s,a)\right)^{2} + \gamma^{2} \left(\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a')\right)^{2} + \left((\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a)\right)^{2} \\ & + 2\mathbf{r}_{\mathcal{E}}(s,a)\gamma \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') - 2\mathbf{r}_{\mathcal{E}}(s,a)(\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a) \\ & - 2\gamma \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a')(\mathcal{T}\mathbf{Q}^{\texttt{SNS}}_{k})(s, a) \mid \mathcal{H}_k \Bigg] \end{align}\]

Thus, utilizing Eq. 43 , we obtain:

\[\begin{align} \mathbb{E} \left[\left(\mathcal{N}_k(s,a)\right)^{2} \mid \mathcal{H}_k \right] &= \left(\mathbf{r}_{\mathcal{E}}(s,a)\right)^{2} + \gamma^{2} \mathbb{E} \Bigg[ \left(\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a')\right)^{2} \mid \mathcal{H}_k \Bigg] + \left(\mathbf{r}_{\mathcal{E}}(s,a)\right)^{2} \\ &+ \gamma^{2} \mathbb{E} \Bigg[ \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg]^{2} \\ &+ 2 \gamma \mathbf{r}_{\mathcal{E}}(s,a) \mathbb{E} \Bigg[ \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg] \\ &+ 2\gamma \mathbf{r}_{\mathcal{E}}(s,a) \mathbb{E} \Bigg[\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg] - 2\left(\mathbf{r}_{\mathcal{E}}(s,a)\right)^{2} \\ &- 2\gamma \mathbf{r}_{\mathcal{E}}(s,a) \mathbb{E} \Bigg[\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg] \\ &-2\gamma \mathbf{r}_{\mathcal{E}}(s,a)\mathbb{E} \Bigg[\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg] \\ &- 2\gamma^{2}\mathbb{E} \Bigg[ \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg]^{2} \\ &= \gamma^{2} \mathbb{E} \Bigg[ \left(\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a')\right)^{2} \mid \mathcal{H}_k \Bigg] \\ &- \gamma^{2}\mathbb{E} \Bigg[ \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \mid \mathcal{H}_k \Bigg]^{2} \\ &\leq \gamma^{2} \mathbb{E} \Bigg[ \left(\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a')\right)^{2} \mid \mathcal{H}_k \Bigg] \\ &- \gamma^{2} \left(\underset{s' \in \mathcal{S}}{\min} \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}_{k}(s', a') \right)^{2} \end{align}\]

Therefore, the third condition is satisfied. It remains to demonstrate that the operator is a weighted maximum norm pseudo-contraction. Before proceeding with the proof, we first highlight an interesting property of the transition probability, which will play a crucial role in the proof.

We now utilize Lemma 6 to demonstrate that the operator is a weighted maximum norm pseudo-contraction. Specifically, for any two functions \(\mathbf{Q}^{\texttt{SNS}}(\cdot)\) and \(\hat{\mathbf{Q}}^{\texttt{SNS}}(\cdot)\), and a vector \(\nu \in \mathbb{R}^{|\mathcal{S}|}\) with strictly positive elements, we can express:

\[\begin{align} \left|(\mathcal{T}\mathbf{Q}^{\texttt{SNS}})(s,a)-(\mathcal{T}\hat{\mathbf{Q}}^{\texttt{SNS}})(s,a)\right| &= \left|\gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}(s', a') - \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \max_{a' \in \mathcal{A}} \hat{\mathbf{Q}}^{\texttt{SNS}}(s', a')\right| \\ & \leq \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \left|\max_{a' \in \mathcal{A}} \mathbf{Q}^{\texttt{SNS}}(s', a') - \max_{a' \in \mathcal{A}}\hat{\mathbf{Q}}^{\texttt{SNS}}(s', a')\right|\\ & \leq \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \max_{a' \in \mathcal{A}}\left| \mathbf{Q}^{\texttt{SNS}}(s', a') - \hat{\mathbf{Q}}^{\texttt{SNS}}(s', a')\right|\\ & \leq \| \mathbf{Q}^{\texttt{SNS}} - \hat{\mathbf{Q}}^{\texttt{SNS}}\|_{\nu} \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \nu(s') ~~~~~~~ \text{(Using Lemma \ref{lemma:transition95prob95contraction})} \\ & \leq \lambda \| \mathbf{Q}^{\texttt{SNS}} - \hat{\mathbf{Q}}^{\texttt{SNS}}\|_{\nu} \nu(s) \end{align}\]

We divide both sides by \(\nu(s)\) and then take the maximum over all \(s \in \mathcal{S}\) and \(a \in \mathcal{A}\), yielding:

\[\begin{align} \|\mathcal{T}\mathbf{Q}^{\texttt{SNS}}-\mathcal{T}\hat{\mathbf{Q}}^{\texttt{SNS}}\|_{\nu} &\leq \lambda \| \mathbf{Q}^{\texttt{SNS}} - \hat{\mathbf{Q}}^{\texttt{SNS}}\|_{\nu} \end{align}\]

Hence, the operator \(\mathcal{T}\) qualifies as a weighted maximum norm pseudo-contraction.

To complete the convergence of the Q-learning, it needs to show that \(\mathbf{Q}^{\texttt{SNS}}_{k}(s, a)\) is bounded. To do so, we denote \(R_{max} = \max_{s \in \mathcal{S}, a \in \mathcal{A}} ~ r_{\mathcal{E}}(s,a)\). Then, it is easy to show that,

\[\mathbf{Q}^{\texttt{SNS}}(s, a) \leq \frac{R_{max}}{1-\gamma}, ~~~~~ \text{for all s \in \mathcal{S}, a \in \mathcal{A}}\]

Therefore, we have the following lemma:

Consequently, since all the required conditions are met and \(\mathbf{Q}^{\texttt{SNS}}(\cdot)\) is bounded, it follows that \(\mathbf{Q}^{\texttt{SNS}}(\cdot)\) converges almost surely to the unique fixed point \(\mathbf{Q}^{\texttt{SNS},\star}(\cdot)\) of \(\mathcal{T}\).

19 Markov Chains and Markov Reward Processes↩︎

In this section, we review some relevant background on Markov Chains and Markov Reward Processes (MRPs) that are needed for our proofs and results in the paper.

19.1 Markov Chains↩︎

This section begins with an introduction to the essential characteristics of Markov chains, as described in Chapter 1 of [31]. A Markov chain is defined as a pair \((\mathcal{S}, p(\cdot))\), where \(\mathcal{S}\) represents a finite set of states and \(p(\cdot)\) is the transition function. Specifically, \[p: \mathcal{S} \times \mathcal{S} \rightarrow [0,1]\] represents the probability function for state transitions, with \(p(s'|s)\) indicating the probability of moving from state \(s\) to state \(s'\). For each state \(s\), it holds that \(p(s'|s) \geq 0\) for every \(s' \in \mathcal{S}\) and \[\sum_{s' \in \mathcal{S}} p(s'|s) = 1.\] We also utilize a matrix representation for the Markov chain transitions, denoted \(P \in \mathbb{R}^{n \times n}\), where \[P(s, s') = p(s'|s).\] The progression of states in a Markov chain is depicted by a sequence of random variables: \[\begin{align} \label{eq:trajectory} S_0, S_1, \ldots, S_k, \ldots, \end{align}\tag{45}\] with the transition probability from state \(S_k = s\) to \(S_{k+1} = s'\) given by \({\mathbf{Pr}\left[S_{k+1} = s'|S_k = s\right]} = p(s'|s)\). For any \(t \in \mathbb{N}\), \[p^t(s'|s) := {\mathbf{Pr}\left[S_{k+t} = s'|S_k = s\right]},\] denotes the transition probability to state \(s'\) after \(t\) steps starting from state \(s\), and can be calculated as \[p^k(s'|s) = P^k(s', s).\]

A Markov chain \((\mathcal{S}, p(\cdot))\) is termed irreducible if for any two states \(s, s'\) there exists a \(k \in \mathbb{N}\) such that \(p^k(s'|s) > 0\). For any state \(s\), define \[\mathcal{T}(s) = \{t \geq 1 | p^t(s, s) > 0\}.\] The period of a state \(s\) is the greatest common divisor of the set \(\mathcal{T}(s)\). If the Markov chain is irreducible, all states share the same period, referred to as the chain’s period. A chain is aperiodic if every state has a period of 1. The following propositions are useful [31]:

19.2 Markov Reward Process (MRP)↩︎

A Markov Reward Process (MRP) is defined as a tuple \(M = (\mathcal{S}, p(\cdot), \mathbf{r}, \gamma)\). The set \(\mathcal{S}\) represents a finite state space, \(p(\cdot)\) is the transition function of the Markov chain, \(\mathbf{r} \in \mathbb{R}^{|\mathcal{S}|}\) denotes a reward vector where \(\mathbf{r}(s)\) signifies the immediate reward for being in state \(s\), and \(\gamma\) is a discount factor that quantifies the relative importance of immediate versus future rewards. The dynamics of an MRP are captured by a sequence of state-reward pairs, represented by the sequence of random variables \(S_0, R_0, S_1, R_1, \ldots, S_k, R_k, \ldots\), where \(k \in \mathbb{N}\) is a time index, and \(R_k = \mathbf{r}(S_k)\) is the reward received at time \(k\).

Value estimation is a primary task in studying MRPs, focusing on determining the value function from each state. This value function is denoted by the vector \(\mathbf{v} \in \mathbb{R}^{|\mathcal{S}|}\), and is defined as \[\mathbf{v}(s) = \mathbb{E} \left[ \sum_{k=0}^{\infty} \gamma^k R_k \mid S_0 = s \right].\]

According to the paper in [30], the vector \(\mathbf{v}\) can be calculated using the formula \[\mathbf{v} = (\mathbf{I} - \gamma \mathbf{P})^{-1} \mathbf{r}\] which relies on both the reward vector and the transition matrix \(\mathbf{P}\). However, in many practical situations, the exact transition probabilities and rewards are unknown, and analysts must rely on data from sampled trajectories as depicted in 45 .

19.3 Temporal Difference (TD) Learning↩︎

Temporal Difference (TD) Learning is known as an effective stochastic approach for estimating the value vector \(\mathbf{v}\) via a sample trajectory. This methodology utilizes the Temporal Difference evaluation algorithm, which progressively refines an estimation \(\mathbf{v}_k \in \mathbb{R}^n\) of \(\mathbf{v}\). Each iteration involves updating the estimate based on each sample \((S_k, R_k, S_{k+1})\) from the MRP trajectory, starting from any initial condition \(\mathbf{v}_0 \in \mathbb{R}^{|\mathcal{S}|}\). For each step \(k\), the next estimate \(\mathbf{v}_{k+1}\) is calculated as follows: \[\begin{align} \mathbf{v}_{k+1}(s) = \begin{cases} \mathbf{v}_k(s) + \alpha_k (R_k + \gamma \mathbf{v}_k(S_{k+1}) - \mathbf{v}_k(s)) & \text{if } s = S_k \\ \mathbf{v}_k(s) & \text{if } s \neq S_k \end{cases} \end{align}\] where \(\alpha_k > 0\) is a positive step-size. The convergence of this iterative process to the true value function is contingent upon the proper selection of step sizes as follows:

Under these conditions, and given that the MRP characterized by \((\mathcal{S}, p(\cdot))\) is irreducible and aperiodic, it is established that the TD algorithm converges to this theoretical fixed point almost surely, as represented by [31]: \[\begin{align} \label{eq:TD95fixedpoint} \lim_{k \rightarrow \infty} \mathbf{v}_k = \mathbf{v} = (\mathbf{I} - \gamma \mathbf{P})^{-1} \mathbf{r}. \end{align}\tag{46}\]

20 Details on the Experiments↩︎

We demonstrated our theoretical results in the context of wireless communication systems in Section 9, which frequently experience dynamic channel conditions due to factors such as fading, interference, and user mobility.

Wireless communication systems are inherently dynamic and complex because of the unpredictable nature of the wireless medium, which causes the quality of the wireless channel to fluctuate over time and across different locations. This variability is influenced by several factors. One is fading, fluctuations in signal strength caused by the constructive and destructive interference of multiple signal paths. Another is interference, unwanted signals from other transmitters that disrupt communication. User mobility also plays a role, as the movement of users alters signal propagation conditions.

To enhance performance under such fluctuating conditions, Adaptive Modulation (AM) techniques are employed. Adaptive Modulation involves dynamically adjusting transmission parameters, such as modulation schemes, to match current channel conditions [24], [25]. This approach aims to maximize data throughput while maintaining reliable communication.

To showcase the effectiveness of our proposed framework, we modeled an adaptive communication system using the SNS-MDP framework. The SNS-MDP effectively captures the stochastic and time-varying nature of wireless environments.

In our model, the transceiver functions as an agent that makes decisions based on observations of the system state. Specifically, the agent selects a frequency band for data transmission after observing the current modulation scheme. \[\mathcal{A} = \{ \texttt{FB}_1, \texttt{FB}_2, \ldots, \texttt{FB}_A \},\] where \(\texttt{FB}_i\) represents the \(i\)-th frequency band, and \(A\) is the total number of available frequency bands.

The states in the system correspond to different Modulation Schemes (MS), each offering a unique trade-off between data rate and noise tolerance: \[\mathcal{S} = \{ \texttt{MS}_1, \texttt{MS}_2, \ldots, \texttt{MS}_S \},\] where \(\texttt{MS}_j\) represents the \(j\)-th modulation scheme, and \(S\) is the number of available modulation schemes.

The environmental states represent the channel conditions, which are crucial yet typically unobservable factors that influence communication dynamics. \[\mathcal{E} = \{ \text{Excellent (E)}, \text{Good (G)}, \text{Fair (F)}, \text{Poor (P)} \}.\]

20.1 Markovian Dynamics of Channel Conditions↩︎

Channel conditions are often modeled using Markovian dynamics, with transitions governed by a probability matrix \(q(e'|e)\) [32]. This approach captures the temporal dependencies of channel conditions due to factors like fading and mobility. Channel condition transition probability can be estimated, but in this paper, we just use some predefined values to show the convergence of the RL algorithms upon the SNS-MDP framework. Table 1 shows the content of channel condition transition probability ².

In practice, Probability of Successful Transmission, which is denoted by \(P_{\text{success}}(s, e, a)\) can be estimated through empirical measurements or analytical models [26], [27]. For our simulation, we use predefined values to focus on demonstrating the convergence properties of our algorithms [28]. In Table 2 and 3, there are the detailed values for each \(P_{\text{success}}(s, e, a)\). Once a frequency band is selected, the corresponding table is chosen, where each table contains the probability of successful transmission for each pair of modulation schemes and channel conditions.

The state transition probabilities \(p_e(s'|s, a)\) are influenced by \(P_{\text{success}}(s, e, a)\) and are defined as:

\[p_e(s'|s, a) = \begin{cases} P_{\text{success}}(s, e, a), & \text{if } s' = s, \\ \displaystyle \frac{1 - P_{\text{success}}(s, e, a)}{\text{Index}(s') \times \sum_{k=1}^{|\mathcal{S}| - 1}\frac{1}{k}}, & \text{if } s' \neq s, \end{cases}\]

where \(\text{Index}(s')\) returns the position of modulation scheme \(s'\) in the ordered list starting from 1. This formulation ensures that if transmission is successful, the state remains the same; otherwise, it transitions to other states with a probability inversely proportional to their indices.

The reward function \(\mathbf{R}(s, e)\) measures system performance by balancing data throughput with penalties for unfavorable conditions, expressed as: \[\mathbf{R}(s, e) = \alpha \cdot \text{Rate}(s) \cdot \text{Decay}(e) - \beta \cdot \text{Decay}(e),\]

where \(\alpha\) controls the importance of the data rate, \(\beta\) penalizes the use of higher-order schemes in poor conditions, \(\text{Rate}(s)\) is the data rate linked to modulation scheme \(s\), and \(\text{Decay}(e)\) represents degradation due to channel condition \(e\). This formulation promotes modulation schemes that maximize throughput while discouraging risky decisions under poor conditions. In the simulation, \(\alpha\) set to 10 and \(\beta\) set to 2. Table ¿tbl:table:datarates? and [tbl:table:decayrates] represent the content of the date rate for each modulation scheme and the decay rate for each channel condition.

The simulations are done in Python code, which is available through the link below ³. All the algorithms start with the same initial policy that recommends frequency band 1 for all the modulation schemes. The results are shown in Section 9 of the paper.

References↩︎

---

1. A shortened version of this paper has been accepted for publication in the Proceedings of the 2026 IEEE Conference on Decision and Control (CDC). The present manuscript is the extended version and contains complete proofs, supporting background material, and full experimental details.↩︎

2. All the values for the probabilities in the Tables are scaled from 0 to 1.↩︎

3. https://github.com/mohsen1amiri/SNS-MDP.↩︎