An Optimal Algorithm for the Stochastic Bandits with Knowing Near-optimal Mean Reward

摘要

This paper studies a variation of stochastic multi-armed bandit (MAB) problem where the agent knows a prior knowledge named Near-optimal Mean Reward (NoMR). We show that the cumulative regret of this bandit variation has a lower bound of Ω(1/Δ), where Δ is the gap between the optimal and the second optimal mean reward. An algorithm called NOMR-BANDIT is proposed to this variation, and we demonstrate that the cumulative regret of NoMR-BANDIT has a uniform upper bound of O(Δ). It is concluded that NOMR-BANDIT is optimal in terms of the order of regret bounds.