SNAPP Seminar || Kevin Jamieson (University of Washington) || October 7, 2024

Speaker: Kevin Jamieson (University of Washington) || October 7, 2024, Mon, 11:30am Eastern Time

Title: Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning

Abstract: In this talk, we explore the non-asymptotic sample complexity for the pure exploration problem in both contextual bandits and tabular reinforcement learning (RL), specifically focusing on identifying an ε-optimal policy from a given set of policies Π with high probability. In the bandit setting, prior work has demonstrated that it is possible to identify the best policy by focusing on estimating only the differences in behaviors between individual policies, rather than estimating each policy’s behavior independently, leading to significant improvements in sample efficiency. However, the best-known approaches for tabular RL fail to exploit this idea and instead estimate the behavior of each policy individually. We investigate whether this efficiency can be extended to RL by estimating only the differences in policy behaviors, and we present a nuanced answer. For contextual bandits, we show that such an approach is indeed sufficient. However, for tabular RL, we establish that it is not, revealing a key distinction between the two settings. Nevertheless, we propose a new approach inspired by this observation, showing that it is nearly sufficient to estimate behavior differences in RL when anchored by a reference policy. Our algorithm leverages this insight to provide the tightest known bound on the sample complexity of tabular RL, offering both theoretical advancements and practical implications for reinforcement learning research.

Speaker's Bio: Kevin Jamieson is an Associate Professor in the Paul G. Allen School of Computer Science & Engineering at the University of Washington. He received his B.S. in 2009 from the University of Washington under the advisement of Maya Gupta, his M.S. in 2010 from Columbia University under the advisement of Rui Castro, and his Ph.D. in 2015 from the University of Wisconsin - Madison under the advisement of Robert Nowak, all in electrical engineering. He returned to the University of Washington as faculty in 2017 after a postdoc in the AMP lab at the University of California, Berkeley working with Benjamin Recht. Jamieson's work has been recognized by an NSF CAREER award and Amazon Faculty Research award.