Breaking the Sample Size Barrier in Reinforcement Learning

Speaker:  Yuxin Chen – Philadelphia, USA
Topic(s):  Artificial Intelligence, Machine Learning, Computer Vision, Natural language processing

Abstract

Emerging reinforcement learning (RL) applications necessitate the design of sample-efficient solutions in order to accommodate the explosive growth of problem dimensionality. Despite the empirical success, however, our understanding about the statistical limits of RL remains highly incomplete. In this talk, I will present some recent progress towards settling the sample complexity limits in RL. The first scenario is concerned with RL with a generative model, which allows one to query arbitrary state-action pairs to draw independent samples. We prove that a model-based algorithm (a.k.a. the plug-in approach) achieves minimal-optimal sample complexity without any burn-in cost. The second scenario is concerned with online RL, where an agent learns via real-time interactions with an unknown environment. We develop the first algorithm — an optimistic model-based algorithm — that achieves minimax-optimal regret for the entire range of sample sizes. Time permitting, we will also discuss the effectiveness of model-based paradigms in offline RL and multi-agent RL. Our results emphasize the prolific interplay between high-dimensional statistics, online learning, and game theory.

About this Lecture

Number of Slides:  50
Duration:  55 minutes
Languages Available:  Chinese (Simplified), English
Last Updated:  03/02/2026

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.