Max-Min Grouped Bandits

No. 8: AAAI-22 Technical Tracks 8

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Machine Learning III

In this paper, we introduce a multi-armed bandit problem termed max-min grouped bandits, in which the arms are arranged in possibly-overlapping groups, and the goal is to find a group whose worst arm has the highest mean reward. This problem is of interest in applications such as recommendation systems, and is also closely related to widely-studied robust optimization problems. We present two algorithms based successive elimination and robust optimization, and derive upper bounds on the number of samples to guarantee finding a max-min optimal or near-optimal group, as well as an algorithm-independent lower bound. We discuss the degree of tightness of our bounds in various cases of interest, and the difficulties in deriving uniformly tight bounds.

10.1609/aaai.v36i8.20838