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 …

Cite: Ayesta U. , Foss S. , Jonckheere M. , Puricellia V.
When Q-Learning fails: unstable behavior for infinite state spaces
ACM SIGMETRICS Performance Evaluation Review. 2026. V.53. N4. P.79--83.

Dates:

Published print:

Mar 31, 2026

Identifiers: No identifiers