acceptodds
Under review as a conference paper at ICLR 2027

Robust Reinforcement Learning under Heavy-Tailed Dynamics

Abstract

We study reinforcement learning under heavy-tailed dynamics, where rare but large state transitions can make the Bellman target heavy-tailed and its variance need not be finite. In this setting, standard sample-mean-based Bellman updates can be sensitive to large observations and do not admit the usual light-tailed concentration guarantees. To address this issue, we develop a robust reinforcement learning algorithm based on the median-of-means (MoM) estimator. We incorporate MoM into the Bellman update and construct an exploration bonus from its high-probability estimation bound. A key challenge is that Bellman targets collected during learning are adaptive because the value estimates change over time. We handle this by comparing the adaptive targets with fixed reference Bellman targets and separating the statistical estimation error from the propagated value estimation error. Under moment and stability conditions, we establish an explicit sublinear expected regret bound for an unbounded state space. The bound depends on both the moment condition of the reference Bellman target and how strongly large state deviations can be controlled. Numerical results further show that MoM substantially reduces cumulative regret and more reliably selects the optimal action in a synthetic heavy-tailed environment.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Heavy-Tailed Dynamics, Robust Reinforcement Learning, Regret Analysis

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_VP56OpenReview ↗
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
  1. 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.

  2. 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
  1. 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, c(x,a)=g(x)+f(a)c(x, a)=g(x)+f(a), ignores the joint affect of the state and action on the rewards.

  2. 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
  1. 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?

  2. In Algorithm 1, why does each x1kx_1^k follow from xHk−1x_H^{k-1} 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

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)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)c(x,a) = g(x) + f(x,a), where ff is bounded (Section 2.1). The proof does not change, since it uses ff only through this bound (Appendix E). However, we note that costs whose action effect grows with the state, such as c(x,a)=xac(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−1x_1^k = x_{H+1}^{k-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−γρ),\mathrm{Regret}(K) \le \widetilde{O}\big((1 + C_{\mathcal{X}}|\mathcal{A}|)\,(KH)^{1-\gamma\rho}\big), where ∣A∣|\mathcal{A}| is the number of actions, and CXC_{\mathcal{X}} 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|x| \le u is at most CX(1+u)C_{\mathcal{X}}(1+u). For example, CX=2C_{\mathcal{X}} = 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)ρC_{\mathcal{X}}(KH)^{\rho}. This enters the bound through the factor CX∣A∣C_{\mathcal{X}}|\mathcal{A}| and through the exponent 1−γρ1-\gamma\rho. Thus, the regret grows at most linearly in ∣A∣|\mathcal{A}| and CXC_{\mathcal{X}}. We also note that the hidden factor in O~(⋅)\widetilde{O}(\cdot) grows exponentially with the horizon HH, and we state this in Theorem 1.

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.

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

The paper studies reinforcement learning under heavy-tailed dynamics, where rare, large state transitions can make Bellman targets highly variable or even infinite in variance, undermining standard sample-mean-based updates. This is an important problem in RL.

The main contribution of the paper is a robust RL algorithm using the median-of-means (MoM) estimator for Bellman updates, with an exploration bonus derived from its estimation error bound. To handle adaptive Bellman targets that change as value estimates evolve, the paper compares them with fixed reference targets and separate statistical estimation errors from propagated value-estimation errors. Under certain moment, regularity, and stability assumptions, the paper establishes an explicit sublinear expected regret bound for an unbounded state space. Empirical validation consists of a toy synthetic experiments. In a heavy-tailed environment, MoM-based RL reduces final cumulative average regret compared to the sample-mean baseline.

Overall, the paper offers an interesting theoretical contribution supported by synthetic results.

Critical strengths

The paper addresses an important challenge in reinforcement learning under heavy-tailed dynamics, where rare, extreme transitions can destabilize standard Bellman updates. Its use of median-of-means estimation provides a principled way to improve robustness without requiring finite variance.

Critical weaknesses

1. The proposed MoM-based algorithm and its exploration bonus explicitly rely on knowledge of the heavy-tail order parameter ϵ\epsilon and the central moment bound M1+ϵM_{1+\epsilon}​. Also, the number of blocks mm is tied to the total horizon TT through δ\delta. This means the algorithm requires prior knowledge of the time horizon TT to set its block structure.

2. The empirical validation is only conducted on a toy synthetic environment with a fixed short horizon of H=2H=2. It is true that the theoretical analysis addresses general finite horizons, but evaluating the algorithm merely on a two-step MDP does not effectively test its ability to handle long-horizon and complex statistical decision-making tasks.

Questions for authors

1. Theorem 1 and Lemma 1 specify that the number of blocks must scale with the time horizon TT. This leads to a growing block count for large horizons. However, the simulation setup entirely departs from this requirement by fixing m=5m=5 for T=20000T=20000 steps. I wonder whether the theoretical regret bound still holds under a fixed, small constant mm (such as m=5m=5), or does the theoretical proof fail to hold when mm is decoupled from TT?

2. The algorithm's exploration bonus βn\beta_n​ is explicitly constructed using the tail parameter ϵ\epsilon and the moment bound M1+ϵM_{1+\epsilon}. If these parameters are unknown a priori, which is common in real-world application scenarios, how will the algorithm perform? In other words, how sensitive are the theoretical regret bounds and the empirical performance of the algorithm to the misspecification of these parameters?

3. The theoretical analysis requires the block count mm to scale according to time TT. However, the experiment seems to completely decouple this by fixing the value of mm at m=5m=5 for T=20000T=20000 steps. I am confused why this is the case? Or am I misunderstanding the experimental parameters?

4. I would suggest expanding empirical evaluation beyond horizons larger than H=2H=2. Evaluating the algorithm on multi-step environments would provide stronger evidence regarding how the error of the algorithm scales with longer horizons.

3 comments

We thank the reviewer for the helpful comments. We uploaded a revised version, and the changes are marked in blue.

Response to Questions 1 and 3: We apologize that this point was not clear in the original version. Yes, you understood the experimental setting correctly. Our theory needs mm to grow as log⁡(2/δ)\log(2/\delta), that is, as log⁡T\log T. With this choice, all MoM estimates are accurate at the same time with high probability. With a fixed mm, the failure probability of each estimate does not decrease with TT, so the current proof does not apply. Thus, we do not claim that the regret bound holds for a fixed mm.

The value m=5m=5 in the experiments is a practical choice. The constant in the theory comes from a worst-case bound and is conservative. With such a large mm, each state-action pair must be visited many times before its first update, so learning becomes slow. In the revision, we state clearly in the simulation setting that Theorem 1 does not directly apply to the fixed m=5m=5 (Appendix J). To check the effect of mm, we also added experiments with m∈3,5,9,15,41m \in \\{3, 5, 9, 15, 41\\}, where m=41=⌈log⁡(2/δ)⌉m = 41 = \lceil \log(2/\delta) \rceil follows the log⁡T\log T scaling of the theory (Table 2 in Appendix K). MoM reduces the cumulative regret for all these values, by 23–34%.

As you pointed out in Weakness 1, the algorithm uses TT as prior knowledge, through δ\delta. However, TT enters the algorithm only through log⁡(2/δ)\log(2/\delta). Thus, an upper bound on TT is enough, and it changes only the logarithmic factors. If TT is totally unknown, the standard doubling trick gives the same rate. We explain this in Section 4.1 and give the details in Appendix G.

Response to Question 2: We agree that the bonus uses ϵ\epsilon and M1+ϵM_{1+\epsilon}. In the revision, we show that these can be set from simple properties of the transitions (Appendix E). In the original version, M1+ϵM_{1+\epsilon} was a moment bound on the Bellman target, which depends on the unknown optimal value function. We now show that this bound follows from the moment of the state increments. Here, rr is the order of the moment of the state increment ∣X′−x∣|X'-x| that is finite, and MrM_r is its bound, that is, E[∣X′−x∣r]≤Mr\mathbb{E}[|X'-x|^r] \le M_r (Assumption 3). For any ϵ≤r−1\epsilon \le r-1, M1+ϵM_{1+\epsilon} can be computed from MrM_r and other known constants. Thus, the algorithm does not need any information about the optimal value function. It only needs a lower bound on rr and an upper bound on MrM_r, which describe how large the state changes can be.

In practice, these values may not be known exactly. In this case, we can use a conservative choice. Since a smaller ϵ\epsilon or a larger M1+ϵM_{1+\epsilon} still satisfies the moment condition, the regret bound still holds with such a choice. The cost is a larger exploration bonus, so the bound becomes somewhat larger.

Thus, we also added experiments with ϵ∈0.1,0.25,0.4,0.5\epsilon \in \\{0.1, 0.25, 0.4, 0.5\\} and with different bonus coefficients, without retuning (Table 2 in Appendix K). MoM reduces the cumulative regret by 18–34% for all values of ϵ\epsilon, and by 15–32% for bonus coefficients from 0.5 to 4. When the bonus coefficient is too large (i.e., 8), both methods mostly explore, and they have almost the same regret.

Response to Question 4: Thank you for this suggestion. We agree that it is important to check how the performance changes with longer horizons. Thus, we added experiments with H=5H=5 and H=10H=10, using the same environment and without retuning (Fig. 3 and Table 2 in Appendix K). MoM reduces the final cumulative regret by 15.6% for H=5H=5 and by 15.2% for H=10H=10, and the 95% confidence intervals are above zero. The reduction is smaller than for H=2H=2, because the number of state-action pairs grows with HH, and the bonus coefficient was selected for H=2H=2. We agree that more complex long-horizon environments are an important next step.

I thank the authors for their rebuttal, including new experimental results on various values of ϵ\epsilon and bonus coefficients. I will keep my rating for now and revisit it after the reviewer discussion.

We thank you for reading our response and for your quick reply. We sincerely appreciate your willingness to revisit your rating after the reviewer discussion. If you have any further comments or questions, please let us know.

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

The paper studies reinforcement learning problems under heavy-tailed dynamics, where large state transitions can lead to Bellman target with potentially infinite variance. Existing sample-mean based Bellman updates are sensitive to these large observations, which motivates the use of a median-of-means (MoM) estimator instead. The authors proposed a MoM based Q-learning algorithm with an exploration bonus derived from its concentration bound. Under some moment and stability assumptions, they establish a sublinear expected regret bound, together with numerical experiments showing improvement over the standard sample-mean baseline.

Critical strengths

I think the strongest part of this paper is on the problem setup, which I think is fundamentally interesting: obtaining sublinear regret guarantees for RL under heavy-tailed transitions. I appreciate the authors' clear motivation for developing a robust Bellman estimator using MoM, and also provide a clear presentation for the regret analysis.

More generally, I think understanding how classical Bellman updates can incorporate robust estimators beyond the empirical mean while still maintaining sublinear regret guarantees is an interesting direction. The authors provide such a guarantee for MoM under finite-moment assumptions in an unbounded state space, which I think is a meaningful contribution.

Critical weaknesses

My main concerns are on two things: which are on the strength of the assumptions and that the somewhat incremental nature of the technical contribution.

For the first point, I think that some of the assumptions are quite restrictive, and the authors should spend some time explaining their necessity and how much they limit the applicability of the results. I'm particularly concerned about the Lyapunov drift condition (Equation 28), which assumes stability throughout learning. This seems to abstract away an important difficulty of RL in unbounded state space, which is that exploration itself may lead to unstable state evolution. I'm therefore curious how restrictive this assumption is in practice, and under what natural conditions it can be guaranteed. I am also concerned about the assumption of a one-dimensional countable state space with only O(U)O(U) states in [−U,U][-U, U], which excludes natural spaces to consider, say continuous spaces and multidimensional state spaces.

For the second point, algorithmically, the method seems to be replacing the empirical mean in standard Q-learning with MoM, which is quite natural, but I do not see anything fundamentally different in the proof technique (in particular on Lemma 3 and 4): it seems that much of the analysis seems to follow existing techniques with relatively straightforward modifications. I am therefore not fully convinced the technical contribution is sufficiently substantial beyond extending existing approach to this particular setting, even though I found the setting particularly interesting.

Questions for authors

More details on the first two questions are provided in the Critical Weaknesses section.

  1. Can the authors elaborate on the main technical novelty of the regret analysis compared to existing robust Q-learning results?
  2. How restrictive are the assumptions used for the main result, particularly the Lyapunov drift condition (Equation 28) and the assumption that ∣X∩[−U,U]∣=O(U)|\mathcal{X}\cap[-U,U]|=O(U)? Are these assumptions necessary for the proposed algorithm, or are they mainly limitations of the current analysis? It would be helpful to understand how broadly these assumptions apply to natural classes of unbounded MDPs.
  3. Can the authors briefly discuss on how the regret rate in Theorem 1 compare with existing guarantees for heavy-tailed RL? In particular, is there any indication that the rate is optimal under the stated assumptions, or could it potentially be improved?
4 comments

We are thankful for the helpful comments and for finding our problem setting interesting. We uploaded a revised version, and the changes are marked in blue.

Response to Question 1: Thank you for this question. The main difference from existing robust Q-learning results comes from the setting. Existing heavy-tailed RL studies consider only heavy-tailed rewards, so their value functions are bounded. In our setting, the transitions are heavy-tailed, so the state space is unbounded, and the next-state value in the Bellman target is also heavy-tailed and unbounded. As a result, two standard steps do not directly apply.

  • Adaptive targets. The standard analysis handles adaptive targets with a martingale argument, which needs a linear estimator and bounded targets. Neither holds for MoM with heavy-tailed targets. Instead, Lemma 2 compares the adaptive targets with fixed reference targets, using only two properties of the median: it changes by at most the largest change of the block means, and it is monotone. The monotonicity also keeps optimism in Lemma 3 (Section 4.2).
  • Unbounded values. The value errors grow with the state, so they cannot be bounded by a constant as in the standard analysis. In Lemma 3, we use growing regions and a boundary term for the transitions that leave these regions (Section 4.3). Lemma 4 bounds this boundary term and the out-of-region regret. These two terms are new, since analyses with bounded values do not need them (Section 4.4).

Since our model differs from those in these works, we believe that a one-to-one comparison of the regret analyses may not be straightforward. We clarified these points in the Introduction and Related Work (Section 1) and in Sections 4.2–4.3.

Response to Question 2:

Thank you for the important question.

Drift condition (Assumption 4, which was Eq. (28) in the original version). We believe that this condition is natural in many systems with heavy-tailed dynamics. For example, consider a cloud server that receives jobs with rare but very large bursts, and suppose that every service level can process more than the average amount of incoming work. Then a burst can make the queue very long, but the queue still decreases on average. In this case, the drift condition holds for any selected action, including exploratory actions. More generally, it holds whenever every action moves a large state toward the origin on average, which can be checked from the model (Proposition 1 in Appendix H).

We also separate the setting where the state is reset in each episode from the continuing setting, where the state is not reset (Section 2.1). The drift condition is needed only in the continuing setting, and it is used only in Lemma 4, to bound how often the state leaves [−U,U][-U,U] (Sections 4.1 and 4.4). In the reset setting, the same result holds without the drift condition (Proposition 2 in Appendix H). Thus, this condition is not needed by the algorithm itself.

However, as you pointed out, our analysis does not apply to systems without such a negative drift in the continuing setting, for example when some actions can make the state grow without bound. We state this as a limitation in the Conclusion and Appendix H.

State space (Assumption 1). This assumption is used only to count the states in the bounded region, and the algorithm does not use it. It holds for integer-valued states, such as queue lengths. The analysis extends to multidimensional countable state spaces, with a regret exponent that depends on the dimension (Appendix I). Continuous state spaces are not covered, since our algorithm keeps one estimate for each visited state. We state this as future work.

Response to Question 3: Thank you for this question. As in our response to Question 1, since existing heavy-tailed RL works assume bounded values, a direct comparison of the bounds may not be straightforward. Instead, we checked that our bound is consistent with known results. In our bound, γ=r−1\gamma = r-1 describes how strongly large states are controlled (Assumption 4). A larger γ\gamma means that large states are visited less often. In the formal limit γ→∞\gamma \to \infty, large states become negligible, and our exponent approaches 1/(1+ϵ)1/(1+\epsilon). This matches the order of the lower bound for heavy-tailed bandits (Bubeck et al., 2013). We would be glad to add a more detailed discussion on this comparison if it would be helpful.

In the revision, we tightened the last step of the analysis by choosing the threshold UU directly (Section 4.5 and Appendix G). With ϵ=r−1\epsilon = r-1, the bound is now O~((KH)2/(r+1))\widetilde{O}\big((KH)^{2/(r+1)}\big). For example, when r=1.5r = 1.5, the exponent improves from 0.8890.889 to 0.80.8. We do not claim that this rate is optimal. A lower bound for heavy-tailed transitions in an unbounded state space is still open, and we leave it for future work.

Dear Reviewer yqx1,

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.

Reviewer_yqx1OpenReview ↗

Response to Author

I thank the authors for the detailed response and for taking the time to address my questions.

I found the explanation of the technical challenges involving adaptive Bellman targets and unbounded value functions helpful. I also appreciate the improved regret bound and the additional results concerning the drift condition and multidimensional state spaces.

That said, while the rebuttal has helped clarify the assumptions and their applicability, I still feel that the results remain somewhat restricted. Similarly, I remain somewhat uncertain about the degree of technical novelty, though I do appreciate the challenges highlighted by the authors.

The rebuttal has improved my assessment of the paper, and I am inclined to reconsider my rating. I think the problem is interesting and relevant to the community, but I would like more time to carefully assess the revisions and consider the other reviewers' perspectives before making a decision. I will maintain my rating for now and revisit it during the reviewer discussion period.

Thank you very much for reading our response and for your reply. We sincerely appreciate that you will revisit and reconsider your rating. We fully understand your remaining concerns, so please take your time to look at the revision before making your decision. If you have any further questions, please let us know at any time.

Comments on the paper

2 comments

Dear Reviewers and Area Chair,

We sincerely thank all reviewers and the area chair for taking the time to read our paper, and the reviewers for providing detailed and helpful comments. We revised the paper based on all comments and uploaded the new version. The changes from the original version are marked in blue, except for minor changes. The main changes are as follows.

  • Main result. We improved the regret bound in Theorem 1 (Section 4.1). With ϵ=r−1\epsilon = r-1, the bound is now O~((KH)2/(r+1))\widetilde{O}\big((KH)^{2/(r+1)}\big). We also clearly show the dependence on the number of actions and states in Theorem 1. In addition, Theorem 1 now needs one fewer assumption. In the original version, we assumed a moment bound on the Bellman targets. We now show that this bound follows from Assumptions 2 and 3 (Section 4.1 and Appendix E). (Reviewers yqx1, 6qUH, VP56)
  • Drift condition. We explain that the drift condition is needed only when the state is not reset between episodes (Section 4.1). We added a simple sufficient condition that can be checked from the model (Proposition 1 in Appendix H). 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, the condition holds: a burst can make the queue very long, but the queue still decreases on average. We also show that the same result holds without the drift condition when the state is reset in each episode (Proposition 2 in Appendix H). However, our analysis does not cover systems in which some actions can make the state grow without bound, and we state this as a limitation (Conclusion and Appendix H). (Reviewers yqx1, VP56)
  • Technical novelty. Existing heavy-tailed RL studies consider only heavy-tailed rewards, and their value functions are bounded. Existing RL studies in unbounded state spaces assume light-tailed transitions. To the best of our knowledge, our work is the first to consider heavy-tailed transitions together with the unbounded state space that they create. In this setting, the existing analyses do not apply, and we develop new steps to handle it (Sections 4.2–4.4). We clarified these points in the Introduction and Related Work (Section 1). (Reviewer yqx1)
  • Presentation. To make Theorem 1 easier to follow, we collected all assumptions as Assumptions 1–4 and placed them before Theorem 1 (Section 4.1). We removed repeated statements, so the theorem and lemmas are shorter and easier to read. We also added a notation table and a short explanation of the relation among the parameters α\alpha, rr, ϵ\epsilon, and γ\gamma (Appendix A). (Reviewer VP56)
  • Generality. We generalized the cost from c(x,a)=g(x)+f(a)c(x,a) = g(x) + f(a) to c(x,a)=g(x)+f(x,a)c(x,a) = g(x) + f(x,a), so the action cost can now depend on the state. This change does not affect the proof (Section 2.1 and Appendix E). We also extended the analysis to multidimensional countable state spaces (Appendix I), and we explain how to handle an unknown number of episodes (Appendix G). (Reviewers VP56, yqx1, 6qUH)
  • Additional experiments. We added experiments with different values of mm, ϵ\epsilon, and the bonus coefficient, and with longer horizons H=5H=5 and H=10H=10 (Section 5 and Appendix K). Without retuning, MoM reduces the cumulative regret in all these settings, except when the bonus coefficient is too large and exploration dominates both methods. These results show that the benefit of MoM is robust to the choice of parameters and also holds for longer horizons. (Reviewer 6qUH)

We note that some equations are renumbered in the revised version, and we also simplified some of the notation. We will answer the questions of each reviewer in a separate comment.

Dear Reviewers and Area Chair,

Following the discussion, we made one more revision and clarified the drift condition. The new changes are marked in orange.

  • General cost. We now use a general cost c(x,a)c(x,a) instead of g(x)+f(x,a)g(x)+f(x,a), which makes the system model more general and clearer (Section 2.1). The proof does not change.

  • Drift condition. Our drift condition (Assumption 4) is a polynomial drift condition, which is weaker than the standard geometric one and is designed for heavy tails [1]. It is required for the actions selected during learning, but such a uniform condition over policies is also used in learning for countable state-space MDPs, often in a stronger form [2]. It is a condition on the system, not on the algorithm, and many practical systems satisfy it. For example, a call center usually keeps enough staff to answer more calls than the average number of incoming calls, even at its smallest staffing level. Then the queue decreases on average under any staffing level, even after a rare and very large burst of calls. Systems in which some actions make the state grow without bound (e.g., an action that stops the service) raise a different problem. In this paper, we focus on systems where rare large jumps occur but the state still returns on average.

We sincerely thank all reviewers for carefully reading our responses and for the valuable comments. We hope that these additional responses help to address your concerns.

[1] Jarner and Roberts, Polynomial Convergence Rates of Markov Chains, Annals of Applied Probability, 2002.

[2] Adler and Subramanian, Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space, NeurIPS, 2023.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.