# Combinatorial Multi-Armed Bandit with General Reward Functions

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2016.

## Built on by (most cited first, 30 of 56)

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Improving Multi-Document Summarization through Referenced Flexible Extraction with Credit-Awareness](https://mlsanity.com/paper/2205.01889/) (2022)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [Online Learning of Network Bottlenecks via Minimax Paths](https://mlsanity.com/paper/2109.08467/) (2021)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Multi-Armed Bandits with Self-Information Rewards](https://mlsanity.com/paper/2209.02211/) (2022)
- [ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning](https://mlsanity.com/paper/2502.00775/) (2025)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Censored Semi-Bandits for Resource Allocation](https://mlsanity.com/paper/2104.05781/) (2021)
- [Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations](https://mlsanity.com/paper/2106.06712/) (2021)
- [A Multi-Arm Bandit Approach To Subset Selection Under Constraints](https://mlsanity.com/paper/2102.04824/) (2021)
- [Conservative Contextual Combinatorial Cascading Bandit](https://mlsanity.com/paper/2104.08615/) (2021)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes](https://mlsanity.com/paper/2110.02248/) (2021)
- [Contextual Combinatorial Multi-output GP Bandits with Group Constraints](https://mlsanity.com/paper/2111.14778/) (2021)
- [Risk-Aware Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2112.01141/) (2021)
- [Online Learning for Adaptive Probing and Scheduling in Dense WLANs](https://mlsanity.com/paper/2212.13585/) (2022)
- [Bandit Learning to Rank with Position-Based Click Models: Personalized and Equal Treatments](https://mlsanity.com/paper/2311.04528/) (2023)
- [Learning to Price Homogeneous Data](https://mlsanity.com/paper/2407.05484/) (2024)
- [A Complete Characterization of Learnability for Stochastic Noisy Bandits](https://mlsanity.com/paper/2410.09597/) (2024)
- [Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays](https://mlsanity.com/paper/2407.15439/) (2024)

## Abstract (arXiv)

In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the max() function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve O(logT) distribution-dependent regret and tildeO(√T) distribution-independent regret, where T is the time horizon. We apply our results to the K-MAX problem and expected utility maximization problems. In particular, for K-MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first tildeO(√ T) bound on the (1-ε)-approximation regret of its online problem, for any ε>0.