Abstract: Many reinforcement/machine learning problems involve loss minimization, min-max optimization and fixed-point equations, all of which can be cast under the framework of Variational Inequalities (VIs). Stochastic methods like SGD, SEG and TD/Q Learning are prevalent, and their constant stepsize versions have gained popularity due to effectiveness and robustness. Viewing the iterates of these algorithms as a Markov chain, we study their fine-grained probabilistic behavior. In particular, we establish finite-time geometric convergence of the iterates distribution, and relate the ergodicity properties of the Markov chain to the characteristics of the VI, algorithm and data.

Using techniques of coupling and basic adjoint relationship, we characterize the limit distribution and how its bias depends on the stepsize. For smooth problems, exemplified by TD learning and smooth min-max optimization, the bias is proportional to the stepsize. For nonsmooth problems, exemplified by Q-learning and generalized linear model with nonsmooth link functions (e.g., ReLU), the bias has drastically different behavior and scales with the square root of the stepsize.

This precise probabilistic characterization allows for variance reduction via tail-averaging and bias reduction via Richardson-Romberg extrapolation. The combination of constant stepsize, averaging and extrapolation provides a favorable balance between fast mixing and low long-run error, and we demonstrate its effectiveness in statistical inference compared to traditional diminishing stepsize schemes.

Bio: Qiaomin Xie is an assistant professor in the Department of Industrial and Systems Engineering at the University of Wisconsin-Madison. Her research interests lie in the fields of reinforcement learning, applied probability, game theory and stochastic networks, with applications to computer and communication networks. She was previously a visiting assistant professor at School of Operations Research and Information Engineering at Cornell University (2019-2021). Prior to that, she was a postdoctoral researcher with LIDS at MIT. Qiaomin received her Ph.D. in Electrical and Computing Engineering from University of Illinois Urbana-Champaign in 2016. She received her B.S. in Electronic Engineering from Tsinghua University. She is a recipient of NSF CAREER Award, JPMorgan Faculty Research Award, Google Systems Research Award and UIUC CSL PhD Thesis Award.