Thesis Defense, Noah Golowich - Title: Theoretical Foundations for Learning in Games and Decision-Making

Abstract: As learning algorithms become increasingly capable of acting autonomously, it is important to better understand the behavior that results from their interactions (1) amongst themselves and (2) with their environments. This talk will present work addressing each of these aspects:

(1) A pervasive challenge in multi-agent learning settings, which spans both theory and practice and dates back decades, has been the failure of convergence for iterative algorithms such as gradient descent. Accordingly, a longstanding central question with broad relevance is: how quickly can we compute solution concepts, i.e., equilibria, in multi-agent settings? I will discuss results which address this question at several scales, starting with simpler normal-form games and building up to larger games such as extensive-form games.

(2) To understand how agents can optimally act in dynamic environments, the framework of reinforcement learning (RL) is used. A notorious challenge in RL is partial observability of the environment, which is typically modeled using Partially Observable Markov Decision Processes (POMDPs). Many existing provable guarantees for POMDPs relied on computationally intractable oracles. I will present the first guarantees for end-to-end learning of a near-optimal policy under a simple condition on the environment known as observability.