- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies finite-horizon tabular MDPs with generative-model (simulator) access, known rewards and unknown transitions. An algorithm can query any and receive one next state, and its cost is the total number of queries. The paper compares two planners that use samples only and build no transition model.
Critical strengths
The question is clearly posed and the proofs are complete and self-contained. The lower bound allows adaptive queries, and Table 1 together with Appendix 9.1 carefully converts prior results to the expected-gap criterion. The key steps appear correct, including the gap decomposition in Lemma 2, Lemmas 6–8 and the constants in Theorem 2, the variance and anti-concentration arguments in Lemmas 10–11, and the query count in Theorem 3. Section 6.3 openly states that the two procedures differ in both evaluation and update, and that the NPG bound is not optimal. The simulations use 500 independent runs and bootstrap intervals.
Critical weaknesses
W1. By the paper's own proofs, both methods need the same order of samples per . Theorem 3 requires rollouts per triple. Corollary 1 requires iterations with one sample per triple, which is even a factor more. The only difference is the cost of one sample. A backward-induction sample is a full rollout that costs transitions, while an NPG sample is a single transition. The extra factor is exactly the rollout length.
W2. Theorem 1 seems to adapt the construction of Kakade (2003) with a standard KL and Pinsker argument. Its rate is already known in online and generative settings (Domingues et al., 2021; Li et al., 2024), and the only change is the expected-gap criterion. Theorem 2 is a standard stochastic mirror descent analysis in the framework of Lan (2023) and Xiao (2022). It bounds the estimation error crudely by and is a factor above the lower bound. Theorem 3 is a lower bound for one specific naive implementation.
W3. The theoretical separation is only in the power of . At fixed , the ratio of query counts between the two methods is a constant. The experiment uses only, so it cannot test the main result.
W4. The experiment fixes the step size at rather than the step size analyzed in Corollary 1.
Questions for authors
Q1. What is the sample complexity of NPG with fresh MC rollouts?
Q2. Do multiple sweeps () change Theorem 3?
Q3. As varies, does the query ratio between NPG and backward induction grow like ? Does NPG still win at larger budgets?