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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 24 Oct 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [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)
- [Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations](https://mlsanity.com/paper/2106.06712/) (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)
- [Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2308.10238/) (2023)

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

- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)

## Abstract (arXiv)

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.