# Combinatorial Multi-armed Bandits: Arm Selection via Group Testing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 38 references that are in the map.
- First posted on arXiv 14 Oct 2024.

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

- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping](https://mlsanity.com/paper/2006.14084/) (2020)
- [A (simple) classical algorithm for estimating Betti numbers](https://mlsanity.com/paper/2211.09618/) (2022)

## Abstract (arXiv)

This paper considers the problem of combinatorial multi-armed bandits with semi-bandit feedback and a cardinality constraint on the super-arm size. Existing algorithms for solving this problem typically involve two key sub-routines: (1) a parameter estimation routine that sequentially estimates a set of base-arm parameters, and (2) a super-arm selection policy for selecting a subset of base arms deemed optimal based on these parameters. State-of-the-art algorithms assume access to an exact oracle for super-arm selection with unbounded computational power. At each instance, this oracle evaluates a list of score functions, the number of which grows as low as linearly and as high as exponentially with the number of arms. This can be prohibitive in the regime of a large number of arms. This paper introduces a novel realistic alternative to the perfect oracle. This algorithm uses a combination of group-testing for selecting the super arms and quantized Thompson sampling for parameter estimation. Under a general separability assumption on the reward function, the proposed algorithm reduces the complexity of the super-arm-selection oracle to be logarithmic in the number of base arms while achieving the same regret order as the state-of-the-art algorithms that use exact oracles. This translates to at least an exponential reduction in complexity compared to the oracle-based approaches.