AI4OPT Seminar Series

Date: Thursday, October 6, 2022

Location: Virtual Meeting

Time: Noon – 1:00 pm

Meeting Link: https://gatech.zoom.us/j/99381428980

Speaker: Chi Jin (金驰)

When Is Partially Observable Reinforcement Learning Not Scary?

Abstract: Partially observability is ubiquitous in applications of Reinforcement Learning (RL), in which agents learn to make a sequence of decisions despite lacking complete information about the latent states of the controlled system. Partially observable RL is notoriously difficult in theory---well-known information-theoretic results show that learning partially observable Markov decision processes (POMDPs) requires an exponential number of samples in the worst case. Yet, this does not rule out the possible existence of interesting subclasses of POMDPs, which include a large set of partial observable applications in practice while being tractable. In this talk we identify a rich family of tractable POMDPs, which we call weakly revealing POMDPs. This family rules out the pathological instances of POMDPs where observations are uninformative to a degree that makes learning hard. We prove that for weakly revealing POMDPs, a simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) is sufficient to guarantee a polynomial sample complexity. To the best of our knowledge, this gives the first line of provably sample-efficient results for learning from interactions in POMDPs. This is based on joint works with Qinghua Liu, Alan Chung, Akshay Krishnamurthy, Sham Kakade, and Csaba Szepesvari.

Bio: Chi Jin is an assistant professor at the Electrical and Computer Engineering department of Princeton University. He obtained his Ph.D. in Computer Science at University of California, Berkeley, advised by Michael I. Jordan. His research mainly focuses on theoretical machine learning, with special emphasis on nonconvex optimization and reinforcement learning. His representative work includes proving noisy gradient descent escape saddle points efficiently and proving the efficiency of Q-learning and least-squares value iteration when combined with optimism in reinforcement learning.

About Seminar Series:

Artificial Intelligence Institute for Advances in Optimization (AI4OPT) is an NSF funded AI institute jointly between Georgia Tech and several other institutions. Starting this Fall, the institute is kicking off a new seminar series, broadly on AI and Optimization. The weekly seminar announcements will be sent in the new ai4opt-seminars mailing list. To receive these announcements, please subscribe here: https://lists.isye.gatech.edu/mailman/listinfo/ai4opt-seminars

We have the following lineup of speakers for the Fall semester (with a few more that will be added).

• Hamsa Bastani, Wharton School of Business, U. Penn
• Satyen Kale, Google Research
• Chi Jin, Princeton
• Spyros Chatzivasileiadis, Technical University of Denmark
• Karthyek Murthy, Singapore University of Technology and Design
• Dylan Foster, Microsoft Research
• Soroosh Shafieezadeh Abadeh, CMU
• Subhabrata Sen, Harvard