Multi-armed Bandits with Structured and Correlated Arms

Abstract:  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. They are being used in applications such as clinical trials, system testing, scheduling in computing systems, and web optimization. Most of the works on multi-armed bandit algorithms assume independence of the rewards across arms. In reality, 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 done through a unified approach that enables translating any current/future bandit algorithm to the structured and correlated settings.

Bio: Osman Yağan is an Associate Research Professor of Electrical and Computer Engineering (ECE) at Carnegie Mellon University (CMU). Prior to joining the faculty of the ECE department in August 2013, he was a Postdoctoral Research Fellow in CyLab at CMU. He has also held a visiting Postdoctoral Scholar position at Arizona State University during Fall 2011. 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.

Dr. Yağan’s research interests are in modeling, design, and performance evaluation of engineering systems with particular emphasis on communication systems and networks. Specific research topics include wireless communications, security, random graphs, social and information networks, and cyber-physical systems.

Dr. Yağan is a Senior Member of IEEE and a recipient of CIT Dean’s Early Career Fellowship.

Join Zoom Meeting https://umich.zoom.us/j/97598571292

Meeting ID: 975 9857 1292

Passcode: XXXXXX (Will be sent via email to attendees)