mlsanityData to 14 Oct 2026

Combinatorial Neural Bandits

arXiv 2306.00242 ↗First posted 31 May 2023stat.ML cs.LGcited by 16

Not on the map. Why?

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.

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

13 of 41 references.

References · 13

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  4. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  5. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  6. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  7. 2020Neural Thompson Samplingcited by 128
  8. 2015Cascading Bandits: Learning to Rank in the Cascade Modelcited by 77
  9. 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 71
  10. 2016Cascading Bandits for Large-Scale Recommendation Problemscited by 45
  11. 2014Efficient Learning in Large-Scale Combinatorial Semi-Banditscited by 36
  12. 2017Online Clustering of Contextual Cascading Banditscited by 24
1 more
  1. 2018Online Learning to Rank with Featurescited by 18

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 7; 2026: 5.

16 papers.

Sort:

By area:

  1. 2025Adaptive Batch-Wise Sample Scheduling for Direct Preference Optimizationcited by 17
  2. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  3. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  4. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  5. 2025Online Clustering of Dueling Banditscited by 3
  6. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  7. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  8. 2025Thompson Sampling for Multi-Objective Linear Contextual Banditcited by 2
  9. 2026Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximationcited by 1
  10. 2026Generalized Linear Bandits with Memorycited by 1
  11. 2024Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Banditscited by 0
  12. 2024Combinatorial Multi-armed Bandits: Arm Selection via Group Testingcited by 0
4 more
  1. 2025Clutch Control: An Attention-based Combinatorial Bandit for Efficient Mutation in JavaScript Engine Fuzzingcited by 0
  2. 2026Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilitiescited by 0
  3. 2026Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signalscited by 0
  4. 2026Diversified Multinomial Logit Contextual Banditscited by 0