A Class of Restless Bandit Problems: Indexability and Optimality of Whittles Index

Dr. Qing Zhao
Assoc. Professor
U.C. Davis
Abstract:
The long‐standing multi‐armed bandit problem (MAB), propounded in early 1930's, was
solved by Gittins almost 40 years later in late 1960's when he established the simple
index structure of the optimal policy. In 1988, Whittle generalized MAB to the so‐called
restless multi‐armed bandit problem (RMAB) to take into account system dynamics that
cannot be directly controlled. Gittin's index policy is no longer optimal, and RMAB has
been shown to be PSPACE‐hard in general.
In this talk, we present a brief history of bandit problems and some recent results on a
special class of RMAB. We show that this class of RMAB is indexable, and Whittle's index
policy has a simple semi‐universal structure and achieves optimality.
This class of RMAB is particularly relevant to cognitive radio, user/server scheduling,
and optimal activation in multi‐agent systems.
Bio:
http://www.ece.ucdavis.edu/~qzhao/
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 UC Davis where she is currently an Associate Professor.
Her research interests are in the general area of dynamic systems and communication
networks. She received the 2000 Young Author Best Paper Award from IEEE Signal Processing
Society and the 2008 Outstanding Junior Faculty Award from the UC Davis College of
Engineering.
Host: Bhaskar Krishnamachari

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Shane Goodoff