- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
this paper studies online learning in adversarial tabular MDPs (transition is fixed but losses change arbitrarilly over episodes) with bandit feedback. the only difference with Jin et al. (2020) is that the learner additional has access to a "potentially misspecified prediction of the transition kernel"
this paper gives an FTRL-based algorithm, whose regret is no worse that the state-of-the-art bound in Jin et al. (2020), and can be sharper whenever the predition has good quality.
Critical strengths
- this paper is studying a reasonable problem in online learning, which generally lies under the framework of "algorithm with predictions", "learning-augmented algorithms", and "robust-consistency tradeoff"
- this paper proposes a novel detection/test of identifying the "accuracy"/"quality" of prediction, so that the final guarantee is shaper when prediction is good, while the worst-case guarantee is never hurt.
Critical weaknesses
- I'm concerned about some of the proofs. please see details in "Questions For Authors"
- the writing&presentation can be improved
Questions for authors
- the update rule in your main algorithm is FTRL-style, but the corresponding regret analysis (lemma 10) is for OMD?
- the proof for the general $\kappa $ part is unclear to me: if I look at the proof of lemma 20 (general ), it simply says that lemma 20 is implied by lemma 16. However, seems to me that lemma is only for ?
- In the proof of lemma 20, is it true that Term 1 always dominates Term 2? What if is super large?
some comments/feedback for writing:
- Abstract should be self-contained in general. in this case you may want to briefly define .
- "we characterize" between lines 363 and 364 should be capitalized?
- in the contribution list (sec. 1.2) you may want to talk about the range of so that the readers know what the final regret could be.
- wrong reference format in line 583 : "Ali Nouri. A bayesian sampling approach to exploration in reinforcement learning. In Proceedings of the. . . , 2009."
3 comments
Final Reminder: Follow-up on Our Rebuttal
Dear Reviewer q4dg,
As only a few hours remain in the discussion period, we would like to kindly follow up on our rebuttal. We have provided detailed clarifications addressing all your technical concerns. We would sincerely appreciate it if you could review our responses before the deadline and reconsider your rating in light of these clarifications.
Thank you very much for your time and consideration.
Best regards,
Authors
Reviewer q4dg: Final Follow-up on Our Rebuttal and Rating Reconsideration
Dear Reviewer q4dg,
Thank you again for your time and constructive feedback.
Although we have not yet received a follow-up response to our rebuttal, we have carefully addressed all your concerns. We would sincerely appreciate it if you could review our clarifications and consider increasing your rating accordingly.
Thank you very much for your time and consideration.
Best regards,
Authors
We sincerely thank the reviewer for the careful reading and constructive feedback. We particularly appreciate the reviewer for identifying several issues and ambiguities in our theoretical analysis. We have carefully revisited the proofs and revised the manuscript accordingly. Our detailed responses are provided below.
Q1. The update rule in your main algorithm is FTRL-style, but the corresponding regret analysis (Lemma 10) is for OMD.
We thank the reviewer for pointing out that the connection between the FTRL update in our algorithm and the regret analysis in Lemma 10 was not sufficiently clear in the original manuscript.
We have carefully revisited the proof and revised the derivation to explicitly establish the regret inequality from the stated FTRL optimization problem. In particular, we derive the required inequality using the optimality condition of the FTRL objective and the associated KL-divergence identity, while explicitly accounting for the nested feasible sets.
Importantly, the resulting bound in Lemma 10 for FTRL remains unchanged.
Corresponding revisions: The revised proof is provided in Lines 1166–1241, highlighted in blue.
We sincerely appreciate the reviewer for helping us improve the clarity and rigor of our theoretical analysis.
Q2. In the proof of Lemma 20, it is unclear to me if Lemma 20 is implied by Lemma 16. However, Lemma 16 seems to be only for κ=0.
We thank the reviewer for this insightful observation. We agree that the original presentation did not sufficiently explain how the analysis for the general κ case follows from the zero-discrepancy case.
To clarify this point, we have revised the proof of Lemma 20. Rather than directly invoking Lemma 16, we follow its proof strategy and replace the transition error bounds used in the zero-discrepancy analysis with the corresponding bounds established in Lemma 19.
More specifically, Lemma 19 provides two bounds under arbitrary κ: an upper bound on the total transition error, which is used to control Term 1; and a coordinate-wise upper bound on the transition error, which is used to control Term 2. Both bounds incorporate the factor 1+κ. Substituting these bounds into the corresponding steps of the proof of Lemma 16 allows us to extend the analysis to arbitrary κ.
Thus, the general κ analysis does not rely on the zero-discrepancy assumption of Lemma 16. Instead, it follows the same proof strategy using the more general transition error bounds established in Lemma 19. We have clarified this argument in the revised manuscript (lines 1742-1745). The corresponding revisions are highlighted in blue.
We appreciate the reviewer for pointing out that this distinction needed to be made explicit.
Q3. In the proof of Lemma 20, is it true that Term 1 always dominates Term 2? What if κ is super large?
We thank the reviewer for raising this question. We would like to clarify the relationship between the two terms.
Following the analysis of Jin et al. (2020, Appendix B.2) [2], we bound the two terms separately. In our setting, Term 1 grows as O(T), whereas Term 2 grows as O(lnT), with the remaining problem parameters fixed. Consequently, as the episode horizon T increases, Term 1 asymptotically dominates Term 2. Furthermore, both terms contain the same factor (1+κ). Therefore, even when κ is arbitrarily large, it does not change the asymptotic relative growth of the two terms.
Finally, we emphasize that our unified regret bound takes the minimum of the discrepancy-dependent and prediction-independent guarantees. Thus, regardless of the magnitude of κ, the prediction-independent worst-case guarantee remains valid.
[2] Jin, Chi, et al. ``Learning adversarial markov decision processes with bandit feedback and unknown transition." International Conference on Machine Learning. PMLR, 2020.
Additional revisions
Following the reviewer's suggestions, we have also improved the presentation of the manuscript and highlighted the corresponding revisions in blue.
We sincerely thank the reviewer again for the constructive comments, which have helped us improve the rigor, clarity, and presentation of our work.