# Multi-thresholding Good Arm Identification with Bandit Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 13 Mar 2025.

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

- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [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)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization](https://mlsanity.com/paper/2006.04655/) (2020)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Multi-Objective Generalized Linear Bandits](https://mlsanity.com/paper/1905.12879/) (2019)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Skyline Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1711.04213/) (2017)

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

- [Test-Time Scaling via Budgeted Multi-Attribute Verification](https://mlsanity.com/paper/2609.34322/) (2026)

## Abstract (arXiv)

We consider a good arm identification problem in a stochastic bandit setting with multi-objectives, where each arm i ∈ [K] is associated with a distribution Di defined over RM. For each round t, the player pulls an arm it and receives an M-dimensional reward vector sampled according to Dit. The goal is to find, with high probability, an ε-good arm whose expected reward vector is larger than bmxi - ε 1, where bmxi is a predefined threshold vector, and the vector comparison is component-wise. We propose the Multi-Thresholding UCB~(MultiTUCB) algorithm with a sample complexity bound. Our bound matches the existing one in the special case where M=1 and ε=0. The proposed algorithm demonstrates superior performance compared to baseline approaches across synthetic and real datasets.