Skip to yearly menu bar Skip to main content


Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

Shintaro Nakamura · Masashi Sugiyama

MR1 & MR2 - Number 102
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT


We study the real-valued combinatorial pure exploration of the multi-armed bandit in the fixed-budget setting. We first introduce an algorithm named 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.

Live content is unavailable. Log in and register to view live content