Multi-armed Bandits with Structured and Correlated Arms

演讲人: Osman Yağan Carnegie Mellon University
时间: 2024-07-24 14:00-2024-07-24 15:00
地点:FIT 1-222
内容:

Multi-armed bandit algorithms, which aim to maximize the cumulative reward or identify the best option among a set of choices (referred to as arms), are naturally suited for problems involving sequential decision-making under uncertainty. They are being used in applications such as clinical trials, system testing, scheduling in computing systems, and web optimization. Most existing works on multi-armed bandit algorithms assume that the rewards across arms are independent from each other. In practice, however, rewards from different arms are often correlated or reward distributions of arms are related through their dependence on a latent parameter/feature. Not exploiting such inherent structure and correlation between arms can lead to significantly higher sample-complexity, especially when the number of arms is large. In this talk, we will present our recent work on exploiting known latent structures and correlation between arms to drastically reduce the sample complexity of multi-armed bandit algorithms. Specifically, we will present reward maximization algorithms for two different frameworks: i) the structured bandit framework, where the rewards depend on a common latent feature vector, and ii) a novel correlated bandit framework where reward realizations from arms are correlated with each other. This will be done through a unified approach that enables translating any current/future bandit algorithm to the structured and correlated settings.

个人简介:

Osman Yağan is a Full Research Professor of Electrical and Computer Engineering (ECE) at Carnegie Mellon University (CMU), where he is also an affiliate faculty in the School of Computer Science and a core member of CyLab Security and Privacy Institute. Prior to joining the faculty of the ECE department in August 2013, he was a Postdoctoral Research Fellow in CyLab at CMU. Dr. Yağan received his Ph.D. degree in Electrical and Computer Engineering from the University of Maryland at College Park, MD in 2011, and his B.S. degree in Electrical and Electronics Engineering from the Middle East Technical University, Ankara (Turkey) in 2007.  His research focuses on modeling, analysis, and performance optimization of computing systems, and uses tools from applied probability, network science, data science, and machine learning. In the context of data science and ML, he is working on statistical inference and decision making using sequential samples (e.g., multi-armed bandits), and resilient distributed machine learning. On the network science side, he has broad interests including robustness of cyber-physical systems; secure and reliable design of large-scale ad-hoc networks; and contagion processes in complex networks with a focus on modeling, analysis, and control of spread of viruses, (mis)information, and opinions. He is a senior member of IEEE, and a recipient of a CIT Dean's Early Career Fellowship, an IBM Academic Award, and best paper awards in ICC 2021, IPSN 2022, and ASONAM 2023.