- Rating
- 4
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies online reinforcement learning in tabular episodic Markov decision processes (MDPs), where the goal is to learn a near-optimal policy for each reward function in a finite collection. The collection of reward functions is known to the learner in advance. The paper proposes an algorithm that achieves minimax-optimal sample complexity without additional burn-in costs.
A closely related problem is reward-free (or reward-agnostic) exploration, where the reward functions are unknown to the learner during the data collection phase.
Critical strengths
-
The theoretical result is strong. To the best of my knowledge, this is the first work to achieve minimax-optimal sample complexity without additional burn-in costs in the studied setting.
-
The problem setup and theorem statements are clearly presented. The introduction is well written and provides an accessible overview of the research landscape, effectively positioning the paper within the existing literature.
Critical weaknesses
There is no critical weaknesses of the paper. In the questions for authors section, I have listed clarification questions that could, if addressed, potentially improve the quality of the paper.
Questions for authors
-
Is the multi-reward setting studied in this paper novel? More importantly, is there a fundamental difference between the reward-agnostic setting, where the collection of reward functions is unknown during data collection, and the multi-reward setting, where this collection is known in advance? Since reward-agnostic exploration already achieves minimax-optimality in terms of the leading sample complexity term, do the authors believe that eliminating the burn-in cost is also possible in this more challenging setting, or might there be an information-theoretic barrier?
-
Table 1 identifies some prior works as studying "reward-free exploration." Should the reward-agnostic setting also be explicitly identified for Zhang et al. (2020), Li et al. (2026), and Ridel & Cohen (2026)? Clarifying the distinctions among these settings would make the comparison more informative.
-
Judging from Table 1, the sample complexity bound of Zhang et al. (2020) does not appear to contain a burn-in term with higher-order dependence on S and H. Is this because such a term is omitted from the reported bound, or does their result genuinely avoid this burn-in cost? If the latter is true, how does their result differ from the claimed contribution of the present paper?
-
The introduction does not clearly explain what gives rise to the burn-in term or why eliminating it is difficult. Is there an existing line of research specifically focused on reducing or eliminating burn-in costs? What are the main technical obstacles, and how does the proposed approach overcome them?
-
The paper builds on the MVP framework of Zhang et al. (2021), which is appropriately acknowledged. However, the main paper does not explain this framework in sufficient detail to distinguish the existing techniques from the new contributions. Could the authors provide a more detailed overview of the MVP framework and explicitly identify the algorithmic modifications and technical challenges specific to the multi-reward MDP setting?
-
Could the authors elaborate on why conservative evaluation, which shrinks the continuation value rather than adding an exploration bonus, is necessary for establishing the proposed sample complexity bound? In particular, which part of the theoretical analysis requires this design choice, and what would fail if a more conventional bonus-based approach were used? I think it is addressed in the paragraph starting in line 348, but it is hard to understand fully from this paragraph. In my opinion, this is the most interesting technical contribution, and discussing this clearly in the main paper would significantly improve the quality of the paper.