Agnostic Reinforcement Learning in Low-Rank MDPs and Rich Observations

Agnostic Reinforcement Learning in Low-Rank MDPs and Rich Observations (via Zoom)

Abstract: There have been many recent advances on provably efficient Reinforcement Learning (RL) in problems with rich observation spaces. However, all these works share a strong realizability assumption about the optimal value function of the true MDP. Such realizability assumptions are often too strong to hold in practice. In this talk, I will discuss some recent work, where we consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies \Pi that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank d of the underlying MDP. Specifically, our algorithm enjoys a sample complexity bound of $O(H^{4d} K^{3d} \log\abs{\Pi}/\eps^2)$ where H is the length of episodes, K is the number of actions and \eps>0 is the desired sub-optimality. I will next discuss a nearly matching lower bound for this agnostic setting that shows that the exponential dependence on rank is unavoidable, and discuss extensions of this algorithms that allow adaptivity to unknown eigenspectrum and the rank of the underlying MDP. 

This is joint work with Christopher Dann (Google), Yishay Mansour (Google / Tel Aviv), Mehryar Mohri (Google / NYU) and Karthik Sridharan (Cornell). 

Bio: Ayush Sekhari is a 4th year PhD student in the Computer Science department at Cornell University, advised by Professor Karthik Sridharan and Professor Robert D. Kleinberg. His research interests span across online learning, reinforcement learning and control, optimization and the interplay between them. Before coming to Cornell, he spent a year at Google as a part of the Brain residency program. Before Google, he completed his undergraduate studies in computer science from IIT Kanpur in India.