Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality
This addresses a specific problem in power system security analysis with incremental algorithmic improvements.
The paper tackles the optimal discovery problem with probabilistic expert advice, which originates from power system security analysis, by proposing an algorithm based on the optimistic paradigm and Good-Turing estimator. It proves regret bounds under weak assumptions and macroscopic optimality under stricter hypotheses, with numerical experiments validating the theoretical results.
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.