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

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

Abstract

Identifying whether the minimum mean of several unknown distributions falls below a specific threshold is a fundamental task in reinforcement learning, game-playing, and quality control. This paper introduces Murphy Sampling, a novel sequential testing strategy that achieves theoretical optimality by conditioning exploration on the "worst-case" scenario. By combining this approach with a new aggregate stopping rule, the authors provide a framework that outperforms traditional bandit algorithms across both possible hypotheses, ensuring efficiency regardless of the underlying truth.

Introduction

In many decision-making scenarios, such as Monte Carlo Tree Search (MCTS) or safety-critical quality control, the primary objective is not to find the best average performer, but to determine the value of the "worst-case" or "best-case" outcome. For instance, in a minimax game tree, the value of a state is defined by the minimum possible outcome over an opponent's potential moves.

This paper addresses a specific sequential testing problem: given $K$ distributions with unknown means $\mu_1, \dots, \mu_K$, and a threshold $\gamma$, we must decide between two hypotheses:

  • $H_<: \min_i \mu_i < \gamma$
  • $H_>: \min_i \mu_i > \gamma$

The goal is to reach a decision with a predefined confidence level $1-\delta$ while minimizing the number of samples taken.

The Challenge of Asymmetric Evidence

The fundamental difficulty in this problem lies in the asymmetry of the required evidence. The optimal sampling strategy shifts dramatically depending on which hypothesis is true:

  1. If $H_<$ is true: One only needs to find a single arm that is significantly below $\gamma$. An efficient algorithm should focus its samples on the most promising candidate for the minimum.
  2. If $H_>$ is true: One must prove that every single arm is above $\gamma$. This requires a broad, exhaustive exploration of all $K$ distributions.

Existing algorithms typically excel in only one of these regimes. Thompson Sampling (TS), which samples arms based on the probability they are the minimum, is highly efficient for $H_<$ but fails to explore sufficiently to prove $H_>$. Conversely, Lower Confidence Bound (LCB) methods are effective for $H_>$ but waste samples on suboptimal arms when $H_<$ is true. This "split personality" requirement makes it difficult for standard algorithms to remain optimal across all possible outcomes.

Murphy Sampling: Embracing the Worst Case

To bridge this gap, the authors propose Murphy Sampling (MS). The algorithm is a "pessimistic" adaptation of Thompson Sampling. While standard TS samples from the posterior distribution of the means, Murphy Sampling samples from the posterior conditioned on the event that the minimum is below the threshold ($\mu^* < \gamma$).

This conditioning is the "Murphy's Law" of the algorithm: it forces the sampler to act as if the threshold has been violated.

  • If $H_<$ is indeed true, MS behaves like TS and focuses on the minimum, quickly gathering evidence to confirm the hypothesis.
  • If $H_>$ is true, the conditioning forces the algorithm to repeatedly check every arm to see if it could be the one to violate the threshold. This ensures that enough evidence is gathered to eventually reject $H_<$ and accept $H_>$.

The Aggregate Stopping Rule

Beyond the sampling strategy, the authors introduce a novel Aggregate Stopping Rule. Traditional stopping rules often use a "box" approach, monitoring each arm's confidence interval independently. A decision is reached only when one arm is proven to be below $\gamma$ or all arms are proven to be above $\gamma$.

The Aggregate Stopping Rule instead uses self-normalized deviation inequalities to sum the evidence across multiple arms. This is particularly powerful for $H_<$: the test can stop if the collective evidence from several "low-looking" arms is strong enough to conclude that at least one must be below the threshold, even if no single arm has reached that level of certainty yet. This allows for significantly earlier termination in complex environments.

Results and Impact

The authors provide a rigorous theoretical analysis, proving that Murphy Sampling, when paired with their aggregate stopping rule, is asymptotically optimal. This means that as the error probability $\delta$ approaches zero, the sample complexity matches the mathematical lower bounds for the problem.

Empirical evaluations using Gaussian and Bernoulli bandits demonstrate that Murphy Sampling consistently matches or outperforms specialized one-sided algorithms. Key findings include:

  • Efficiency: MS avoids the "exploration waste" of LCB in $H_<$ scenarios.
  • Robustness: MS avoids the "exploration failure" of TS in $H_>$ scenarios.
  • Speed: The aggregate stopping rule significantly reduces sample counts when multiple arms are near or below the threshold, showing better scalability as the number of arms $K$ increases.

Conclusion

Murphy Sampling offers a robust, theoretically grounded solution to the sequential testing of minimum means. By conditioning exploration on the "worst-case" scenario, it balances the need for focused exploitation and exhaustive exploration. While the current work focuses on "flat" multi-armed bandits, the insights regarding evidence aggregation and pessimistic sampling provide a promising foundation for more complex structures, such as deep Monte Carlo Tree Search and hierarchical decision-making.

Summary updated

Abstract

Learning the minimum/maximum mean among a finite set of distributions is a fundamental sub-problem 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.
BibTeX
@inproceedings{kaufmann2018sequential,
  author = {Emilie Kaufmann and Wouter M. Koolen and Aurélien Garivier},
  title = {{Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BkNfd_-_bS},
}
Figure