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: