Missing Mass and Optimal Discovery

# 153


We tackle a novel problem arising in the context of security analysis in power systems, which we refer to as 'optimal discovery with probabilistic expert advice.' To address this challenge, we propose an algorithm that leverages the optimistic paradigm and utilizes the Good-Turing missing mass estimator. Through rigorous analysis, we establish two distinct regret bounds to evaluate the performance of this algorithm, imposing only weak assumptions on the probabilistic experts. Furthermore, by imposing more stringent assumptions, we demonstrate a macroscopic optimality result by comparing the algorithm against both an oracle strategy and uniform sampling. To support our theoretical findings, we supplement our study with numerical experiments, which provide concrete illustrations of the algorithm's performance and its alignment with the established theoretical framework.

Prof. Aurélien Garivier, Ecole Normale Supérieure de Lyon, France

Aurélien Garivier, a Professor at Ecole Normale Supérieure de Lyon in France, works in the realm of stochastic and statistical modeling, approaching the subject from diverse perspectives. With a Ph.D. in Information Theory, his research has primarily focused on Machine Learning, with a particular emphasis on reinforcement learning. Garivier's most influential contributions pertain to the field of bandit models. His research interests extend beyond this domain and encompass Markov models, perfect simulation, and the optimization of stochastic functions, among others. Notably, he has recently delved into the areas of differential privacy and risk-aware reinforcement learning.