# Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

arXiv: https://arxiv.org/abs/2308.10238 · HTML: https://mlsanity.com/paper/2308.10238/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 20 Aug 2023.

## Builds on (most cited first, 8 of 8)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [Pure Exploration of Multi-armed Bandit Under Matroid Constraints](https://mlsanity.com/paper/1605.07162/) (2016)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Thompson Sampling for (Combinatorial) Pure Exploration](https://mlsanity.com/paper/2206.09150/) (2022)
- [A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2306.09202/) (2023)

## Built on by (most cited first, 2 of 2)

- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2310.15681/) (2023)

## Abstract (arXiv)

We study the real-valued combinatorial pure exploration of the multi-armed bandit (R-CPE-MAB) problem. In R-CPE-MAB, a player is given d stochastic arms, and the reward of each arm s∈1, ldots, d follows an unknown distribution with mean μs. In each time step, a player pulls a single arm and observes its reward. The player's goal is to identify the optimal action boldsymbolπ* = argmax_boldsymbolπ ∈ A boldsymbolμtopboldsymbolπ from a finite-sized real-valued action set Asubset ℝd with as few arm pulls as possible. Previous methods in the R-CPE-MAB assume that the size of the action set A is polynomial in d. We introduce an algorithm named the Generalized Thompson Sampling Explore (GenTS-Explore) algorithm, which is the first algorithm that can work even when the size of the action set is exponentially large in d. We also introduce a novel problem-dependent sample complexity lower bound of the R-CPE-MAB problem, and show that the GenTS-Explore algorithm achieves the optimal sample complexity up to a problem-dependent constant factor.