Efficient Learning in Large-Scale Combinatorial Semi-Bandits
arXiv:1406.7443
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 combinatorial constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we consider efficient learning in large-scale combinatorial semi-bandits with linear generalization, and as a solution, propose two learning algorithms called Combinatorial Linear Thompson Sampling (CombLinTS) and Combinatorial Linear UCB (CombLinUCB). Both algorithms are computationally efficient as long as the offline version of the combinatorial problem can be solved efficiently. We establish that CombLinTS and CombLinUCB are also provably statistically efficient under reasonable assumptions, by developing regret bounds that are independent of the problem scale (number of items) and sublinear in time. We also evaluate CombLinTS on a variety of problems with thousands of items. Our experiment results demonstrate that CombLinTS is scalable, robust to the choice of algorithm parameters, and significantly outperforms the best of our baselines.
References in corpus (5)
Cited by in corpus (26)
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Combinatorial Bandits Revisited
- Cascading Bandits: Learning to Rank in the Cascade Model
- Combinatorial Cascading Bandits
- Thompson Sampling for Combinatorial Semi-Bandits
- Unbiased Cascade Bandits: Mitigating Exposure Bias in Online Learning to Rank Recommendation
- Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
- Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
- Learning to Act Greedily: Polymatroid Semi-Bandits
- Contextual User Browsing Bandits for Large-Scale Online Mobile Recommendation
- Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
- Meta-Learning Bandit Policies by Gradient Ascent
- Neural Combinatorial Clustered Bandits for Recommendation Systems
- Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
- Offline Evaluation of Ranking Policies with Click Models
- Waterfall Bandits: Learning to Sell Ads Online
- Bandits with Knapsacks beyond the Worst-Case
- Algorithms for slate bandits with non-separable reward functions
- Regret vs. Bandwidth Trade-off for Recommendation Systems
- Thompson Sampling Algorithms for Cascading Bandits
- Shrinking the Upper Confidence Bound: A Dynamic Product Selection Problem for Urban Warehouses
- An Arm-Wise Randomization Approach to Combinatorial Linear Semi-Bandits
- A Map of Bandits for E-commerce
- Correlation Robust Influence Maximization
- Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
- Sleeping Combinatorial Bandits