Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/172702
DC FieldValue
dc.titleBest Arm Identification for Cascading Bandits in the Fixed Confidence Setting
dc.contributor.authorZhong, Zixin
dc.contributor.authorCHEUNG WANG CHI
dc.contributor.authorTan, Vincent VF
dc.date.accessioned2020-08-14T09:20:10Z
dc.date.available2020-08-14T09:20:10Z
dc.date.issued2020-08-14
dc.identifier.citationZhong, Zixin, CHEUNG WANG CHI, Tan, Vincent VF (2020-08-14). Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting. International Conference on Machine Learning. ScholarBank@NUS Repository.
dc.identifier.urihttps://scholarbank.nus.edu.sg/handle/10635/172702
dc.description.abstractWe design and analyze CASCADEBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CASCADEBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.’s) which we term asleft-sidedsub-Gaussianr.v.’s;theseclassisarelaxed version of sub-Gaussian r.v.’s. This enables the application of a sufficiently tight Bernsteintype concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CASCADEBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CASCADEBAI as well as the tightness of our upper bound on its time complexity.
dc.sourceElements
dc.typeConference Paper
dc.date.updated2020-08-13T15:46:22Z
dc.contributor.departmentINDUSTRIAL SYSTEMS ENGINEERING AND MANAGEMENT
dc.description.sourcetitleInternational Conference on Machine Learning
dc.description.placeUnited States
dc.published.stateUnpublished
Appears in Collections:Staff Publications
Elements

Show simple item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
conf_cascadeBAI_icml_v13.pdfAccepted version1.78 MBAdobe PDF

OPEN

Post-printView/Download

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.