Meteorite logoMeteorite
Back to videos

SNAPP Seminar || Alexandre Proutiere (KTH Royal Institute of Technology) || Oct 10, 2022

SNAPP Webpage: https://sites.google.com/view/snappseminar/home Speaker: Alexandre Proutiere, KTH Royal Institute of Technology Title: Near-Optimal Latent State Decoding in Block MDPs October 10, 2022, 11:30 am US Eastern Abstract: In this talk, we report recent advances on the problems of model estimation and reward-free learning in episodic Block MDPs. In these MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are first interested in estimating the latent state decoding function (the mapping from the observations to latent states) based on data generated under a fixed behavior policy. We derive an information-theoretical lower bound on the error rate for estimating this function and present an algorithm approaching this fundamental limit. In turn, our algorithm also provides estimates of all the components of the MDP. We then study the problem of learning near-optimal policies in the reward-free framework. Based on our efficient model estimation algorithm, we show that we can infer a policy converging (as the number of collected samples grows large) to the optimal policy at the best possible rate. Interestingly, our analysis provides necessary and sufficient conditions under which exploiting the block structure yields improvements in the sample complexity for identifying near-optimal policies. When these conditions are met, the sample complexity in the minimax reward-free setting is improved by a multiplicative factor n, where n is the number of possible contexts. Joint work with Y. Jedra, J-H. Lee and S-Y. Yun Speaker's Bio: Alexandre Proutiere is a professor in the EECS school at KTH, Royal Institute of Technology, Stockholm, Sweden. He was a researcher at Microsoft Research (Cambridge) from 2007 to 2011, and a research engineer at France Telecom R&D from 2000 to 2006. He was an invited lecturer and researcher at the computer science department ENS Paris from 2004 to 2006. Alexandre received a Ph.D. in Applied Mathematics from Ecole Polytechnique, he graduated in Mathematics from Ecole Normale Superieure (Paris) and has an engineering degree from Telecom Paris. He is an engineer from Corps des Mines. He received the ACM Sigmetrics rising star award in 2009, the ACM best papers awards at Sigmetrics 2004 and 2010, and Mobihoc 2009. He held an ERC consolidator grant from 2012 to 2017.

Suggested videos