Featured image of post Recent Advances in Average-Reward Restless Bandits

Recent Advances in Average-Reward Restless Bandits

Weina Wang


Time: 4:00-5:00 PM; 01/09/2024
Location: Packard 202


Weina Wang
Assistant Professor,
Computer Science Department,
Carnegie Mellon University


We consider the infinite-horizon, average reward restless bandit problem. A central challenge is designing computationally efficient policies that achieve a diminishing optimality gap as the number of arms, N, grows large. Existing policies, including the renowned Whittle index policy, all rely on a uniform global attractor property (UGAP) assumption to achieve asymptotic optimality, which is a complex and difficult-to-verify assumption. In this talk, I will present new, sampling-based policy designs for restless bandits. One of our proposed policies breaks the long-standing UGAP assumption for the first time, and the subsequent policies eliminate the need for the UGAP assumption to achieve asymptotic optimality. Our techniques offer new insights into guaranteeing convergence (avoiding undesirable attractors or cycles) in large stochastic systems. This talk is based on joint work with Yige Hong (CMU), Qiaomin Xie (UW–Madison), and Yudong Chen (UW–Madison).



Weina Wang is an Assistant Professor in the Computer Science Department at Carnegie Mellon University. Her research lies in the broad area of applied probability and stochastic systems, with applications in cloud computing, data centers, and privacy-preserving data analytics. She was a joint postdoctoral research associate in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign, and in the School of ECEE at Arizona State University, from 2016 to 2018. She received her Ph.D. degree in Electrical Engineering from Arizona State University in 2016, and her Bachelor’s degree from the Department of Electronic Engineering at Tsinghua University in 2009. Her dissertation received the Dean’s Dissertation Award in the Ira A. Fulton Schools of Engineering at Arizona State University in 2016. She received the Kenneth C. Sevcik Outstanding Student Paper Award at ACM SIGMETRICS 2016, the Best Paper Award at ACM MobiHoc 2022, an NSF CAREER award in 2022, and the ACM SIGMETRICS Rising Star Research Award in 2023.


Logo designed by Seohyun Jeon
Theme Stack designed by Jimmy