Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits

Abstract

A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample efficient learning in stochastic combinatorial semi-bandits. In particular, we analyze a UCB-like algorithm for solving the problem, which is known to be computationally efficient; and prove $O(KL(1/\Delta )\log n)$ and $O(\sqrt{KLn\log n})$ upper bounds on its $n$-step regret, where $L$ is the number of ground items, $K$ is the maximum number of chosen items, and $\Delta$ is the gap between the expected returns of the optimal and best suboptimal solutions. The gap-dependent bound is tight up to a constant factor and the gap-free bound is tight up to a polylogarithmic factor.

Proceedings of the 18th International Conference on Artificial Intelligence and Statistics

References in corpus (4)

• Matroid Bandits: Fast Combinatorial Optimization with Learning
• An Information-Theoretic Analysis of Thompson Sampling
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• Learning to Act Greedily: Polymatroid Semi-Bandits

Cited by in corpus (60)

• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Cascading Bandits: Learning to Rank in the Cascade Model
• Minimal Exploration in Structured Stochastic Bandits
• Combinatorial Multi-Armed Bandit with General Reward Functions
• Combinatorial Cascading Bandits
• DCM Bandits: Learning to Rank with Multiple Clicks
• Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• Thompson Sampling for Combinatorial Semi-Bandits
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Multiple-Play Bandits in the Position-Based Model
• Online Influence Maximization under Linear Threshold Model
• PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer
• First-order regret bounds for combinatorial semi-bandits
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Learning to Act Greedily: Polymatroid Semi-Bandits
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Contextual Blocking Bandits
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Stochastic Bandits with Delay-Dependent Payoffs
• (Locally) Differentially Private Combinatorial Semi-Bandits
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Combinatorial Multi-Objective Multi-Armed Bandit Problem
• Optimal Routing for Delay-Sensitive Traffic in Overlay Networks
• Learning to Route Efficiently with End-to-End Feedback: The Value of Networked Structure
• Hierarchical Bayesian Bandits
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Conservative Contextual Combinatorial Cascading Bandit
• Algorithms for slate bandits with non-separable reward functions
• Non-Stationary Delayed Bandits with Intermediate Observations
• Recurrent Submodular Welfare and Matroid Blocking Bandits
• Waterfall Bandits: Learning to Sell Ads Online
• Bandits with Knapsacks beyond the Worst-Case
• Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
• A Reliability-aware Multi-armed Bandit Approach to Learn and Select Users in Demand Response
• Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
• Offline Evaluation of Ranking Policies with Click Models
• No Regrets for Learning the Prior in Bandits
• Thompson Sampling Algorithms for Cascading Bandits
• Control Variates for Slate Off-Policy Evaluation
• Fundamental Limits of Online Network-Caching
• On the Suboptimality of Thompson Sampling in High Dimensions
• Experimental Design for Regret Minimization in Linear Bandits
• Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications (Extended Version)
• Risk-Aware Algorithms for Combinatorial Semi-Bandits
• DART: aDaptive Accept RejecT for non-linear top-K subset identification
• Sleeping Combinatorial Bandits
• Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations
• Combining Reward and Rank Signals for Slate Recommendation
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
• Online Learning for Measuring Incentive Compatibility in Ad Auctions
• Combinatorial Bandits without Total Order for Arms
• Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
• Combinatorial Bandits under Strategic Manipulations