Optimal and instance-dependent guarantees for Markovian linear stochastic approximation

DOI10.4171/MSL/44MaRDI QIDQ6386586zbMATH OpenFDO

Authors Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright, Peter L. Bartlett

Publication date 23 December 2021

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4171/MSL/44

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Minimax procedures in statistical decision theory (62C20) Stochastic approximation (62L20) Markov processes: estimation; hidden Markov models (62M05) Stochastic learning and adaptive control (93E35)

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_{mathrmmix}fracdn$ on the squared error of the last iterate of a standard scheme, where $t_{mathrmmix}$ 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_{mathrmmix})$ 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 $lambdain[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).

Cited in

(3)

• Online estimation and inference for robust policy evaluation in reinforcement learning
• On Bellman equations for continuous-time policy evaluation: high-order discretization and function approximation
• A review of off-policy evaluation in reinforcement learning

This page was built for publication: Optimal and instance-dependent guarantees for Markovian linear stochastic approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6386586)