- 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?
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) 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=SA variables, d=S equality constraints, full column rank, feasible-region radius bounds, and the condition-number bound κ(B⊤B)≤4S2/α2.
The theoretical implementation of the LP requires O~(S2(SA)3/2) transition-row queries and 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/3 term.
The higher-order term arises from balancing coarse-reference learning, with sample cost O~(SAG2/τ2), against repeated transition reconstruction and correction planning, with cost O~(S5(SA)3/2Gτ/ϵ2). Choosing τ≍(Gϵ2/(S5SA))1/3 yields the additional term O~(S14/3A4/3H4/3/ϵ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=4000.
We selected n=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=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, and n=4000.
We distinguish two statistics:
For SAVIA, the previously reported zero SD is not reproduced. For example, on the
ring S10 d0.5instance, the consistency scores are 1.0, 0.8, and 1.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.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