Yudong Chen

Nonsmooth Learning Algorithms Behave Differently from Smooth Ones Many learning algorithms, including Q-learning, update their estimates through noisy recursive rules. When these updates use a constant step size and involve nonsmooth operators, their long-run behavior can be difficult to characterize: the iterates do not converge to a single point but instead settle into a stationary distribution, and classical tools for smooth dynamics may fail. In “Prelimit Coupling and Steady-State Convergence of Constant-Step-Size Nonsmooth Contractive SA,” Yixuan Zhang, Dongyan (Lucy) Huo, Yudong Chen, and Qiaomin Xie develop a prelimit coupling framework for analyzing such nonsmooth stochastic approximation procedures. They establish Wasserstein convergence to a unique stationary distribution, characterize the limiting steady-state distribution as the step size vanishes, and show that nonsmoothness can create a bias of order of the square root of the step size, unlike the bias linear in the step size that is typical of smooth dynamics. The results also justify Richardson–Romberg extrapolation as a tool for bias reduction, with applications to Q-learning.

We consider linear stochastic approximation (LSA) with constant step size and Markovian data. Viewing the joint process of the data and LSA iterate as a time-homogeneous Markov chain, we prove its convergence to a unique limiting and stationary distribution and establish nonasymptotic, geometric convergence rates. Furthermore, we show that the bias vector of this limit admits an infinite series expansion with respect to the step size. Consequently, the bias is proportional to the step size up to higher-order terms. This result contrasts with LSA under independent and identically distributed data, for which the bias vanishes. In the reversible chain setting, we characterize the relationship between the bias and the mixing time of the Markovian data, establishing that they are roughly proportional to each other. Although Polyak–Ruppert tail averaging reduces the variance of LSA iterates, it does not affect the bias. The above characterization implies that the bias can be reduced using Richardson–Romberg extrapolation with [ ] step sizes, eliminating the [ ] leading terms in the bias expansion. This extrapolation scheme leads to an exponentially smaller bias and an improved mean-squared error both theoretically and empirically. Our results immediately apply to the temporal difference learning algorithm with linear function approximation and stochastic gradient descent applied to quadratic functions. Funding: Y. Chen is supported in part by the National Science Foundation Division of Computing and Communication Foundations [Grants CCF-1704828 and CCF-2233152] and the University of Wisconsin–Madison [Vilas Associate Award]. Q. Xie is supported in part by the National Science Foundation Division of Computer and Network Systems [Grant CNS-1955997]; the Division of Electrical, Communications and Cyber Systems [Grants ECCS-2339794 and ECCS-2432546]; and JPMorgan Chase and Company [Faculty Research Award].

We consider the infinite-horizon, average-reward restless bandit problem in discrete time. We propose a new class of policies that are designed to drive a progressively larger subset of arms toward the optimal distribution. We show that our policies are asymptotically optimal with an [ ] optimality gap for an N-armed problem, assuming only a unichain and aperiodicity assumption. Our approach departs from most existing work that focuses on index or priority policies, which rely on the Global Attractor Property to guarantee convergence to the optimum, or a recently developed simulation-based policy, which requires a Synchronization Assumption. Funding: Y. Hong and W. Wang are supported in part by the U.S. National Science Foundation (NSF) [Grants ECCS-2145713, CCF-2403194, CCF-2428569, and ECCS-2432545]. Y. Chen is supported in part by the NSF [Grant CCF-2233152]. Q. Xie is supported in part by the NSF [Grants CNS-1955997, ECCS-2339794, and ECCS-2432546]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2024.0678 .

Motivated by robust and quantile regression problems, we investigate the stochastic gradient descent (SGD) algorithm for minimizing an objective function f that is locally strongly convex with a sub--quadratic tail. This setting covers many widely used online statistical methods. We introduce a novel piecewise Lyapunov function that enables us to handle functions f with only first-order differentiability, which includes a wide range of popular loss functions such as Huber loss. Leveraging our proposed Lyapunov function, we derive finite-time moment bounds under general diminishing stepsizes, as well as constant stepsizes. We further establish the weak convergence, central limit theorem and bias characterization under constant stepsize, providing the first geometrical convergence result for sub--quadratic SGD. Our results have wide applications, especially in online statistical methods. In particular, we discuss two applications of our results. 1) Online robust regression: We consider a corrupted linear model with sub--exponential covariates and heavy--tailed noise. Our analysis provides convergence rates comparable to those for corrupted models with Gaussian covariates and noise. 2) Online quantile regression: Importantly, our results relax the common assumption in prior work that the conditional density is continuous and provide a more fine-grained analysis for the moment bounds.

Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.

Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.