UCLA

This dissertation addresses key challenges in reinforcement learning (RL): inefficiency in large state-action spaces and vulnerability in non-stationary environments. As a cornerstone of artificial intelligence (AI), RL enables autonomous agents to learn optimal decision-making through environmental interaction. While successful in many domains, RL often struggles with the complexity of vast state-action spaces and performance degradation in unstable settings. To overcome these limitations, this work establishes theoretical foundations and develops efficient algorithms tailored for these challenging scenarios.

The first part of this dissertation focuses on achieving efficient and near-optimal RL in large state-action spaces. We introduce a function approximation approach that estimates expected cumulative rewards using a predefined function class, enabling effective exploration and exploitation. By employing a variance-aware weighted scheme, we theoretically guarantee optimal worst-case regret. Furthermore, we develop a linear function approximation-based RL algorithm that exploits the environment's specific structure to significantly reduce regret and enhance performance.

The second part of this dissertation explores maintaining stable RL performance in non-stationary environments, addressing two specific challenges. First, we consider unreliable observations with potential adversarial corruption of rewards and transitions. To mitigate this, we introduce an uncertainty-aware weighted mechanism that adaptively weights observations, balancing the impact of adversarial influence. Based on this, we present an algorithm achieving optimal regret under a bounded adversary. Second, we focus on asynchronous federated reinforcement learning, enabling collaborative policy adjustment among multiple agents. We develop a robust algorithm that eliminates strict participation requirements, allowing voluntary agent contribution while ensuring near-optimal performance with low communication overhead.

The methods and techniques presented herein contribute to a deeper theoretical understanding of RL's fundamental limitations, particularly in non-stationary environments. These findings also pave the way for future research and highlight open questions toward designing more robust and efficient decision-making algorithms.