ORIE Colloquium: Kevin Jamieson (Washington)

Sample Complexity Reduction via Policy Difference Estimation in Reinforcement Learning

An autonomous agent is placed into an unfamiliar environment with unknown rules and hidden rewards – how quickly can it learn to navigate and maximize its rewards? Efficient exploration is central to reinforcement learning (RL), with critical applications from robotics to personalized healthcare. In this talk, we focus on the pure exploration problem in contextual bandits and tabular RL, aiming to identify an approximately optimal policy from a set of candidates with high probability. Previous work in contextual bandits significantly improved sample efficiency by estimating only differences between policies rather than behaviors individually. However, existing methods in tabular RL fail to exploit this insight, instead estimating each policy’s behavior directly. We investigate extending this efficient approach from bandits to RL and present a nuanced answer: difference estimation is sufficient for contextual bandits but fundamentally insufficient in tabular RL. Inspired by this limitation, we propose anchoring policy estimates to a single reference policy, achieving substantial sample complexity improvements and delivering the tightest known bounds in tabular RL. Our findings provide new theoretical insights and practical strategies for efficient exploration in RL. Based on joint work with Adhyyan Narang, Andrew Wagenmaker, and Lillian Ratliff.

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.