Abstract
Combinatorial optimization is one of the core areas in theoretical computer science and operations research, with many classical problems such as graph shortest paths, minimum spanning trees, maximum weighted matchings, and it also has numerous modern applications such as in networking, online advertising, crowd sourcing, and viral marketing. However, in many of these modern applications, the exact parameters needed as inputs, such as link latencies in wireless networking, click-through rates in online advertising, worker-task performance in crowd sourcing, and diffusion probabilities in viral marketing, are stochastic and unknown, and thus have to be learned over time. On the other hand, well-studied online learning and optimization frameworks, exemplified by the classical multi-armed bandit problem, cannot be applied directly to address these problems due to the exponential blowup in the solution space. Therefore, it demands a new framework that could incorporate combinatorial learning seamlessly into the existing combinatorial optimization framework, without re-engineering the optimization tasks from scratch.
In this talk, I will introduce a series of works I and my collaborators have done in the recent years to systematically build such a framework. I will first introduce our work on the general combinatorial multi-armed bandit (CMAB) framework that incorporates optimization tasks with non-linear objective functions and approximation guarantees, and provide a modularized learning algorithm with tight regret analysis. I will then introduce our recent studies including CMAB with probabilistically triggered arms, CMAB with general reward functions, and combinatorial pure exploration, which cover different aspects of combinatorial online learning. Throughout my talk I will illustrate how the framework and the results can be applied to applications such as online advertising, crowd-sourcing, and viral marketing, and discuss many opportunities in further advancing this line of research.
Time
2017-11-16 10:00 ~ 11:00Speaker
Wei Chen, Microsoft Research AsiaRoom
Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics
