Georgia Institute of Technology
Finite-sample Guarantees of Stochastic Approximation Algorithms in Average-reward Reinforcement Learning and Decentralized Stochastic Optimization
Abstract
dc:description.abstractThis 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 × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/77903