Back to search

Georgia Institute of Technology

Sample complexity of Reinforcement Learning algorithms with a focus on policy space methods

Abstract

dc:description.abstract

In this thesis, we develop fast Reinforcement Learning algorithms with finite sample complexity guarantees. The work is divided into two main parts. In the first, we investigate stochastic approximation across various domains to establish finite sample complexity bounds. We study two settings: federated stochastic approximation and two-time-scale linear stochastic approximation with Markovian noise. In the former, we develop a FedSAM algorithm where multiple agents are utilized to solve a fixed-point equation, following a stochastic approximation with Markovian noise. Moreover, we show that FedSAM has linear speedup with respect to the number of agents, while enjoying a constant communication cost. In the latter, we explore two-time-scale linear stochastic approximation with Markovian noise, establishing tight finite-time bounds. The second part delves into finite-time bounds for Reinforcement Learning algorithms, with an emphasis on policy space methods. First, we consider two-time-scale natural actor-critic algorithm with on-policy data. For this algorithm we establish a ε-6 sample complexity for convergence to the global optimum. Next, we study two-loop natural actor-critic, and we establish a ε-3 sample complexity, improving upon the two-time-scale counterpart. In this case, we consider an off-policy sampling strategy. To enhance the sample complexity of the natural actor-critic, we separate the algorithm into 'Actor' and 'Critic' components. For the Critic, we consider federated TD-learning and TD-learning with Polyak averaging. For the former, we show a linear speedup, and in the latter we establish a tight finite time bound. Furthermore, we establish a tight finite time convergence bound for the TDC algorithm. For the Actor, we demonstrate linear and superlinear convergence rates for the natural policy gradient.

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
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Khodadadian, Sajad
Advisor dc:contributor.advisor
  • Maguluri, Siva Theja
Committee members dc:contributor.committeemember
  • Lan, Guanghui (George)
  • Pananjady, Ashwin
  • Romberg, Justin
  • Russo, Daniel

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Khodadadian, Sajad. Sample complexity of Reinforcement Learning algorithms with a focus on policy space methods. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/73172