- 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
-
A conditional convergence result for Q-learning under Robbins–Monro state-action coverage, using weighted norms to handle polynomially growing rewards
-
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.
-
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.
-
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.
-
Regular selection of strongly stabilizing policies. There must exist a fixed integer such that, for every epoch , at least one of the policies selected during epochs through belongs to . 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.
-
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.
-
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.
-
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
-
Under what verifiable conditions is the class nonempty for a given class ? Can the authors provide a general proposition—beyond the queueing examples?
-
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?
-
What is a practical way to construct or certify a policy family that contains a policy in without knowing the transition kernel?
-
Can Assumption 2.1 be weakened from irreducibility under every policy to irreducibility only for policies selected by the exploration rule?
-
Can the convergence be established with local visit-count step sizes rather than the global step size ? This would align more closely with standard tabular Q-learning implementations.
-
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
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 -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 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]
Rebuttal (last)
[continuation]
We now answer the questions for the authors:
QA1 In fact, in our setting, it is an assumption that the set contains a policy in the class . As we explained above in W1, the notion of stability and 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 such that it contains stable policies, implies the existence of a policy in , for some unknown .
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 . What we argue in the article is that in many realistic problems, policies in 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 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 for some .
QA2 In our analysis, the reference state can be completely arbitrary. In fact, we made no optimality assumptions with respect to the state . Under our irreducible assumptions, all states are accessible if the selected policies have full-support over the actions. More precisely, let be any state and denote the class of policies defined by the same condition as but where the hitting time is replaced by . It then follows from the irreducibility assumption that policies in the class are also in for some .
QA3 Our view is that many problems naturally admit a parametrized family of policies sufficiently rich in order to contain within it (an open subset of) stable policies. Then, stable policies are seen to belong to in many cases, and therefore, discretizing yield a set of policies 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 that contains policies in 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 is included in 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.
Rebuttal
We provide a reply to the "critical weaknesses",
W1 We agree that in full generality, the condition for membership to class Θ(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).
Irrespectively of that, we would like to argue that Θ(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, where action 0 moves the state one step to the left and action 1 moves the state one step to the right. At each decision epoch, action 0 is chosen with probability ε. At state x at time n, a single action is selected and then applied for a duration of x time units (note that c=1), in order to mimic Algorithm 1. Starting from the initial state x=1, and for simplicity defining $\tau = \text{inf} \lbrace t > 0 : X_t = 1 \rbrace $. It can be shown that E(τ)<+∞ holds only if ε>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]