EUVIMEDEUVIMED entdecken
Crossref

A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation

Zaiwei Chen, Siva T. Maguluri, Sanjay Shakkottai, Karthikeyan Shanmugam

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →