Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback

Combinatorial bandits with semi-bandit feedback generalize multi-armed\nbandits, where the agent chooses sets of arms and observes a noisy reward for\neach arm contained in the chosen set. The action set satisfies a given\nstructure such as forming a base of a matroid or a path in a graph. We focus on\nthe pure-exploration problem of identifying the best arm with fixed confidence,\nas well as a more general setting, where the structure of the answer set\ndiffers from the one of the action set. Using the recently popularized game\nframework, we interpret this problem as a sequential zero-sum game and develop\na CombGame meta-algorithm whose instances are asymptotically optimal algorithms\nwith finite time guarantees. In addition to comparing two families of learners\nto instantiate our meta-algorithm, the main contribution of our work is a\nspecific oracle efficient instance for best-arm identification with\ncombinatorial actions. Based on a projection-free online learning algorithm for\nconvex polytopes, it is the first computationally efficient algorithm which is\nasymptotically optimal and has competitive empirical performance.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC