Multi-Armed Bandit: Online Learning in Dynamic Systems with Unknown Models

Qing Zhao

UC Davis

Abstract

Since the first multi-armed bandit (MAB) problem posed by Thompson in 1933 for the application of clinical trials, MAB has developed into an important branch in stochastic optimization and machine learning and has found a wide range of applications in economics and finance, medicine, and industrial engineering. It has recently received increasing attention from the communications and networking research community for formulating and tackling the optimization of learning and activation in dynamic systems with unknown models. A mathematical abstraction of the MAB problems involves a player who can operate one of N arms at each time, with each yielding a random reward drawn from an unknown distribution when operated. The objective is an arm selection policy that minimizes the regret defined as the performance loss with respect to a genie who knows the reward model of each arm. In this talk, we present our recent results that extend the classic MAB theory in several directions: from exponential family of reward distributions to heavy tail reward distributions, from a single player to multiple distributed players, from i.i.d. reward models to restless Markov reward models, and from independent to correlated arms.

Biography

Qing Zhao received the Ph.D. degree in Electrical Engineering in 2001 from Cornell University, Ithaca, NY. In August 2004, she joined the Department of Electrical and Computer Engineering at University of California, Davis, where she is currently a Professor. Her research interests are in the general area of stochastic optimization, decision theory, and algorithmic theory in dynamic systems and communication and social networks.

She received the 2010 IEEE Signal Processing Magazine Best Paper Award and the 2000 Young Author Best Paper Award from the IEEE Signal Processing Society. She holds the title of UC Davis Chancellor’s Fellow and received the 2008 Outstanding Junior Faculty Award from the UC Davis College of
Engineering. She was a plenary speaker at the 11th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2010. She is also a co-author of two papers that received student paper awards at ICASSP 2006 and the IEEE Asilomar Conference 2006.