- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies a finite horizon reinforcement learning problem with a countably infinite, unbounded state space and heavy-tailed transition increments. To better estimate the Bellman target, the author proposes using the median-of-means (MoM) method, which is more robust than estimating the mean of the samples. By subtracting an exploration bonus for optimistic cost minimization, the proposed algorithm updates the corresponding Q-value with interactive data collection. Then, a learning regret upper bound is proposed under several moment and stability assumptions. Numerical results are provided by comparing the sample-mean and MoM-based RL methods in a synthetic heavy-tailed MDP designed to expose the learning algorithms to rare but large state transitions.
Critical strengths
-
To address the technical challenge of replacing the sample mean with median-of-means, the paper careful handle the adaptive Bellman targets. It compares changing Bellman targets with fixed reference targets and separates statistical estimation error from propagated value-estimation error. This provides a meaningful tool for the regret analysis.
-
Under its stated assumptions, the paper provides regret guarantee combining heavy-tailed estimation and unbounded-state analysis. This setting is meaningful for some real-world applications, and has not been investiged previously as stated in the paper.
Critical weaknesses
-
Some of the assumptions seem to be strong. For example, the Lyapunov drift condition must hold for the actions actually selected at every learning step. And assuming that the cost function is the sum of two terms, , ignores the joint affect of the state and action on the rewards.
-
The non-rigorous mathematical symbol definitions, together with the writing logic, make the paper hard to follow. The organization of the paper is also confusing. For example, in Theorem 1, it cites the assumption that appears in a later part of the text, which makes understanding the theorem much harder.
Questions for authors
-
Equation (28) assumes that the Lyapunov drift condition holds at every learning step for the actions selected by the algorithm. Could you provide verifiable conditions on the dynamics and action set that ensure Algorithm 1 satisfies this assumption in an action-dependent control problem, particularly when exploratory actions could destabilize the system?
-
In Algorithm 1, why does each follow from rather than starting from a brand new episode? Since most theoretical analyses of RL algorithms with finite horizon have multiple independent episodes. Meanwhile, some other parameters, such as the size of the state space (which is infinite in this paper), the size of the action space, are not include in the final regret bound. Could you illustrate how this possibly large parameter be reflected in the final regret bound?
5 comments
Dear Reviewer VP56,
If you have time, could you please take a look at our response and let us know whether it addresses your concerns? We would be happy to answer any further questions or comments while the discussion is open.
Thanks for the authors' reply and my concerns are only addressed partly. The extension of the reward structure weakens the assumption, however, it is still unclear to me why such a structure should be imposed. For instance, g is only related to the state and has some Lipschitz properties, while f is related to the state-action pair and is bounded. When g is large, the cost c is dominated by the state space only. In particular, for the assumptions new to this setting, the necessity of using them should be presented more clearly. For the assumptions that are standard in the related literature, a comparison is needed.
I will keep my score in the current state and may reconsider the score if necessary.
We thank the reviewer for the careful reading and helpful comments. We uploaded a revised version, and the changes are marked in blue. We are sorry that the organization of the paper made it hard to follow. Following your comment, we collected all assumptions as Assumptions 1–4 and placed them before Theorem 1, so that Theorem 1 no longer refers to later parts of the text (Section 4.1). We also added a notation table in Appendix A, fixed symbols that had two meanings, and removed repeated statements. We hope that the revised version is easier to follow.
Response to Question 1: Thank you for this question. We agree that exploration may destabilize the system in an unbounded state space. In the revision, we added a simple condition that can be checked from the model (Proposition 1 in Appendix H). If every action moves the state toward the origin on average when the state is large, the drift condition (Assumption 4, which was Eq. (28) in the original version) holds for every state-action pair. Thus, it holds for any action that the algorithm selects, including exploratory actions, and it can be checked from the dynamics alone. For example, consider a cloud server that receives jobs with rare but very large bursts. If every service level can process more than the average amount of incoming work, this condition holds. A burst can make the queue very long, but the queue still decreases on average.
We also note that the drift condition is needed only in the continuing setting, and it is not needed when the state is reset in each episode (Proposition 2 in Appendix H). However, as you pointed out, our analysis does not cover systems in which some actions can make the state grow without bound. We state this as a limitation in the Conclusion and Appendix H.
Regarding the cost structure in Weakness 1, we agree that c(x,a)=g(x)+f(a) does not capture the joint effect of the state and action. In the revision, we generalized it to c(x,a)=g(x)+f(x,a), where f is bounded (Section 2.1). The proof does not change, since it uses f only through this bound (Appendix E). However, we note that costs whose action effect grows with the state, such as c(x,a)=xa, are still not covered.
Response to Question 2:
Episode linkage. We model the continuing setting, where each episode starts from the state at the end of the previous episode, i.e., x1k=xH+1k−1. We chose this setting because many systems with unbounded states, such as queues, cannot be reset between episodes. For example, the workload left at the end of one period remains at the start of the next period. Our results also cover the standard setting with independent episodes. In the revision, we describe both settings in Section 2.1, and we show that Theorem 1 holds in the reset setting without the drift condition (Proposition 2 in Appendix H).
Size of the state and action spaces. Thank you for pointing this out. In the revision, we show this dependence explicitly in Theorem 1: Regret(K)≤O((1+CX∣A∣)(KH)1−γρ), where ∣A∣ is the number of actions, and CX is the constant in Assumption 1 that bounds the number of states in a bounded region, that is, the number of states with ∣x∣≤u is at most CX(1+u). For example, CX=2 for integer-valued states. Since the state space is infinite, the analysis does not count all states. Instead, it counts only the states in a bounded region, and their number grows as CX(KH)ρ. This enters the bound through the factor CX∣A∣ and through the exponent 1−γρ. Thus, the regret grows at most linearly in ∣A∣ and CX. We also note that the hidden factor in O(⋅) grows exponentially with the horizon H, and we state this in Theorem 1.