# Combinatorial Neural Bandits

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Online Clustering of Contextual Cascading Bandits](https://mlsanity.com/paper/1711.08594/) (2017)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)

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

- [Adaptive Batch-Wise Sample Scheduling for Direct Preference Optimization](https://mlsanity.com/paper/2506.17252/) (2025)
- [Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2405.20165/) (2024)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2506.01250/) (2025)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)
- [Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation](https://mlsanity.com/paper/2607.13686/) (2026)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)
- [Combinatorial Multi-armed Bandits: Arm Selection via Group Testing](https://mlsanity.com/paper/2410.10679/) (2024)
- [Clutch Control: An Attention-based Combinatorial Bandit for Efficient Mutation in JavaScript Engine Fuzzing](https://mlsanity.com/paper/2510.12732/) (2025)
- [Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities](https://mlsanity.com/paper/2601.06913/) (2026)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)
- [Diversified Multinomial Logit Contextual Bandits](https://mlsanity.com/paper/2607.11684/) (2026)

## Abstract (arXiv)

We consider a contextual combinatorial bandit problem where in each round a learning agent selects a subset of arms and receives feedback on the selected arms according to their scores. The score of an arm is an unknown function of the arm's feature. Approximating this unknown score function with deep neural networks, we propose algorithms: Combinatorial Neural UCB (textttCN-UCB) and Combinatorial Neural Thompson Sampling (textttCN-TS). We prove that textttCN-UCB achieves tildeO(tilded √T) or tildeO(√tilded T K) regret, where tilded is the effective dimension of a neural tangent kernel matrix, K is the size of a subset of arms, and T is the time horizon. For textttCN-TS, we adapt an optimistic sampling technique to ensure the optimism of the sampled combinatorial action, achieving a worst-case (frequentist) regret of tildeO(tilded √TK). To the best of our knowledge, these are the first combinatorial neural bandit algorithms with regret performance guarantees. In particular, textttCN-TS is the first Thompson sampling algorithm with the worst-case regret guarantees for the general contextual combinatorial bandit problem. The numerical experiments demonstrate the superior performances of our proposed algorithms.