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

Area of Science:

• Machine Learning
• Reinforcement Learning
• Optimization Algorithms

Background:

• Traditional multiarmed bandit (MAB) problems lack prior knowledge of the optimal mean reward.
• Practical applications, such as web advertising, often allow for estimation of a near-optimal mean reward (NoMR).
• Integrating NoMR can significantly enhance MAB algorithm performance.

Purpose of the Study:

• To formalize the stochastic MAB problem with known NoMR.
• To analyze the theoretical performance bounds (regret) of such problems.
• To develop and evaluate novel algorithms for MAB with NoMR.

Main Methods:

• Formalization of the MAB problem incorporating NoMR.
• Analysis of cumulative regret, establishing a lower bound of Ω(1/∆).
• Development of the NoMR-BANDIT algorithm utilizing NoMR for efficient exploration.
• Proposal of CASCADE-BANDIT for enhanced generalization when NoMR is below the suboptimal reward.

Main Results:

• The NoMR-BANDIT algorithm achieves a uniform regret upper bound of O(1/∆), matching the theoretical lower bound.
• CASCADE-BANDIT demonstrates a regret upper bound of O(∆logn), comparable to conventional MAB methods.
• Experimental results show NoMR-BANDIT reduces cumulative regret by 10%-80% compared to state-of-the-art algorithms.

Conclusions:

• NoMR-BANDIT is an optimal algorithm for MAB problems with known NoMR.
• The integration of NoMR provides significant performance improvements in MAB.
• The proposed algorithms offer efficient solutions for practical MAB applications with prior knowledge.