# Max-Min Grouped Bandits

arXiv: https://arxiv.org/abs/2111.08862 · HTML: https://mlsanity.com/paper/2111.08862/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 17 Nov 2021.

## Builds on (most cited first, 12 of 12)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Local Clustering in Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2103.00063/) (2021)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit](https://mlsanity.com/paper/1906.03979/) (2019)
- [Multi-Armed Bandits with Dependent Arms](https://mlsanity.com/paper/2010.09478/) (2020)
- [Robust Monotone Submodular Function Maximization](https://mlsanity.com/paper/1507.06616/) (2015)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (2021)
- [Categorized Bandits](https://mlsanity.com/paper/2005.01656/) (2020)

## Built on by (most cited first, 7 of 7)

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2412.08031/) (2024)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Active Context Selection Improves Simple Regret in Contextual Bandits](https://mlsanity.com/paper/2605.20040/) (2026)

## Abstract (arXiv)

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 the group whose worst arm has the highest mean reward. This problem is of interest in applications such as recommendation systems and resource allocation, 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.