- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the sample complexity of infinite-horizon average-reward reinforcement learning in tabular MDPs under weakly communicating and communicating assumptions, where data are collected along a single trajectory. The authors propose a value-based algorithm and a policy-based algorithm that achieve sample complexities of and , respectively.
The value-based algorithm consists of three stages. In the first stage, the algorithm identifies the recurrent class by executing an arbitrary policy. In the second stage, it performs anchored value iteration with recursive sampling for variance reduction. In the final stage, it perturbs the resulting policy. The algorithm requires prior knowledge of several problem-dependent parameters, including the hitting time, covering time, and span of the optimal value function. Under the stronger assumption of communicating MDPs, the authors further develop an algorithm that does not require prior knowledge of these parameters.
The policy-based algorithm builds on mirror ascent, alternating between policy evaluation and policy improvement. The policy evaluation step leverages several techniques developed for the value-based algorithm, including anchoring, single-trajectory estimation, and recursive sampling.
Critical strengths
Strong theoretical contribution. To the best of my knowledge, this paper is the first to establish finite-sample complexity guarantees for average-reward reinforcement learning in weakly communicating MDPs using data collected along a single trajectory.
Critical weaknesses
Clarity of presentation and algorithmic motivation. The proposed algorithms combine several techniques, but the motivation for each technique and its specific contribution to the theoretical guarantees are not sufficiently clear. In particular, it would be helpful to explain which components are essential for obtaining the stated sample complexity bounds and what would be lost if certain components were omitted.
Questions for authors
-
Role of the SAMPLE subroutine. Could the authors clarify what quantity the SAMPLE subroutine is intended to estimate? My understanding is that it estimates a quantity associated with the given function . Is this interpretation correct? A brief explanation of the purpose of SAMPLE and its role in the overall algorithm would improve the clarity of the presentation.
-
Motivation for anchoring and recursive sampling. The value iteration stage combines several techniques, particularly anchoring and recursive sampling. Could the authors explain more explicitly why each technique is needed and what role it plays in achieving the theoretical guarantees? Are both techniques essential for obtaining a provable sample complexity bound, or could one obtain a (possibly weaker) bound without them? Clarifying the individual contributions of these techniques would make the algorithm design easier to understand.
-
Necessity of policy perturbation. Could the authors explain why the policy perturbation step in the third stage is necessary? In particular, is there an example of an MDP for which Lemma 3.1 fails when the policy does not lie in the interior of ? Such an example would help illustrate the role of this step.
-
Definition of in Algorithm 3. As I understand it, is defined in the theorem and depends on the data-dependent quantity . Therefore, should not be a fixed input to the algorithm. However, the title of Algorithm 3 appears to suggest that is specified in advance. Should instead be determined within the algorithm?
3 comments
Question 3
We appreciate the reviewer for raising this question. Upon revisiting the argument, we found that the perturbation is unnecessary in our settings.
Let be -optimal from every state in the restricted MDP, and let be any stationary extension to . For and , the average reward remains unchanged because is closed under every action by Fact 1, and so . But the problem is the average reward at transient states, and this is why we used perturbation to establish a valid bound. However, we can handle this issue as follows.
For any fixed , by definition of the average reward, omitting the first rewards does not change the limiting average reward. Thus, conditioning on and using the Markov property, we get
Then, we can split this expectation according to whether belongs to or . Also, using for all and near-optimality on , we obtain
where , and is constant in a weakly communicating MDP. Moreover, because is transient under by Fact 1 and the state space is finite, we get
Letting , we finally obtain
In this way, we realized that, by just extending the policy obtained from in SAVIC, we directly obtain a near-optimal policy. So we have removed that step and replaced its justification with this direct extension argument, preserving the sample-complexity guarantee. We have revised the draft accordingly at the end of subsection 3.1.
Question 4.
The reviewer is correct. The quantity should be determined within the algorithm. In the revised draft, we have moved the computation of inside the loop and removed it from the list of predetermined numerical inputs.
Critical weakness
Following the reviewer's suggestion, we have added a description of the SAMPLE subroutine and clarified the roles of anchoring and recursive sampling in the revised draft. We appreciate the reviewer's effort to improve the clarity of the presentation. If the reviewer has any additional comments or questions, we are happy to answer. Also, if our responses have addressed reviewer's concerns, we would greatly appreciate your reconsideration of the overall score.
References
[1] Jongmin Lee and Ernest Ryu. Optimal non-asymptotic rates of value iteration for average-reward MDPs. International Conference on Learning Representations, 2025a.
[2] Mario Bravo and Juan Pablo Contreras. Stochastic Halpern iteration in normed spaces and applications to reinforcement learning. arXiv preprint arXiv:2403.12338, 2024.
[3] Jongmin Lee, Mario Bravo, and Roberto Cominetti. Near-optimal sample complexity for MDPs via anchoring. International Conference on Machine Learning, 2025.
I thank the authors for the responses. They addressed my concerns and questions. I will raise the score to 3 accordingly.
We appreciate the reviewer’s detailed comments.
Question 1.
The reviewer’s interpretation is correct. Given a function (or vector) d:R→R, SAMPLE estimates
(Pd)(s,a)=E[d(S′)∣S=s,A=a],(s,a)∈R×A.
Specifically, to estimate Pd with high precision, we use at most m successor observations for each state–action pair, and so the output of SAMPLE is
D(s,a)=m1∑j=1minm,Ns,ad(Ss,a,j′),
where Ns,a is the number of available visits during the sampling round. The trajectory-length choice ensures that every required pair receives at least m observations with high probability, as theoretically guaranteed by Lemma 2.3.
Following the reviewer's suggestion, we have added a brief explanation of SAMPLE after Lemma 2.3 in subsection 2.3.
Question 2.
We apologize for the confusion. Anchored value iteration and recursive sampling address different difficulties. First, anchoring provides an explicit finite-iteration convergence guarantee. In the average-reward setting, the Bellman operator is generally noncontractive, and standard value iteration can oscillate on periodic MDPs. Interestingly, anchoring handles this issue. Lee and Ryu (2025a) showed that the anchored update provides an O(1/k) bound on the span of the Bellman residual in the exact setting, and this residual bounds the policy error.
On the other hand, recursive sampling provides us with efficient sample complexity. Specifically, recursive sampling uses
Tk=Tk−1+Dk,Dk≈P(hk−hk−1),
instead of estimating Phk afresh. Then, the concentration bound for each increment depends on ∣hk−hk−1∣sp2, and the theoretical analysis shows that this gives a variance-reduction effect. Particularly, in the generative model setup, the earlier anchored value-iteration method without recursive sampling shows a O(ϵ−7) sample-complexity (Bravo and Contreras, 2024), while the method with recursive sampling improves it to O(ϵ−2) (Lee et al., 2025).
To summarize, anchoring provides the convergence guarantee used in our analysis, and recursive sampling is not necessary merely to obtain some finite sample-complexity guarantee, but it is used for efficient sample complexity. We have added an additional explanation about the different roles of anchoring and recursive sampling at the end of subsection 3.1.