acceptodds
Under review as a conference paper at ICLR 2027

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

Abstract

While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs, and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of and from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we show that our value-based method requires no prior knowledge of problem-dependent quantities for communicating MDPs.

Primary area:
reinforcement learning
Keywords:
Average-reward reinforcement learning, model-free, PAC bound, weakly-communicating MDP, single trajectory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_UybyOpenReview ↗
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 O(1/ε2)O(1/\varepsilon^2) and O(1/ε4)O(1/\varepsilon^4), 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
  1. 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 dd. 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.

  2. 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.

  3. 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 Π\Pi? Such an example would help illustrate the role of this step.

  4. Definition of tkt_k in Algorithm 3. As I understand it, tkt_k is defined in the theorem and depends on the data-dependent quantity mkm_k. Therefore, tkt_k should not be a fixed input to the algorithm. However, the title of Algorithm 3 appears to suggest that tkt_k is specified in advance. Should tkt_k instead be determined within the algorithm?

3 comments

We appreciate the reviewer’s detailed comments.

Question 1.

The reviewer’s interpretation is correct. Given a function (or vector) d:R→Rd:\mathcal R\to\mathbb R, SAMPLE estimates

(Pd)(s,a)=E[d(S′)∣S=s,A=a],(s,a)∈R×A.(Pd)(s,a)=\mathbb E[d(S')\mid S=s,A=a], \qquad (s,a)\in \mathcal R\times\mathcal A.

Specifically, to estimate PdPd with high precision, we use at most mm successor observations for each state–action pair, and so the output of SAMPLE is

D(s,a)=1m∑j=1min⁡m,Ns,ad(Ss,a,j′),D(s,a)=\frac1m\sum_{j=1}^{\min\\{m,N_{s,a}\\}}d(S'_{s,a,j}),

where Ns,aN_{s,a} is the number of available visits during the sampling round. The trajectory-length choice ensures that every required pair receives at least mm 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)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),T_k=T_{k-1}+D_k, \qquad D_k\approx P(h_k-h_{k-1}),

instead of estimating PhkPh_k afresh. Then, the concentration bound for each increment depends on ∣hk−hk−1∣sp2\\|h_k-h_{k-1}\\|_{\mathrm{sp}}^2, 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)\widetilde O(\epsilon^{-7}) sample-complexity (Bravo and Contreras, 2024), while the method with recursive sampling improves it to O~(ϵ−2)\widetilde O(\epsilon^{-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.

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 πR\pi_{\mathcal R} be ε\varepsilon-optimal from every state in the restricted MDP, and let πˉ\bar\pi be any stationary extension to S\mathcal S. For s∈Rs\in\mathcal R and a∈Aa\in\mathcal A, the average reward remains unchanged because R\mathcal R is closed under every action by Fact 1, and so JπR(s,a)=Jπˉ(s,a)J^{\pi_{\mathcal R}}(s,a)=J^{\bar{\pi}}(s,a). 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 n≥1n\ge1, by definition of the average reward, omitting the first nn rewards does not change the limiting average reward. Thus, conditioning on (sn,an)(s_n,a_n) and using the Markov property, we get

Jπˉ(s,a)=Es,aπˉ[Jπˉ(sn,an)].J^{\bar\pi}(s,a) = \mathbb E_{s,a}^{\bar\pi}[J^{\bar\pi}(s_n,a_n)].

Then, we can split this expectation according to whether (sn,an)(s_n,a_n) belongs to R×A\mathcal R\times\mathcal A or T×A\mathcal T\times\mathcal A. Also, using Jπˉ(s,a)≥−∣r∣∞J^{\bar\pi}(s,a)\ge-\\|r\\|_\infty for all (s,a)∈S×A(s,a)\in\mathcal{S}\times\mathcal{A} and near-optimality on R\mathcal R, we obtain

Jπˉ(s,a)=Es,aπˉ![Jπˉ(sn,an)1(sn,an)∈R×A]+Es,aπˉ![Jπˉ(sn,an)1(sn,an)∈T×A]≥(J⋆−ε),Es,aπˉ![1(sn,an)∈R×A]−∣r∣∞,Es,aπˉ![1(sn,an)∈T×A]=(J⋆−ε),Ps,aπˉ((sn,an)∈R×A)−∣r∣∞,Ps,aπˉ((sn,an)∈T×A),\begin{aligned} J^{\bar\pi}(s,a) &= \mathbb E_{s,a}^{\bar\pi} \\!\left[J^{\bar\pi}(s_n,a_n)\mathbf 1_{\\{(s_n,a_n)\in\mathcal R \times \mathcal{A}\\}}\right] + \mathbb E_{s,a}^{\bar\pi} \\!\left[J^{\bar\pi}(s_n,a_n)\mathbf 1_{\\{(s_n,a_n)\in\mathcal T \times \mathcal{A}\\}}\right]\\\\ &\ge (J^\star-\varepsilon)\\, \mathbb E_{s,a}^{\bar\pi} \\!\left[\mathbf 1_{\\{(s_n,a_n)\in\mathcal R \times \mathcal{A}\\}}\right] - \\|r\\|_\infty\\, \mathbb E_{s,a}^{\bar\pi} \\!\left[\mathbf 1_{\\{(s_n,a_n)\in\mathcal T \times \mathcal{A}\\}}\right]\\\\ &= (J^\star-\varepsilon)\\, \mathbb P_{s,a}^{\bar\pi}((s_n,a_n)\in\mathcal R \times \mathcal{A}) - \\|r\\|_\infty\\,\mathbb P_{s,a}^{\bar\pi}((s_n,a_n)\in\mathcal T \times \mathcal{A}), \end{aligned}

where max⁡(s,a)∈R×A(J⋆(s,a)−Jπˉ(s,a))≤ε\max_{(s,a)\in\mathcal R\times\mathcal{A}}(J^\star(s,a)-J^{\bar\pi}(s,a))\le\varepsilon, and J⋆J^\star is constant in a weakly communicating MDP. Moreover, because T\mathcal T is transient under πˉ\bar\pi by Fact 1 and the state space is finite, we get

lim⁡n→∞Ps,aπˉ(Sn∈T)=0,lim⁡n→∞Ps,aπˉ(Sn∈R)=1.\lim_{n \rightarrow \infty}\mathbb P_{s,a}^{\bar\pi}(S_n\in\mathcal T)=0, \qquad \lim_{n \rightarrow \infty} \mathbb P_{s,a}^{\bar\pi}(S_n\in\mathcal R)=1.

Letting n→∞n\to\infty, we finally obtain

Jπˉ(s,a)≥J⋆−εfor all (s,a)∈S×A.J^{\bar\pi}(s,a)\ge J^\star-\varepsilon \qquad \text{for all } (s,a)\in\mathcal{S}\times\mathcal{A}.

In this way, we realized that, by just extending the policy obtained from QQ 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 tkt_k should be determined within the algorithm. In the revised draft, we have moved the computation of tkt_k 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.

Reviewer_2aqjOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies policy learning in average reward MDPs using one trajectory generated by a fixed positive behavior policy. It combines recurrent and transient state classification, sampling at return times, and existing optimization frameworks to establish finite sample guarantees for weakly communicating MDPs.

The proposed value based method, SAVIC, achieves O~(1/ϵ2)\widetilde O(1/\epsilon^2) sample complexity. Its variant SAVIC+ removes prior knowledge of problem dependent quantities for communicating MDPs. The policy based method, SCPMA, combines clipped policy mirror ascent with an anchored policy evaluation routine and achieves O~(1/ϵ4)\widetilde O(1/\epsilon^4) sample complexity with adaptive step sizes. These rates suppress substantial dependence on properties of the MDP and behavior policy.

Critical strengths
  1. Extending finite sample guarantees to one trajectory under weak communication is a useful theoretical contribution. The analysis accommodates transient states and does not require every policy to induce an ergodic chain. Sampling at successive visits allows the authors to handle dependence without imposing aperiodicity on the behavior chain. The significance lies in extending the applicability of existing methods to a broader sampling setting while preserving the favorable accuracy dependence of the value based approach.

  2. SAVIC+ provides the most compelling algorithmic result by removing prior parameter knowledge in communicating MDPs. The algorithm collects the required number of visits directly and uses an empirical Bellman residual to decide when to stop. This turns the theoretical convergence argument into an observable stopping procedure. Although the construction builds on existing anchored value iteration, establishing its sample complexity along a continuing trajectory makes the result more actionable.

Critical weaknesses
  1. The significance of the general guarantees is limited by substantial prior information requirements and potentially large problem dependent factors. SAVIC requires quantities governing transient escape, coverage, visitation frequencies, and the optimal value span. SCPMA additionally chooses its clipping level using a gap defined over deterministic policies and their recurrent classes, while its evaluation lengths and adaptive step sizes require further unknown quantities. Merely establishing that these quantities are finite does not clarify how large the resulting sample requirements can become. Table 1 compares only accuracy exponents, which makes the statistical improvement difficult to assess across different information requirements. The advertised policy rate also applies to adaptive step sizes; the constant step size bound has a leading accuracy dependence of 1/ϵ91/\epsilon^9.

  2. The algorithmic novelty is more limited than the repeated descriptions of novel methods suggest. SAVIC retains the anchored iteration and recursive estimation framework of Lee et al. (2025), while SCPMA retains the earlier clipped policy mirror ascent framework. The principal new contribution is their analysis and adaptation to trajectory sampling. That extension is valuable, but the paper should distinguish more clearly which conclusions require new arguments beyond combining return time sampling, existing coverage bounds, and existing convergence results. In particular, the stated need for the final policy perturbation is unclear under the paper’s own assumption that the transient set remains transient under every policy.

Questions for authors
  1. What is the minimal prior information needed to implement each algorithm? For SCPMA, can the policy dependent evaluation lengths be replaced explicitly by supplied uniform upper bounds? Please also clarify how the clipping parameter can be selected without knowing the gap over deterministic policies and recurrent classes.

  2. Why is the final perturbation in SAVIC necessary? Under Fact 1, the recurrent set is closed and its complement is transient under every policy. If the restricted policy is approximately optimal from every recurrent state, does any stationary extension already inherit the same average reward guarantee from transient starting states?

  3. Can Table 1 compare the complete sample bounds and required prior information? A worked example with transient states and a periodic recurrent class would also help demonstrate the additional scope of the results and illustrate the size of the coverage and policy evaluation factors.

3 comments

We appreciate the reviewer’s constructive comments.

Weakness 1 and Questions 1 and 3.

As the reviewer pointed out, finiteness of the problem-dependent quantities indeed does not clarify how large our resulting sample requirements can be. Specifically, SAVIC requires information about thit,tcov,∣Q⋆∣spt_{\mathrm{hit}},t_{\mathrm{cov}},\\|Q^\star\\|_{\mathrm{sp}}, 1/dmin⁡πb1/d_{\min}^{\pi_b}, and SCPMA requires information about thit,tcov,1/dmin⁡πb,tα,Qα,Cα,∣Q⋆∣∞,1/Gt_{\mathrm{hit}},t_{\mathrm{cov}},1/d_{\min}^{\pi_b},t_\alpha,Q_\alpha,C_\alpha,\\|Q^\star\\|_\infty,1/G. We acknowledge that all we did was show finiteness of these quantities, and we did not meaningfully quantify them. This is a limitation of our methods. However, we note that prior works by Li et al. (2024) and Lee and Ryu (2025b) also require problem-dependent information for their theoretical parameter choices. Additionally, we point out that what we actually need are certified upper bounds on the previously mentioned quantities, rather than their exact values, though the corresponding sample bounds may increase.

We agree that comparing only accuracy exponents in Table 1 is insufficient. First, we have expanded Table 1 in the main text by stating all the sample-complexity results we obtained, including ϵ−9\epsilon^{-9}, and mentioning which methods require no prior knowledge of problem-dependent quantities. Moreover, in the Appendix A, we have provided a detailed table with explicit sample complexities containing all the coefficients used in each work. For prior methods, Li et al. (2024) obtain an expected-error guarantee with

O~!(tmix3κ2μˉε2)\widetilde O\\!\left( \frac{t_{\mathrm{mix}}^3\kappa^2} {\bar\mu\varepsilon^2} \right)

samples under ergodicity and policy-dependent trajectory sampling, where tmixt_{\mathrm{mix}} controls mixing, μˉ\bar\mu is a uniform lower bound on the smallest eigenvalue of the relevant feature covariance matrices, and κ2\kappa^2 bounds the second moment of the span of the critic estimates. Tuynman et al. (2024) provide a model-based method without prior problem-dependent knowledge, with online sample complexity

O~!(SAD2ε2+S2AD3),\widetilde O\\!\left( \frac{SAD^2}{\varepsilon^2}+S^2AD^3 \right),

where DD is the MDP diameter. For Lee and Ryu (2025b), the single-trajectory bound for R-Anc-F-QI, when the Bellman approximation error is zero, is

O~!(b−1/κ(c0′)(1+κ)/κ(∣r∣∞+∣Qπ⋆∣∞)4∣Qπ⋆∣∞4Cμ4ε8),\widetilde O\\!\left( \frac{ b^{-1/\kappa}(c_0')^{(1+\kappa)/\kappa} (\\|r\\|_\infty+\\|Q^{\pi^\star}\\|_\infty)^4 \\|Q^{\pi^\star}\\|_\infty^4C_\mu^4 }{\varepsilon^8} \right),

where CμC_\mu is the coverage coefficient, and the stationary trajectory satisfies βℓ≤βˉe−bℓκ,\beta_\ell\le\bar\beta e^{-b\ell^\kappa}, the function-class and confidence factors are c0′=log⁡(1/δ)+log⁡!(max⁡c1,βˉ),c1=16e2(VF+1)(VFmax⁡+1)(24e)VF+VFmax⁡,c_0'=\log(1/\delta)+\log\\!\bigl(\max\\{c_1,\bar\beta\\}\bigr), c_1= 16e^2(V_{\mathcal F}+1)(V_{\mathcal F_{\max}}+1) (24e)^{V_{\mathcal F}+V_{\mathcal F_{\max}}}, where VFV_{\mathcal F} denotes the pseudodimension of F\mathcal F.

As these methods use different class of MDPs, sampling models, and information requirements, a direct comparison requires care. In particular, although both SAVIC+ and the Tuynman et al. require no prior problem-dependent bounds in communicating MDPs, Tuynman et al. adaptively control the actions in the online setting, whereas SAVIC+ uses a trajectory generated by a fixed behavior policy. On the other hand, both SAVIC and the method of Lee and Ryu consider a single trajectory in weakly communicating MDPs, but Lee and Ryu consider function approximation and impose stationarity, coverage, and mixing assumptions on the trajectory. Nevertheless, explicitly stating these requirements is useful, as the reviewer pointed out. We have expanded the comparison in Table 1 with detailed sample complexities in Appendix A.

The reviewer raised a good point. For SCPMA, the policy-dependent evaluation lengths can indeed be replaced by explicit uniform choices. Specifically, Proposition 4.1 permits

nk=⌈16tαQαε′⌉n_k= \left\lceil \frac{16t_\alpha Q_\alpha}{\varepsilon'} \right\rceil

for all kk since ttarπk≤tα,∣Qπk∣sp≤2∣Qπk∣∞≤2Qα.t_{\mathrm{tar}}^{\pi_k}\le t_\alpha, \\|Q^{\pi_k}\\|_{\mathrm{sp}} \le 2\\|Q^{\pi_k}\\|_\infty \le 2Q_\alpha. Moreover, this does not worsen the sample-complexity bound since we already use these uniform bounds in the analysis. We have revised this part to simplify the SCPMA algorithm.

Following the reviewer's suggestion, we have added the toy example in the Appendix A, which shows the finiteness of our coefficients.

Let S=s,0,1\mathcal S=\\{s,0,1\\} and A=a+,a−\mathcal A=\\{a_+,a_-\\}. Both actions have the same transition matrix, with rows and columns ordered as s,0,1s,0,1:

P=(1/21/20001010).P= \begin{pmatrix} 1/2&1/2&0\\\\ 0&0&1\\\\ 0&1&0 \end{pmatrix}.

Set

r(s,a)=0,r(0,a+)=r(1,a+)=1,r(0,a−)=r(1,a−)=0,r(s,a)=0,\qquad r(0,a_+)=r(1,a_+)=1,\qquad r(0,a_-)=r(1,a_-)=0,

and use the fixed behavior policy

πb(a+∣x)=1/2,πb(a−∣x)=1/2for all x∈S.\pi_b(a_+\mid x)=1/2,\qquad \pi_b(a_-\mid x)=1/2 \quad\text{for all }x\in\mathcal S.

The state ss is transient under every policy, while R=0,1\mathcal R=\\{0,1\\} is a closed recurrent class of period two. Thus, the MDP is weakly communicating. Then, for α∈(0,1/2)\alpha\in(0,1/2), we obtain

\\|Q^\star\\|_{\mathrm{sp}}=2, \\,\\,\\, G=1/2. \end{aligned}$$ **Weakness 2 and Question 2.** We agree that the contribution should be described more precisely. Following the reviewer's suggestion, we revised the contribution part in the introduction to (1) New single-trajectory analysis, (2) Adaptation of existing model-free methods, and (3) Improved sample complexity for policy-gradient methods. As the reviewer pointed out, our main contribution lies in the analysis of sampling from a single trajectory under a fixed behavior policy in weakly communicating MDPs and its integration into baseline methods. Specifically, Lemma 2.3 controls visit-indexed samples when the number of available returns is random and provides an exponential-moment bound through stopping-time arguments and the strong Markov property. We also suggest sampling subroutines and adapt the baseline methods, anchored value iteration with recursive sampling and $\alpha$-clipped policy-gradient methods, to single-trajectory sampling both algorithmically and theoretically. Additionally, for the policy-gradient method, there are two contributions. The first contribution is anchored policy evaluation with variance reduction. Compared to the prior work of Lee and Ryu (2026), the explicit sample complexity of policy evaluation improves from $\widetilde O(\varepsilon^{-6})$ to $\widetilde O(\varepsilon^{-4})$. This leads to an improvement in the explicit sample-complexity dependence for policy-gradient methods from $\widetilde O(\varepsilon^{-12})$ to $\widetilde O(\varepsilon^{-9})$ for constant step sizes and from $\widetilde O(\varepsilon^{-6})$ to $\widetilde O(\varepsilon^{-4})$ for adaptive step sizes. Also, while the sample complexity has hidden dependence on $\epsilon$ because $\alpha$ depends on $\epsilon$ in that prior work, in this work, through $G$, which quantifies the gap over deterministic policies and their recurrent classes, we make $\alpha$ independent of $\epsilon$.

We greatly appreciate the reviewer’s observation about policy perturbation. The reviewer is right. Let πR\pi_{\mathcal R} be ε\varepsilon-optimal from every state in the restricted MDP, and let πˉ\bar\pi be any stationary extension to S\mathcal S. For s∈Rs\in\mathcal R and a∈Aa\in\mathcal A, the average reward remains unchanged because R\mathcal R is closed under every action by Fact 1, and so JπR(s,a)=Jπˉ(s,a)J^{\pi_{\mathcal R}}(s,a)=J^{\bar{\pi}}(s,a). But the problem is the average reward at transient states, and this is why we used perturbation to establish a valid bound. However, indeed, we can handle this issue as follows.

For any fixed n≥1n\ge1, by definition of the average reward, omitting the first nn rewards does not change the limiting average reward. Thus, conditioning on (sn,an)(s_n,a_n) and using the Markov property, we get

Jπˉ(s,a)=Es,aπˉ[Jπˉ(sn,an)].J^{\bar\pi}(s,a) = \mathbb E_{s,a}^{\bar\pi}[J^{\bar\pi}(s_n,a_n)].

Then, we can split this expectation according to whether (sn,an)(s_n,a_n) belongs to R×A\mathcal R\times\mathcal A or T×A\mathcal T\times\mathcal A. Also, using Jπˉ(s,a)≥−∣r∣∞J^{\bar\pi}(s,a)\ge-\\|r\\|_\infty for all (s,a)∈S×A(s,a)\in\mathcal{S}\times\mathcal{A} and near-optimality on R\mathcal R, we obtain

Jπˉ(s,a)=Es,aπˉ![Jπˉ(sn,an)1(sn,an)∈R×A]+Es,aπˉ![Jπˉ(sn,an)1(sn,an)∈T×A]≥(J⋆−ε),Es,aπˉ![1(sn,an)∈R×A]−∣r∣∞,Es,aπˉ![1(sn,an)∈T×A]=(J⋆−ε),Ps,aπˉ((sn,an)∈R×A)−∣r∣∞,Ps,aπˉ((sn,an)∈T×A),\begin{aligned} J^{\bar\pi}(s,a) &= \mathbb E_{s,a}^{\bar\pi} \\!\left[J^{\bar\pi}(s_n,a_n)\mathbf 1_{\\{(s_n,a_n)\in\mathcal R \times \mathcal{A}\\}}\right] + \mathbb E_{s,a}^{\bar\pi} \\!\left[J^{\bar\pi}(s_n,a_n)\mathbf 1_{\\{(s_n,a_n)\in\mathcal T \times \mathcal{A}\\}}\right]\\\\ &\ge (J^\star-\varepsilon)\\, \mathbb E_{s,a}^{\bar\pi} \\!\left[\mathbf 1_{\\{(s_n,a_n)\in\mathcal R \times \mathcal{A}\\}}\right] - \\|r\\|_\infty\\, \mathbb E_{s,a}^{\bar\pi} \\!\left[\mathbf 1_{\\{(s_n,a_n)\in\mathcal T \times \mathcal{A}\\}}\right]\\\\ &= (J^\star-\varepsilon)\\, \mathbb P_{s,a}^{\bar\pi}((s_n,a_n)\in\mathcal R \times \mathcal{A}) - \\|r\\|_\infty\\,\mathbb P_{s,a}^{\bar\pi}((s_n,a_n)\in\mathcal T \times \mathcal{A}), \end{aligned}

where max⁡(s,a)∈R×A(J⋆(s,a)−Jπˉ(s,a))≤ε\max_{(s,a)\in\mathcal R\times\mathcal{A}}(J^\star(s,a)-J^{\bar\pi}(s,a))\le\varepsilon, and J⋆J^\star is constant in a weakly communicating MDP. Moreover, because T\mathcal T is transient under πˉ\bar\pi by Fact 1 and the state space is finite, we get

lim⁡n→∞Ps,aπˉ(Sn∈T)=0,lim⁡n→∞Ps,aπˉ(Sn∈R)=1.\lim_{n \rightarrow \infty}\mathbb P_{s,a}^{\bar\pi}(S_n\in\mathcal T)=0, \qquad \lim_{n \rightarrow \infty} \mathbb P_{s,a}^{\bar\pi}(S_n\in\mathcal R)=1.

Letting n→∞n\to\infty, we finally obtain

Jπˉ(s,a)≥J⋆−εfor all (s,a)∈S×A.J^{\bar\pi}(s,a)\ge J^\star-\varepsilon \qquad \text{for all } (s,a)\in\mathcal{S}\times\mathcal{A}.

In the revised draft, we have removed the third stage and replaced its justification with this direct extension argument, preserving the sample-complexity guarantee. We thank the reviewer for identifying a simplification that improves both the algorithm and its presentation.

References

[1] Tianjiao Li, Feiyang Wu, and Guanghui Lan. Stochastic first-order methods for average-reward Markov decision processes. Mathematics of Operations Research, 2024

[2] Adrienne Tuynman, Rémy Degenne, and Emilie Kaufmann. Finding good policies in average-reward Markov decision processes without prior knowledge. Neural Information Processing Systems, 2024.

[3] Jongmin Lee and Ernest K Ryu. Finite-time bounds for average-reward fitted Q-iteration. Neural Information Processing Systems, 2025b.

[4] Jongmin Lee and Ernest K Ryu. Policy gradient algorithms in average-reward multichain MDPs. arXiv preprint arXiv:2602.18003, 2026.

Reviewer_ma1iOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper lies in the field of average-reward MDPs. Specifically, the authors aim to establish finite-sample complexity guarantees in weakly communicating MDPs. First, the authors introduce the properties of weakly communicating MDPs, namely how to escape from transient states and how to sample recurrent states, building upon previous literature. Then, delve into the problem of sampling from a single trajectory, whose main challenge is to handle the dependency between samples. The issue is solved by leveraging stopping times and the Markov property. The authors introduce three algorithms to guarantee a PAC bound for obtaining an approximately optimal policy in this setup. SAVIC is a three-stage algorithm which allows it to escape from recurrent states, learns a near-optimal policy via anchored value iteration, and finally perturbs the policy to obtain an ϵ\epsilon-policy for the whole MDP. Since SAVIC requires knowledge of problem-dependent constants, SAVIC+ is introduced, which exploits the structure of a communicating MDP to avoid the first two steps of SAVIC, obtaining guarantees independent of prior knowledge. Finally, SCPMA is introduced, a policy-based method based on PMA, in which, in the first stage, the agent gathers information about the MDP; then, in the second stage, generalised policy iteration is performed. All the introduced algorithms provide finite-sample complexity guarantees, improving state-of-the-art results.

Critical strengths

Although highly technical, the paper is generally well written and self-contained. I appreciated that the authors include facts and lemmas in the main paper to support their claims. Furthermore, the paper is well grounded in the literature, and, when necessary, the results borrowed from previous works are made explicit.

Critical weaknesses

The authors acknowledge the fact that SAVIC and SCPMA need the knowledge of problem-dependent quantities. My main concern regards the initialisation of the Bellman operator T−1T^{-1}, which, to my understanding, seems to require knowledge of the reward function for any state and action in recurrent states. This would also have an impact on SAVIC+, since Algorithm 6 implements SAVIC. Do the algorithms need the rewards to be known? Should this be seen as an additional assumption?.

Furthermore, although the dependence on ϵ\epsilon in the sample complexity seems good, the authors do not discuss the optimality of the results, both in the accuracy and in the problem-dependent constants. Do the authors have any intuition on the optimality of their algorithms?

Finally, a minor concern regards the practical implementability of the proposed algorithms, since their parameter choices depend on quantities that may not be accessible in practice.

Questions for authors

See weaknesses.

3 comments

We appreciate the reviewer’s positive comments.

Weaknesses 1

We apologize for the confusion. As the reviewer pointed out, our analysis assumes that the reward function is known and deterministic, so environmental stochasticity arises only from the transition kernel. In the revised draft, we explicitly state this assumption in the problem formulation in the preliminaries subsection.

Also, though we assume that the reward function is known for simplicity of the argument, we believe that our technique can also be extended to unknown rewards. Consider an observed trajectory (s0,a0,r0,s1,a1,r1,…)(s_0,a_0,r_0,s_1,a_1,r_1,\ldots). Under our behavior-policy assumptions, the covering-time arguments ensure that every state–action pair in the recurrent set is visited with high probability after sufficiently many steps. If rewards are deterministic, a single observation at each such pair reveals its reward exactly. For bounded stochastic rewards drawn from a fixed state–action-dependent distribution independently of the past conditional on the current state–action pair, successive visits to each fixed state–action pair provide i.i.d. reward observations for estimating its mean reward, by the same strong Markov argument used in Fact 3. So, in the same manner, we can approximate the mean reward function using these reward samples, with additional reward-estimation error and sample cost.

Additionally, we note that assuming the mean reward function is known is a convention used in some sample-complexity analyses, including Tuynman et al. (2024). Li et al. (2024) and Lee and Ryu (2025b) use observed reward values rather than requiring the entire reward function to be known in advance. In our theoretical context, we mainly focus on stochasticity from the transition kernel, which can be problematic in the learning process.

Weaknesses 2

The reviewer raises very good points. To our knowledge, no prior work explicitly establishes a sample-complexity lower bound characterizing this average-reward setting, learning from a single trajectory generated by a fixed behavior policy, and its dependence on behavior-policy quantities. In contrast, for the generative model setup, which permits i.i.d. sampling from arbitrary state–action pairs, lower bounds have been extensively studied. In particular, for communicating MDPs, Wang et al. (2022, Theorem 4) establish, under the theorem's parameter conditions, a worst-case expected-sample lower bound of Ω!(SADε−2log⁡(1/δ)),\Omega\\!\left(SAD\varepsilon^{-2}\log(1/\delta)\right), where SS and AA are the numbers of states and actions, and DD bounds the MDP’s diameter. Their Corollary 5 also states the span-based lower bound Ω!(SAHε−2log⁡(1/δ)),\Omega\\!\left(SAH\varepsilon^{-2}\log(1/\delta)\right), where H=∣h⋆∣spH=\\|h^\star\\|_{\mathrm{sp}} is the span seminorm of an optimal bias function.

However, since a generative model provides stronger sampling access than our setup and can simulate a trajectory under a fixed behavior policy, these lower bounds also constrain our setting on the same MDP classes when the prior information is matched. They do not characterize the dependence on behavior-policy quantities. Observing that the ε−2\varepsilon^{-2} dependence is consistent with the statistical dependence appearing in these lower bounds, we expect that the sample complexities of SAVIC and SAVIC+ might be near-optimal in their dependence on ε\varepsilon. We indeed believe that establishing lower bounds tailored to our setting is a promising future direction, and we have added this discussion to the conclusion section of the revised draft.

Weaknesses 3

As the reviewer pointed out, we acknowledge that requiring knowledge of problem-dependent quantities limits the practical applicability of some of our algorithms. Specifically, SAVIC and SCPMA require prior information for their theoretical parameter choices in general weakly communicating MDPs, as stated in Theorems 3.3 and 4.2. In contrast, SAVIC+ does not require prior knowledge of these quantities and uses a data-dependent stopping rule for communicating MDPs, as Theorem 3.4 shows. We note that other prior methods, including Li et al. (2024) and Lee and Ryu (2025b), require problem-dependent information for their theoretical parameter choices. We have also added this point as a future direction in the conclusion section.

References

[1] Tianjiao Li, Feiyang Wu, and Guanghui Lan. Stochastic first-order methods for average-reward Markov decision processes. Mathematics of Operations Research, 2024

[2] Adrienne Tuynman, Rémy Degenne, and Emilie Kaufmann. Finding good policies in average-reward Markov decision processes without prior knowledge. Neural Information Processing Systems, 2024.

[3] Jongmin Lee and Ernest K Ryu. Finite-time bounds for average-reward fitted Q-iteration. Neural Information Processing Systems, 2025b.

[4] Wang, J., Wang, M., and Yang, L. F. Near sample-optimal reduction-based policy learning for average reward MDP. arXiv:2212.00603, 2022.

I thank the authors for their detailed responses, which address my concerns. Having also considered the other reviewer's comments, I decided to keep my original score.

Comments on the paper

1 comment

We appreciate the reviewer’s effort and constructive feedback. In response to the reviewer’s comments, we have revised the manuscript as follows. All changes are highlighted in blue.

Section 1

We clarified the contributions and expanded the comparison table [Reviewer 2aqj]. We also explicitly stated the assumption that the reward function is known [Reviewer ma1i].

Section 2

We added a brief explanation of the SAMPLE subroutine [Reviewer Uyby].

Section 3

We removed the policy perturbation step from SAVIC and instead use a natural extension of the policy [Reviewer 2aqj, Reviewer Uyby]. Accordingly, we revised Lemma 3.1 to show that this extension preserves the policy’s suboptimality guarantee. We also moved the computation of tkt_k inside the algorithm and clarified the distinct roles of anchoring and recursive sampling [Reviewer Uyby].

Section 4

We simplified SCPMA by replacing the policy-dependent evaluation lengths nkn_k with a common nn and updated Theorem 4.2 accordingly [Reviewer 2aqj].

Section 5

We added two future research directions: developing prior knowledge free method for weakly communicating MDPs and establishing lower bounds for our setting [Reviewer ma1i].

Appendix A

We added a table with explicit sample-complexity bounds corresponding to the comparison in the main text, together with a toy example illustrating the finiteness of the problem-dependent quantities [Reviewer 2aqj].

Appendix C

We provided the proof of the revised Lemma 3.1 [Reviewer 2aqj, Reviewer Uyby].

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.