----------------------------------------------------------------------------------------------------

     Department of Systems Engineering and Engineering Management

                    The Chinese University of Hong Kong

----------------------------------------------------------------------------------------------------

Date: Tuesday, September 29, 2026, 4:30pm to 5:30pm HKT

Venue: ERB 909, The Chinese University of Hong Kong

Title:  Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

Speaker: Dr. Zhengchao Wang, University of Sydney Business School

Abstract:

We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of 4.45√KT+10.75K for K arms and horizon T. This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on [0,1] through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.

Biography:

Zhengchao Wang is a Lecturer in the Discipline of Business Analytics at the University of Sydney Business School. His research combines optimization and statistical learning to support data-driven decision-making, with applications in revenue management and social good. His work spans assortment optimization, customer choice modelling, fundraising for nonprofit organizations, and human-in-the-loop recommendations. His research has been published in Operations Research. He holds a PhD in Analytics and Operations from Imperial College Business School, where he also worked as a Research Associate before joining the University of Sydney.

Everyone is welcome to attend the talk!

SEEM-5201 Website: http://seminar.se.cuhk.edu.hk