Best of both worlds: Stochastic & adversarial best-arm identification
The study investigates designing an algorithm to optimally identify the best arm in both random (stochastic) and malicious (adversarial) reward scenarios without knowing the reward structure. The ProbabilityONE learner achieves near-optimal error rates in both settings simultaneously, proving that a single learner can perform well across these challenging environments up to logarithmic factors.