A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
This provides an efficient solution for combinatorial decision-making problems in bandits, though it appears incremental as it builds on transductive linear bandit frameworks.
The paper tackles the real-valued combinatorial pure exploration problem in multi-armed bandits where the action set is polynomial in size, introducing the CombGapE algorithm whose sample complexity matches the theoretical lower bound up to a constant factor and outperforms existing methods in experiments.
We study the real-valued combinatorial pure exploration problem in the stochastic multi-armed bandit (R-CPE-MAB). We study the case where the size of the action set is polynomial with respect to the number of arms. In such a case, the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We introduce an algorithm named the combinatorial gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor. We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.