Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
This addresses the challenge of efficiently identifying optimal combinatorial actions in bandit problems with limited samples, which is incremental but provides optimality guarantees.
The paper tackles the real-valued combinatorial pure exploration problem in multi-armed bandits under fixed budgets, introducing two algorithms: CSA for exponentially large action classes and Minimax-CombSAR for polynomial-sized ones, with both proven to match theoretical lower bounds and outperform previous methods in experiments.
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.