Recently, the research team led by Shuai Li, an associate professor at the John Hopcroft Center for Computer Science in SEIEE, has made significant progress in the study of the linear bandit problem. The related paper "Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm" has been accepted by the Annual Conference on Learning Theory (COLT) 2023. All the authors of this paper are from Shanghai Jiao Tong University. The first and second authors are both Ph.D. students under the guidance of Shuai Li. Shuai Li is the corresponding author. This is the first time Shanghai Jiao Tong University has published a paper at COLT, and it is the sole affiliation of the authors.

The linear bandit problem has been studied for many years in both stochastic and adversarial settings. Designing an algorithm that can optimize the environment without knowing the loss type attracts lots of interest. Lee et al. [2021] propose an algorithm that actively detects the loss type and then switches between different algorithms specially designed for different settings. However, such an approach requires meticulous designs to perform well in all settings. Follow-the-regularized-leader (FTRL) is another popular algorithm type that can adapt to different environments. This algorithm is of simple design and the regret bounds are shown to be optimal in traditional multi-armed bandit problems compared with the detect-switch type algorithms. Designing an FTRL-type algorithm for linear bandits is an important question that has been open for a long time. In this paper, we prove that the FTRL-type algorithm with a negative entropy regularizer can achieve the best-of-three-world results for the linear bandit problem with the tacit cooperation between the choice of the learning rate and the specially designed self-bounding inequality.

Paper Link：https://arxiv.org/abs/2303.06825

About Shuai Li

Shuai Li is an Associate Professor at Shanghai Jiao Tong University. His research focuses on reinforcement learning algorithms and machine learning theory. Shuai Li received his Bachelor's degree in Mathematics at Zhejiang University, a Master's degree in Mathematics from the Academy of Mathematics and Systems Science at the Chinese Academy of Sciences, and a Ph.D. in Computer Science and Engineering from the Chinese University of Hong Kong. In 2019, he joined the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. Shuai Li was a recipient of the Google PhD Fellowship in 2018 and the Yangfan Plan Talent Program in Shanghai in 2020.

About COLT

COLT, initiated in 1988 and hosted by the Association for Computational Learning (ACL), is a premier international conference in the field of machine learning theory. It is widely recognized as one of the most prestigious conferences in this area, known for its highly competitive acceptance rates. As of 2022, among research institutions and universities in mainland China, only four papers have been accepted with a single affiliation.