Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling
This addresses a fundamental sub-task in AI planning and reinforcement learning, offering a novel solution with theoretical optimality and practical improvements, though it is incremental in refining existing sampling strategies.
The paper tackles the problem of sequentially testing whether the minimum mean among a set of distributions exceeds a threshold, a key task in planning and reinforcement learning, and introduces Murphy Sampling, which is proven optimal for both low and high true minima and outperforms existing methods in experiments.
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.