# Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

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

- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Toward Defining a Domain Complexity Measure Across Domains](https://mlsanity.com/paper/2303.04141/) (2023)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [Leveraging Causal Graphs for Blocking in Randomized Experiments](https://mlsanity.com/paper/2111.02306/) (2021)
- [An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration](https://mlsanity.com/paper/2502.01429/) (2025)
- [LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection](https://mlsanity.com/paper/2601.00933/) (2026)
- [Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/2605.00762/) (2026)

## Abstract (arXiv)

Many real-world problems like Social Influence Maximization face the dilemma of choosing the best K out of N options at a given time instant. This setup can be modeled as a combinatorial bandit which chooses K out of N arms at each time, with an aim to achieve an efficient trade-off between exploration and exploitation. This is the first work for combinatorial bandits where the feedback received can be a non-linear function of the chosen K arms. The direct use of multi-armed bandit requires choosing among N-choose-K options making the state space large. In this paper, we present a novel algorithm which is computationally efficient and the storage is linear in N. The proposed algorithm is a divide-and-conquer based strategy, that we call CMAB-SM. Further, the proposed algorithm achieves a textitregret bound of tilde O(K^frac12N^frac13T^frac23) for a time horizon T, which is textitsub-linear in all parameters T, N, and K. %When applied to the problem of Social Influence Maximization, the performance of the proposed algorithm surpasses the UCB algorithm and some more sophisticated domain-specific methods.