  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. Existing methods in the R-CPE-MAB and transductive linear
bandits have a gap of problem-dependent constant terms and logarithmic terms
between the upper and lower bounds of the sample complexity, respectively. We
close these gaps by proposing an algorithm named the combinatorial gap-based
exploration (CombGapE) algorithm, whose sample complexity upper bound matches
the lower bound. Finally, we numerically show that the CombGapE algorithm
outperforms existing methods significantly.
