Best Arm Identification with Fixed Budget: A Large Deviation Perspective

arXiv:2312.12137v2 Announce Type: replace
Abstract: We consider the problem of identifying the best arm in stochastic Multi-Armed Bandits (MABs) using a fixed sampling budget. Characterizing the minimal instance-specific error probability for this problem constitutes one of the important remaining open problems in MABs. When arms are selected using a static sampling strategy, the error probability decays exponentially with the number of samples at a rate that can be explicitly derived via Large Deviation techniques. Analyzing the performance of algorithms with …

abstract arm arxiv budget cs.lg deviation error identification instance multi-armed bandits perspective probability sampling stat.ml stochastic type