# Skyline Identification in Multi-Armed Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2017.

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

- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Multi-thresholding Good Arm Identification with Bandit Feedback](https://mlsanity.com/paper/2503.10386/) (2025)
- [Optimal Algorithms for Range Searching over Multi-Armed Bandits](https://mlsanity.com/paper/2105.01390/) (2021)

## Abstract (arXiv)

We introduce a variant of the classical PAC multi-armed bandit problem. There is an ordered set of n arms A[1],dots,A[n], each with some stochastic reward drawn from some unknown bounded distribution. The goal is to identify the skyline of the set A, consisting of all arms A[i] such that A[i] has larger expected reward than all lower-numbered arms A[1],dots,A[i-1]. We define a natural notion of an varepsilon-approximate skyline and prove matching upper and lower bounds for identifying an varepsilon-skyline. Specifically, we show that in order to identify an varepsilon-skyline from among n arms with probability 1-δ,  Thetabigg(fracnvarepsilon2 · minbigg logbigg(frac1varepsilon δbigg), logbigg(fracnδbigg) bigg bigg)  samples are necessary and sufficient. When varepsilon gg 1/n, our results improve over the naive algorithm, which draws enough samples to approximate the expected reward of every arm; the algorithm of (Auer et al., AISTATS'16) for Pareto-optimal arm identification is likewise superseded. Our results show that the sample complexity of the skyline problem lies strictly in between that of best arm identification (Even-Dar et al., COLT'02) and that of approximating the expected reward of every arm.