Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling
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.
This paper considers a variant of the pure exploration multi-armed bandit problem, where we are given a threshold gamma and we wish to identify whether the minimum mean among the arms is larger or smaller than gamma.  An algorithm is designed that identifies the correct hypothesis with probability at least 1-delta.  Lower bounds on expected sample size are also provided, and the algorithm's expected sample size is shown to match (exactly, not up to constants) asymptotically in the limit as delta goes to 0.  The paper assumes that the sampling distributions are independent and from a known exponential family.  I'm positive on this paper.  It contains a thorough analysis and a novel algorithm with strong results for this problem. One could object to the strength of the parametric sampling assumption, but this is offset by the precision of the analysis, and I find the assumptions to be fine.  There is an older literature on something called "multiple comparisons with a standard" and "multiple comparisons with the best".  In this problem, we have a collection of arms, typically with independent sampling distributions in exponential families, and we wish to make statistically valid statements about the difference between each arm's mean and either some known value (gamma) or the best arm.  In particular, here is a quote from the abstract of Kim and Nelson (2005): "The goal is to find systems whose expected performance measures are larger or smaller than a single system referred to as a standard and, if there is any, to find the one with the largest or smallest performance.  Our procedures allow.. known or unknown expected performance of the standard."  So it seems that this literature is very close to the problem considered here, but not identical.  While Kim and Nelson seem to do hypothesis testing of mu^* > gamma, the paper seems different because their procedure does additional statistical inference.  The paper would better serve to teach the ML community about older relevant literature if it reviewed the most relevant of this literature.  A survey into the literature is Goldsman and Nelson (1998).  Goldsman, D., and B. L. Nelson. 1998. Comparing Systems via Simulation. In Handbook of simulation: Principles, Methodology, Advances, Applications, and Practice, ed. J. Banks, 273–306. New York: John Wiley & Sons.  Kim, Seong-Hee. "Comparison with a standard via fully sequential procedures." ACM Transactions on Modeling and Computer Simulation (TOMACS) 15.2 (2005): 155-174.  Another criticism is that the problem considered seems unusual.  Are there applicatios where I would want to know whether mu* > gamma, but I wouldn't also want to know the identity of the best arm?  Overall, I found the paper very clear, and the analysis novel and of high quality.  Significance is affected by the applicability of the problem considered.  Here are a few typos and small comments:  - Are conditions needed on the prior?  I don't see any stated, but at the bare minimum it seems that we need the prior to have support on both H_> and H_ gamma, but I wouldn't also want to know the identity of the best arm?"  In the Monte Carlo Tree Search application, the paper unfortunately doesn't provide enough details given my background to evaluate whether the problem formulation really does have direct applicability to MCTS.  I agree that in spirit it is close, but after skimming the given reference [33] I wonder:  - in 33, pruning (Algorithm 3) is done by comparing the estimated min/max value of a particular child node against the root.  There is error in estimating the min/max value of the root while applying the method in this paper would treat it as a constant (gamma). - in 33, samples of a child nodes value don't seem to come iid, but instead are biased through hierarchical estimation: the value of node u is estimated as the min/max value of its child nodes.  Even if the estimates of the values of the leaf nodes are unbiased, it seems that estimates will be biased higher in the tree. - in MCTS, if I sample 1 child node u, then that can improve the estimates for another node v at the same level because it can help estimate the value of nodes at lower levels shared by these nodes u and v. - is the measure of correctness used really the most appropriate thing for MCTS?  The number of nodes tested is extremely large in MCTS, and it seems that the sample complexity required to make every decision correctly with reasonable probability would just be too large.  Instead, it seems like one would expect some errors, and one would wish that the size of the errors wouldn't be too large most of the time.  This would seem to suggest an error measure that put more weight on incorrect conclusions for arms with large gaps between the value and gamma.  In the quality control applications, there is also room for improving the clarity of the application context.  For example: - regarding the e-learning application, we typically grade students by estimating their average performance across a range of subjects rather than their minimum.  Are there existing e-learning settings where performance is certified in this way?  - when certifying a batch of machines has a minimum probability of successfully producing a widget, I'd feel better if I had more detail about a situation where one would want to do this.  Does this arise for regulatory reasons?  If a plant owner were doing this, and found that the minimum probability fell below a threshold, then she would probably want to know which machine was causing the problem so that she could fix / replace it.  If it is for regulatory reasons, why do they care about the worst machine instead of caring about the fraction of the widgets (produced by all the machines) that have quality below a threshold?  Is the proposed loss function the best one? - unfortunately I do not understand the anomaly detection setting on line 38. - In crowdsourcing, when establishing the quality of workers, what would I do if I found out that a cohort contained a careless one?  Would I simply go get a new cohort?  Would I have some other non-crowd workers do the task I originally planned for the crowd?  It seems like an approach that is more efficient than each of these would be to try to figure out which one(s) were careless and ignore their work.  At the same time, I feel that the motivating quality control applications are nearly on par in terms of actual applicability with many other theoretical bandit papers published in the past at NIPS.  (For example, the assumption of each arm having iid rewards common in the stochastic bandits literature is routinely violated in applications.)  Finally, the Bernoulli argument is a good one in favor of the parametric assumption.