# When Q-Learning fails: unstable behavior for infinite state spaces

Urtzi Ayesta, Sergey Foss, M Jonckheere, Vittorio Puricelli

► To cite this version:

Urtzi Ayesta, Sergey Foss, M Jonckheere, Vittorio Puricelli. When Q-Learning fails: unstable behavior for infinite state spaces. IFIP WG 7.3 Performance 2025, Nov 2025, Amsterdam, Netherlands. hal-05506960

HAL Id: hal-05506960

https://hal.science/hal-05506960v1

Submitted on 12 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# When Q-Learning fails:
unstable behavior for infinite state spaces

U. Ayesta<sup>a,c</sup>, S. Foss<sup>d</sup>, M. Jonckheere<sup>b</sup> and V. Puricelli<sup>a,b,*</sup>

<sup>a</sup> CNRS, IRIT, 2 rue C. Camichel, 31071 Toulouse, France.

<sup>b</sup> CNRS, LAAS, 7 av. du colonel Roche, 31031 Toulouse, France.

<sup>c</sup> IKERBASQUE - Basque Foundation for Science, 48011 Bilbao, Spain.

<sup>d</sup> School of MACS, Heriot-Watt University and Maxwell Institute, EH14 4AS, Edinburgh, UK.

## ABSTRACT

The Q-learning algorithm is well known for its convergence guarantees to the optimal policy in finite-state environments. In this paper, we investigate its limitations in countable infinite state spaces – a setting common in real-world problems. To this end, we introduce a simple queueing model, based on a load balancing problem, with a countably infinite state space. In this model, a dispatcher assigns incoming jobs to one of two queues by choosing between two possible actions: “red” and “green”. The “red” action leads to transient behavior, whereas the “green” action ensures stability. Our main result shows that, under certain parameter conditions, Q-learning exhibits instability and fails to converge to the optimal policy. Our findings reveal a critical gap in the theoretical understanding of model-free Reinforcement Learning methods in infinite domains. Numerical experiments illustrate that the transience also occurs with decreasing step-sizes that satisfy the usual Robbins-Monro conditions.

## 1. INTRODUCTION

In the realm of Reinforcement Learning (RL), simple algorithms such as Q-learning or SARSA stand out as an easily implemented and successful approaches for solving complex stochastic decision-making problems. In particular, Q-learning has garnered significant attention as an algorithm with the ability to learn optimal policies without requiring a model of the environment.

In many real-world problems, however, such as resource allocation in communication networks or control of physical systems, natural models have an infinite state space. This is the starting point of the present article, where we discuss Q-learning on discrete but infinite state spaces.

In the context Markov Decision Processes (MDPs) or model-based methods, several recent studies have explored the challenges associated with infinite state spaces. For instance, [5] addressed the convergence of the Natural Policy Gradient algorithm on some queueing MDPs in infinite state spaces, providing insights into how finite-state approaches can be extended. These generalizations typically rely on the structural properties of the state space and on the continuity

of the reward and transition functions, which allow for the extension of convergence proofs from finite to infinite environments, both for discounted and undiscounted settings.

Interestingly, our results indicate that such generalizations do not necessarily hold when dealing with model-free approaches. Model-free methods, which do not assume knowledge of the underlying MDP dynamics, face significant and different challenges from MDPs in infinite state spaces. In particular, the lack of a prior knowledge of state transitions and costs can lead to instability and to convergence issues that are not present in model-based approaches. Within the realm of model-free Reinforcement Learning, we focus on the Q-learning algorithm, which stands out as one of the most fundamental and widely studied algorithms due to its simplicity and theoretical grounding. Our goal in this paper is to formally demonstrate that, under certain parameter conditions, the Q-learning algorithms can exhibit instability in the form of *transience*, implying the inability to learn the optimal policy.

To this end, we consider a queueing system that models a load balancing problem – a widely studied scenario that is appealing due to its simplicity, despite operating in an infinite (countable) state space. In this queueing example, jobs arrive and are dispatched to one of two queues. The state of the system is represented by the number of jobs in each queue, and the goal is to balance the load between the queues to optimize performance metrics such as throughput and waiting time. The dispatcher can choose between two actions, “red” and “green”, which determine the probability of assigning jobs to the queues. The parameters are chosen so that if the “red” action were taken at every state, the number of jobs in the system would be transient, whereas with the “green” action, the number of jobs would remain stable.

The main result of this work Theorem 1 states that, under certain parameter conditions, the Q-learning algorithm exhibits transient behavior. This transience implies that the agent's policy will not stabilize, leading to suboptimal performance. This result is significant as it highlights a fundamental limitation of Q-learning and of similar algorithms in infinite state spaces, where traditional convergence guarantees may not hold. The discrepancy between the results obtained in the MDP and RL setting highlight the need for new theoretical frameworks and algorithms specifically designed to address infinite state spaces in RL.

For a full-length version of this extended abstract see [1].

<footnote>*Corresponding author. email: vpuricelli@laas.fr</footnote>
## 2. RELATED WORK

Regarding Q-learning, as mentioned in the introduction, the first convergence results towards the optimal policy were established for step sizes satisfying the Robbins-Monro conditions and finite state MDPs in [9] and [8]. Convergence guarantees for tabular Q-learning with constant step sizes in finite state spaces were provided in [2]. Let $\hat{Q}_n$ denote the n-step estimate of $Q^*$, the optimal action-value function. In [2], the authors show that for any $\theta > 0$, there exists a step size $\alpha_\theta > 0$ and $K_\theta > 0$ such that for all $\alpha \le \alpha_\theta$ and $n \ge K_\theta$, $||\hat{Q}_n - Q^*||_\infty \le \theta$.

In the context of model-based approaches for infinite state spaces, convergence of the Natural Policy Gradient (NPG) algorithm is proven in [5] for queueing MDPs under the additional assumption on the initial policy being stable. In [3], again for queueing systems, the authors consider a parameterized policy class and construct a practical algorithm that iteratively improves the average reward. This algorithm is also initialized with a stable policy.

In [7], the authors propose a model-free algorithm for discounted reward MDP with an infinite state space, under the generative framework (where one can sample transitions from any pair of state/action). The proposed algorithm operates in a forward-backward manner, where at every step the action is determined based on a simulation of the future events. They show that the process obtained by the application of this algorithm is stable.

## 3. THE MODEL: STATE DEPENDENT LOAD BALANCING

In this section, we present a class of two-dimensional problems arising in a queueing system, for which we will establish instability of Q-learning in Theorem 1. We have not identified a nontrivial one-dimensional example that exhibits transience phenomena. Consider jobs arriving to a dispatcher with rate $\lambda$. After a job arrives the dispatcher sends the job to one of two queues. The dispatcher can choose between actions $r$ (“red”) and $g$ (“green”), where action $a$ represents selecting $p_a$ for the probability of assigning a job to Queue 1. Meanwhile jobs leave the system in the following way: when both queues are busy a job in Queue $i$ leaves the system with rate $\mu_i$ for $i = 1, 2$. When one (no matter which one) queue is empty a job leaves the busy queue at rate $\tilde{\mu}$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Load balancing</figcaption></figure>

It is known from theory that given a continuous-time Markov chain on a discrete state space, one can construct a corresponding discrete-time Markov chain by observing the system at the random times when state transitions occurs. This yields what is known as the embedded Markov chain.

In this construction, the transition probabilities of the embedded chain capture the probability of jumping from one state to another, conditioned on the fact that a transition occurs. Following this approach, we consider a discrete-time MDP $(S, A, p)$ where: the state space is $S = \mathbb{Z}_+^2$ (2-dimensional integer-valued vectors with non-negative coordinates) so each state indicates the lengths of both queues (how many jobs are in each queue), action space $A = \{r, g\}$ and standard results yield that the transition probabilities $p(s' | s, a)$ defined for different states $s = (s^{(1)}, s^{(2)})$ are as follows:

1. For states with $s^{(1)} > 0, s^{(2)} > 0$:

$$ 
\begin{aligned}
p(s + (1, 0) | s, a) &= \frac{\lambda p_a}{\lambda + \mu_1 + \mu_2} \\
p(s + (0, 1) | s, a) &= \frac{\lambda(1 - p_a)}{\lambda + \mu_1 + \mu_2} \\
p(s + (-1, 0) | s, a) &= \frac{\mu_1}{\lambda + \mu_1 + \mu_2} \\
p(s + (0, -1) | s, a) &= \frac{\mu_2}{\lambda + \mu_1 + \mu_2}
\end{aligned} 
\quad (1) $$

2. For boundary states with $s^{(2)} = 0, s^{(1)} > 0$:

$$ 
\begin{aligned}
p(s + (1, 0) | s, a) &= \frac{\lambda p_a}{\lambda + \tilde{\mu}} \\
p(s + (0, 1) | s, a) &= \frac{\lambda(1 - p_a)}{\lambda + \tilde{\mu}} \\
p(s + (-1, 0) | s, a) &= \frac{\tilde{\mu}}{\lambda + \tilde{\mu}}
\end{aligned} 
\quad (2) $$

3. For boundary states with $s^{(1)} = 0, s^{(2)} > 0$:

$$ 
\begin{aligned}
p(s + (1, 0) | s, a) &= \frac{\lambda p_a}{\lambda + \tilde{\mu}} \\
p(s + (0, 1) | s, a) &= \frac{\lambda(1 - p_a)}{\lambda + \tilde{\mu}} \\
p(s + (0, -1) | s, a) &= \frac{\tilde{\mu}}{\lambda + \tilde{\mu}}
\end{aligned} 
\quad (3) $$

4. For the origin state $s = (0, 0)$:

$$ 
\begin{aligned}
p((1, 0) | (0, 0), a) &= p_a \\
p((0, 1) | (0, 0), a) &= 1 - p_a
\end{aligned} 
\quad (4) $$

### 3.1 The drift conditions

Our goal is to model an agent that: has no prior knowledge of the transition dynamics $p(s' | s, a)$ and that at each time step $n \ge 0$ it has to select some action $A_n$ at state $S_n$, leading to a next state $S_{n+1} \sim p(\cdot | S_n, A_n)$.

We then analyze whether the stochastic process $(S_n)_{n \ge 0}$ on $S$ can be unstable in the following sense:

**DEFINITION 1.** We say that $(S_n)_{n \ge 0}$ is transient or unstable if for any bounded set $U \subset S$, there is $s_0 \notin U$ such that

$$ \mathbb{P}(\inf\{n \ge 1 : S_n \in U\} = +\infty | S_0 = s_0) > 0. \quad (5) $$
We say that $(S_n)_{n \ge 0}$ is positive recurrent or stable if for any bounded set $U \subset S$ and any $s_0 \notin U$

$$ \mathbb{E}(\inf\{n \ge 1 : S_n \in U\} \mid S_0 = s_0) < +\infty. \quad (6) $$

Note that Definition 1 coincides with the standard definition of transience and positive recurrence in the case of irreducible Markov chains on $S$.

Consider an agent always applying “red” action, yielding a Markov chain $(S_n^r)_{n \ge 0}$, and another always applying “green” action, yielding another Markov chain $(S_n^g)_{n \ge 0}$. We establish parameter conditions ensuring $(S_n^r)_{n \ge 0}$ is transient (unstable) and $(S_n^g)_{n \ge 0}$ positive recurrent (stable).

Then first condition concerns the instability of action $r$,

$$ \left\{ \begin{array}{l} \mu_1 < \lambda p_r \\ \mu_2 < \lambda(1 - p_r). \end{array} \right. \qquad (7) $$

Concerning action $g$ we assume

$$ \left\{ \begin{array}{l} \mu_1 < \lambda p_g \\ \mu_2 > \lambda(1 - p_g). \end{array} \right. \qquad (8) $$

and also that

$$ \tilde{\mu} > \lambda \left( \frac{(\mu_1 + \mu_2)p_g - \mu_1}{\mu_2 - \lambda(1 - p_g)} \right). \qquad (9) $$

Note that if $\mu_1 + \mu_2 < \lambda < \tilde{\mu}$, conditions (7), (8) and (9) are satisfied for some $p_r, p_g \in (0, 1)$.

For each action its corresponding drift $D_a$ is given by

$$ D_a(s) = (1, 0) \times p(s + (1, 0) | s, a) \\ + (0, 1) \times p(s + (0, 1) | s, a) \\ + (-1, 0) \times p(s + (-1, 0) | s, a) \\ + (0, -1) \times p(s + (0, -1) | s, a). \qquad (10) $$

Observe that $D_a(s)$ takes 4 different values as a function of the state according to (1), (2), (3) and (4). We refer to Figure 2 for a visual representation of $D_a(s)$ for both actions. The drift in the positive orthant (states with both coordinates strictly positive) plays an important role in Theorem 1, and we reserve for it the notation $D_a$. From (10) and (1):

$$ D_a = \left( \frac{\lambda p_a - \mu_1}{\lambda + \mu_1 + \mu_2}, \frac{\lambda(1 - p_a) - \mu_2}{\lambda + \mu_1 + \mu_2} \right). \qquad (11) $$

From Theorem 3.3.1 of [4] it follows that if (7) holds the Markov chain $(S_n^r)_{n \ge 0}$ is transient, and that if (8) and (9) hold the Markov chain $(S_n^g)_{n \ge 0}$ is positive recurrent.

<figure><img src="image_3.png" /><figcaption>Figure 2: Drift of red (left) and green (right) action.</figcaption></figure>

We still need to assume one further condition upon the parameters for our main result Theorem 1 to hold. Consider

the quantity

$$ \begin{aligned} \varrho &:= \min\{D_r \cdot (1, 0), D_g \cdot (1, 0)\} \\ &= \min \left\{ \frac{\lambda p_r - \mu_1}{\lambda + \mu_1 + \mu_2}, \frac{\lambda p_g - \mu_1}{\lambda + \mu_1 + \mu_2} \right\} \qquad (12) \\ &= \frac{\lambda p_r - \mu_1}{\lambda + \mu_1 + \mu_2}, \end{aligned} $$

where the last equality follows from (7) and (8). Then we will assume that the vector $(\varrho/2)D_r + (1 - \varrho/2)D_g$ has all its coordinates positive (see Figure 3). Precisely in terms of the parameters, this is equivalent to the following condition:

$$ \mu_2 < \lambda(1 - p_g) + \frac{1}{2} \frac{(\lambda p_r - \mu_1)(p_g - p_r)}{\lambda + \mu_1 + \mu_2}. \qquad (13) $$

<figure><img src="image_4.png" /><figcaption>Figure 3: The configuration of the drifts derived from (7), (8) and (13).</figcaption></figure>

## 3.2 The cost function

We end the description of our model by considering a specific cost function $c: S \times A \times S \to \mathbb{R}$ given by:

$$ c(s, a, s') = (s'^{(1)} - s^{(1)}) + (s'^{(2)} - s^{(2)}). \qquad (14) $$

We refer this cost as being “local”, in the sense that it only depends on the transition, and not on the current state. This assumption is required in order to formally establish the main result, see Section 5 for more details. Numerical experiments reported in Section 6 illustrate that the instability of Q-learning remains when the cost function is defined as the sum of the coordinates of the current state.

In infinite-horizon cost problems the goal for an agent is to minimize for some fixed $\gamma \in (0, 1]$ the following objective:

$$ J_{\gamma} := \limsup_{n} \mathbb{E} \left( \sum_{i=1}^{n} \gamma^{i} c(S_{i}, A_{i}, S_{i+1}) \right), \qquad (15) $$

where $J_\gamma$ is called the total discounted cost for $\gamma < 1$, while $J := J_1$ is the total cost.

We see that for the cost function defined by (14) in addition of penalizing the growth of the queues, having finite total cost prevents transience as defined by Definition 1.

Since the agent that always applies green action defines a positive recurrent Markov chain, it has finite total cost. Moreover we have that

$$ J_{\gamma}^{g} := \mathbb{E} \left( \sum_{i=1}^{+\infty} \gamma^{i} c(S_{i}^{g}, g, S_{i+1}^{g}) \right) = O(1) \text{ as } \gamma \to 1. \qquad (16) $$

for a complete proof of (16) we refer to [1].
## 4. Q-LEARNING

As underlined in the introduction, the Q-learning algorithm is a popular option to solve total or discounted cost problems. The algorithm is based on sequentially approaching the optimal state-value function $Q^*: S \times A \to \mathbb{R}$, which is known to be the unique solution of the so-called Bellman equation [6], that for $\gamma < 1$ takes the form:

$$Q^*(s, a) = \min_{a' \in A} \left\{ \sum_{s' \in S} p(s'|s, a)[c(s, a, s') + \gamma Q^*(s', a')] \right\}.$$

The knowledge of $Q^*$ allows to obtain an optimal policy $\pi^*$ (i.e. such that $J_{\gamma}^* \le J_{\gamma}^{\pi}$ for all $\pi$) by considering $A^*(s) = \arg \min_{a \in A} Q^*(s, a)$ and setting

$$\pi^*(a | s) = \begin{cases} \frac{1}{|A^*(s)|} & \text{if } a \in A^*(s) \\ 0 & \text{if not.} \end{cases}$$

**DEFINITION 2.** Fix $\varepsilon \in [0, 1]$ and $\alpha > 0$ the exploration parameter and step-size respectively. Consider $s_0 \in S$ and $\hat{Q}_0: S \times A \to \mathbb{R}$. The asynchronous Q-learning with constant step size $\alpha$ is the sequence $(S_n, A_n, \hat{Q}_n)_{n \ge 0}$ where $S_0 = s_0$ and for each $n \ge 0$:

$$1. \quad \pi(a | \hat{Q}_n(S_n, \cdot)) = \begin{cases} \frac{1-\varepsilon}{|\hat{A}_n|} + \varepsilon/2 & \text{if } a \in \hat{A}_n \\ \varepsilon/2 & \text{if not,} \end{cases}$$

where $\hat{A}_n := \arg \min_{a' \in A} \hat{Q}_n(S_n, a')$,

$$2. \quad A_n \sim \pi(\cdot | \hat{Q}_n(S_n, \cdot)),$$

$$3. \quad S_{n+1} \sim p(\cdot | S_n, A_n),$$

and lastly

$$\hat{Q}_{n+1}(s, a) = \hat{Q}_n(s, a) + \mathbb{1}_{\{S_n=s, A_n=a\}} \times \\ \times \alpha[c(S_n, A_n, S_{n+1}) + \gamma \min_{a' \in A} \hat{Q}_n(S_{n+1}, a') - \hat{Q}_n(S_n, A_n)].$$

This can be called $(1-\varepsilon)$-greedy asynchronous Q-learning with constant step-size $\alpha$. We recall that in [2] (see Theorem 3.4), the authors derive an upper bound for the expected error of the approximation $\mathbb{E}(\|\hat{Q} - Q^*\|_{\infty})$ in the case of finite state spaces.

## 5. MAIN RESULT

In this section we state our main result Theorem 1, where we show that for the model defined in Section 3, Q-learning exhibits transient behavior. This transience arises because upon the first visit to each state, the agent chooses with sufficiently high probability the “red” action and is unable to recover from its instability (see (7)), leading to a transient behavior. As a consequence, we demonstrate that Q-learning exhibits suboptimal behavior in terms of total discounted cost.

**THEOREM 1.** Consider $(S, A, p)$ as defined in Section 3. Then for all $\varepsilon \in [0, 1]$ and $\alpha > 0$ if $\hat{Q}_0 = 0$ the process $(S_n)_{n \ge 0}$ induced by the Q-learning algorithm given by Definition 2 is transient. Also

$$J_{\gamma} = \Omega \left( \frac{1}{1-\gamma} \right) \quad \text{as } \gamma \to 1. \qquad (17)$$

We observe that this implies that for $\gamma$ sufficiently close to 1, Q-learning is sub-optimal under the assumptions of Theorem 1. This sub-optimality arises because the optimal discounted cost $J_{\gamma}^*$ satisfies the inequality $J_{\gamma}^* \le J_{\gamma}^g = O(1)$ (see (16)) while from Theorem 1 we obtain $J_{\gamma} = O(1/(1-\gamma)) \to +\infty$ as $\gamma \to 1$.

A complete proof of Theorem 1 can be found in [1]. We provide here a sketch of the proof for the transience of Q-learning.

**Sketch of the proof of transience.** From the model described in Section 3, we define a new model enlarging the state space in such a way that we erase the effect of the boundary states. This new model is explicitly given by $(S', A', p')$, where $S' = \mathbb{Z}^2$, $A' = \{r, g\}$ and $p'$ is given by (1) for all $s \in \mathbb{Z}^2$. Observe that in this new model each action $a$ induces a constant drift $D_a$ in space which by construction is given by (11). We also extend the cost function $c$ given by (14) to all $\mathbb{Z}^2$. This allows us to consider $(S_n, A_n, \hat{Q}_n)_{n \ge 0}$ defined exactly by Definition 2 in this new model $(S', A', p')$. The key step of the proof is to show that there exits a uniformly positive probability on the initial condition $S_0$, for $S_n > S_0$ coordinate-wise for all $n \ge 1$. By construction this property also holds for the process derived from Q-learning in the original model. To verify the transience of Q-learning (see Definition 1), we consider any bounded set $U$ and $s_0 > s$ for all $s \in U$, and obtain

$$\mathbb{P}(\inf\{n \ge 1 : S_n \in U\} = +\infty \mid S_0 = s_0) \\ \ge \mathbb{P}(S_n > S_0 \text{ for all } n > 0 \mid S_0 = s_0) > 0,$$

which follows since there is a positive probability of $S_n > S_0$ for all $n \ge 1$.

In order to derive this key step of the proof, we first show that $\delta := \lim_n \frac{1}{n} \sum_{i=0}^{n-1} \mathbb{1}_{\{A_i=r\}}$, the average number of times Q-learning applies red action, is well defined and that

$$\lim_{n} \frac{S_{n}}{n} = \delta D_{r} + (1 - \delta) D_{g} \in \mathbb{R}^{2} \quad \text{P-a.s..} \qquad (18)$$

We aim to prove that all coordinates of the limiting drift (18) are positive. This is crucial to stablish that there exists a uniformly bounded positive probability, on the initial condition $S_0$, for $S_n > S_0$ coordinate-wise for all $n \ge 1$. To show that all coordinates of (18) are positive, we establish the bound $\delta \ge \varrho/2$ (recall (12)) through two observations. First, $\varrho$ is a lower bound for the average number of times the process $(S_n)_{n \ge 0}$ visits new states. Second, since $\hat{Q}_0 = 0$, at these states visited for the first time there is at least probability $1/2$ of applying red action. Finally this bound on $\delta$ implies that the limiting drift (18) lies in the line between $D_r$ and $(\varrho/2)D_r + (1 - \varrho/2)D_g$. Using (13) we deduce that both coordinates of (18) are strictly positive (see Figure 3).

We conclude giving some details on how to establish (18), the main idea is to show that $(S_n)_{n \ge 0}$ has a regenerative structure. Given the assumptions on the drifts, we focus on the process $D_r$ and $D_g$ have a common component towards $l = (1, 0)$, we are going to focus $(S_n \cdot l)_{n \ge 0}$, with $l = (1, 0)$, which captures the horizontal drift of the process. We then show that there exists some random time $\tau_1 \ge 0$ such that $S_{\tau_1} \cdot l > S_t \cdot l$, for all $t < \tau_1$ and $S_{\tau_1+l} \cdot l \ge S_{\tau_1} \cdot l$, for all $t \ge 0$. Due to the locality nature of the cost function (see (14)) and the way in which the Q-learning algorithm operates (see Definition 2), it follows that $\tau_1$ is a renewal epoch for $(S_n)_{n \ge 0}$. This enables us to find a next random time $\tau_2 > \tau_1$ such that $S_{\tau_2} \cdot l > S_t \cdot l$, for all $t < \tau_2$ and
$S_{\tau_2+t} \cdot l \geq S_{\tau_2} \cdot l$, for all $t \geq 0$. Iterating this process we conclude that $(S_n)_{n \geq 0}$ has a renewal structure, with renewal epochs $\tau_n$, $n = 0, 1, \dots$. This renewal structure implies in turn the existence of the limit and its characterization in (18).

## 6. NUMERICS

In this section we perform numerical experiments to illustrate the behavior of Q-learning in various settings combining constant and non-constant step size and local and non-local cost function. As non-constant step size we consider $\alpha_n = 1/(n+1)$, which satisfies the classical Robbins-Monro conditions. As a non-local cost function we consider the total number of jobs, namely $c(s, a, s') = s^{(1)} + s^{(2)}$, which is a standard objective considered in the literature. In particular, we consider the following four settings: (i) (setting of Theorem 1) constant step-size and local cost function as given by (14), (ii) constant step-size and non-local cost function, (iii) non-constant step-size and local cost function, and (iv) non-constant step-size and non-local cost function.

Throughout the experiments, we fix the following choice of parameters for the load balancing model: $\lambda = 1.5$, $\mu_1 = 0.1$, $\mu_2 = 0.35$, $p_r = 0.45$, $p_g = 0.8$ and $\bar{\mu} = 0.01 + \lambda((\mu_1 + \mu_2)p_g)/(\mu_2 - \lambda(1 - p_g))$. We consider the discounting factor $\gamma = 0.1$, exploration parameter $\varepsilon = 0.1$, step-size $\alpha = 0.2$, initial condition $S_0 = (0, 0)$ and initialization $\hat{Q}_0(s, a) = 0$.

<figure><img src="image_5.png" /><figcaption>Figure 4: Evolution over time of the L1-norm of $(S_n)_{n \geq 0}$ derived from Q-learning in various settings (circles) and of $(S_n^g)_{n \geq 0}$ (triangles). The dashed line indicates the value $J^g$.</figcaption></figure>

In Figure 4 we simulate $N = 1000$ trajectories up to time $n = 10000$ and we plot over time the average $L_1$ norm $||s||_1 = s^{(1)} + s^{(2)}$ as a function of time for $(S_n^g)_{n \geq 0}$ and $(S_n)_{n \geq 0}$ derived from Q-learning for settings (i)-(iv) with initial condition $S_0 = (0, 0)$. We observe that the qualitative behavior of Q-learning is similar across all settings, suggesting that Q-learning remains transient even when using decreasing step-sizes and non-local costs.

In Figure 5, under the setting of Theorem 1, we plot the discounted cost functions $J_\gamma$ and $J_\gamma^g$ as a function of $\gamma$. For this we simulate $N = 100$ values of $J_\gamma$, calculated for a $n = 10000$ path-length, and plot an average for each $\gamma$. We recall that from Equation (15), we know that as $\gamma \to 1$, $J_\gamma^g \to J^g = \lim_n \mathbb{E}(S_n^{(1)} + S_n^{(2)})$, a value we represent with a big circle in Figure 5. As predicted by Theorem 1, we observe that $J_\gamma$ increases with $\gamma$ and has an asymptote at

<figure><img src="image_6.png" /><figcaption>Figure 5: The discounted cost $J_\gamma$ for the Q-learning algorithm (solid) and $J_\gamma^g$ (dashed) as a function of $\gamma$.</figcaption></figure>

$\gamma = 1$, whereas $J_\gamma^g$ stays finite.

## Acknowledgment

The authors would like to thank Sean Meyn for valuable discussions. Research partially supported by the French "Agence Nationale de la Recherche (ANR)" through the project ANR-22-CE25-0013-02 (ANR EPLER).

## References

[1] U. Ayesta, S. Foss, M. Jonckheere, and V. Puricelli. On the instability of local learning algorithms: Q-learning can fail in infinite state spaces. 2025. URL: https://arxiv.org/abs/2510.25572.

[2] C. Beck and R. Srikant. "Error bounds for constant step-size Q-learning". In: Systems & Control Letters 61.12 (2012), pp. 1203-1208.

[3] J. G. Dai and M. Gluzman. "Queueing Network Controls via Deep Reinforcement Learning". In: Stochastic Systems 12.1 (2021), pp. 30-67.

[4] G. Fayolle, V. A. Malyshev, and M. V. Menshikov. Topics in the constructive theory of countable Markov chains. Cambridge: Univ. Press, 1995.

[5] I. Grosof, S. T. Maguluri, and R. Srikant. "Convergence of Natural Policy Gradient for a family of infinite-state queueing MDPs". In: Queueing Systems 109.22 (2025).

[6] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. English. Wiley Ser. Probab. Math. Stat. New York, NY: John Wiley & Sons, Inc., 1994. ISBN: 0-471-61977-9.

[7] D. Shah, Q. Xie, and Z. Xu. "Stable Reinforcement Learning with Unbounded State Space". In: Learning for Dynamics and Control (L4DC) 2020. 2020.

[8] J. N. Tsitsiklis. "Asynchronous stochastic approximation and Q-learning". In: Machine Learning 16.3 (1994), pp. 185-202. ISSN: 0885-6125.

[9] C. J. C. H. Watkins and P. Dayan. "Q-learning". In: Machine Learning 8.3-4 (1992), pp. 279-292. ISSN: 0885-6125.