Abstract

Reinforcement learning (RL) is an interactive decision making problem where an agent tries to maximize its cumulative reward through interacting with an unknown environment. RL has seen a surge of interest over the past decade, fueled primarily by its empirical success in a wide range of tasks, including Atari games, Go, robotics and dialogue systems.

 Motivated by and complementing empirical research, theoretical understanding of RL has also made substantial progress in the past few years. In the most basic case, tabular RL, minimax optimal algorithms have been identified and analyzed. Recent focus of research in the tabular case has shifted toward instance dependent bounds, adversarial settings and multi-agent RL.

However, the tabular case fails to capture many real-world problems where the number of states is huge or infinite, in which case function approximation is necessary. In contrast to the usual supervised learning case where complexity measures such as VC dimension are able to characterize the feasibility of learning, the search for structural assumptions that would empower efficient RL remains inconclusive. It has been conjectured and recently proven that realizability alone is insufficient even for linear function approximation, making stronger conditions necessary. Several candidates include low Bellman rank, low witness rank and low Bellman-Eluder dimension, yet the picture is far from complete.

My research focus would be on improving the theoretical understanding of RL by addressing some of the aforementioned challenges, such as those about multi-agent learning and function approximation RL. On the multi-agent side, I would like to investigate which solution concepts, such as rationalizability, no-regret and various equilibria, are attainable in RL. On the function approximation side, I hope to identify minimal structural assumptions that permit efficient RL.