From the archives
Optimal Discovery with Probabilistic Expert Advice: Finite Time Analysis and Macroscopic Optimality
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: Journal of Machine Learning Research
Date: February, 2013
PageStart: 601
PageEnd: 623
Authors: Sébastien BubeckDamien ErnstAurélien Garivier
Abstract: We consider an original problem that arises from the issue of
security analysis of a power system and that we name optimal discovery with probabilistic
expert advice. We address it with an algorithm based on the optimistic paradigm and on the
Good-Turing missing mass estimator. We prove two different regret bounds on the performance
of this algorithm under weak assumptions on the probabilistic experts. Under more
restrictive hypotheses, we also prove a macroscopic optimality result, comparing the
algorithm both with an oracle strategy and with uniform sampling. Finally, we provide
numerical experiments illustrating these theoretical findings.
Direct link: free access on JMLR
Volume: 14
Keywords:
