会议介绍

Tianyuan Jin is currently an Assistant Professor in the Data Science and Analytics (DSA) Thrust at The Hong Kong University of Science and Technology (Guangzhou). He received his Ph.D. degree in Computer Science from the National University of Singapore (NUS) in 2024, and his M.S. degree in Computer Science and B.S. degree in Mathematics from the University of Science and Technology of China (USTC). Prior to joining HKUST(GZ), he was a Research Fellow at NUS. His research interests include online learning, bandit algorithms, reinforcement learning, and their applications to large language models and other real-world problems. He has published papers in leading venues and journals, including COLT, NeurIPS, ICML, ICLR, and JMLR. He also serves as a reviewer for leading AI, machine learning, and theory conferences and journals, including NeurIPS, ICLR, ICML, AAAI, AISTATS, JMLR, SODA, ITCS, and TIT. He received the Google PhD Fellowship and the AISG PhD Fellowship in 2021, as well as the Dean’s Graduate Research Excellence Award in 2024.

Abstract:
Thompson Sampling (TS) is one of the most widely used algorithms for sequential decision-making, owing to its simplicity and strong empirical performance. In this talk, we present recent advances in Thompson Sampling for combinatorial multi-armed bandits (CMABs). A key challenge in this setting is that existing regret guarantees for Combinatorial Thompson Sampling (CTS) often scale exponentially with the size of the optimal super arm, limiting their applicability in large-scale problems.
To address this issue, we introduce Single-Seed Combinatorial Thompson Sampling (CTS³), a new algorithm in which the posterior samples of all base arms are generated using a shared random seed. This coupling preserves the correct posterior marginal distributions while inducing coordinated optimism across arms. Leveraging this property, CTS³ achieves the first polynomial regret bound for Thompson Sampling in general CMAB settings.
We further demonstrate through extensive experiments that CTS³ consistently outperforms standard CTS, achieving significantly lower regret across a variety of settings.