Minimax and Bayes Optimal Best-Arm Identification

Two criteria, usually two strategies

A fixed-budget experiment can be judged in two ways. Minimax optimality asks how a strategy performs against the worst instance it could face; Bayes optimality asks how it performs on average against a prior. These criteria normally push a design in different directions, and the experimenter is asked to pick one in advance.

This paper shows that the choice is unnecessary: one strategy attains both, asymptotically.

The strategy

The procedure has a sampling phase followed by a recommendation phase, and the sampling phase itself has two stages:

1. Pilot stage. Allocate samples uniformly across arms in order to eliminate clearly suboptimal arms and to estimate the outcome variances.
2. Main stage. Solve a Gaussian minimax game, which yields both a sampling policy and a decision rule, and allocate the remaining budget according to that policy.

The recommendation phase then applies the decision rule obtained from the game.

Guarantees

• The strategy is simultaneously asymptotically minimax optimal and Bayes optimal for the simple regret.
• The upper bounds coincide exactly with the lower bounds, including the constant terms.
• The lower bounds hold against every adaptive experiment and for every fixed number of arms.
• The strategy attains them without knowing the outcome distributions or the prior.