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.