Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
Lijie Chen, Jian Li, Mingda Qiao
Abstract
In the Best-k-Arm problem, we are given n stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the k arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-k-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-k-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-1-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-k-Arm (module constant factors).
BibTeX
@InProceedings{pmlr-v54-chen17a,
title = {{Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection}},
author = {Chen, Lijie and Li, Jian and Qiao, Mingda},
booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics},
pages = {101--110},
year = {2017},
editor = {Singh, Aarti and Zhu, Jerry},
volume = {54},
series = {Proceedings of Machine Learning Research},
month = {20--22 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v54/chen17a/chen17a.pdf},
url = {https://proceedings.mlr.press/v54/chen17a.html},
abstract = {In the Best-k-Arm problem, we are given n stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the k arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-k-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-k-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-1-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-k-Arm (module constant factors).}
}