Combinatorial semi-bandit with known covariance
arXiv:1612.01859
Abstract
The combinatorial stochastic semi-bandit problem is an extension of the classical multi-armed bandit problem in which an algorithm pulls more than one arm at each stage and the rewards of all pulled arms are revealed. One difference with the single arm variant is that the dependency structure of the arms is crucial. Previous works on this setting either used a worst-case approach or imposed independence of the arms. We introduce a way to quantify the dependency structure of the problem and design an algorithm that adapts to it. The algorithm is based on linear regression and the analysis develops techniques from the linear bandit literature. By comparing its performance to a new lower bound, we prove that it is optimal, up to a poly-logarithmic factor in the number of pulled arms.
arXiv commentin NIPS 2016 (Conference on Neural Information Processing Systems), Dec 2016, Barcelona, Spain
References in corpus (1)
Cited by in corpus (14)
- Thompson Sampling for Combinatorial Semi-Bandits
- A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
- Tight Lower Bounds for Combinatorial Multi-Armed Bandits
- Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
- Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem
- Online linear optimization with the log-determinant regularizer
- A survey on multi-player bandits
- Lifelong Learning in Multi-Armed Bandits
- Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
- Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
- Continuous Mean-Covariance Bandits
- Experimental Design for Regret Minimization in Linear Bandits
- On the Suboptimality of Thompson Sampling in High Dimensions
- Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem