Name
Abstract | ||
|---|---|---|
We introduce a variant of the classical PAC multi-armed bandit problem. There is an ordered set of n arms A[1],..., 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],..., A[i - 1]. We define a natural notion of an epsilon-approximate skyline and prove matching upper and lower bounds for identifying an epsilon-skyline. Specifically, we show that in order to identify an epsilon-skyline from among n arms with probability 1 - delta, Theta(n/epsilon(2) center dot min {log (1/epsilon(delta)), (n/delta)}) samples suffice and are necessary in the worst case. When epsilon >> 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. [Full version available on arXiv: arxiv.org/abs/1711.04213]. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/isit.2018.8437618 | 2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) |
DocType | Volume | Citations |
Conference | abs/1711.04213 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Albert Cheu | 1 | 2 | 3.08 |
| Ravi Sundaram | 2 | 762 | 72.13 |
| Jonathan Ullman | 3 | 485 | 40.07 |