Halpern Iteration with Markovian Data

Most stochastic-approximation analyses begin with independent samples. In online reinforcement learning, the data instead arrive along a trajectory, so each state depends on the previous one. This dependence becomes particularly important in fixed-point iterations with a non-expansive operator, where contraction cannot be relied on to damp sampling errors.

We study the residual of the final iterate when every observation comes from one continuing Markov chain. Our method combines Halpern iteration, which anchors each update to the starting point, with PAGE, a recursive variance-reduction method. The analysis covers Hilbert spaces and finite-dimensional Banach spaces, including the sup norm used by many reinforcement-learning operators.

Residuals for non-expansive maps

A fixed-point problem asks for a point x* satisfying T(x*) = x*. In many reinforcement-learning problems, T is non-expansive: applying it does not increase distances, but it need not shrink them either. Without contraction, sampling errors are not automatically damped. We therefore measure the final iterate directly through its residual ||x - T(x)||; a guarantee for an averaged iterate would not provide the same information.

Halpern iteration anchors every update to the initial point. In its deterministic form, x_n is a weighted average of that anchor and the previous iterate after applying T. The anchor supplies structure that yields a last-iterate residual guarantee for non-expansive maps. The challenge is to preserve that guarantee when T is only observed through noisy samples from a dependent trajectory.

Markovian blocks

The paper assumes a finite, irreducible, aperiodic Markov chain and works with stochastic operator evaluations whose stationary mean is T. A block of consecutive states is not an independent minibatch. In particular, its error can have a predictable boundary component because the chain's starting state is known from the observations collected so far.

The analysis handles this through the Poisson equation. For a state-dependent error g with stationary mean zero, the equation rewrites its sum along the chain as martingale differences plus a telescoping boundary term. If ||g||₂,π denotes its stationary root-mean-square size, then for a block of length S the conditional bias of the block average is at most C_B ||g||₂,π / S, and its conditional second moment is at most C_V ||g||₂,π² / S. Thus the random component shrinks at the usual square-root rate, while the boundary bias decays as 1/S. The bounds remain valid when a block starts at a stopping time and its length is chosen before observing the block.

These Poisson bounds allow blocks to begin away from stationarity and avoid restarting the chain. They rely on finite-state geometric mixing, with constants that depend on the chain.

Direct block estimation

A direct method estimates T at each iteration by averaging a new block of transitions. To keep the accumulated perturbation small enough for the Halpern residual bound, later estimates must become increasingly accurate. The resulting baseline has expected last-iterate residual O(log N / N), but its sample complexity scales as ε⁻⁵ up to logarithmic factors. The cost comes from repeatedly building accurate estimates from scratch.

PAGE

PAGE avoids rebuilding every estimate independently. It occasionally refreshes an estimate using a block of samples. Between refreshes, it updates that estimate using the difference between operator evaluations at the current and previous query points, computed on the same sampled states. When the query points are close, much of the sample noise is shared and cancels in the difference, so the recursive estimate can be updated with a shorter block.

This cancellation requires the second moment of the same-state difference error to grow at most proportionally to the squared distance between query points, analogous to the mean-square regularity condition used in variance-reduced stochastic optimization. Finite variance of individual evaluations by itself does not imply this property.

PAGE also requires a multi-point oracle: one observed transition must support evaluations at both the current and previous value function or Q-function. In our tabular experiments, a stored transition provides both evaluations without another environment step. This oracle is stronger, and uses more computation, than one restricted to a single query point per sample.

Hilbert and Banach geometries

In a Hilbert space, non-expansiveness of T makes the residual operator I - T cocoercive. The paper uses this structure to control the PAGE estimator for the residual directly. The resulting leading sample complexity is O(ε⁻³), without an additional logarithmic factor in that accuracy dependence.

Many reinforcement-learning operators are non-expansive in the sup norm but not in an inner-product norm, so the Hilbert residual argument does not apply to them. For a general finite-dimensional Banach norm, the paper instead controls changes in the anchored Halpern displacement between successive iterates. This gives expected sample complexity scaling as ε⁻³ up to logarithmic factors. The same analysis covers sup and block-sup norms, with their norm-comparison constants stated explicitly. The broader geometry preserves the leading accuracy power of the Hilbert result while introducing logarithmic terms.

The paper also gives a high-probability Banach-space guarantee. It controls the estimator in an auxiliary smooth norm that dominates the working norm. For sup-norm applications, smooth approximations introduce logarithmic dimension dependence. The result requires additional concentration and stability assumptions; concentration is not applied directly in the nonsmooth sup norm.

Experiments

The experiments use two synthetic eight-state average-reward problems driven by a continuing cycle chain. One is fixed-policy evaluation, whose Bellman operator is non-expansive in Euclidean norm. The other is two-action control, whose optimality operator is non-expansive in the sup norm but not in a Hilbert norm. Each is tested with a fast- and a slow-mixing chain. The methods are compared at common environment-transition budgets, on twenty trajectories per setting, with each method pair sharing the same trajectory.

Figure 1 reports the median normalized last-iterate residual, with the interquartile range across trajectories. Rows separate evaluation from control; columns separate fast from slow mixing. The comparisons count observed transitions, not operator evaluations, so PAGE's two evaluations on one stored transition are reflected in its oracle-access requirement rather than charged as another environment step.

Figure 1. Median normalized fixed-point residual versus environment-transition budget. Top: Hilbert-space policy evaluation. Bottom: sup-norm control. Left and right columns use fast- and slow-mixing chains. Shaded bands show the interquartile range over 20 trajectories.

The comparison changes with the chain’s mixing speed. On fast policy evaluation, block Halpern reaches residual 0.05 sooner than PAGE (8,839 versus 14,684 transitions), reflecting its lower initial overhead. The curves later cross: at 128,000 transitions, PAGE’s median residual is 0.00515, compared with 0.0290 for the block method. On the slow-mixing chain, PAGE reaches residual 0.05 in a median of 107,374 transitions for policy evaluation and 80,000 for control. The block method does not reach that target within 2,048,000 transitions in policy evaluation, and only 8 of 20 control runs reach it.

Median observed transitions to normalized residual 0.05 on the slow-mixing chain. Parentheses report successful runs when fewer than 20 reach the target; the maximum budget is 2,048,000 transitions.

On the fast-mixing policy-evaluation task, the block method reaches 0.05 in 8,839 transitions versus 14,684 for PAGE, while PAGE has the lower median residual later, at 128,000 transitions.

These tabular experiments test the algorithms and oracle assumptions along one continuing trajectory. They do not estimate worst-case complexity or establish large-scale performance. Within this setting, PAGE’s recursive differences help most on the slow-mixing chain, while the block method remains competitive early on the fast-mixing chain.

Assumptions and the remaining lower-bound question

The guarantees require a finite irreducible aperiodic chain, stable iterates, controlled stationary second moments, and a mean-square bound on same-state oracle differences. High-probability results add smooth-norm and concentration conditions. Blocks may begin away from stationarity and the chain runs continuously throughout, under the assumed Markovian mixing conditions.

Our ε⁻³ Hilbert rate is not shown to be minimax optimal. The cited Ω(ε⁻³) lower bound covers a broad linear-span class with a single-point oracle, while PAGE evaluates two query points on the same sample. A lower bound for PAGE’s stronger oracle model remains open.

The result applies when the operator is non-expansive in the geometry of interest, samples come from one mixing trajectory, and a transition can be reused at neighboring query points. Under these conditions, Halpern anchoring and recursive estimation give last-iterate guarantees without restarting the environment. The Banach-space analysis includes sup-norm control problems alongside the Hilbert-space setting.