[en] 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.
Disciplines :
Computer science
Author, co-author :
Bubeck, Sébastien
Ernst, Damien ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Smart grids
Garivier, Aurélien
Language :
English
Title :
Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality
Publication date :
February 2013
Journal title :
Journal of Machine Learning Research
ISSN :
1532-4435
eISSN :
1533-7928
Publisher :
Microtome Publishing, Brookline, United States - Massachusetts
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235-256, 2002. (Pubitemid 34126111)
S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
F. Fonteneau-Belmudes. Identification of Dangerous Contingencies for Large Scale Power System Security Assessment. PhD thesis, University of Liège, 2012.
F. Fonteneau-Belmudes, D. Ernst, C. Druet, P. Panciatici, and L. Wehenkel. Consequence driven decomposition of large-scale power system security analysis. In Proceedings of the 2010 IREP Symposium - Bulk Power Systems Dynamics and Control - VIII, Buzios, Rio de Janeiro, Brazil, August 2010.
W. A. Gale and G. Sampson. Good-turing frequency estimation without tears. Journal of Quantitative Linguistics, 2(3):217-237, 1995.
A. Garivier and O. Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24rd Annual International Conference on Learning Theory, 2011.
I. J. Good. The population frequencies of species and the estimation of population parameters. Biometrika, 40:237-264, 1953. ISSN 0006-3444.
D. McAllester and L. Ortiz. Concentration inequalities for the missing mass and for histogram rule error. J. Mach. Learn. Res., 4:895-911, December 2003. ISSN 1532-4435.
D. A. McAllester and R. E. Schapire. On the convergence rate of Good-Turing estimators. In COLT, pages 1-6, 2000.
C. McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 148-188. Cambridge Univ. Press, Cambridge, 1989.
A. Orlitsky, N. P. Santhanam, and J. Zhang. Always good Turing: Asymptotically optimal probability estimation. In FOCS'03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 179+, Washington, DC, USA. IEEE Computer Society. ISBN 0-7695-2040-5.
