- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper focuses on improving the total sample complexity of stochastic policy mirror descent for online discounted reinforcement learning. Building on Ju & Lan (2025), the authors proposed an adaptive rollout length so that each iteration only needs to sufficiently explore states where multiple actions still have non-negligible probabilities. This yields an instance-dependent sample complexity bound based on statewise hitting times and advantage gaps, at the cost of an additional factor in the iteration complexity. The authors also show that their algorithm achieves a matching upper and lower sample complexity bound, up to logarithmic factors, on a specific family of MDPs with a fixed discount factor.
Critical strengths
1, The proposed adaptive rollout length is interesting and seems to reduce the total sample complexity by avoiding unnecessary exploration of states whose optimal actions have already been identified.
2, The authors establish matching upper and lower sample complexity bounds on a constructed family of MDPs.
Critical weaknesses
1, The proposed analysis introduces an additional factor in the iteration complexity compared with Ju & Lan (2025). Therefore, the resulting total sample complexity is not necessarily better than the previous guarantee.
2, Although the authors demonstrate a polynomial improvement over a global exploration charge on a specific family of MDPs, it remains unclear how much the general sample complexity bound improves over the original -dependent bound of Ju & Lan (2025).
Questions for authors
1, Can the authors provide a more quantitative comparison between their general sample complexity bound and the original -dependent bound of Ju & Lan (2025), beyond the constructed examples?
2, Can the authors characterize a broader class of MDPs for which the reduction in rollout complexity outweighs the additional factor, leading to a provable improvement in total sample complexity?
3, Is the additional dependence necessary for the proposed algorithm, or could it be avoided with a tighter convergence analysis?
4 comments
Thanks the authors for the rebuttal. However, my concerns still remain.
On the sample complexity of Ju & Lan According to Theorem 3.5 of Ju & Lan, isn't the sample complexity ? Then the total complexity of this paper replace with a 'local' constant at the cost of additional .
To address my concern, could the authors also provide a analysis on dependence on and other problem dependent constant?
On relation between and The authors claim a relation between and which shows that the local count is always smaller. However, I did not find a formal proof supporting the claim in paper. Further, I am asking about whether the benefit gain from local count can balance the additional in iterate count so the total sample complexity is indeed smaller. To answer this, I believe it is necessary to expand every constant in terms of discount factor, problem dependent constant like mixing time so a clean comparison can be made.
Thanks a lot for your follow-up questions. We response as follows.
On the sample complexity of Ju & Lan
Ignoring the factors in , the complexity in Theorem 3.5 of Ju & Lan is . Here , and is the Lipschitz constant of the regularizer. Our setting has no regularization, so , and contributes an additional . Hence, their total complexity is
The exploration term in our paper is . In the worst case, when all gaps are below , it becomes
As for the dependence of on and on the other constants, under the geometric ergodicity assumption of Ju & Lan we have with (Corollary 3.10), where is the mixing parameter of the optimal policy and its stationary distribution. In comparison, . Hence, carries , whereas carries .
Compared with Ju & Lan, our bound contains an additional outside these constants. It comes from the different proof techniques mentioned above. In their paper, they check the bias control of and while to apply it to get the result, they require the bias control of and earlier intermediate , which requires additional verification. We therefore adopt another technique to control the last iterate, which pays an extra in the error of the last iterate, and this becomes in the iteration count after squaring. Hence, we think that the two bounds are not directly comparable in this factor.
On the relation between and
The comparison between the local and the global count with the same is Proposition 3.5. Ju & Lan consider the global count and use to build the global bound, which can be looser than the global count with . As compared earlier in this reply, under the geometric ergodicity regime of Ju & Lan we have and . The upper bound on is given in Corollary 3.10. Besides, on an explicit family (Section 4), we discuss how the uniform upper bounds on and on can be loose: both grow exponentially with , while a careful analysis based on the structure of the MDP gives a polynomial bound via controlling .
For comparison, as derived above, the two final bounds are
The factor in front of our bound is the additional one from the different proof technique discussed above, and it may be not directly comparable. In the remaining factors, the powers of , and in our bound are all smaller.
My concerns have been addressed and I raised my score to 3.
Response to Reviewer Dhz2
We thank the reviewer for the review, and respond to the weaknesses and questions in the following.
The different dependence on γ comes from a different proof technique. The last-iterate analysis of Ju & Lan requires bias control along earlier iterates πt0, whereas the bias control that is verified is relative to the optimal policy π∗. We did not adopt that proof technique and instead prove last-iterate convergence directly. The direct argument has one additional factor (1−γ)−1 in the error of the last iterate, which becomes (1−γ)−2 in the iteration count. This is the only additional factor. Since the two analyses use different techniques, and theirs is not applicable when bias control along earlier iterates is not available, the two iteration counts are not directly comparable.
Besides the iteration count, the comparison could be made on the total sample complexity. There, in terms of γ and ε, the bound of Ju & Lan is O((1−γ)−5ε−2Dexpl), where the global constant Dexpl∝(1−γ)−2bˉ contains the mixing-time parameter bˉ and can be exponential in the mixing time. Our exploration term is O((1−γ)−5maxsHθ(s)/max(1−γ)ε,Δ(s)2), which avoids this constant. Whether the additional factor that occurs in our analysis can be removed could be a possible future direction. The revised paper states this comparison in Remark 3.7 (lines 311–313) and explains where the factor arises in Section 5.1 (lines 463–464).
The improvement holds for general MDPs, beyond the constructed family. The Dexpl-dependent bound charges the hardest-to-reach state at every iteration, which is a global count, whereas our bound is a local count that charges each state only until it is locked. With the same hitting cost Hθ, the two exploration terms are
global count((1−γ)ε)2maxsHθ(s)andlocal countsmaxmax(1−γ)ε,Δ(s)2Hθ(s).
The local count is never larger than the global one. The gain matters most in the high-precision regime. Once the accuracy (1−γ)ε falls below the gap of a state, that state is charged Δ(s)−2 and its cost stops growing with 1/ε. For example, as ε approaches 0, the global count grows like ε−2 times the cost of the hardest state, whereas in the local count only the states whose gaps are still below the accuracy are charged ε−2, and if all gaps are positive the exploration term becomes independent of ε. The improvement therefore appears whenever hard-to-reach states have gaps above the target accuracy.
The comparison above is made within our framework, with the same hitting cost Hθ. In Ju & Lan, this cost is bounded through the mixing time of the intermediate policies, which gives Dexpl. On the family we provide, Dexpl grows exponentially in n, whereas maxsHθ(s)=n2. The revised paper states this comparison in the introduction (lines 97–100) and discusses it in Section 3.5 (lines 322–350).