  We study the real-valued combinatorial pure exploration of the multi-armed
bandit in the fixed-budget setting. We first introduce the Combinatorial
Successive Asign (CSA) algorithm, which is the first algorithm that can
identify the best action even when the size of the action class is
exponentially large with respect to the number of arms. We show that the upper
bound of the probability of error of the CSA algorithm matches a lower bound up
to a logarithmic factor in the exponent. Then, we introduce another algorithm
named the Minimax Combinatorial Successive Accepts and Rejects
(Minimax-CombSAR) algorithm for the case where the size of the action class is
polynomial, and show that it is optimal, which matches a lower bound. Finally,
we experimentally compare the algorithms with previous methods and show that
our algorithm performs better.
