Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
Top Cited Papers
Open Access
- 8 March 2024
- journal article
- research article
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 7 (1) , 41-153
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}}\frac{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 \mathrm{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 \mathrm{TD}(\lambda) algorithm).Keywords
All Related Versions
This publication has 54 references indexed in Scilit:
- A concentration bound for contractive stochastic approximationSystems & Control Letters, 2021
- Statistical and computational guarantees for the Baum-Welch algorithm2015
- Central limit theorems for stochastic approximation with controlled Markov chain dynamicsESAIM: Probability and Statistics, 2015
- Technical Update: Least-Squares Temporal Difference LearningMachine Learning, 2002
- Learning Rates for Q-LearningLecture Notes in Computer Science, 2001
- Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivativesIEEE Transactions on Automatic Control, 1999
- An analysis of temporal-difference learning with function approximationIEEE Transactions on Automatic Control, 1997
- Efficient estimation of the stationary distribution for exponentially ergodic Markov chainsJournal of Statistical Planning and Inference, 1991
- Adaptive Algorithms and Stochastic Approximations1990
- Stochastic Approximation Methods for Constrained and Unconstrained Systems1978