We investigate pure exploration K-armed bandit problems in the fixed confidence setting, specifically addressing a class of problems we term monotone bandits. In monotone bandits, the expected reward \(\mu _i\) of arm i satisfies the monotonicity constraint \(\mu _1\le \mu _2\le \cdots \le \mu _K\) . While existing Track-and-Stop strategies achieve asymptotically optimal sample complexity by tracking the optimal arm-draw proportion estimated from current sample means and incorporating exploration to escape suboptimal answers, we propose a fundamentally different approach. Our novel algorithm for monotone bandits eschews tracking the optimal arm-draw proportion in favor of a simpler strategy: selecting the least-drawn arm among those with non-zero optimal arm-draw proportions. We use a maximum likelihood estimator (MLE) under the monotonicity constraint, which differs from the sample mean in this setting, to identify arms with non-zero optimal arm-draw proportions. Our algorithm integrates this MLE-based sampling rule with an appropriate arm-elimination strategy and stopping criterion, achieving computational efficiency while maintaining asymptotically optimal sample complexity with respect to the reciprocal of the confidence level, notably without requiring exploration to escape suboptimal answers. Numerical experiments demonstrate that our algorithm’s empirical sample complexity is superior to that of established Track-and-Stop algorithms that employ forced exploration.
