Reinforcement learning under general function approximation and novel interaction settings

Reinforcement Learning (RL) is an area of machine learning where an intelligent agent solves sequential decision-making problems based on experience. Recent advances in the applications of RL have been witnessed not only in the field of games, control systems, and healthcare, but also in language models and addressing open problems in mathematics. Despite the recent progress, RL algorithms are deemed to be data-hungry and unstable in training. Therefore, a flurry of research has focused on building fundamental guarantees for provably efficient RL algorithms. This line of research aims to provide a theoretical backbone and deepen our understanding of RL methods, which is crucial for the success of applications of RL in real-world scenarios. The main theme of this thesis is to propose and analyze sample efficient algorithms under different structural complexity measures and various interaction settings. In the thesis, we examine numerous setups: from pure offline RL to online RL with exploration, from Markov Decision Processes (MDPs) with low-rank structures to MDPs under more general function approximators, and from reward-aware to reward-free learning. More concretely, this thesis shows theoretical results in the sequel. The first part of this thesis revisits data coverage and function class representability assumptions in offline RL and makes an important conjecture that initiates future research. The second part provides a positive result in offline RL under non-exploratory data and weak function approximation. The third part focuses on the reward-free learning framework under general non-linear function approximation, bridges the sizeable gap in our understanding of reward-aware and reward-free settings, and shows an exponential separation between low-rank and linear completeness settings. Lastly, in the fourth part, we consider representation learning and reward-free learning in low-rank MDPs from the angle of the density candidate feature class. When establishing statistical complexity guarantees for RL algorithms under structural assumptions, we leverage powerful tools from machine learning theory literature. Throughout the thesis, we tackle complex scenarios in RL, where the agent faces challenges such as the absence of online data collection or a lack of reward information as guidance while exploring the environment. Overall, this thesis proposes sample efficient algorithms and presents theoretical results under general function approximation and novel interaction protocols.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Chen, Jinglin

Contributors dc:contributor

• Jiang, Nan
• Banerjee, Arindam
• Raginsky, Maxim
• Krishnamurthy, Akshay

• Reinforcement Learning
• Sample Complexity Analysis
• Machine Learning
• Artificial Intelligence

Statement dc:rights

• Copyright 2023 Jinglin Chen

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121992

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121992