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

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

TL;DR

This paper introduces Good-UCB, a novel algorithm for the "optimal discovery problem," where the goal is to find as many unique "interesting" items as possible by querying a set of probabilistic experts. By combining the classic Good-Turing missing mass estimator with the optimistic Upper Confidence Bound (UCB) framework, the authors provide a strategy that is proven to be macroscopically optimal and significantly outperforms uniform sampling in both theory and simulation.

What Problem Does This Paper Address?

Imagine you are a power grid operator. There are hundreds of thousands of possible "contingencies" (equipment failures) that could happen, but only a tiny fraction are truly dangerous. You don't have the time or computing power to simulate every single one. Instead, you have several different "experts"—heuristic models or algorithms—that can suggest which contingencies to check. Each expert has a different, unknown probability of pointing you toward a dangerous event you haven't seen yet.

The authors formalize this as the optimal discovery problem. Unlike the standard Multi-Armed Bandit (MAB) problem, where you want to maximize the sum of rewards, here you want to maximize the count of unique interesting items discovered. This introduces a unique "restoring property": if you make a sub-optimal choice now, the interesting items you missed aren't gone forever; they just wait to be discovered later. The challenge is to figure out which expert is currently most likely to yield a new discovery.

Methods

The authors propose the Good-UCB algorithm, which merges two powerful statistical ideas:

  1. Good-Turing Estimator: Developed by Alan Turing and I.J. Good during WWII to crack Enigma codes, this technique estimates the "missing mass"—the total probability of all outcomes that have not yet appeared in a sample. In this paper, it is adapted to estimate the probability that the next sample from an expert will be a new interesting item.
  2. Optimistic Paradigm (UCB): To handle the trade-off between sticking with a known good expert (exploitation) and trying others (exploration), the algorithm calculates an Upper Confidence Bound. It doesn't just use the estimated missing mass; it adds a "confidence bonus" to account for uncertainty.

The algorithm works sequentially: at each step, it queries the expert with the highest UCB for its missing mass of interesting items.

Datasets

The paper does not use standard public datasets. Instead, it evaluates the algorithm through numerical simulations designed to mimic the properties of the power system security problem:

  • 7-Expert Setting: A synthetic environment where experts have varying proportions of interesting items (ranging from 51.2% down to 0.8%).
  • Geometric Experts: A more challenging setup where experts draw from geometric distributions and the "interesting items" are prime numbers. This test specifically violates the "non-intersecting supports" assumption used in the mathematical proofs to see how robust the algorithm is in practice.

Key Insights and Ideas

  • The Restoring Property: This is the "aha moment" of the paper. In traditional reinforcement learning, a mistake costs you reward that is lost forever. In discovery, a mistake only costs you time. If an expert has a high probability of finding something new, that probability stays high (or even increases relatively) until you actually find those items. This makes the regret (the performance gap between the algorithm and an oracle) behave very differently than in standard bandits.
  • Macroscopic Optimality: The authors show that as the "haystack" (the set of items) grows to infinity, Good-UCB's performance converges to that of an "Omniscient Oracle" that knows the underlying distributions.
  • Good-Turing for Discovery: While Good-Turing is a staple of linguistics and ecology, applying it to an active selection problem (choosing which distribution to sample) with UCB is a novel and effective bridge between estimation and control.

Key Results

  • Finite-Time Regret: The authors prove a regret bound of $O(\sqrt{Kt \log t})$, which is standard for bandit-style problems but provides a solid theoretical floor for performance.
  • Waiting Time Analysis: They provide a "non-linear" regret bound showing that the time Good-UCB takes to reach a certain discovery threshold is very close to the theoretical minimum.
  • Superiority over Uniform Sampling: In simulations, Good-UCB significantly outperforms the naive strategy of querying experts in a round-robin fashion. For example, as the number of items $N$ increases, the gap between Good-UCB and uniform sampling grows, while the gap between Good-UCB and the Oracle narrows.
  • Robustness: Even when the mathematical assumptions (like experts having non-overlapping sets of items) are violated, the algorithm remains highly effective.

Limitations and Future Work

  • Non-Intersecting Supports: Much of the rigorous proof relies on the assumption that different experts don't "share" the same interesting items. While simulations show the algorithm works even when they do, a formal proof for the "overlapping" case remains a theoretical challenge.
  • Parameter Tuning: The confidence constant $C$ in the UCB formula is derived from conservative concentration inequalities. The authors note that in practice, smaller values of $C$ often perform better, suggesting that tighter theoretical bounds might be possible.
  • Real-World Deployment: While motivated by power systems, the paper stops at synthetic simulations. Future work could involve testing this on actual power system contingency data or web-based 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