Dominant Arm Identification with Mixing and Recycling Observed Samples

In many real-world scenarios—such as real-time bidding, algorithm selection, or consumer choice—the goal is not to maximize the expected cumulative reward, but to identify the option that most frequently produces the single highest realized outcome in a given round. Traditional multi-armed bandit algorithms often focus on mean rewards or pairwise comparisons, which can fail to capture the nuances of crossing cumulative distribution functions (CDFs) or heterogeneous tail behaviors. This paper addresses the challenge of identifying the "dominant arm" that maximizes the probability of outperforming all other arms simultaneously.

The authors propose a new "dominance score" based on local distributional dominance. Instead of requiring one arm to be globally superior, the reward space is partitioned into regions where different arms are locally dominant. The dominance score aggregates the performance of an arm relative to these locally dominant benchmarks. To estimate this efficiently, the authors introduce a joint mixing and recycling mechanism. This approach uses auxiliary models to impute missing reward information for unselected arms, combined with a doubly robust estimator to ensure simultaneous convergence of the empirical distribution functions for all arms, even when individual arms are sampled infrequently.

The study demonstrates that the proposed Doubly Robust Dominance Score Elimination (DRDSE) algorithm correctly identifies the best dominant arm with a sample complexity that matches the theoretical lower bound up to logarithmic factors. Numerical experiments confirm that the DRDSE algorithm consistently outperforms existing baselines, particularly in settings with diverse reward distributions (e.g., Bernoulli, Gaussian, and Pareto) where mean-based methods are insufficient. The recycling mechanism allows the learner to gain information about all arms at every round, significantly reducing the error for unselected arms compared to standard empirical estimators.