# Top-k Combinatorial Bandits with Full-Bandit Feedback

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [Nearly Minimax Optimal Regret for Multinomial Logistic Bandit](https://mlsanity.com/paper/2405.09831/) (2024)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Efficient Optimal Selection for Composited Advertising Creatives with Tree Structure](https://mlsanity.com/paper/2103.01453/) (2021)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [Gaussian Process Bandits with Aggregated Feedback](https://mlsanity.com/paper/2112.13029/) (2021)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback](https://mlsanity.com/paper/2303.13604/) (2023)
- [A Contextual Combinatorial Bandit Approach to Negotiation](https://mlsanity.com/paper/2407.00567/) (2024)
- [Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making](https://mlsanity.com/paper/2510.21788/) (2025)
- [Good Allocations from Bad Estimates](https://mlsanity.com/paper/2601.05597/) (2026)
- [Pure Exploration with Structured Preference Feedback](https://mlsanity.com/paper/2104.05294/) (2021)
- [No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting](https://mlsanity.com/paper/2405.12439/) (2024)
- [Combining Diverse Information for Coordinated Action: Stochastic Bandit Algorithms for Heterogeneous Agents](https://mlsanity.com/paper/2408.03405/) (2024)
- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)
- [Generative Modeling with Multi-Instance Reward Learning for E-commerce Creative Optimization](https://mlsanity.com/paper/2508.09730/) (2025)
- [Dueling Bandits with Team Comparisons](https://mlsanity.com/paper/2107.02738/) (2021)
- [Neural Bandits for Data Mining: Searching for Dangerous Polypharmacy](https://mlsanity.com/paper/2212.05190/) (2022)
- [Master-slave Deep Architecture for Top-K Multi-armed Bandits with Non-linear Bandit Feedback and Diversity Constraints](https://mlsanity.com/paper/2308.12680/) (2023)
- [BandiK: Efficient Multi-Task Decomposition Using a Multi-Bandit Framework](https://mlsanity.com/paper/2512.24708/) (2025)
- [Semi-overlapping Multi-bandit Best Arm Identification for Sequential Support Network Learning](https://mlsanity.com/paper/2512.24959/) (2025)
- [Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/2605.00762/) (2026)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

Top-k Combinatorial Bandits generalize multi-armed bandits, where at each round any subset of k out of n arms may be chosen and the sum of the rewards is gained. We address the full-bandit feedback, in which the agent observes only the sum of rewards, in contrast to the semi-bandit feedback, in which the agent observes also the individual arms' rewards. We present the Combinatorial Successive Accepts and Rejects (CSAR) algorithm, which generalizes SAR (Bubeck et al, 2013) for top-k combinatorial bandits. Our main contribution is an efficient sampling scheme that uses Hadamard matrices in order to estimate accurately the individual arms' expected rewards. We discuss two variants of the algorithm, the first minimizes the sample complexity and the second minimizes the regret. We also prove a lower bound on sample complexity, which is tight for k=O(1). Finally, we run experiments and show that our algorithm outperforms other methods.