Technical Summary: Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

1. Problem Statement

This paper addresses the finite-sample concentration analysis of Stochastic Approximation (SA) algorithms, specifically focusing on the high-probability bounds of the error $\|x_k - x^*\|_c$, where $x^*$ is the unique fixed point of the averaged operator $\bar{F}$. The study considers a general recursion of the form:
$$x_{k+1} = x_k + \alpha_k (F(x_k, S_k) + Z_k - x_k)$$
where the noise consists of two distinct components:

1. Markovian Noise: A finite-state Markov chain $\{S_k\}$ that introduces temporal dependence and bias in the operator estimates.
2. Additive Martingale-Difference Noise: A sequence $\{Z_k\}$ that is conditionally unbiased given the past filtration.

The work targets two primary regimes often found in applications like Reinforcement Learning (RL) and large-scale optimization:

• General Step Sizes: Step sizes of the form $\alpha_k = \alpha/(k+h)^z$ where $z \in (0, 1]$.
• Heavy-Tailed Noise: The additive noise $Z_k$ may be unbounded, following distributions such as sub-Weibull or sub-Pareto, rather than being strictly bounded or sub-Gaussian.

The central challenge is to establish maximal concentration bounds (time-uniform bounds holding with probability $1-\delta$) under these combined conditions, where previous literature often required bounded noise, specific step sizes (e.g., $O(1/k)$), or independence assumptions.

2. Methodology and Techniques

The authors develop novel proof techniques to overcome three specific challenges: general step sizes, unbounded noise, and Markovian dependence.

2.1. Handling General Step Sizes and Expansive Operators

When step sizes decay slowly ($z < 1$) or the random operator is expansive with positive probability, the error can grow exponentially, rendering standard "bootstrapping" techniques (which rely on uniform bounds) ineffective.

• Projected Auxiliary Algorithm: The authors introduce an auxiliary SA algorithm where iterates are projected onto a ball of radius $B$ centered at $x^*$. This ensures the iterates are uniformly bounded, preventing exponential error growth.
• Coincidence Argument: They demonstrate that if the radius $B$ is chosen sufficiently large (dependent on $\delta$), the projection step is inactive with high probability. Thus, the high-probability bounds derived for the bounded auxiliary iterates apply to the original unbounded iterates.

2.2. Handling Unbounded Additive Noise

For the case of unbounded, identically distributed additive noise, standard moment-generating function (MGF) techniques fail because the MGF of the error may not exist.

• Truncation Argument: The authors define a new auxiliary sequence by truncating the additive noise at a level $B$. This creates a bounded-noise setting where existing concentration results apply.
• Bias Correction: Truncation introduces a bias, shifting the fixed point of the auxiliary operator from $x^*$ to $\tilde{x}$. The authors bound this bias using the contraction property of the average operator $\bar{F}$. They show that for sufficiently large truncation levels, the distance between $x^*$ and $\tilde{x}$ is small, and the original and auxiliary iterates coincide with high probability.

2.3. Handling Markovian Noise

Markovian noise introduces a bias in the drift of the error, preventing the use of standard Lyapunov functions designed for unbiased Martingale-difference noise.

• Poisson Equation-Based Lyapunov Function: The analysis utilizes the solution $V_x$ to the Poisson equation associated with the Markov chain to construct a novel Lyapunov function. This function involves the moment-generating function of the squared error plus a correction term derived from $V_x$.
• Supermartingale Construction: This modified Lyapunov function allows the authors to establish a recursive inequality for the MGF of the error, effectively compensating for the Markovian bias and enabling the derivation of tight high-probability bounds.

3. Key Contributions and Results

3.1. General SA with Bounded Additive Noise

The paper establishes maximal concentration bounds for SA with finite-state Markovian noise and bounded additive noise under general step sizes $\alpha_k = \alpha/(k+h)^z$. The tail behavior of the error depends on the parameter $D = A_1 + A_3 - 1$, where $A_1$ and $A_3$ relate to the Lipschitz constants of the noise and operator, respectively.

• Case $D < 0$ (Almost Surely Contractive):
  • For $z=1$, the error tail is sub-Gaussian.
  • For $z \in (0, 1)$, the error tail is sub-Weibull.
• Case $D = 0$ (Almost Surely Non-Expansive):
  • For $z=1$, the error tail is sub-Gaussian.
  • For $z \in (0, 1)$, the error tail is sub-Weibull (specifically, lighter than any Pareto but heavier than any Weibull).
• Case $D > 0$ (Expansive with Positive Probability):
  • For $z=1$, the error tail is sub-Weibull.
  • For $z \in (0, 1)$, the error tail is heavier than any Weibull but lighter than any Pareto (specifically, of the form $\exp(\log(1/\delta)^{(1-z)/z})$).

The authors provide impossibility results (Theorem 2.3) showing that qualitatively sharper bounds are impossible in general. Specifically, the error cannot be bounded by a sub-Gaussian distribution when $D \ge 0$ or $z < 1$, and the derived bounds match the lower bounds established by counter-examples.

3.2. Contractive SA with Unbounded Additive Noise

For contractive operators ($D < 0$) with step sizes $\alpha_k = O(1/k)$, the authors relax the boundedness assumption on the additive noise to allow for arbitrary unbounded distributions (e.g., sub-Weibull, sub-Pareto).

• Tail Behavior: The concentration bound is expressed in terms of the tail of the noise distribution.
  • If the noise is sub-Weibull with parameter $\theta$, the error tail is sub-Weibull with parameter $2\theta + 1/2$ (roughly 2 to 3 times heavier than the noise).
  • If the noise is sub-Pareto with parameter $\theta$, the error tail is sub-Pareto with parameter $\theta/4$ (requiring $\theta > 4$ for convergence).
• Methodology: This result is achieved via the "black-box truncation argument" described in Section 3.2, which reduces the unbounded case to the bounded case while controlling the bias introduced by truncation.

3.3. Applications and Illustrations

The general results are instantiated for specific settings:

• Contractive SA: Recovering bounds for standard contractive SA algorithms.
• Stationary Mean Estimation: Deriving Hoeffding-like bounds for the empirical mean of a Markov chain.
• Linear SA: Applying results to linear systems with Hurwitz matrices.
• Polyak-Ruppert Averaging: Combining their bounds with recent results on averaging to show that while averaging improves asymptotic variance, it may result in heavier tails for the estimation error compared to the unaveraged iterates, particularly when the operator is expansive.

4. Significance and Claims

The paper claims to provide the first maximal concentration bounds for stochastic approximation algorithms that simultaneously handle:

1. Finite-state Markovian noise.
2. General step sizes ($O(1/k^z)$ for $z \in (0, 1]$).
3. Potentially unbounded, heavy-tailed additive noise.

The authors emphasize that their results are order-wise optimal (up to polylogarithmic factors) and qualitatively sharp, as demonstrated by their impossibility theorems. They highlight that previous literature was limited to either bounded noise, specific step sizes (like $O(1/k)$), or independence assumptions, which are often violated in practical applications like Reinforcement Learning with function approximation.

The methodological contribution lies in the combination of a Poisson-equation-based Lyapunov function (to handle Markovian bias) and auxiliary coupled iterates (via projection and truncation) to handle general step sizes and unbounded noise. This framework allows for a unified analysis of the tail behavior of SA iterates across a wide range of noise regimes and operator properties.