Online Learning for Combinatorial and Stochastic Optimization Tasks




2023-04-13 10:00:00 ~ 2023-04-13 11:00:00






Many real-world optimization tasks involve stochastic and uncertain inputs, such as stochastic delays in network routing or unknown click-through rates in advertising. This leads to the paradigm of online learning, where an agent learns uncertain environmental inputs while performing optimization in a sequential and online manner. The combinatorial multi-armed bandit (CMAB) framework was introduced to address this challenge. In this talk, I will focus on a more complex set of tasks within the CMAB framework, where the feedback on the unknown variables of the system may be stochastically triggered, potentially generating a cascade of feedback among the variables. This problem is modeled as the combinatorial multi-armed bandit with probabilistically triggered arms (CMABT).

I will first introduce the basic framework of CMABT, including the conditions that enable effective performance of the online learning algorithm. Next, I will discuss recent research advances in this area, such as variance-based conditions that further enhance online learning performance. Additionally, I will present several applications that fall within the CMABT framework. Some of these applications may not initially seem connected to CMABT, while others represent ongoing research.


Wei Chen is a Principal Researcher and the Director of Theory Center at Microsoft Research Asia. He is also an Adjunct or Guest Professors at several universities such as Shanghai Jiao Tong University, Tsinghua University, and Shenzhen University. He is a standing committee member of the Technical Committee on Theoretical Computer Science, Chinese Computer Federation (CCF), and a member of the CCF Technical Committee on Big Data. He is a Fellow of Institute of Electrical and Electronic Engineers (IEEE).  Wei Chen’s main research interests include online learning and optimization, social and information networks, network game theory and economics, distributed computing, and fault tolerance. He has served as editors, academic conference chairs and program committee members for many academic conferences and journals. Wei Chen has Bachelor and Master degrees from Tsinghua University and a Ph.D. degree in computer science from Cornell University. For more information, you are welcome to visit his home page at http://research.microsoft.com/en-us/people/weic/.

© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University

邮箱:jhc@sjtu.edu.cn 电话:021-54740299