A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of the Multi-Armed Bandit

Area of Science:

• Machine Learning
• Optimization
• Reinforcement Learning

Background:

• The real-valued combinatorial pure exploration problem (R-CPE-MAB) is a key challenge in stochastic multi-armed bandit settings.
• Existing methods struggle with large action sets, which are common in practical applications.

Purpose of the Study:

• To develop an efficient algorithm for the R-CPE-MAB problem with polynomial action set sizes.
• To establish theoretical performance guarantees for the proposed algorithm.
• To demonstrate the practical superiority of the new algorithm over existing methods.

Main Methods:

• Introducing the Combinatorial Gap-based Exploration (CombGapE) algorithm.
• Analyzing the sample complexity of CombGapE, showing it matches the theoretical lower bound.
• Conducting numerical experiments on synthetic and real-world datasets.

Main Results:

• The CombGapE algorithm achieves an upper bound on sample complexity that matches the lower bound, up to a constant factor.
• Numerical results demonstrate significant performance improvements of CombGapE compared to existing algorithms.
• The algorithm's effectiveness is validated on both simulated and real-world data.

Conclusions:

• CombGapE offers a theoretically grounded and practically effective solution for the R-CPE-MAB problem.
• The algorithm provides a significant advancement in the field of stochastic multi-armed bandits, particularly for problems with large action sets.