The Role of Contextual Information in Best Arm Identification
Journal of Machine Learning Research (JMLR).
- best-arm identification
- fixed confidence
- Track-and-Stop
- sample complexity
In one sentence. Covariates observed during the experiment reduce the number of samples needed to identify the arm with the best marginalized mean reward, and a context-aware Track-and-Stop attains the instance-specific lower bound.
Setting
Fixed-confidence best-arm identification with contextual information: a covariate is observed in each round and can be used when choosing which arm to draw, but the quantity of interest is the mean reward marginalized over the covariate distribution. The goal is to identify the best arm with as few samples as possible subject to a given error rate.
The interesting tension is that context is useful for sampling even though it does not appear in the target. Contexts differ in how informative they are about which arm is better, and an experimenter who can condition the allocation on the realized context can extract more information per sample.
Contributions
- Instance-specific sample complexity lower bounds for the problem.
- A context-aware version of the Track-and-Stop strategy, in which the proportion of arm draws tracks the set of optimal allocations.
- A proof that the expected number of arm draws matches the lower bound asymptotically.
- A comparison showing the improvement over the context-free result of Garivier & Kaufmann (2016), and experiments confirming faster identification.