Related papers: Optimal and instance-dependent guarantees for Markovian linear stochastic approximation

Optimal and instance-dependent guarantees for Markovian linear stochastic approximation

URL: http://arxiv.org/abs/2112.12770v2
Date: Sun, 12 May 2024 02:06:43 GMT
Title: Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
Authors: Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright, Peter L. Bartlett,
Abstract summary: We show a non-asymptotic bound of the order $t_mathrmmix tfracdn$ on the squared error of the last iterate of a standard scheme. We derive corollaries of these results for policy evaluation with Markov noise.
Score: 47.912511426974376
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study stochastic approximation procedures for approximately solving a $d$-dimensional linear fixed point equation based on observing a trajectory of length $n$ from an ergodic Markov chain. We first exhibit a non-asymptotic bound of the order $t_{\mathrm{mix}} \tfrac{d}{n}$ on the squared error of the last iterate of a standard scheme, where $t_{\mathrm{mix}}$ is a mixing time. We then prove a non-asymptotic instance-dependent bound on a suitably averaged sequence of iterates, with a leading term that matches the local asymptotic minimax limit, including sharp dependence on the parameters $(d, t_{\mathrm{mix}})$ in the higher order terms. We complement these upper bounds with a non-asymptotic minimax lower bound that establishes the instance-optimality of the averaged SA estimator. We derive corollaries of these results for policy evaluation with Markov noise -- covering the TD($\lambda$) family of algorithms for all $\lambda \in [0, 1)$ -- and linear autoregressive models. Our instance-dependent characterizations open the door to the design of fine-grained model selection procedures for hyperparameter tuning (e.g., choosing the value of $\lambda$ when running the TD($\lambda$) algorithm).