A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

Shintaro Nakamura, Masashi Sugiyama
6/15/2023
cs.LG

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

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. We introduce an algorithm named the combinatorial gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor. We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Complexity Analysis of a Countable-armed Bandit Problem

83% match2023

Pure Exploration in Bandits with Linear Constraints

82% match1 repo32023

Cost-Aware Optimal Pairwise Pure Exploration

82% match2025

Optimal Thresholding Linear Bandit

82% match2024

Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem

82% match2025

On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit

82% match2025

Cite this paper

@article{nakamura2023fast,
  title  = {A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit},
  author = {Shintaro Nakamura and Masashi Sugiyama},
  year   = {2023},
  eprint = {2306.09202},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.09202v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.09202.svg)](https://codeofpaper.com/paper/2306.09202)

Discussion