- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies the problem of Best Of Both Worlds (BOBW) guarantees for MDPs with heavy-tailed losses (only finite moment less than or equal to 2), i.e., the loss distributions per round can either be fixed or chosen adversarially. This has previously been studied in a recent work by Chen et al. (2026). The authors' main contribution is to both improve the regret bounds (for both stochastic and adversarial settings) as well as to relax a truncated non-negativity assumption made by the previous paper. They also move to a policy optimization approach rather than an occupancy measure approach of the previous work.
Critical strengths
- Impoved regret bounds for all settings (known/unknown transitions, and stochastic/adversarial losses) of an interesting and established problem.
- Relaxing the truncated non-negativity assumption on the losses made by previous works.
Critical weaknesses
The main issue for me with this work is it's presentation and overall writing. While the problem is inherently complex, the authors should have made an effort to distill their key contributions and provide the reader with more insight on these key points. Instead the paper mostly describes the challenges with low details, and provides only boilerplate math in the actual analysis, deferring all informative details to the appendix.
I recognize the mathematical complexity of this problem, and how difficult it is to distill the key insights into human readable text/math. However, I believe this is a critical aspect of paper writing that cannot be overlooked.
Questions for authors
Could you narrow the presentation of the main text to focus either on a simpler setting (known transitions?) that still demonstrates the main techniques?
Can you cleanly connect to previous work analysis and then focus on the key points where your analysis differs and at least sketch how your approaches resolve the issues that arise?
4 comments
Thank you for incorporating my suggestions.
- The centered clipping explanation is very useful.
- The rest of the proof sketches introduce 3 new pages, which are extremely math dense. I made a best effort to go over them given my time constraints. I found it somewhat hard to follow, though I am not sure how much this can be avoided.
Given that I could not fully go over the new 3 pages, I still have some reservations regarding acceptance. However, they are quite minor and I will not object to it.
Thank you for your positive feedback! We are glad to hear that our explanation of the centered clipping mechanism was helpful, and we appreciate the time you spent reviewing the additional proof sketches.
We agree that even the proof sketch for the known-transition case is a bit dense. Nevertheless, we would like to note that this is mainly due to the following two reasons:
- First, although our algorithms build on the dilated-bonus policy optimization framework in [1,2], our approach to eliminating the dependence on the optimal action at each state differs from that in [1]. As mentioned, [1] achieves this through a sophisticated conditional “loss shifting” technique, whereas we achieve it directly through our advantage function estimator and the carefully designed clipping threshold . Thus, even without considering the effects of heavy-tailed noise, we believe this different approach to eliminating the dependence of the FTRL stability term on warrants an explanation. Providing that explanation takes a fair amount of space in the Bounding paragraph of our proof sketch.
- Second, heavy-tailed feedback introduces additional challenges. In particular, we need to explain how we control the signed bias weighted by the comparator’s occupancy , which is the focus of the Bounding paragraph. Moreover, since one of our motivations is to eliminate the truncated non-negativity assumption required in [3], we also devote space to explaining how we achieve this in the Bounding paragraph.
Therefore, the proof sketch is indeed somewhat dense, but this was not intentional. Its density stems from the several new challenges posed by heavy-tailed noise and from the fact that, even without such noise, the key idea for eliminating the dependence on in our algorithm and analysis differs from that in [1] for studying BOBW PO for MDPs with bounded feedback. Our aim was to provide enough details to explain both the new challenges posed by heavy-tailed noise and the difference between our approach to eliminating the dependence on and that of [1].
We will include the above discussion in a future version of our paper to further clarify the role of each part of the proof sketch and help readers follow the main ideas more easily.
[1] Dann et al. Best of both worlds policy optimization. ICML, 23.
[2] Luo et al. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. NeurIPS, 21.
[3] Chen et al. Best-of-both-worlds for heavy-tailed markov decision processes. ICML, 26.
Thank you for the additional clarifications. I understand the challenges. I will consider this positively in the post rebuttal discussion period.
Response 1
We thank the reviewer for recognizing the significance of our results and our elimination of the truncated non-negativity assumption of previous work. Our response to each question is provided below.
Q1. "Instead the paper mostly describes the challenges with low details, ... to the appendix." "I recognize the mathematical complexity of this problem, ... cannot be overlooked." "Could you narrow the presentation of the main text to focus ... demonstrates the main techniques?"
We would like to thank the reviewer again for raising this suggestion, which we believe further improves the readability and the clarity of our paper.
We have now restructured our Section 3 to focus only on the algorithmic details for the known-transition setting (highlighted in orange). Further, we rewrote the part about the construction of our advantage function estimator and the centered clipping mechanism to provide more insights. In particular, we elaborate on why the canonical Q-function estimator will make it difficult to achieve O(poly(logT)) regret in the stochastic regime, and why our advantage function estimator can overcome this obstacle. We also provide a more accurate description of the intuition behind the design of our learning rate βt. The discussion of these key insights is highlighted in red. We defer all the algorithmic details for the extension to the unknown-transition case to Appendices A.1-A.2 for better readability.
Q2. "Can you cleanly connect to previous work analysis ... resolve the issues that arise?"
Thanks again for this comment!
We have rewritten the proof sketch for our Theorem 4.1, which is now highlighted in orange and focuses only on the known-transition case. In particular, we now first invoke the global-to-local regret reduction lemma from previous works on policy optimization [1, 2] and then explain what the key differences and difficulties are and how we address them. We have further emphasized the insights underlying the key technical parts of our proofs and have tried our best to avoid going into too many low-level computational details. These key insights as well as the derivations associated with them are highlighted in red. The additional proof sketch for the unknown-transition case is deferred to Appendix A.3.
[1] Dann et al. Best of both worlds policy optimization. ICML, 23.
[2] Luo et al. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. NeurIPS, 21.