Combinatorial Multi-Armed Bandit with General Reward Functions

Abstract

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(\log T)$ distribution-dependent regret and $\tilde{O}(\sqrt{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 $\tilde{O}(\sqrt{T})$ bound on the $(1-\epsilon )$-approximation regret of its online problem, for any $\epsilon >0$.

Published in Neural Information Processing Systems (NIPS) 2016. New in this version: a minor bug fix

References in corpus (6)

• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Matroid Bandits: Fast Combinatorial Optimization with Learning
• Combinatorial Cascading Bandits
• Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

Cited by in corpus (23)

• Thompson Sampling for Combinatorial Semi-Bandits
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Online Learning for Adaptive Probing and Scheduling in Dense WLANs
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Bandit Learning with Delayed Impact of Actions
• Task Replication for Vehicular Edge Computing: A Combinatorial Multi-Armed Bandit based Approach
• Multinomial Logit Bandit with Linear Utility Functions
• Distributed Task Replication for Vehicular Edge Computing: Performance Analysis and Learning-based Algorithm
• Thompson Sampling for a Fatigue-aware Online Recommendation System
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Recurrent Submodular Welfare and Matroid Blocking Bandits
• Fully Gap-Dependent Bounds for Multinomial Logit Bandit
• Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications (Extended Version)
• The Influence of Shape Constraints on the Thresholding Bandit Problem
• Active Information Acquisition for Linear Optimization
• Censored Semi-Bandits for Resource Allocation
• Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations
• Sleeping Combinatorial Bandits
• Risk-Aware Algorithms for Combinatorial Semi-Bandits
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
• Online Learning for Measuring Incentive Compatibility in Ad Auctions