Thresholding bandit with optimal aggregate regret

Chao Tao; Saúl A. Blanco; Jian Peng; Yuan Zhou

Thresholding bandit with optimal aggregate regret

Chao Tao, Saúl A. Blanco, Jian Peng, Yuan Zhou

Research output: Contribution to journal › Conference article › peer-review

Abstract

We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold ?, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.

Original language	English (US)
Journal	Advances in Neural Information Processing Systems
Volume	32
State	Published - 2019
Event	33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 - Vancouver, Canada Duration: Dec 8 2019 → Dec 14 2019

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@article{1ca2b4a2ded6481e90546d3f999f1a18,

title = "Thresholding bandit with optimal aggregate regret",

abstract = "We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold ?, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.",

author = "Chao Tao and Blanco, {Sa{\'u}l A.} and Jian Peng and Yuan Zhou",

note = "Publisher Copyright: {\textcopyright} 2019 Neural information processing systems foundation. All rights reserved. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 ; Conference date: 08-12-2019 Through 14-12-2019",

year = "2019",

language = "English (US)",

volume = "32",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

}

TY - JOUR

T1 - Thresholding bandit with optimal aggregate regret

AU - Tao, Chao

AU - Blanco, Saúl A.

AU - Peng, Jian

AU - Zhou, Yuan

PY - 2019

Y1 - 2019

N2 - We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold ?, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.

AB - We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold ?, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.

UR - http://www.scopus.com/inward/record.url?scp=85090176057&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85090176057&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85090176057

VL - 32

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

SN - 1049-5258

T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019

Y2 - 8 December 2019 through 14 December 2019

ER -