Multi-thresholding Good Arm Identification with Bandit Feedback

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.