Back to search

Georgia Institute of Technology

Finite-sample Guarantees of Stochastic Approximation Algorithms in Average-reward Reinforcement Learning and Decentralized Stochastic Optimization

Abstract

dc:description.abstract

This thesis investigates the finite-sample guarantees of stochastic approximation (SA) algorithms, which are central to solving root-finding and fixed-point problems in optimization and reinforcement learning (RL). We first provide the finite-sample guarantees for average-reward TD($\lambda$) with linear function approximation for policy evaluation, and tabular $Q$-learning in the synchronous setting for the control problem, addressing challenges posed by the lack of contraction in the average-reward setting. Next, we develop a unified non-asymptotic theory for SA under seminorm-contractive operators, extending classical Lyapunov stability results and enabling tighter performance bounds. Finally, we propose and analyze a stochastic dual accelerated method that achieves optimal deterministic and stochastic error bounds for online stochastic distributed averaging, with theoretical guarantees confirmed through numerical experiments. The method and analysis are further extended to a broader class of problems—specifically, decentralized strongly convex stochastic optimization with quadratic objectives and noisy estimates of the gradients. Collectively, these contributions deepen the theoretical understanding of SA algorithms and provide practical tools for designing efficient learning and optimization methods.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Sheng
Advisor dc:contributor.advisor
  • Romberg, Justin
Committee members dc:contributor.committeemember
  • Pananjady, Ashwin
  • Maguluri, Siva Theja
  • Lan, Guanghui
  • Doan, Thinh

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/77903

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Sheng. Finite-sample Guarantees of Stochastic Approximation Algorithms in Average-reward Reinforcement Learning and Decentralized Stochastic Optimization. Doctoral thesis, Georgia Institute of Technology, 2025. https://hdl.handle.net/1853/77903