# Max-Quantile Grouped Infinite-Arm Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [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)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence](https://mlsanity.com/paper/1803.04665/) (2018)
- [PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1901.08386/) (2019)
- [Structured Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1706.05198/) (2017)
- [A Survey of Risk-Aware Multi-Armed Bandits](https://mlsanity.com/paper/2205.05843/) (2022)
- [Quantile Bandits for Best Arms Identification](https://mlsanity.com/paper/2010.11568/) (2020)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Exploring k out of Top ρ Fraction of Arms in Stochastic Bandits](https://mlsanity.com/paper/1810.11857/) (2018)
- [Bandits with Dynamic Arm-acquisition Costs](https://mlsanity.com/paper/2110.12118/) (2021)
- [Best Arm Identification under Additive Transfer Bandits](https://mlsanity.com/paper/2112.04083/) (2021)

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

- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)

## Abstract (arXiv)

In this paper, we consider a bandit problem in which there are a number of groups each consisting of infinitely many arms. Whenever a new arm is requested from a given group, its mean reward is drawn from an unknown reservoir distribution (different for each group), and the uncertainty in the arm's mean reward can only be reduced via subsequent pulls of the arm. The goal is to identify the infinite-arm group whose reservoir distribution has the highest (1-α)-quantile (e.g., median if α = frac12), using as few total arm pulls as possible. We introduce a two-step algorithm that first requests a fixed number of arms from each group and then runs a finite-arm grouped max-quantile bandit algorithm. We characterize both the instance-dependent and worst-case regret, and provide a matching lower bound for the latter, while discussing various strengths, weaknesses, algorithmic improvements, and potential lower bounds associated with our instance-dependent upper bounds.