PhD Thesis Proposal - Chung-Wei Lee

PhD Candidate: Chung-Wei Lee

Title: Online Learning and Its Applications to Games and Partially Observable Systems

Committee: Haipeng Luo (host), David Kempe, Ashutosh Nayyar, Vatsal Sharan, Jiapeng Zhang

Abstract: Online Learning is a general framework for studying sequential decision-making. I will start with its applications in solving games. In particular, Online Learning has been shown as an essential theoretical foundation when building superhuman AI in poker games. We first focus on last-iterate convergence, a favorable property for online learning algorithms in two-player zero-sum games. In normal-form games, we show optimistic multiplicative weight updates (OMWU) and optimistic gradient descent ascent (OGDA) enjoy last-iterate convergence. We then generalize the results to extensive-form games (EFGs), which model sequential actions and incomplete information that appear in card games. We show that a family of regret minimization algorithms have last-iterate convergence, with some of them based on OMWU and OGDA can even converge exponentially fast. We then consider multiplayer games, where our goal becomes minimizing the individual regret of every player. We design two algorithms achieving logarithmic regret in EFGs based on ideas including a reduction from normal-form games and usage of a self-concordant regularizer on a lifted space.

In addition to solving EFGs as an application of Online Learning to partially observable systems, we discuss other examples, including dynamic pricing and recommender systems. Specifically, we formulate the problems as bandits with graph feedback and preference elicitation and discuss our contributions therein. Finally, I will talk about future work in all directions.

WebCast Link: https://usc.zoom.us/j/96191886806?pwd=UExwOXRyaG9ETUhmaW5udEF3TjYzQT09

Audiences: Everyone Is Invited

Contact: Lizsl De Leon