Events Calendar

CS Distinguished Lecture: Sham Kakade (University of Washington) – Sub-Linear Reinforcement Learning

Speaker: Sham Kakade, University of Washington

Talk Title: Sub-Linear Reinforcement Learning

Series: Computer Science Distinguished Lecture Series

Abstract: Suppose an agent is an unknown environment and seeks to maximize his/her long term future reward. We consider the basic question: does the agent need to learn an accurate model of the environment before he/she can start executing a near-optimal long term course of actions?

Specifically, this talk will consider the problem of provably optimal reinforcement learning for (episodic) finite horizon MDPs, i.e., how an agent learns to maximize his/her (long term) reward in an uncertain environment. The talk will present a novel algorithm, the Variance-reduced Upper Confidence Q-learning (vUCQ), which is the first algorithm which enjoys a regret bound that is both sub-linear in the model size and that achieves optimal minimax regret. The algorithm is sub-linear in that the time to achieve epsilon average regret is a number of samples that is far less than that required to learn any (non-trivial) estimate of the underlying model of the environment. The importance of sub-linear algorithms is largely the motivation for algorithms such as "Q-learning" and other "model-free" approaches.

vUCQ is a successive refinement method in which the algorithm reduces the variance in the "Q-value" estimates and couples this estimation scheme with an upper confidence based algorithm. Technically, this coupling of these techniques is what leads to the algorithm's strong guarantees, showing that "model-free" approaches can be optimal.

This lecture satisfies requirements for CSCI 591: Research Colloquium.


Biography: Sham Kakade is a Washington Research Foundation Data Science Chair, with a joint appointment in the Department of Statistics and the Department of Computer Science at the University of Washington.

From 2011-2015, I was a principal research scientist at Microsoft Research, New England. From 2010-2012, I was an associate professor at the Department of Statistics, Wharton, University of Pennsylvania. From 2005-2009, I was an assistant professor at the Toyota Technological Institute at Chicago.

I completed my PhD at the Gatsby Computational Neuroscience Unit under the supervision of Peter Dayan, and I was an undergraduate at Caltech where I obtained my BS in physics. I was a postdoc in the Computer and Information Science department at the University of Pennsylvania under the supervision of Michael Kearns.


Host: Computer Science Department

Location: Henry Salvatori Computer Science Center (SAL) - 101

Audiences: Everyone Is Invited

Contact: Computer Science Department