acceptodds
Under review as a conference paper at ICLR 2027

A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps

Abstract

We study stochastic approximation of fixed points of a non-expansive operator when the oracle samples originate from a continuing Markovian trajectory. A direct block-minibatch implementation of Halpern iteration attains an expected last-iterate residual of order , but accrues a substantive complexity of Markovian samples. We therefore introduce a variance-reduced Markovian PAGE-Halpern method whose refresh and same-state difference blocks are analyzed through the Poisson equation. In Hilbert spaces, the cocoercivity of results in an sample complexity. Our main result extends this construction to a general finite-dimensional Banach space. A displacement-level Halpern bound replaces the Hilbert-space potential and yields sample complexity. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm.

Primary area:
reinforcement learning
Keywords:
Stochastic approximation, Halpern iteration, non-expansive operators, Markovian sampling, variance reduction, Banach spaces, reinforcement learning, high-probability guarantees

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_xn54OpenReview ↗
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
  1. 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.

  2. 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
  1. 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 c=0.15c=0.15. With δ=0.02\delta=0.02, 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 100δ2=0.04100\delta^2=0.04 at initialization. On the fast evaluation chain, the oracle difference constant is approximately LF=3.80L_F=3.80, above the chosen L∗=2L^*=2. 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.

  2. 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 O~(ε−3)\widetilde O(\varepsilon^{-3}) 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
  1. 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?

  2. Can you explain the experimental calibration relative to the PAGE lemmas and the requirement L∗≥LFL^*\geq L_F, and show how results change with settings that satisfy these conditions?

  3. 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?

  4. Can you add mean residuals, tail statistics, and experiments where delta changes with the target accuracy?

2 comments
AuthorsOpenReview ↗

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.15c=0.15) violates the per-block bounds. We made four changes.

  • Theory. L∗≥LFL^*\ge L_F is not needed anymore. Cai et al.'s potential uses only the cocoercivity of FF and the estimator error, and LL enters only the block lengths. Theorem 3.5 now requires only L∗≥2L^*\ge2, hence L∗=2L^*=2 is a valid choice.
  • Calibration. Extending your moment calculation to a forward recursion, we can compute exactly the worst-case conditional MSE and bias of every block type over all starting states, block lengths S≥CPS\ge C_P and a set of query points. These multipliers replace the worst-case constants of Lemmas 3.3 and 4.2 (Table 2), and the block lengths are then not tuned. Along all runs, the normalized estimator error max⁡n(n+1)E∣en∣2/δ2\max_n(n+1)\mathbb E\\|e_n\\|^2/\delta^2 stays below 99, against the bound 100100, while the submitted schedule reached 600600–15,00015{,}000 (Table 4, App. F.6).
  • Q4. PAGE now uses δ∝ϵ\delta \propto \epsilon, as in Theorems 3.5 and 4.3, with a separate run for each target accuracy. For each target, we report the mean, median, 10th and 90th percentiles of the transitions needed to reach it, and how many of the 30 trajectories reach it within the budget (Fig. 2, Table 3). The block baseline is tuned in the same way: each method is run over a grid of tuning parameters, and for each target we report its best setting. Fig. 1 in the main text shows the mean residual against observed transitions, and the median stays within a factor of 1.7 of the mean.
  • Instances. Rerunning the submitted lazy-cycle problems this way showed that they are benign: the chain is aperiodic, errors are damped, and an equally tuned block baseline is cheaper there. We therefore moved the experiments to periodic average-reward problems. There the Bellman map has unit-modulus eigenvalues, relative value iteration fails without an aperiodicity transform, and errors are rotated rather than damped, which is the regime our theory targets (it needs only irreducibility).

On the periodic problems, PAGE is empirically 49–210 times cheaper than the tuned baseline at ϵ=0.025\epsilon=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 ϵ\epsilon or the horizon (App. F.1–F.2, Table 2): L=21.8/21.9L=21.8/21.9 (evaluation, ℓ2\ell_2), L≤64L\le64 (control, ℓ∞\ell_\infty), and CP=2.9/8.5C_P=2.9/8.5, with per-state σ0\sigma_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\sigma_1=L). Since block lengths adapt to the observed ∣xn−x0∣\\|x_n-x_0\\| 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 TT. 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 CPC_P. 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/ϵ)\ell\gtrsim t_{mix}\log(1/\epsilon) apart discards a 1−1/ℓ1-1/\ell fraction of the samples, which multiplies the whole cost by tmixlog⁡(1/ϵ)t_{mix}\log(1/\epsilon) and leaves a coupling error. Our blocks use every transition without burn-in and pay CP≤1+4tmixC_P\le1+4t_{mix} only on the leading term, with no log⁡(1/ϵ)\log(1/\epsilon) factor.

We hope these changes address your concerns.

Reviewer_xn54OpenReview ↗

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.

Reviewer_qXDaOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper considers stochastic approximation with non-expansive operators, and analyzes stochastic Halpern iterations driven by Markovian observations. For the algorithm analyzed in the manuscript, the authors establish a O(ϵ−5)\mathcal O(\epsilon^{-5}) sample complexity for a simple baseline algorithm. Then, a variance reduction algorithm is shown to achieve ϵ−3\epsilon^{-3} complexity for Hilbert spaces. An analogous result is established for Banach spaces, under an assumption that the algorithm's output stays close to the anchor x0x_0 in a mean-square sense.

Critical strengths

This paper considers an important problem involving Halpern iterations for non-expansive maps with Markovian observations. The results are potentially useful for average-reward RL, and establishing sampling complexities for Banach spaces is useful for applications involving the sup norm.

Critical weaknesses

I believe that the results of this manuscript are potentially interesting, but it suffers from some critical weaknesses.

This paper compares the ϵ−3\epsilon^{-3} sample complexity established for the proposed algorithm to a ϵ−5\epsilon^{-5} complexity established for a baseline. It is not clear whether the ϵ−5\epsilon^{-5} for that baseline is tight, or whether this improvement is due to a loose argument for analyzing the baseline. Moreover, the improvement is established under a stronger assumption on the underlying oracle (conditions 3.1 and 3.4). So it is not clear whether the improvement comes from the algorithm which appears to be one of the manuscript's main claim, an analysis artifact, or an additional information assumption.

The paper also emphasizes the improvement from ϵ−5\epsilon^{-5} to ϵ−3\epsilon^{-3} as one of the main contributions. However, for the i.i.d. setting, [1] established the ϵ−3\epsilon^{-3} complexity, so it is not clear whether the improvement is due to the new algorithm or a generalization of the results from [1] to the Markovian setting.

In my opinion, the manuscript's title overstates the contribution and is misleading. The Banach space result in Theorem 4.3 requires an ex-ante property (Assumption 2.4) of an algorithm being proposed. This results in an awkward logical chain, where the authors propose an algorithm, assume that the algorithm satisfies properties in Assumption 2.4, then uses the assumed algorithm's guarantee to establish sample complexities for Banach spaces. Therefore, I believe stating that this manuscript establishes a Banach space theory is misleading unless Assumption 2.4 is established. The verification of Assumption 2.4 does not seem to be included for the proposed PAGE algorithm.

I believe moving Assumption 2.4 to Section 4 would improve presentation for two reasons. First, Assumption 2.4 is a property of an algorithm, yet it is assumed before the algorithm under consideration is defined. Second, the sample complexity is established without Assumption 2.4 in Theorem 3.4 for Hilbert spaces. Therefore, moving the assumption would make it clearer that the manuscript establishes the Hilbert space result without assuming Assumption 2.4, which I think would strengthen the paper's contribution. It also seems like Theorem 2.5 can be established using only the p=1p = 1 part of Assumption 2.4, giving the authors freedom to move the p=2p = 2 condition to the Banach space setting.

[1] X. Cai, et. al, ``Stochastic Halpern Iteration with Variance Reudction for Stochastic Monotone Inclusions'', NeurIPS 2022.

Questions for authors
  1. Could the authors clarify what the innovation in the PAGE algorithm is compared to that in [1] above?

  2. Are the authors aware of any lower bounds for the baseline algorithm, whether it is for the i.i.d case or the Markovian setting?

  3. Could the authors provide intuition on what Assumption 2.4 entails? Can it be established for the PAGE algorithm under Assumptions 2.1-2.3 for some non-trivial examples in the Banach space setting (Condition 4.1)?

2 comments
AuthorsOpenReview ↗

Response to Reviewer qXDa

We thank the reviewer for the thoughtful review, which led to substantive improvements.

(1) Is the ϵ−5\epsilon^{-5} baseline tight, and where does the gain come from? (Q2) We added Proposition 3.1, a lower bound for the block baseline under the PAGE (mean-square smooth) oracle model. For any horizon and any block schedule, there exists an instance in (R3,∣⋅∣2)(\mathbb R^3,\\|\cdot\\|_2) satisfying Condition 3.2 with LF=0L_F=0 (same-state differences are noiseless) and i.i.d. samples (CP=1C_P=1) on which E∣xN−TxN∣≤ϵ\mathbb E\\|x_N-Tx_N\\|\le\epsilon requires ∑nkn≥σ2D022ϵ4.\sum_n k_n\\ \ge\\ \frac{\sigma^2D_0^2}{2\epsilon^4}. The instance is the direct sum of a rotation by π/(N+1)\pi/(N+1), which forces N≳D0/ϵN\gtrsim D_0/\epsilon, and the reflection w↦−ww\mapsto-w, which accumulates the block errors as 1N+1∑n(−1)nn,ξˉn\frac{1}{N+1}\sum_n(-1)^n n\\,\bar\xi_n. Khintchine's inequality and Cauchy–Schwarz then give the bound. This bound is tight. We guarantee this since in Hilbert spaces we also tightened the baseline's upper bound to O~(σ2D02ϵ−4)\tilde O(\sigma^2D_0^2\epsilon^{-4}) (Theorem B.7). The proof replaces the first-moment argument by a second-moment potential that uses the cocoercivity of I−TI-T, so errors enter through ∑nn2E∣Un∣2\sum_n n^2\mathbb E\\|U_n\\|^2 plus a martingale term, and kn≍n3k_n\asymp n^3 suffices. The baseline is therefore Θ~(ϵ−4)\tilde\Theta(\epsilon^{-4}) in Hilbert spaces, while PAGE needs O(σ2D0ϵ−3)O(\sigma^2D_0\epsilon^{-3}) on the same instance (Theorem 3.5). Both methods face identical information, so the improvement is due to the algorithm, not to the oracle or to the analysis. Experiments on this instance also confirm the theory. The tuned baseline's empirical exponent is 4.1, versus 2.6 for PAGE (Fig. 2). In general normed spaces the best known minibatch rates (ours, Bravo & Contreras 2026, Diakonikolas 2026) are ϵ−5\epsilon^{-5}, and we clearly state that closing the gap to ϵ−4\epsilon^{-4} there is an open problem. For single-query oracles, Bravo & Contreras prove Ω(ϵ−3)\Omega(\epsilon^{-3}) for linear-span methods. Their resistant oracle has per-sample deviations of order σ2/ϵ\sigma^2/\epsilon and same-sample differences that are not Lipschitz, therefore it is outside our per-state noise and two-query conditions. App. A relates the two lower bounds.

(2) Novelty over Cai et al. (Q1). Please see also G3 in the general response. We now state explicitly that in the Hilbert case our method is a Markovian implementation of their estimator, and that Proposition 3.4 is their potential argument. What is new there is the estimator analysis along one trajectory, with blocks that start at stopping times from inherited states, Poisson control of bias and variance with linear dependence on CPC_P, and adaptive block lengths for affine noise growth. The algorithmic novelty is in the Banach case. The Banach method (Sec. 4) estimates TT instead of FF, and the displacement-level bound replaces their cocoercive potential, which requires an inner product. This covers norms such as ℓ∞\ell_\infty, in which I−TI-T is not monotone for any inner product (our control example), and which lie outside their analysis even under i.i.d. sampling.

(3) Assumption 2.4, its placement, and the title (Q3). Please see G1 in the general response. The assumption is removed entirely, so the Banach-space results (in expectation and with high probability) no longer depend on any property of the algorithm's trajectory. As you pointed out, the Hilbert result never used it in the first place. We believe the title is now accurate, and we are happy to adjust it if you still find it overstated.

We hope these changes address your concerns and would be grateful if you would reconsider your assessment.

I thank the authors for their response. I have raised my score to 3, as they have addressed my concerns.

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

The paper studies stochastic approximation algorithms based on Halpern's iteration, for fixed point problems in Banach spaces, using data coming from ergodic Markov chains. The paper analyzes an increasing-batch algorithm and a variance-reduced algorithm, proving sample complexity upper bounds of O(1/ε5)O (1/\varepsilon^5) and O(1/ε3)O (1/\varepsilon^3), respectively. The latter requires a stronger two-point oracle access. Notably, the result only assumes the operator to be non-expansive under the Banach space norm. No strong contraction or strong convexity assumptions are required.

Critical strengths

The Banach space fixed-point problem has a lot of important applications, and the study under Markovian data is useful in reinforcement learning algorithms. The paper provides general results under relatively weak assumptions, and the results are novel and interesting.

Critical weaknesses
  • Assumption 2.4 is assuming something about the trajectory of the algorithm itself. This cannot be verified in practice. Usually this should be an intermediate step in the analysis that can be proved under other assumptions. The paper circumvents a major technical difficulty by assuming this property, but it is not clear how realistic this assumption is.

  • The bound hides dependencies on many important parameters, including the minimum stationary mass and the dimension of the space. In particular, Lemma C.1 introduces the dependence on πmin⁡−1\pi_{\min}^{-1}, which at least scales as the cardinality of the state space. So the bound becomes large even for fast-mixing chains, as long as the state space is large. The current assumptions ℓ2\ell_2-norm for the variance bounds and the Banach norm for the non-expansiveness. For example, when the Banach norm is ℓ∞\ell_\infty-norm (useful in RL applications), the gap between the two norms will make these constants dimension-dependent. This usually leads to unnecessary dimension/cardinality dependence in the final sample complexity bounds for RL applications.

Questions for authors

In addition to above weakness section, it would be better to clarify the observation model and clearly define the algorithm iterates. Currently these descriptions are scatter throughout the paper with text and equations.

2 comments
AuthorsOpenReview ↗

Response to Reviewer RK2K

We thank the reviewer for the positive assessment and the precise comments.

Assumption 2.4. It is removed, and stability is now proved rather than assumed (Lemma B.1). Please see G1 in the general response.

Dependence on all parameters, and πmin⁡−1\pi_{\min}^{-1}. Please see G2 in the general response. Every theorem now states its dependence on D0,σ0,σ1,LF/LT,CP,αs,κsD_0,\sigma_0,\sigma_1,L_F/L_T,C_P,\alpha_s,\kappa_s (and η\eta for the high-probability bound). Your observation that the old Lemma C.1 introduced πmin⁡−1\pi_{\min}^{-1} was indeed correct. This introduction came from converting a stationary second moment into a uniform bound. In the revision, we have bounded the noise per state and the Poisson solution by the fundamental-matrix constant CPC_P (Lemma C.1), which equals 11 for i.i.d. sampling regardless of ∣Y∣|\mathcal Y| and is at most 1+4tmix1+4t_{mix} in general. App. B.1 explains the relation to the old bound. In our RL examples, CPC_P is 2.92.9 to 8.58.5, while πmin⁡−1\pi_{\min}^{-1} is 6464 to 640640.

Norm conversion. We agree that measuring the variance in ℓ2\ell_2 and the displacement in the working norm was the wrong design. In the revision:

  1. We measure the noise level σ(x)\sigma(x) and the same-sample constant LTL_T per state in an auxiliary norm ∣⋅∣s\\|\cdot\\|_s, and displacements in the working norm, so no Euclidean norm is involved (Assumption 2.3, Condition 4.1).
  2. For the martingale estimates, we use the smoothness of ∣⋅∣s\\|\cdot\\|_s (eq. (1)), which appears only in the analysis.
  3. The geometry enters linearly, through αs2κs\alpha_s^2\kappa_s, where ∣z∣≤αs∣z∣s\\|z\\|\le\alpha_s\\|z\\|_s, and through the norm in which σ\sigma and LTL_T are measured.

For ℓ∞\ell_\infty, and for block-sup norms with dd blocks, the ℓq\ell_q surrogate with q≈2log⁡dq\approx 2\log d costs a factor at most e(2log⁡d+1)e(2\log d+1) in total (κs≤2log⁡d+1\kappa_s\le2\log d+1, and a factor ee from measuring σ\sigma and LTL_T in ∣⋅∣q\\|\cdot\\|_q), so RL applications suffer only a factor O(log⁡d)O(\log d) rather than one polynomial in dd. For Euclidean norms the factor is 11, and for an arbitrary norm it is at most dd (Remark D.2).

Observation model and iterates. We added an "Observation model" paragraph in Sec. 2, which specifies that we use one trajectory from an arbitrary initial state, blocks that start at stopping times with Fτ\mathcal F_\tau-measurable lengths and query points, we do not discard transitions. We also clarify between single- and two-query access, and cost measured in transitions. We also added Algorithm 1 in Sec. 2, a single algorithm block that defines the iterates of all methods (block baseline, Hilbert and Banach PAGE-Halpern) and states when each block length and query point is fixed.

We hope these changes address your concerns.

Thanks for the response. I will keep my positive rating.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to all reviewers

We thank all reviewers for their careful reading. We have uploaded a revised manuscript, we summarize all changes at the end. Below, in items G1–G3, we address the common points raised by the reviewers. All numbering of theorems etc. refers to the revised version.

G1. Assumption 2.4 (iterate stability) is removed (RK2K, qXDa, xn54). All results (baseline, Hilbert, Banach, high-probability) now hold without assuming Assumption 2.4. The pathwise stability Condition 5.2 is also removed. The key observation is that anchoring makes the inexact Halpern recursion self-stabilizing (new Lemma B.1): For xn=(1−βn)x0+βn(Txn−1+Un)x_n=(1-\beta_n)x_0+\beta_n(Tx_{n-1}+U_n), pathwise, dist(xn,Fix,T)≤D0+Wn,Wn=1n+1∑i≤ni∣Ui∣,\mathrm{dist}(x_n,\mathrm{Fix}\\,T)\le D_0+W_n,\qquad W_n=\frac{1}{n+1}\sum_{i\le n} i\\|U_i\\|, with D0=dist(x0,Fix,T)D_0=\mathrm{dist}(x_0,\mathrm{Fix}\\,T). The displacement bound (Theorem 2.4) and all later results use this lemma in place of the assumed constants R1,R2R_1,R_2. For PAGE, E∣Ui∣2≤100δ2/i\mathbb E\\|U_i\\|^2\le 100\delta^2/i gives Wn=O(δn)W_n=O(\delta\sqrt n), which is absorbed into the δ\delta term. On the high-probability event, Wn≤δn/2W_n\le\delta n/2 is absorbed in the same way. Block lengths adapt to the noise level σ(xn)=σ0+σ1∣xn−x0∣\sigma(x_n)=\sigma_0+\sigma_1\\|x_n-x_0\\| at the current iterate, so the noise may grow affinely (Assumption 2.3) and no bound on the visited region is needed.

G2. Explicit constants: mixing, πmin⁡\pi_{\min}, dimension (RK2K, xn54). The Markovian block lemma is rewritten (Lemmas C.1–C.2):

  • The noise is bounded per state (Assumption 2.3), and mixing enters through the Poisson constant CP=max⁡y∑y′∣Z(y,y′)∣C_P=\max_y\sum_{y'}|Z(y,y')|, Z=(I−P+1π⊤)−1Z=(I-P+\mathbf 1\pi^\top)^{-1}, with CP≤1+4tmixC_P\le 1+4t_{mix} (CP=1C_P=1 for i.i.d. sampling for any ∣Y∣|\mathcal Y|). There is no πmin⁡−1\pi_{\min}^{-1}, and aperiodicity is not needed.
  • A sub-block argument makes the leading term linear in CPC_P, and quadratic dependence appears only in lower-order terms.
  • Estimation errors are measured in an auxiliary smooth norm with ∣z∣≤αs∣z∣s\\|z\\|\le\alpha_s\\|z\\|_s and smoothness constant κs\kappa_s (eq. (1)), used only in the analysis. The geometric cost is 11 for Euclidean norms and O(log⁡d)O(\log d) for ℓ∞\ell_\infty/block-sup norms. The Euclidean comparison constant μ\mu is gone. For instance, with σˉ=σ0+σ1D0\bar\sigma=\sigma_0+\sigma_1D_0, the Banach PAGE complexity (Theorem 4.3) is now O~(αs2κsCP(σˉ2D0+LT2D03)ϵ3+αsCPLTD05/2ϵ5/2+CPD0ϵ).\tilde O\Big(\frac{\alpha_s^2\kappa_s C_P(\bar\sigma^2D_0+L_T^2D_0^3)}{\epsilon^3}+\frac{\alpha_sC_PL_TD_0^{5/2}}{\epsilon^{5/2}}+\frac{C_PD_0}{\epsilon}\Big).

G3. Relation to i.i.d. results (qXDa: Cai et al. 2022, xn54: Diakonikolas 2026 and RAIN). All three assume i.i.d. samples, and Cai et al. and RAIN are Euclidean, relying on monotonicity of I−TI-T for an inner product. We study one continuing Markov trajectory, and our main result is for non-Euclidean norms in which I−TI-T need not be monotone for any inner product (e.g. our ℓ∞\ell_\infty control example). We now state that (i) in the Hilbert case our method is a Markovian implementation of Cai et al.'s estimator, (ii) RAIN's O~(ϵ−2)\tilde O(\epsilon^{-2}) is better in the Euclidean i.i.d. case, but its mechanism (strongly monotone anchored subproblems) needs an inner product, and the Ω(ϵ−3)\Omega(\epsilon^{-3}) lower bound of Bravo & Contreras for single-query linear-span methods with bounded-variance oracles in a normed space shows that this rate does not transfer to general norms, and (iii) Diakonikolas (July 2026) runs a gradual Halpern scheme with clipped recursive differences and obtains high-probability rates in smooth Banach spaces under i.i.d. sampling: O~(ϵ−5)\tilde O(\epsilon^{-5}) with single queries, O~(ϵ−3)\tilde O(\epsilon^{-3}) with Lipschitz-in-expectation two-query oracles. Our setting differs in the sampling: inherited block states make every block average biased, which clipping and median-of-means do not address, and the Poisson analysis does. In exchange we use per-state noise bounds and problem constants in the block lengths. A comparison table is now in Sec. 1 (Table 1), with details in App. A.

Summary of revisions. We removed the rightly criticized Assumption 2.4 and added Lemma B.1 to prove stability. We made the Markovian block lemma explicit in the Poisson constant of the chain (Lemmas C.1–C.2). We showed that the block baseline needs Θ~(ϵ−4)\tilde\Theta(\epsilon^{-4}) samples in Hilbert spaces, with a lower bound that holds even under the PAGE oracle (Proposition 3.1) and a matching upper bound (Theorem B.7). We added an observation-model paragraph and a unified Algorithm 1 (Sec. 2). We included explicit constants in all theorems. We added Table 1 and App. A for comparisons. We added new better-calibrated experiments on periodic average-reward problems with δ∝ϵ\delta\propto\epsilon, means and tail statistics (Sec. 6, App. F). A document marking all changes relative to the initial submission is included in the supplementary material.

Dear Reviewers,

Thank you again for your detailed reviews. We would appreciate it if you could look at our response before the discussion period closes. In brief, the revision (i) removes the iterate-stability assumption by proving stability for the anchored recursion (Lemma B.1), and makes all bounds explicit in the Poisson constant of the chain without a πmin⁡−1\pi_{\min}^{-1} factor (Lemmas C.1–C.2); (ii) shows that the block baseline needs Θ~(ϵ−4)\tilde\Theta(\epsilon^{-4}) samples in Hilbert spaces even under two-query access (Proposition 3.1), and compares our results with Cai et al., RAIN, Diakonikolas, and Blaser and Zhang (Table 1, Appendix A); and (iii) adds calibrated experiments on periodic average-reward problems (Section 6, Appendix F). A document marking all changes is included in the supplementary material. If any concern remains, we would be glad to address it during the discussion.

Best regards,

The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.