Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling

By Emilie Kaufmann, Wouter M. Koolen, Aurélien Garivier. 2018

28 citations recorded by the source corpus.

Learning the minimum/maximum mean among a finite set of distributions is a fundamental sub-task in planning, game tree search and reinforcement learning. We formalize this learning task as the problem of sequentially testing how the minimum mean among a finite set of distributions compares to a given threshold. We develop refined non-asymptotic lower bounds, which show that optimality mandates very different sampling behavior for a low vs high true minimum. We show that Thompson Sampling and the intuitive Lower Confidence Bounds policy each nail only one of these cases. We develop a novel approach that we call Murphy Sampling. Even though it entertains exclusively low true minima, we prove that MS is optimal for both possibilities. We then design advanced self-normalized deviation inequalities, fueling more aggressive stopping rules. We complement our theoretical guarantees by experiments showing that MS works best in practice.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Controlling Overestimation Bias with Truncated Mixture of Continuous Distributional Quantile Critics (2020, background): “The problem of overestimation has also been discussed in the context of optimal stopping and sequential testing (Kaufmann et al., 2018).”