acceptodds
Under review as a conference paper at ICLR 2027

Reinforcement Learning in Infinite State Spaces: Convergence Guarantees via Stable Exploration

Abstract

Q-learning is a simple and widely used model-free reinforcement learning algorithm with well-understood guarantees in finite state spaces. Extending it to countably infinite state spaces poses fundamental challenges due to potential instability, i.e. the state drifting away, induced by the exploration mechanism. In this paper, we present a novel framework for fully online, model-free Q-learning in infinite state spaces under discounted rewards. Our main contributions are twofold: *(i)* a proof of Q-learning convergence under stable exploration in infinite state spaces, *(ii)* an online algorithm that ensures a stable exploration. Combining *(i)* and *(ii)*, our results provide, to the best of our knowledge, the first convergence guarantees of Q-learning in infinite state spaces. We also present numerical examples to compare the performance of various variants of the framework.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, Q-learning, stability, discounted reward criterion, decision making, online learning, model-free

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_t9VKOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies discounted tabular online Q-learning in countably infinite state spaces, where conventional exploration schemes may cause the state process to drift away and prevent adequate state-action coverage. It proves that Q-learning converges under suitable recurrence, reward-growth, and discounting conditions once the Robbins–Monro visitation requirement is satisfied. It then proposes an epoch-based exploration procedure that seeks to enforce this requirement by repeatedly applying policies with sufficiently strong return-to-reference-state behavior. The result provides an end-to-end convergence guarantee for a structured class of discounted infinite-state MDPs, motivated by queueing and related systems.

Critical strengths
  1. A conditional convergence result for Q-learning under Robbins–Monro state-action coverage, using weighted norms to handle polynomially growing rewards

  2. An epoch-based exploration scheme that provides sufficient conditions for this coverage through recurrent deployment of policies with controlled return times to a reference state.

  3. The authors identify an important issue that is absent in finite-state analyses: randomizing actions does not by itself ensure recurrent state coverage. Its use of weighted bounds and localization is technically appropriate, and the connection between exploration stability, recurrence, and Q-learning convergence is conceptually clear. The stable-exploration result is the manuscript’s most distinctive contribution.

Critical weaknesses

However, the main concern is that the overall approach relies on strong assumptions.

  1. Existence of a strongly stabilizing policy. The supplied policy class must contain a policy whose return time to a reference state has an exponential tail on a time scale proportional to the initial state magnitude. This is substantially stronger than ordinary positive recurrence and generally requires model-specific drift, Lyapunov, or fluid-limit analysis to verify.

  2. Regular selection of strongly stabilizing policies. There must exist a fixed integer DD such that, for every epoch MM, at least one of the policies selected during epochs MM through M+DM + D belongs to θ(c)\theta (c). This requirement is restrictive because many adaptive or randomized selection rules do not guarantee such a deterministic bound, even if they select strongly stabilizing policies infinitely often.

  3. Long state-dependent policy commitments. A selected policy is run for a duration proportional to the current state magnitude, with the proportionality factor eventually exceeding the unknown stability threshold. If the chosen policy performs poorly or drives the system farther away, the algorithm cannot change it until the epoch ends. It does not bound how many samples, epochs, or time steps are needed to attain a specified Q-function error or policy-performance level.

  4. Persistent full action support. Every action must eventually have positive probability at every state under every selected policy. This is stronger than the minimal requirement of infinite cumulative visitation.

  5. Restrictive MDP structure. The analysis assumes finite actions, bounded one-step state changes, irreducibility under every policy, polynomial reward growth, and discounted rewards. It does not directly cover nonlocal dynamics, reducible controlled chains, continuous actions, or average-reward objectives.

Questions for authors
  1. Under what verifiable conditions is the class θ(c)\theta (c) nonempty for a given class Λ\Lambda? Can the authors provide a general proposition—beyond the queueing examples?

  2. How is the reference state 0 selected in non-queueing applications? Does the analysis extend to return to a finite “small” or regenerative set rather than a single state, and what conditions ensure that such a set is accessible under the selected policies?

  3. What is a practical way to construct or certify a policy family Λ\Lambda that contains a policy in θ(c)\theta (c) without knowing the transition kernel?

  4. Can Assumption 2.1 be weakened from irreducibility under every policy to irreducibility only for policies selected by the exploration rule?

  5. Can the convergence be established with local visit-count step sizes rather than the global step size 1/(n+1)1/(n+1)? This would align more closely with standard tabular Q-learning implementations.

  6. Can the authors make the numerical section more comprehensive by reporting return-time distributions, visit frequencies for selected state–action pairs, and Q-value error diagnostics, and by examining sensitivity to epoch lengths and policy-family design?

6 comments

We provide a reply to the "critical weaknesses",

W1 We agree that in full generality, the condition for membership to class Θ(c)\Theta(c) is stronger than mere stability. However, as discussed at the end of Section 4.2 (lines 256–258, and more details in Appendix G), for many settings stable policies will belong to the class Θ(c)\Theta(c).

Irrespectively of that, we would like to argue that Θ(c)\Theta(c) is natural to consider in our online framework. Expanding what is explained in lines 249-254, we first mention that, to the best of our knowledge, there is no general criteria to conclude whether a given policy is stable or not after being executed for some finite time. Nevertheless, if a policy is stable, under some irreducibility conditions, the expected hitting time from any initial state to any other state is finite. However, this general result does not quantify how this expected hitting time behaves. Therefore, it is not clear, in the generality of our framework, for how much time one has to execute a policy to detect certain recurrence. Also, executing different stable policies for small amounts of time (say, uniformly bounded time) may define an unstable process (e.g. see the second example in Section 5).

For all the above, our solution was to consider policies were the hitting time to a given reference state has exponential tail and a mean that scales linearly with the initial state magnitude.

W2 We agree with the referee that randomized policy selection might yield in practice a scheme that stabilizes the system, as we actually illustrated in the numerical section with scheme A.2. However, it can be shown mathematically that sampling randomly from a subset of policies does not give sufficient recurrence conditions in general, revealing a fundamental theoretical limitation.

Consider the following toy-example: the state space is Z≥0\mathbb{Z}_{\geq 0}, where action 00 moves the state one step to the left and action 11 moves the state one step to the right. At each decision epoch, action 00 is chosen with probability ε\varepsilon. At state xx at time nn, a single action is selected and then applied for a duration of xx time units (note that c=1c= 1), in order to mimic Algorithm 1. Starting from the initial state x=1x = 1, and for simplicity defining $\tau = \text{inf} \lbrace t > 0 : X_t = 1 \rbrace $. It can be shown that E(τ)<+∞\mathbb{E}(\tau) < +\infty holds only if ε>1/2\varepsilon > 1/2.

This example illustrates that in random policy selection the probability of selecting between the stable policies must be sufficiently large; since in the model-free setting this can not be ensured apriori, a dynamic mechanism must be devised to increase this probability over time.

In this work we concentrate on giving, to the best of our knowledge, the first working procedure for stable exploration in a purely model-free and online setting. As me mention in the Conclusions, we aim in future work to address more complex selection procedures.

W3 We agree with the referee that the scheme might perform poorly due to the fact that unstable polices might be executed for long periods of time. However, we would like to note that: i) our scheme successfully accomplishes to stabilize the system. and that ii) in the generality of our assumptions and our online framework, it is not known how to detect unequivocally that a ``policy is performing poorly'' in terms of stability. See also our our response to the first question above.

As future work, it would be very interesting to investigate criteria to detect instability in an online fashion, for example, if a Lyapunov function is known. Besides of having interest on its own, if such a criteria were available, bad excursions seen in our scheme could be capped, which would improve the performance of the algorithm.

[continues below]

AuthorsOpenReview ↗

Rebuttal (cont.)

[continuation]

W4 This condition might not be necessary but it simplifies the stability analysis by bringing sufficient irreducible conditions that we subsequently exploit in the proofs. We also mention that due to the fact that Q-learning is off-policy, persistent exploration does not harm the algorithm's convergence. We would also like to note that this type of exploration is standard for Q-learning even in finite-state problems.

W5 We would like to note that in fact, some of the assumptions, i.e., polynomial reward growth, are in fact necessary in the infinite state space (see below). Others, for instance, discounted rewards, represents a general framework, with a whole literature devoted to it. In summary, we respectfully disagree with our assumptions being restrictive, given in particular that is the first paper that extends the theory of tabular Q-learning to problems with infinite state space.

We discuss in more detail the assumptions.

Regarding polynomial growth. Since we consider an MDP with an infinite state space, the reward function must satisfy certain conditions to ensure that the associated Bellman equation is well defined (e.g., that it has a unique solution). In particular, if the reward function exhibits exponential growth, Assumptions 6.10.2 of Theorem 6.10.4 from [14] is not verified. We observe that in Appendix A, we verify that the assumptions of Theorem 6.10.4 hold in our framework.

The irreducibility assumption could perhaps be relaxed to some extent, but assuming it facilitates clean mathematical results. Nevertheless, it is worth noting that non-irreducible MDPs pose different problems -- for example, exploration may lead the system to a transient region from which it can never return -- that are outside the scope of this article. Regarding irreducibility being strong in reinforcement learning, we argue that even in the finite-state case, irreducibility is often assumed because it provides a convenient sufficient condition guaranteeing that Q-learning with an exploratory policy (like ε\varepsilon-greedy) visits every state-action pair infinitely often.

We agree with the Reviewer that the uniformly bounded range assumption does not hold in all settings, such as queues with batch arrivals. However, we believe that it remains a reasonable assumption in many applications where the transitions are local, i.e., within a neighborhood of the current state. In any case, the range can in principle grow with the norm, and Theorem 3.1 in the article will remain valid if the rewards are bounded. Otherwise, the growth of the reward g:=sup⁡y∼xW(y)/W(x)g := \sup_{y\sim x} W(y)/W(x) will be, instead of a constant, a function of the state, bringing several complications in the proof.

Extensions of our results to continuous action and average-reward objectives give rise to issues that require a devoted analysis.

[continues below]

AuthorsOpenReview ↗

Rebuttal (last)

[continuation]

We now answer the questions for the authors:

QA1 In fact, in our setting, it is an assumption that the set Λ\Lambda contains a policy in the class Θ(c)\Theta(c). As we explained above in W1, the notion of stability and Θ(c)\Theta(c) are closely intertwined, and in many settings are in fact equivalent, see Appendix G. Hence, our positioning is that the fact that a system can be stabilized, i.e. being able to construct Λ\Lambda such that it contains stable policies, implies the existence of a policy in Θ(c)\Theta(c), for some unknown cc.

In our model-free setting, since the dynamics are not known, there is no way to certify apriori that a given policy belongs to class Θ(c)\Theta(c). What we argue in the article is that in many realistic problems, policies in Θ(c)\Theta(c) class exist and that therefore our scheme is plausible of being applied.

Lastly, we would like to mention that we do not aim in this work to characterize all problems for which stable policies in class Θ(c)\Theta(c) exist. However, we believe that an extension of Theorem G.1 to a more general class of Markov chains and with weaker assumptions can be obtained. Concretely, the proof of that theorem suggests that the existence of an exponential Lyapunov function is sufficient for membership to class Θ(c)\Theta(c) for some c>0c>0.

QA2 In our analysis, the reference state can be completely arbitrary. In fact, we made no optimality assumptions with respect to the state 00. Under our irreducible assumptions, all states are accessible if the selected policies have full-support over the actions. More precisely, let xgx_g be any state and Θ(c,xg)\Theta(c,x_g) denote the class of policies defined by the same condition as Θ(c)\Theta(c) but where the hitting time τ0\tau_0 is replaced by τxg\tau_{x_g}. It then follows from the irreducibility assumption that policies in the class Θ(c′,xg)\Theta(c',x_g) are also in Θ(c)\Theta(c) for some c′≠cc' \neq c.

QA3 Our view is that many problems naturally admit a parametrized family of policies Λ^\widehat{\Lambda} sufficiently rich in order to contain within it (an open subset of) stable policies. Then, stable policies are seen to belong to Θ(c)\Theta(c) in many cases, and therefore, discretizing Λ^\widehat{\Lambda} yield a set of policies Λ\Lambda suitable to be applied by our Algorithm 1. The above is in fact explained in Appendix F, where we discuss in more detail how such a set Λ\Lambda that contains policies in Θ(c)\Theta(c) can be constructed.

QA4 We do not exclude the existence of policies defining a reducible Markov Chain. Our key assumption regarding irreducibility, is that if a policy executes any action at any state with positive probability, then this policy defines an irreducible Markov chain.

QA5 Yes, we believe the convergence proof can also be established in the case of local step size, which it definitely makes sense for infinite state spaces. Should the paper be accepted we will add a remark on this for the camera-ready version.

QA6 In our view, the main contribution of the paper is the theoretical results. The simulated examples and the performance metrics considered are intentionally simple, and their purpose was not to demonstrate the performance of the scheme in a complex benchmark, but rather to illustrate several of its key properties.

In line with the suggestion by the reviewer, in future work, it would be very interesting to carry out a comprehensive experimental of the algorithm in more complex scenarios and metrics that could investigate, among others, these aspects: (i) performance of the algorithm in more complex reinforcement learning environments, (ii) an iterative discretization of a parametric policy until a policy in Θ(c)\Theta(c) is included in Λ\Lambda eventually, (iii) performance of the policy selection strategies that favor the selection of stable policies (but that do not satisfy Assumption I of Theorem 4.1), or (iv) further investigating the apparent trade-off between stability and learning (a very stable exploration strategy might be less effective in exploring and learning the optimal policy). If the paper is accepted, we will incorporate additional experiments addressing some of these aspects in the camera-ready version whenever possible, while leaving the more comprehensive investigation for future work.

Reviewer_T2YqOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies Q-learning in systems with infinitely many states, such as queues, where exploration can push the system farther away. It proves convergence when exploration revisits states often enough, proposes an online scheme alternating candidate policies to keep exploration stable, and claims the first such guarantees, with queueing simulations.

Critical strengths
  • In infinite state spaces such as queueing networks, giving every action positive probability is not enough, because exploration itself can push the system away and stall learning. The paper identifies this issue clearly and treats it without truncating the state space or resetting the environment.

  • Theorem 3.1 gives convergence under the Robbins–Monro condition with polynomially growing rewards, and it appears correct and can be useful separately

Critical weaknesses

I have critical concerns with the correctness of the paper

Theorem 4.1, and therefore Corollary 4.1, does not hold as stated. counter example : a single queue whose length goes up or down by one at each step. The agent alternates between a "good" policy that mostly moves the queue down (it is in Θ(c)\Theta(c)) and a "bad" policy that mostly moves it up. Take E={0}\mathcal E=\{0\} and let the epoch length grow linearly, as in the paper's own A1 setup (p.7 l.364). Assumptions I–III are all satisfied. What goes wrong: each bad epoch pushes the queue further out than the one before, so each good epoch needs longer to bring it back to 0. The agent still returns to 0 infinitely often, but the returns get rarer: roughly, the kk-th return happens around time k2k^2. Why learning stops: the step size (UD) shrinks like 1/n1/n in global time, so the total learning at state 0 is about ∑k1/k2\sum_k 1/k^2, which is finite. The Robbins–Monro condition fails, and Q-learning stops learning at state 0. For example, with zero rewards and Q^0≡1\widehat Q_0\equiv 1, Q^n(0,a)\widehat Q_n(0,a) never reaches Q∗=0Q^*=0.

Further, there are several inconsistencies with Algo 1 - e.g., line 6 runs the chosen policy for its full scheduled time, but lines 10–13 end the epoch as soon as the state first hits 0. Both cannot happen on one trajectory, so it is unclear what the algorithm actually does.

Finally the novely claim is too broad -- Q-learning convergence on infinite or general spaces already exists under specific structures (e.g., Melo, Meyn & Ribeiro, ICML 2008; Shah & Xie, NeurIPS 2018; Kara, Saldi & Yüksel, JMLR 2023). The claim should be narrowed to exact, tabular, fully online convergence on countable spaces with unbounded rewards.

Questions for authors

1)Can the authors look into the technical correctness of their paper and do a thorough literature review

Reviewer_7tRxOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the issue of instability in exploration mechanisms for discounted MDP with infinite state spaces. Its main contributions include: (i) Establishing the first convergence guarantees for model-free Q-learning in infinite state spaces. and (ii) Proposing a feasible online algorithm to ensure stable exploration. Empirical results demonstrate that traditional exploration methods fail in infinite state spaces, whereas the proposed framework successfully achieves convergence and stability.

Critical strengths

1.Algorithm 1 provides a well-structured exploratory strategy framework, and the authors effectively explain how to satisfy Assumptions I-III in Remark 4.1 and Section 5.

2.The proof chain from Proposition D.1 to Theorem 4.1 is the key to resolving infinite state spaces. It would be even better if the authors could provide a proof sketch to improve readability.

3.This is a solid paper that leverages the Robbins-Monro conditions to prove convergence in infinite state spaces. The overall proof is valuable. As the first work of its kind for infinite state spaces, it serves as an essential reference for future extensions in this direction.

Critical weaknesses

1.The main limitation is that the theoretical guarantee relies on assumptions that are not fully justified or discussed in the paper. In particular, the lack of discussion regarding locality and irreducibility limits the generality of the theorems.

2.The results are limited to asymptotic convergence; there are no finite-time convergence bounds provided.

Questions for authors

The notation formats for literature references and equations overlap, which hinders readability. It would be better to use distinct bracket notations to differentiate equations from citations.

1 comment

We thank the referee for their positive assessment of the manuscript. If the paper is accepted, we will include an sketch of the proof chain from Proposition D.1 to Theorem 4.1 to clarify the underlying line of reasoning.

Replies to the ``critical weaknesses'':

W1: We acknowledge that certain assumptions were made without an according justification. We will add such explanations to the camera-ready version, in case the paper is accepted, following the lines of the response W5 to Reviewer t9VK.

W2: Indeed, we do not address finite-time analysis in this work. We believe this is an interesting and natural venue for future research in infinite state problems.

Replies to the questions for the authors:

Q1: We thank the reviewer for pointing this out. We will revise subsequently the notations formats for references and equations in order to improve readability.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.