Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
algorithmic efficiencyasymptotically optimal algorithmscomputationally tractable algorithmdecision theoryexpected reward functionexploration-exploitation trade-offgraves-lai optimization problemi.i.d. rewardsmodesmultimodaloptimization problemperformance boundsreward structurestatistical learning theorystochastic multi-armed bandit
We consider a stochastic multi-armed bandit problem with i.i.d. rewards where the expected reward function is multimodal with at most $m$ modes. We propose the first known computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem.