Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach

Technical Summary: Concentration and Mean-Square Bounds for Contractive Stochastic Approximation

Problem Formulation
The paper addresses the finite-time analysis of Stochastic Approximation (SA) algorithms defined by the iteration:
$$x_{k+1} = x_k + \beta_k (f(x_k) - x_k + M_{k+1})$$
where $x_k \in \mathbb{R}^d$ is the iterate, $\beta_k$ is the stepsize, $f(\cdot)$ is a mapping with a unique fixed point $x^*$, and $M_{k+1}$ is a martingale difference noise sequence. The analysis focuses on two specific challenges prevalent in Reinforcement Learning (RL) and other applications:

1. Arbitrary Norm Contractivity: The mapping $f(\cdot)$ is contractive with respect to an arbitrary norm $\|\cdot\|_c$ (e.g., the $\ell_\infty$ norm used in Q-learning), rather than the Euclidean norm. This complicates the derivation of Lyapunov drift inequalities because the squared norm is non-smooth in these cases.
2. Multiplicative Noise: The noise is not uniformly bounded; instead, its conditional second moment scales affinely with the norm of the iterates: $\mathbb{E}[\|M_{k+1}\|_c^2 \mid \mathcal{F}_k] \leq \sigma^2 (1 + \|x_k\|_c^2)$. Consequently, the iterates $x_k$ are potentially unbounded, which obstructs the direct application of standard martingale concentration inequalities that require almost-sure bounds.

Methodology
The authors propose a unified and elementary framework that avoids the complex machinery used in prior works, such as generalized Moreau envelopes for smoothing non-smooth norms or multi-stage bootstrapping arguments for handling unbounded iterates. The core techniques are:

1. Averaged Noise and Auxiliary Iterates:
   The authors define an averaged noise sequence $\xi_{k+1} = (1-\beta_k)\xi_k + \beta_k M_{k+1}$ (with $\xi_0=0$) and auxiliary iterates $z_k = x_k - \xi_k$. This transformation allows the original iteration to be rewritten in terms of $z_k$:
   $$z_{k+1} = z_k + \beta_k (f(z_k) - z_k + \Delta_k)$$
   where $\Delta_k = f(x_k) - f(z_k)$. Crucially, this construction yields a one-step Lyapunov drift inequality for the squared error $\|z_k - x^*\|_c^2$ directly, without needing to smooth the norm or construct an envelope. The error $\|x_k - x^*\|_c$ is then bounded by $\|z_k - x^*\|_c + \|\xi_k\|_c$.

2. Inductive Arguments for Control:
   Since the noise depends on the iterates, the term $\|\xi_k\|_c$ must be bounded separately for the mean-square and concentration analyses using induction:

   • Mean-Square Bound: A straightforward induction is used to show that the iterates remain bounded in expectation ($\mathbb{E}[\|x_k\|_c^2]$ is uniformly bounded). This suffices to bound $\mathbb{E}[\|\xi_k\|_c^2]$.
   • Concentration Bound: A probabilistic induction is employed over a sequence of "good" events $\{C_k\}$ where the error is controlled. The proof decomposes the probability of the union of bad events by the first time a good event fails. On the event that all previous events held, the iterates (and thus the noise) are effectively bounded, allowing the application of the standard Azuma-Hoeffding inequality to a truncated martingale difference sequence.

Key Results
The paper establishes two primary theorems under the assumption that $f(\cdot)$ is contractive with factor $\lambda < 1$ and the stepsize is $\beta_k = \beta / (k+h)$.

1. Mean-Square Error Bound (Theorem 1):
   Under the multiplicative noise model, there exist constants such that if $h$ is sufficiently large:
   $$\mathbb{E}[\|x_k - x^*\|_c^2] \leq \frac{\mathfrak{c}_2}{k+h}$$
   For the $\ell_\infty$ norm, the rate is $O(\frac{\sigma^2 \log d}{(1-\lambda)^3 k})$, matching the rates obtained by Chen et al. [13] who used Moreau envelopes.

2. Maximal Concentration Bound (Theorem 2):
   The paper derives a high-probability bound that holds simultaneously for all $k \geq 0$ (a maximal bound). For every confidence level $\delta \in (0,1)$, if the stepsize parameter $h$ depends logarithmically on $\delta$ (specifically $h = \Omega(\log(1/\delta))$), then with probability at least $1 - \frac{\pi^2}{3}\delta$:
   $$\forall k \geq 0: \|x_k - x^*\|_c^2 \leq \frac{\mathfrak{c}_4 \log(d(k+1)/\delta)}{k+h}$$
   This bound features a sub-Gaussian tail (scaling as $\log(1/\delta)$).

Significance and Claims
The authors claim their work provides the first sub-Gaussian tailed maximal (all-time) concentration bound for SA under the multiplicative noise model with potentially unbounded iterates.

• Unification: The approach unifies the analysis of mean-square and concentration bounds using elementary techniques (averaged noise and induction) rather than specialized machinery like Moreau envelopes or complex bootstrapping.
• Sub-Gaussian Tail vs. Impossibility: The paper highlights a trade-off identified in prior work (Chen et al. [15]): achieving a sub-Gaussian tail for multiplicative noise is impossible with a stepsize sequence independent of the confidence level $\delta$. By allowing the initial stepsize (via $h$) to depend mildly on $\delta$ ($h \propto \log(1/\delta)$), the authors recover the sub-Gaussian tail. If $h$ is fixed, the bound only holds after a transient period $k_0 = \Omega(\log(1/\delta))$.
• Generalizability: The authors suggest the noise-averaging technique and probabilistic induction are generalizable to other noise models (e.g., heavy-tailed noise) and iterative algorithms with unbounded iterates (e.g., SSP Q-learning, RVI Q-learning).

The paper concludes that while the proof techniques are simpler, they do not sacrifice sharpness, recovering existing rates for mean-square error and improving the tail behavior for concentration bounds in the multiplicative noise setting.