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

arXiv: https://arxiv.org/abs/1806.00973 · HTML: https://mlsanity.com/paper/1806.00973/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2018.

## Built on by (most cited first, 14 of 14)

- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [An Anytime Algorithm for Good Arm Identification](https://mlsanity.com/paper/2310.10359/) (2023)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits](https://mlsanity.com/paper/2110.09133/) (2021)
- [Testing the Feasibility of Linear Programs with Bandit Feedback](https://mlsanity.com/paper/2406.15648/) (2024)
- [The Batch Complexity of Bandit Pure Exploration](https://mlsanity.com/paper/2502.01425/) (2025)
- [Choosing Answers in varepsilon-Best-Answer Identification for Linear Bandits](https://mlsanity.com/paper/2206.04456/) (2022)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Near Optimal Non-asymptotic Sample Complexity of 1-Identification](https://mlsanity.com/paper/2506.06978/) (2025)
- [Constrained Best Arm Identification with Tests for Feasibility](https://mlsanity.com/paper/2511.09808/) (2025)
- [Gaussian Process Classification Bandits](https://mlsanity.com/paper/2212.13157/) (2022)
- [An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem](https://mlsanity.com/paper/2302.02033/) (2023)

## Abstract (arXiv)

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.