- Rating
- 4(+1)
- Confidence
- 4(+1)
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies approximate fixed points of a nonexpansive operator using samples from one continuing Markov trajectory. The chain is finite, irreducible, and aperiodic, and the operator may have several fixed points.
A block Halpern baseline forms a fresh estimate of the operator at each iteration. Its expected last iterate residual decreases as log(N)/N, with sample complexity epsilon^(-5), up to logarithmic factors.
The proposed PAGE-Halpern method alternates between refresh blocks and blocks estimating operator differences. Each observed Markov state must allow evaluations at two query points. A Poisson equation separates the random error from the conditional bias at block boundaries.
The Hilbert result uses cocoercivity of the residual operator. The Banach result instead controls iterate displacements and changes in scaled estimation errors. Under the stated oracle and stability conditions, the leading sample complexity is epsilon^(-3), with logarithmic factors in Banach spaces. An auxiliary smooth norm gives a high probability extension under a stronger pathwise stability condition.
Experiments compare the methods on two eight-state average reward problems, using common transition budgets and fast or slow mixing chains.
Critical strengths
-
The analysis accounts for the state inherited at each block boundary and for block lengths chosen from past observations. The Poisson decomposition retains the conditional bias rather than treating consecutive blocks as independent. This is useful for algorithms that must use one continuing trajectory. The required two-query access is stated explicitly, and the main proof steps appear consistent under their conditions.
-
The displacement argument provides a clear way to control the residual in the norm where the mean operator is nonexpansive. It supports recursive variance reduction without the Hilbert cocoercive potential. The control example uses a Bellman map that is nonexpansive in the sup norm and cannot be made nonexpansive in an inner-product norm, so the geometric extension has a concrete motivation. The paper states separately the assumptions for the expectation and high-probability bounds.
Critical weaknesses
-
The connection between the conditional theory and the RL examples remains incomplete. Appendix F verifies the mean operators and two-query access, but not all required variance and stability bounds. For the evaluation oracle, the stationary variance grows quadratically along a direction in the query space. It is therefore not uniformly bounded over that space, as Condition 3.1 requires. A localized version would need a bound on the visited queries. For the Banach results, iterate stability and the stronger almost-sure image bound in Condition 5.2 also need justification. Their constants must remain controlled as the horizon and target accuracy change.
With the experimental tuning, the initial estimator MSE exceeds the bound used in the PAGE lemmas. Appendix F explicitly replaces the theoretical constants by . With , the initial block has 375 transitions. A direct moment calculation, with the Markov chain initialized at state 0, gives initial Euclidean estimator MSEs of approximately 0.59 and 0.09 for fast and slow evaluation, and 2.07 and 1.58 for fast and slow control. All exceed the lemmas' bound at initialization. On the fast evaluation chain, the oracle difference constant is approximately , above the chosen . These observations do not contradict the conditional theorems, but limit what the experiments establish about their calibration. Fixed delta and median/IQR reporting also do not test the claimed accuracy scaling or expected residual bounds.
-
The related work should include Diakonikolas, "Solving Stochastic Fixed-Point Equations with High Probability" (July 2026, https://arxiv.org/abs/2607.09097), which gives a high-probability rate of in quadratically smoothable Banach spaces, assuming globally bounded variance and a Lipschitz-in-expectation i.i.d. oracle, without a separate iterate stability assumption. RAIN by Chen and Luo (JMLR 2024, https://www.jmlr.org/papers/v25/22-1126.html) also gives a better epsilon dependence for expected residuals in the Hilbert i.i.d. setting. These are not the same Markov results. However, the paper should explain the additional contribution in assumptions, mixing dependence, and use of consecutive observations, beyond the accuracy exponent alone.
Questions for authors
-
Can you establish the required oracle and stability bounds for the RL examples, with constants controlled as epsilon decreases? For evaluation, would the theorem need an explicit localized variance condition?
-
Can you explain the experimental calibration relative to the PAGE lemmas and the requirement , and show how results change with settings that satisfy these conditions?
-
Please compare with the two works above. On comparable globally controlled oracle classes, what does the consecutive-block analysis gain over applying a suitable i.i.d. method to observations spaced along the continuing chain?
-
Can you add mean residuals, tail statistics, and experiments where delta changes with the target accuracy?
2 comments
raising my rating
I really appreciate the changes you made to the paper. You've done a great job addressing my biggest worry about the Banach space guarantees, which is now much clearer. The new baseline for Hilbert space is also really helpful, and comparing it to Cai et al.'s work makes it easier to see what's new and important here. The added experiments and calibration are a big plus too. Because of these changes, I'm increasing my rating from 3 to 4. One thing to keep in mind is to make sure the main comparison clearly states the scope of Proposition 3.1, especially when it comes to the fixed horizon and the deterministic block schedule.
Response to Reviewer xn54
We thank the reviewer for the very detailed review. The exact moment calculation was especially useful.
(1) Experimental calibration (Q2, Q4). You are right that the submitted schedule (c=0.15) violates the per-block bounds. We made four changes.
On the periodic problems, PAGE is empirically 49–210 times cheaper than the tuned baseline at ϵ=0.025 in evaluation and 35–42 times in control. At the tightest targets most baseline runs exhaust the budget, while every PAGE run finishes. On the hard instance of Proposition 3.1 the empirical exponents are 4.1 (baseline) and 2.6 (PAGE). The lazy-cycle results are reported in App. F.6.
(2) RL conditions (Q1). All conditions are verified with explicit constants that do not depend on ϵ or the horizon (App. F.1–F.2, Table 2): L=21.8/21.9 (evaluation, ℓ2), L≤64 (control, ℓ∞), and CP=2.9/8.5, with per-state σ0 listed. The evaluation oracle's noise grows linearly along non-constant directions, which is exactly the affine growth now allowed (Assumption 2.3 with σ1=L). Since block lengths adapt to the observed ∣xn−x0∣ and stability is proved (G1 in the general response), no localized variance condition is needed. Assumption 2.4 and Condition 5.2 are removed.
(3) Diakonikolas (2026) and RAIN (Q3). Please see G3 in the general response and App. A. Diakonikolas uses a gradual Halpern scheme with i.i.d. samples, median-of-means restarts and differences clipped at the Lipschitz scale of T. This gives high-probability bounds under second moments that are anytime (the target accuracy need not be fixed in advance) and parameter-free, which is more general than our per-state bounds. Our addition is Markovian sampling: blocks start from inherited states, so block averages are biased and correlated, and we control both through CP. RAIN has a better exponent in the Euclidean i.i.d. case, which we now state. Its mechanism, however, requires an inner product.
Consecutive blocks versus thinning. An i.i.d. method run on observations spaced ℓ≳tmixlog(1/ϵ) apart discards a 1−1/ℓ fraction of the samples, which multiplies the whole cost by tmixlog(1/ϵ) and leaves a coupling error. Our blocks use every transition without burn-in and pay CP≤1+4tmix only on the leading term, with no log(1/ϵ) factor.
We hope these changes address your concerns.