- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This submission considers PAC RL with known bounded rewards in episodic low-rank MDPs w/ finite realizable transition-kernel class . It introduces an uncertainty marking machinery that achieves episode sample complexity in the time-homogeneous setting and in the time-inhomogeneous setting, improving upon prior MLE-based sample complexity bounds by factors of and , respectively; at least in certain regimes. To give computationally efficient implementation principles, it provides polynomial-time subroutines for Monte Carlo Hellinger radius estimation, augmented-MDP simulation, rare-switching linear optimistic planning, and slope bisection. It also establishes lower bounds of in the homogeneous setting and in the inhomogeneous setting.
Critical strengths
- The original, mathematically rigorous resolution of the horizon-dependence issue in the important low-rank MDPs model based on a coupling argument for the first-mark trajectory.
- Exemplary scholarly faithfulness, precision, and transparency: This paper is a model of scholarly writing. Every inherited tool, including Ville supermartingale MLE concentration and the one-step-back inequality (Huang et al., 2026; Cheng et al., 2023), the trajectory Hellinger chain rule (Foster et al., 2024), the binary hypothesis-testing variational dual (Elkayam & Feder, 2016), and rare-switching LSVI (Gao et al., 2021), is credited with pinpoint citations at the exact step of use. Furthermore, the paper candidly documents both the high-degree polynomial sample budgets of its certified planning reduction and the exact differences between its certified oracles and the sampled-integration neural implementation in Section 6, as well as why its inhomogeneous lower-bound family does not settle the coefficient in the extreme high-confidence regime.
Critical weaknesses
- The large polynomial exponents in the certified simulation budget in Appendix E.6 and the remaining gap on the explicit confidence term in the time-inhomogeneous setting are transparently disclosed and analyzed in the paper, and do not detract from the primary statistical contributions.
Questions for authors
- Tightening the scaling in
LINPLAN(Appendix E.3, p. 36): InLINPLAN, the simulated episode count arises because the unnormalized augmented return is bounded by with , so normalizing by shrinks the target accuracy to . Since the first-mark indicator occurs at most once per episode (so the cumulative bonus contribution along any trajectory is in rather than , and its expected value under the selected policy is small near the bisection threshold), is it possible to avoid paying the worst-case scaling in ? - Inhomogeneous confidence dependence when (Appendix D.4, pp. 31–32): Appendix D.4 shows that for the restricted hard family , the stagewise estimation errors concentrate across the active stages to give an confidence term. For general inhomogeneous , do you conjecture that the term in Theorem 4 can be improved to by bounding empirical Hellinger errors summed across all stages under a single joint supermartingale (paying from the product class but only for the confidence level), or does stagewise radius feasibility require separate per-stage concentration?
Minor issue: Equation (64) (p. 29, line 1560), replace the undefined symbol in the numerator with the episode count
General question: should the machinery of Lemma A.6 and its proof be demonstrated more concretely in the main text, especially given the fact that the coupling argument in the proof of Lemma A.6 seemingly does not hinge on the low-rank structure?
4 comments
Response to Question1-2
Q1: Tightening the scaling in LINPLAN (Appendix E.3, p. 36): In LINPLAN, the simulated episode count arises because the unnormalized augmented return is bounded by with , so normalizing by shrinks the target accuracy to . Since the first-mark indicator occurs at most once per episode (so the cumulative bonus contribution along any trajectory is in rather than , and its expected value under the selected policy is small near the bisection threshold), is it possible to avoid paying the worst-case scaling in ?
A1: We thank the reviewer for this insightful suggestion. The current normalization by already exploits the fact that the first-mark bonus is paid at most once per episode. Without this property, the worst-case augmented return could scale as . Nevertheless, the one-time bonus can still have magnitude , so the uniform bound on the unnormalized return remains .
We agree that the resulting dependence on is conservative. In particular, near the bisection threshold, the expected marking contribution may be much smaller than its worst-case magnitude. However, the LINPLAN guarantee must hold before TESTMARK determines whether the returned policy is near the threshold, so this property cannot be directly assumed in the current analysis.
A promising direction is to exploit the Bernoulli structure of the marking reward through variance-sensitive concentration or a refined analysis that treats the original reward and marking probability separately. Such an approach may reduce the dependence on , but establishing a uniform planning guarantee with improved complexity would require additional analysis. We therefore keep the conservative bound in the present theorem.
Q2: Inhomogeneous confidence dependence when (Appendix D.4, pp. 31–32): Appendix D.4 shows that for the restricted hard family , the stagewise estimation errors concentrate across the active stages to give an confidence term. For general inhomogeneous , do you conjecture that the term in Theorem 4 can be improved to by bounding empirical Hellinger errors summed across all stages under a single joint supermartingale (paying from the product class but only for the confidence level), or does stagewise radius feasibility require separate per-stage concentration?
A2: We thank the reviewer for this insightful suggestion. We agree that a joint supermartingale over the product class is a promising approach to improving the confidence dependence in the time-inhomogeneous setting. In principle, such an argument could incur for model complexity while paying only a single confidence penalty, rather than treating each stage separately.
However, joint concentration alone does not immediately yield the proposed dependence. Our current analysis relies on stagewise Hellinger-radius feasibility to certify the uncertainty estimates used by the exploration and planning subroutines. A bound on the sum of empirical Hellinger errors across stages does not directly establish these individual feasibility conditions. Thus, closing the gap may require a joint uncertainty certificate or a refined analysis that avoids enforcing separate stagewise radius constraints. We view this as an interesting future work.
Response to Question3-4
Q3: Equation (64) (p. 29, line 1560), replace the undefined symbol in the numerator with the episode count .
A3: We thank the reviewer for catching this typo. The symbol in Equation (64) is undefined and should be replaced by the episode count . Accordingly, the term should read . We will correct this in the revision.
Q4: Should the machinery of Lemma A.6 and its proof be demonstrated more concretely in the main text, especially given the fact that the coupling argument in the proof of Lemma A.6 seemingly does not hinge on the low-rank structure?
A4: We thank the reviewer for this suggestion. We agree that the core argument of Lemma A.6 is more general than the low-rank MDP setting: its coupling/convex-geometric machinery only requires a finite-dimensional linear representation of the form , and does not itself rely on the low-rank transition factorization.
The low-rank structure is used when instantiating Lemma A.6 in our MDP analysis: it ensures that the relevant quantities admit a -dimensional linear representation, so that the resulting bound scales with the low-rank dimension rather than the size of the state space.
We will clarify this separation and give a more concrete description of the mechanism in the main text.
Thank you for your detailed feedback. I keep my positive evaluation unchanged.
Response to Weakness
We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses to each point below.
W1: The large polynomial exponents in the certified simulation budget NSAMP=O(d4AH13/ϵ8) in Appendix E.6 and the remaining H(1+logd) gap on the explicit log(1/δ) confidence term in the time-inhomogeneous setting are transparently disclosed and analyzed in the paper, and do not detract from the primary statistical contributions.
A1: We thank the reviewer for recognizing our primary statistical contributions and for acknowledging the computational and confidence-dependence limitations.
Regarding computational complexity, Appendix E provides a fully specified polynomial-time implementation of our exploration framework, including but not limit to, uncertainty-radius estimation, rare-switching optimistic planning (
LINPLAN), and slope bisection. The large polynomial exponents in NSAMP arise from the conservative accuracy. For example,LINPLANuses a worst-case bound on the augmented return.Our computational contribution is therefore to establish polynomial-time implementability under an approximate MLE oracle. Importantly, these simulation costs are separate from the number of interactions with the real environment. We also acknowledge the remaining H(1+logd) gap between the upper and lower bounds in the explicit log(1/δ) confidence term for the time-inhomogeneous setting. Tightening this dependence and reducing the polynomial simulation costs are interesting future directions.