Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality

Sébastien Bubeck, Damien Ernst, Aurélien Garivier

Introduction

In many high-stakes domains, such as power grid management or cybersecurity, the objective is not simply to maximize a cumulative reward, but to discover as many unique "interesting" or critical items as possible within a limited timeframe. For a power grid operator, this might mean identifying rare equipment failures (contingencies) that could lead to a blackout. Given the vast number of possible scenarios, exhaustive simulation is impossible. Instead, operators rely on "experts"—various heuristic models or algorithms—to suggest potential failures.

This paper formalizes this challenge as the optimal discovery problem and introduces Good-UCB, a novel algorithm that combines classical statistical estimation with the multi-armed bandit framework to achieve near-optimal discovery rates.

The Optimal Discovery Problem

The optimal discovery problem differs fundamentally from the standard Multi-Armed Bandit (MAB) problem. In a standard MAB, the goal is to maximize the sum of rewards; a missed opportunity is a reward lost forever. In discovery, the goal is to maximize the count of unique items found. This introduces the restoring property: if an algorithm fails to select the best expert at a given step, the "interesting" items that expert could have revealed remain in the pool, waiting to be discovered later. Consequently, a sub-optimal choice results in a time delay rather than a permanent loss of potential reward.

Methodology: The Good-UCB Algorithm

The authors propose Good-UCB, which integrates two distinct statistical paradigms:

  1. Good-Turing Estimator: Originally developed by Alan Turing and I.J. Good for cryptanalysis, this estimator calculates the "missing mass"—the total probability of all outcomes in a distribution that have not yet been observed. In this context, it estimates the likelihood that the next sample from a specific expert will yield a previously unseen interesting item.
  2. Upper Confidence Bound (UCB): To manage the exploration-exploitation trade-off, the algorithm does not rely solely on the Good-Turing estimate. It adds a confidence bonus to the estimate, allowing it to account for uncertainty and occasionally sample experts that have been less explored.

At each discrete time step, Good-UCB queries the expert with the highest calculated UCB for its missing mass of interesting items.

Theoretical Contributions

The paper provides a rigorous mathematical foundation for the algorithm's performance:

  • Finite-Time Regret: The authors prove a regret bound of $O(\sqrt{Kt \log t})$, where $K$ is the number of experts and $t$ is time. This establishes a theoretical performance floor comparable to standard bandit algorithms.
  • Macroscopic Optimality: A key contribution is the proof that as the total number of items (the "haystack") grows toward infinity, Good-UCB’s performance converges to that of an Omniscient Oracle—a theoretical benchmark that possesses perfect knowledge of all underlying distributions.
  • Waiting Time Analysis: The research includes a non-linear regret bound, demonstrating that the time required for Good-UCB to reach a specific discovery threshold is asymptotically close to the theoretical minimum.

Experimental Evaluation

Since standard public datasets for this specific problem are scarce, the authors utilized complex numerical simulations to validate Good-UCB:

  • 7-Expert Setting: A synthetic environment where experts have varying success rates (from 51.2% down to 0.8%). Good-UCB significantly outperformed uniform sampling, narrowing the gap with the Oracle as the number of items increased.
  • Geometric Experts: To test robustness, the authors designed a setup where experts draw from geometric distributions and "interesting items" are defined as prime numbers. This setup deliberately violates the "non-intersecting supports" assumption (the idea that experts don't share items) used in the formal proofs. Despite this violation, Good-UCB remained highly effective, demonstrating its practical utility in overlapping domains.

Conclusion and Future Work

Good-UCB represents a significant step forward in active discovery problems. By leveraging the restoring property and the Good-Turing estimator, it provides a strategy that is both theoretically sound and practically robust. While the current proofs rely on non-overlapping expert supports, empirical results suggest the algorithm is broader in application. Future research may focus on formalizing proofs for overlapping supports and deploying the algorithm in real-world power system contingency analysis or large-scale web content discovery.

Summary updated

BibTeX
@article{bubeck2013optimal,
  author = {Sébastien Bubeck and Damien Ernst and Aurélien Garivier},
  title = {{Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality}},
  journal = {J. Mach. Learn. Res.},
  year = {2013},
}
Figure