A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation
Operations Research · 2024-07 · 72 (4) · 1352-1367
DOI: 10.1287/opre.2022.0249 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, 2024-07. Verfasst von Zaiwei Chen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 47 Literaturangaben.
Abstract (Originalsprache)
The stochastic approximation (SA) method stands as the foundational mathematical tool for modern large-scale optimization and machine learning. Therefore, gaining a theoretical understanding of SA algorithms is of fundamental interest. In their paper titled “A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation,” Chen et al. present a unified Lyapunov framework for the finite-sample analysis of a Markovian SA algorithm under a contractive operator with respect to an arbitrary norm. The key novelty lies in the construction of a smooth Lyapunov function called the generalized Moreau envelope. The authors demonstrate the effectiveness of their SA results in the context of reinforcement learning (RL), specifically through popular algorithms such as variants of temporal difference (TD) learning and Q-learning. As byproducts, the results provide theoretical insights into the efficiency of bootstrapping in TD learning with eligibility traces and the bias-variance tradeoff in off-policy learning.
Zitieren
APA
Chen, Z., Maguluri, S. T., Shakkottai, S., & Shanmugam, K. (2024). A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation. Operations Research, 72(4), 1352-1367. https://doi.org/10.1287/opre.2022.0249
Vancouver
Chen Z, Maguluri ST, Shakkottai S, Shanmugam K. A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation. Operations Research. 2024;72(4):1352-1367. doi:10.1287/opre.2022.0249
BibTeX
@article{Chen2024,
author = {Chen, Zaiwei and Maguluri, Siva T. and Shakkottai, Sanjay and Shanmugam, Karthikeyan},
title = {A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation},
journal = {Operations Research},
year = {2024},
volume = {72},
number = {4},
pages = {1352--1367},
doi = {10.1287/opre.2022.0249}
}
EUVIMED