Thompson Sampling for Combinatorial Semi-Bandits

Abstract

In this paper, we study the application of the Thompson sampling (TS) methodology to the stochastic combinatorial multi-armed bandit (CMAB) framework. We first analyze the standard TS algorithm for the general CMAB model when the outcome distributions of all the base arms are independent, and obtain a distribution-dependent regret bound of $O(m\log K_{\max }\log T/{\Delta }_{\min })$, where $m$ is the number of base arms, $K_{\max }$ is the size of the largest super arm, $T$ is the time horizon, and ${\Delta }_{\min }$ is the minimum gap between the expected reward of the optimal solution and any non-optimal solution. This regret upper bound is better than the $O(m(\log K_{\max }{)}^2\log T/{\Delta }_{\min })$ bound in prior works. Moreover, our novel analysis techniques can help to tighten the regret bounds of other existing UCB-based policies (e.g., ESCB), as we improve the method of counting the cumulative regret. Then we consider the matroid bandit setting (a special class of CMAB model), where we could remove the independence assumption across arms and achieve a regret upper bound that matches the lower bound. Except for the regret upper bounds, we also point out that one cannot directly replace the exact offline oracle (which takes the parameters of an offline problem instance as input and outputs the exact best action under this instance) with an approximation oracle in TS algorithm for even the classical MAB problem. Finally, we use some experiments to show the comparison between regrets of TS and other existing algorithms, the experimental results show that TS outperforms existing baselines.

References in corpus (3)

• Further Optimal Regret Bounds for Thompson Sampling
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• Combinatorial semi-bandit with known covariance

Cited by in corpus (19)

• A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• MOTS: Minimax Optimal Thompson Sampling
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Online Learning of Energy Consumption for Navigation of Electric Vehicles
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Online Competitive Influence Maximization
• Accurate and Fast Federated Learning via Combinatorial Multi-Armed Bandits
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Thompson Sampling for a Fatigue-aware Online Recommendation System
• A survey on multi-player bandits
• A Reliability-aware Multi-armed Bandit Approach to Learn and Select Users in Demand Response
• Thompson Sampling Algorithms for Cascading Bandits
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
• Risk-Aware Algorithms for Combinatorial Semi-Bandits
• Adaptive Combinatorial Allocation
• Constant or logarithmic regret in asynchronous multiplayer bandits