Top-k Combinatorial Bandits with Full-Bandit Feedback

Abstract

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.

Cited by in corpus (12)

• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions
• Efficient Optimal Selection for Composited Advertising Creatives with Tree Structure
• Fully Gap-Dependent Bounds for Multinomial Logit Bandit
• DART: aDaptive Accept RejecT for non-linear top-K subset identification
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
• Combinatorial Bandits under Strategic Manipulations