Yuejie Chi
[introductory/intermediate] Statistical and Algorithmic Foundations of Reinforcement Learning
Summary
As a paradigm for sequential decision making in unknown environments, reinforcement learning (RL) has received a flurry of attention in recent years. However, the explosion of model complexity in emerging applications and the presence of nonconvexity exacerbate the challenge of achieving efficient RL in sample-starved situations, where data collection is expensive, time-consuming, or even high stakes (e.g., in clinical trials, autonomous systems, and online advertising). How to understand and enhance the sample and computational efficacies of RL algorithms is thus of great interest. In this tutorial, we aim to introduce both the basics and recent important algorithmic and theoretical developments in RL, highlighting the connections between new ideas and classical topics.
Syllabus
Employing Markov decision processes as the central mathematical model, we cover several distinctive RL scenarios (i.e., RL with a simulator, online RL, offline RL, robust RL, multi-agent RL, RL with human feedback) and present several mainstream RL approaches (i.e., model-based approach, value-based approach, and policy optimization). Our discussions gravitate around the issues of sample complexity, computational efficiency, and algorithm-dependent and information-theoretic lower bounds from a nonasymptotic viewpoint.
References
Yuejie Chi, Yuxin Chen and Yuting Wei, “Statistical and Algorithmic Foundations of Reinforcement Learning”, INFORMS TutORials in Operations Research, pp. 104-144, 2025.
Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai, “Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF”, International Conference on Learning Representations (ICLR), 2025.
Jiin Woo, Gauri Joshi, and Yuejie Chi, “The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond”, Journal of Machine Learning Research, vol. 26, no. 26, pp. 1-85, 2025.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi, “The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model”, Conference on Neural Information Processing Systems (NeurIPS), 2023.
Shicong Cen and Yuejie Chi, “Global Convergence of Policy Gradient Methods in Reinforcement Learning, Games and Control”, arXiv:2310.05230, 2023.
Pre-requisites
Basics of linear algebra, statistics and optimization. No prior background on RL will be assumed.
Short bio
Dr. Yuejie Chi is the Charles C. and Dorothea S. Dilley Professor of Statistics and Data Science at Yale University, with a secondary appointment in Computer Science, and a member of Yale Institute for Foundations of Data Science. She received her Ph.D. and M.A. from Princeton University, and B. Eng. (Hon.) from Tsinghua University, all in Electrical Engineering. Her research interests lie in the theoretical and algorithmic foundations of data science, generative AI, reinforcement learning, and signal processing, motivated by applications in scientific and engineering domains. Among others, Dr. Chi received the Presidential Early Career Award for Scientists and Engineers (PECASE), SIAM Activity Group on Imaging Science Best Paper Prize, IEEE Signal Processing Society Young Author Best Paper Award, and the inaugural IEEE Signal Processing Society Early Career Technical Achievement Award for contributions to high-dimensional structured signal processing. She is an IEEE Fellow (Class of 2023) for contributions to statistical signal processing with low-dimensional structures.
