acceptodds
Under review as a conference paper at ICLR 2027

Asymptotically Optimal Model-Free Reinforcement Learning for Average-Reward MDPs

Abstract

We study average-reward reinforcement learning in finite weakly communicating Markov decision processes with access to a generative model under an working-space constraint, where and denote the numbers of states and actions, respectively. Let , where is an optimal bias function. Our basic algorithm requires no prior bound on and terminates almost surely. With high probability, it returns a stationary deterministic policy that is -optimal from every initial state using \[ \tO\left( SAH\eps^2 + S^14/3A^4/3H^4/3\eps^4/3 \right) \] samples. For fixed , this bound matches the span-based statistical lower bound up to logarithmic factors as . Our approach has two key ingredients: (i) reward shaping based on a coarse reference bias to reduce the value scale of the planning problem; and (ii) space-efficient linear programming coupled with a randomized square-grid decoder that reconstructs transition probability on demand.

Primary area:
learning theory
Keywords:
Weak-communicating average-reward MDP, model-free method, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ecwUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The setting is a weakly communicating average-reward MDP with a generative model, and the constraint that drives the paper is working space of order Õ(SA): the learner is not allowed to hold an empirical transition kernel. The unknown bias span H is handled by trying scales G = 1, 2, 4, ... in turn. At each scale the method first obtains a rough reference bias from a capped version of SAVIA, then shapes the reward with that reference so that what remains to be solved has value scale about τ/α, and finally solves the remaining correction problem as a linear program. The LP is where the space constraint bites, and the paper’s answer is to regenerate each kernel row from fresh samples whenever the solver asks for it. The sample complexity is Õ(SAH/ε² + S^{14/3} A^{4/3} H^{4/3}/ε^{4/3}), without knowledge of H; the first term matches the span-based lower bound, so the rate is optimal in the limit ε → 0 with S, A and H held fixed.

Critical strengths

Whether near-linear space is compatible with the optimal span-dependent rate is a reasonable thing to ask, and I am not aware of an earlier answer.

The calibration idea in Appendix B is the part I liked most. Fixing the rounding rule so that it is constant on a confidence region, and therefore returns identical rows on every reconstruction, is a small device that solves a real problem, and I can imagine it being reused in other streaming or low-memory settings.

The reward shaping and the certification step in Section 4, early-return case included, are easy to follow.

The authors make it lear that the guarantee is asymptotic.

Critical weaknesses

I would reconsider the phrase “model-free”. No kernel is stored, true, but rows are rebuilt from fresh samples on every query and that rebuilding. To me this is model-based planning with under a memory budget. “Near-linear working space” describes what the paper does and would spare the authors a terminological argument that adds nothing to the result.

Appendix D (Lemma 4.3) is hard to check. The authors note that the Corollary 10 they cite is numbered as in the arXiv version rather than the conference version, and their AI-use statement says that this is the section where AI tools were used to analyze the guarantees. I went through it but could not satisfy myself on every step. Since the main theorem rests on this lemma, I would ask the authors to spell out which hypotheses of the cited corollary are being invoked and to confirm that the published version supports them.

The experiments leave me with questions rather than confidence. They feel rather arbitrary rather than tell a whole story (e.g., why n=4000?). I would like a much better explanation and reasoning for why the specific choices.

Questions for authors

Q1. Could the code and the raw per-seed numbers behind Table 2 be released, and can you explain the zero variance of the SAVIA and Zhang–Xie arms?

Q2. Why n = 4000?

Q3. Which result in the SODA version of Liu et al. plays the role of the Corollary 10 cited in Appendix D, and what does it assume?

Q4. Do you expect the S^{14/3} factor to be inherent to row reconstruction, or do you see a path to reducing it?

1 comment

We thank the reviewer for the careful examination of our theoretical arguments and experimental results. We have strengthened the presentation of the low-space LP procedure, clarified the model-free terminology, and conducted additional reproducibility checks.

Regarding the model-free terminology.

We follow the space-based definition of model-free RL in Strehl et al. (2006), adopting the stronger requirement of O~(SA)\tilde{O}(SA) working space. Although our algorithm reconstructs transition probabilities during planning, each recovered row is discarded immediately after use, without retaining the full empirical transition kernel. We have added an explicit definition in Section 2 to clarify the definition of model-free methods.

Regarding the validity of the low-space LP argument.

We have substantially reorganized Appendix D to make the numerical guarantees and their assumptions explicit.

Lemma D.1 establishes the overall CorrectLP guarantee. Lemma D.2 ensures consistent calibrated recovery across adaptive row queries, while Lemma D.3 transfers the numerical policy certificate from the recovered kernel to the true MDP. Lemma D.4 presents the low-space LP guarantee. The relevant LP results from Liu et al. (2026) are explicitly stated in Lemmas D.5 and D.6.

We also verify the structural conditions for the discounted occupancy-measure LP, including n=SAn=SA variables, d=Sd=S equality constraints, full column rank, feasible-region radius bounds, and the condition-number bound κ(B⊤B)≤4S2/α2\kappa(B^\top B)\le 4S^2/\alpha^2.

The theoretical implementation of the LP requires O~(S2(SA)3/2)\tilde{O}(S^2(SA)^{3/2}) transition-row queries and O~(SA)\tilde{O}(SA) working space. We distinguish this theoretical solver from the practical matrix-free interior-point implementation described in Appendix E, which does not inherit the same worst-case query-complexity guarantee.

Regarding the higher-order S14/3S^{14/3} term.

The higher-order term arises from balancing coarse-reference learning, with sample cost O~(SAG2/τ2)\tilde{O}(SAG^2/\tau^2), against repeated transition reconstruction and correction planning, with cost O~(S5(SA)3/2Gτ/ϵ2)\tilde{O}(S^5(SA)^{3/2}G\tau/\epsilon^2). Choosing τ≍(Gϵ2/(S5SA))1/3\tau\asymp(G\epsilon^2/(S^5\sqrt{SA}))^{1/3} yields the additional term O~(S14/3A4/3H4/3/ϵ4/3)\tilde{O}(S^{14/3}A^{4/3}H^{4/3}/\epsilon^{4/3}).

We do not claim that this dependence is information-theoretically necessary. It reflects the overhead of our present construction. We have clarified its origin and limitations in Remark 4.2 and the Discussion, and reducing this dependence remains an important future direction.

Regarding the choice of n=4000n=4000.

We selected n=4000n=4000 as a representative nominal sampling budget at which most methods return policies while meaningful performance differences remain visible. To examine sensitivity to this choice, Figure 2 in Appendix E reports policy-return rates and consistency across multiple sampling budgets. Our numerical comparison therefore includes a broader budget analysis rather than relying exclusively on n=4000n=4000.

Regarding zero standard deviation and reproducibility.

We thank the reviewer for identifying the need to clarify the reported variability. We conducted an additional analysis of SAVIA and Zhang–Xie on 18 MDP instances using three random seeds, ϵ=0.1\epsilon=0.1, and n=4000n=4000.

We distinguish two statistics:

  • Seed-level SD: the sample SD across the three seed-wise suite-mean consistencies.
  • Across-run SD: the sample SD across all successful instance–seed observations, capturing variability across both instances and random seeds.
MethodReturnsSeed-level SDAcross-run SD
SAVIA51/540.00680.1960
Zhang–Xie54/540.00000.1857

For SAVIA, the previously reported zero SD is not reproduced. For example, on the ring S10 d0.5 instance, the consistency scores are 1.01.0, 0.80.8, and 1.01.0 across the three seeds. We have therefore corrected the reported SD to 0.007 in Table 2. For Zhang–Xie, consistency remains identical across seeds within each instance, explaining its zero seed-level SD. However, its across-run SD is 0.18570.1857, indicating substantial differences across MDP instances.

The across-run SD is an additional descriptive statistic and does not replace the seed-level SD. We provide the 108 individual experimental records and corresponding reproduction scripts in the supplementary package. The revised Appendix E also documents the availability of source code, instance-generation routines, random seeds, and individual experimental results.

References

  • Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. (2006). PAC Model-Free Reinforcement Learning. ICML2026

  • Liu, Y., Nguyen, H. A., and Yang, J. (2026). Numerical linear algebra in linear space. SODA2026

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

The paper studies average reward reinforcement learning in finite weakly communicating MDPs with access to a generative model. It proposes an algorithm that requires no prior knowledge of the optimal bias span and uses O~(SA)\widetilde O(SA) working memory. The algorithm combines a coarse bias estimate, reward shaping, and a correction linear program whose transition coefficients are repeatedly reconstructed from fresh samples.

The resulting sample complexity is O~(SAH/ϵ2+S14/3A4/3H4/3/ϵ4/3)\widetilde O(SAH/\epsilon^2+S^{14/3}A^{4/3}H^{4/3}/\epsilon^{4/3}). For fixed problem parameters, the leading term matches the statistical lower bound as the target error approaches zero. Experiments compare the proposed method with five existing algorithms on synthetic MDPs.

Critical strengths
  1. The paper makes a meaningful theoretical advance in the tradeoff between sample complexity and working memory. Compared with the cited methods using O~(SA)\widetilde O(SA) memory, it improves the leading dependence on the optimal bias span from quadratic to linear in the asymptotic regime, while requiring no prior span bound. The significance is that storing a complete transition kernel is unnecessary for attaining the optimal leading statistical term. Although the additional sample cost limits the scope, this is a substantive contribution.

  2. The calibrated transition reconstruction provides an interesting technical contribution beyond the use of reward shaping. Fresh empirical transition estimates would ordinarily give inconsistent coefficients across numerical solver passes. The calibration procedure ensures that repeated reconstructions agree with one fixed rounded kernel, while retaining only a scalar for each state and action. Its uniform directional accuracy supports analysis of the value function computed from that same kernel. Combining this construction with explicit accounting of solver queries and an observable acceptance test makes the overall argument technically informative.

Critical weaknesses
  1. The large additional sample term substantially limits the significance of the asymptotic optimality guarantee for growing problems. Ignoring logarithmic factors, the optimal leading term dominates only when approximately ϵ≲1/(S11/2A1/2H1/2)\epsilon\lesssim 1/(S^{11/2}A^{1/2}H^{1/2}). This follows directly by comparing the two terms in Theorem 4.1 and can require extremely small target errors even for moderate state spaces. The paper acknowledges the asymptotic qualification, but a more explicit discussion of this threshold and the regimes of improvement over existing low memory methods would help readers assess the contribution.

  2. The experimental description is insufficient to assess whether the reported advantages reflect the algorithm and resource guarantees being analyzed. Section 5 and Appendix E do not specify the numerical solver implementation, parameter choices, or how calibration and every repeated transition reconstruction are charged against the sample budget. These details are central because reconstruction is the source of the theoretical overhead. Moreover, the headline metric measures the fraction of states selecting a bias optimal action, which does not directly measure the average reward loss targeted by the theorem. The appendix reports true losses, but the study provides neither measured memory usage nor execution time. Consequently, the evidence does not yet establish the claimed practical sample and storage advantages.

Questions for authors
  1. What precise implementation of Algorithm 1 was used in the experiments? Please specify the correction solver, numerical tolerances, and parameter choices, and confirm whether every calibration and reconstruction sample is included in the stated budget. If practical modifications were used, please describe them.

  2. Can you characterize the parameter regimes in which the complete sample bound improves on SAVIA and the method of Zhang and Xie? In particular, please discuss the threshold at which the additional term becomes smaller than the optimal leading term.

  3. Can you report average reward loss and the probability of satisfying a specified accuracy target as primary experimental outcomes, together with measured memory and execution time? This would connect the experiments more directly to the statistical and memory claims.

1 comment

We thank the reviewer for recognizing our calibrated on-demand transition reconstruction technique and for the constructive suggestions concerning theoretical comparisons, implementation details, sample accounting, and empirical evaluation.

Regarding comparisons with SAVIA and Zhang–Xie.

Our sample-complexity guarantee is O~(SAHϵ2+S14/3A4/3H4/3ϵ4/3)\tilde{O}\left(\frac{SAH}{\epsilon^2}+\frac{S^{14/3}A^{4/3}H^{4/3}}{\epsilon^{4/3}}\right). In comparison, SAVIA+ achieves O~(SAH2/ϵ2)\tilde{O}(SAH^2/\epsilon^2), while Zhang–Xie achieves O~(SAH2/ϵ2+S2AH/ϵ)\tilde{O}(SAH^2/\epsilon^2+S^2AH/\epsilon). In the revision, we have expanded Remark 4.2 to discuss the crossover regime. Ignoring logarithmic factors, the burn-in term becomes smaller than the leading term when ϵ≤S−11/2(AH)−1/2\epsilon\le S^{-11/2}(AH)^{-1/2}. We emphasize that our improvement is asymptotic rather than uniform across all accuracy levels.

We have also clarified in Remark 3.1 why SAVIA is suitable for coarse-reference learning: it provides the Bellman-residual and span guarantees needed by our correction procedure.

Regarding the implementation of CorrectLP.

We have expanded Section 5 and Appendix E to describe the practical implementation. We use a matrix-free primal-dual predictor-corrector interior-point method for the discounted occupancy-measure LP. Newton systems are solved using Jacobi-preconditioned conjugate gradients, while auxiliary policy evaluation uses GMRES with BiCGSTAB as a fallback.

Each state–action pair is calibrated once using Algorithm 3, retaining only its rounding shift. Every subsequent row query uses fresh samples to reconstruct the transition row, which is immediately discarded after use. We use an interior-point tolerance of 2×10−72\times10^{-7}, a CG relative tolerance of 10−910^{-9}, and at most 5555 interior-point iterations. For the practical RAD configuration, we set ϵ=0.1\epsilon=0.1, τ=8ϵ\tau=8\epsilon, and K=12K=12.

The practical solver differs from the theoretical low-space LP algorithm of Liu et al. (2026), which requires specialized bit-complexity-aware linear algebra and precision management. Integrating it with our calibrated row-query mechanism would involve substantial implementation complexity. We therefore use a matrix-free primal-dual interior-point method for experiments, without claiming the theoretical row-query bound of O~(S2(SA)3/2)\tilde{O}(S^2(SA)^{3/2}).

Regarding simulator-sample accounting.

For one correction trial, let QQ denote the number of transition-row queries and nrn_r the number of samples per calibration or recovery batch. The correction-stage sample count is Ncorr=(SA+Q)nrN_{\mathrm{corr}}=(SA+Q)n_r. The total sample count additionally includes coarse-reference learning and frozen estimation, with costs accumulated across trials.

We distinguish the policy-quality experiments, which use the nominal practical budget n=4000n=4000 per state–action pair, from the separate row-query computational benchmark. The former budget is not a strict total simulator-call bound for the theoretical algorithm. The computational benchmark uses nr=3000n_r=3000 logical samples per batch. For S=10,20,50S=10,20,50, the average charged calibration-and-recovery sample counts are approximately 7.04×10137.04\times10^{13}, 3.48×10143.48\times10^{14}, and 2.58×10152.58\times10^{15}, respectively.

Regarding average-reward loss and PAC success.

We agree that average-reward loss is more directly aligned with our theoretical objective than action consistency.

In the revised Appendix E, we explicitly define the true average-reward loss as L(π^)=max⁡s∈S{ρ⋆−ρπ^(s)}L(\hat{\pi})=\max_{s\in\mathcal S}\{\rho^\star-\rho^{\hat{\pi}}(s)\} and empirical PAC success as the fraction of instance–seed runs returning a policy satisfying L(π^)≤ϵL(\hat{\pi})\le\epsilon.

Figure 1 reports true average-reward loss alongside consistency. In the displayed experiments, RAD's per-instance average losses do not exceed 2×10−42\times10^{-4}. Figure 2 additionally reports policy-return rates and consistency across different sampling budgets.

Regarding practical runtime and memory.

We have added a computational comparison in Appendix E (Table 3) using three ring MDPs with S∈{10,20,50}S\in\{10,20,50\}, A=2A=2, and four random seeds.

The row-query interior-point implementation takes 0.211±0.0310.211\pm0.031, 1.027±0.0801.027\pm0.080, and 7.889±0.5217.889\pm0.521 seconds, respectively. For comparison, RAD-dense takes 0.692±0.0730.692\pm0.073, 0.740±0.0440.740\pm0.044, and 0.620±0.0920.620\pm0.092 seconds under its separate sampling configuration. These results confirm the substantial computational overhead of repeated transition reconstruction and iterative numerical planning.

Peak memory differences are relatively small. At S=50S=50, most implementations use approximately 121121–127127 MiB of process memory. This is likely because the Python runtime, numerical libraries, and simulator infrastructure contribute substantial fixed overhead, masking differences in algorithm-specific storage.

Reference: Liu et al. 2026: Liu, Y., Nguyen, H. A., and Yang, J. (2026). Numerical linear algebra in linear space.

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

The paper studies average-reward reinforcement learning in finite weakly communicating MDPs with access to a generative model. The proposed method combines reward shaping, transition reconstruction, and memory-efficient planning to obtain an ϵ\epsilon-optimal policy without prior knowledge of HH, optimal bias function. With high probability, it establishes

O~(SAHϵ2+S14/3A4/3H4/3ϵ4/3)\widetilde{O}\left( \frac{SAH}{\epsilon^2} + \frac{S^{14/3}A^{4/3}H^{4/3}}{\epsilon^{4/3}} \right)

samples and O~(SA)\widetilde{O}(SA) working space. For fixed SS, AA, and HH, this sample complexity matches the statistical lower bound up to logarithmic factors as ϵ→0\epsilon \to 0. The paper also presents experiments comparing six methods on 18 synthetic MDP instances.

Critical strengths

The paper develops a model-free method that requires no prior knowledge of HH, which measures the span of an optimal bias function. By combining reward shaping, transition reconstruction, and memory-efficient planning, the authors improve the leading sample-complexity dependence on HH. Overall, this combination provides an interesting theoretical improvement, achieving the optimal leading sample-complexity term as the target error approaches zero.

Critical weaknesses

Although the paper provides a meaningful theoretical result, I am not convinced that the contribution meets the bar for acceptance. The authors establish interesting connections among three techniques, but the resulting improvement comes with substantially worse dependence on the numbers of states and actions. The optimal leading term dominates only when the target error ϵ\epsilon is extremely small. For applications with large state and action spaces, this trade-off may offer limited benefit. I am also concerned about the computational cost of repeatedly reconstructing transition probabilities and solving the correction problem through linear programming. The experiments compare policy quality under a fixed sample budget but do not report runtime or measured memory use. Consequently, they do not establish whether the proposed approach offers a useful practical trade-off between sample efficiency, memory, and computation.

Questions for authors

What is the computational cost of the method compared with other methods?

Could the authors clarify their definition of “model-free”? The method reconstructs transition probabilities and uses them in a planning LP, while avoiding storage of the full transition model. Does “model-free” here refer specifically to the O~(SA)\widetilde O(SA) memory requirement, rather than the absence of an estimated model used for planning?

1 comment

We thank the reviewer for the thoughtful comments and for highlighting the importance of computational efficiency, practical trade-offs, and the definition of model-free reinforcement learning. We have revised the manuscript to clarify these aspects.

Regarding computational efficiency.

We agree that our algorithm incurs substantial computational overhead. Our main contribution is an asymptotically optimal sample-complexity guarantee under a near-linear working-space constraint, rather than a computationally efficient practical algorithm.

In the revision, we have added an explicit running-time analysis in Section 3.3:

O~(SAHϵ2+S14/3A4/3H4/3ϵ4/3+S11/2A3/2)\tilde O(\frac{SAH}{\epsilon^2}+\frac{S^{14/3}A^{4/3}H^{4/3}}{\epsilon^{4/3}}+S^{11/2}A^{3/2}).

The last term accounts for numerical planning overhead.

We have also added runtime and peak-memory experiments in Appendix E (Table 3). At S=50,A=2S=50,A=2, our row-query interior-point implementation takes 7.889±0.5217.889\pm0.521 seconds, compared with 0.620±0.0920.620\pm0.092 seconds for the dense implementation. These measurements use different sampling configurations and are not equal-budget comparisons.

The results confirm that repeated transition reconstruction and iterative linear-system solves introduce considerable computational costs. We acknowledge this limitation and view reducing the overhead as an important future direction.

Regarding the practical memory–runtime trade-off.

Our approach avoids retaining the full empirical transition kernel by reconstructing rows on demand and discarding them after use. This reduces the planner's working-space requirements but increases the number of sampling and numerical operations.

The revised Appendix E reports peak resident memory alongside runtime. At the tested scales, most implementations consume approximately 121–127 MiB at S=50S=50. We believe the relatively small differences arise because Python, numerical libraries, and simulator infrastructure contribute substantial fixed overhead, masking differences in algorithm-specific storage.

Furthermore, the measured runtime uses accelerated multinomial batch sampling and does not include the cost of executing each logical simulator draw individually. Thus, the computational burden of the theoretical sampling procedure is substantially greater than these wall-clock measurements alone suggest.

Regarding the model-free terminology.

We acknowledge that our algorithm performs transition-based planning. Nevertheless, we follow the space-based definition of model-free RL in Strehl et al. (2006), adopting the stronger requirement of O~(SA)\tilde{O}(SA) working space.

In the revision, we have added an explicit definition in Section 2. Our use of model-free refers to space complexity rather than the complete absence of model-based computations. We do not claim that the method is model-free under every definition in the literature.

Regarding the burn-in term and asymptotic improvement.

We agree that the higher-order term can dominate at moderate accuracy levels. The sample-complexity improvement is asymptotic as ϵ→0\epsilon\to0 for fixed S,A,HS,A,H, and does not imply uniformly superior finite-budget performance.

We have expanded Remark 4.2 to clarify this limitation and the crossover regime. The burn-in term arises from balancing coarse-reference learning against repeated transition reconstruction. Reducing this dependence remains an open direction.

Reference

  • Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. (2006). PAC Model-Free Reinforcement Learning. Proceedings of the 23rd International Conference on Machine Learning (ICML), pp. 881–888.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.