Efficient learning in large-scale combinatorial semi-bandits

A stochastic combinatorial semi-bandit is an on-line learning problem where at each step a learn-ing agent chooses a subset of ground items sub-ject to combinatorial constraints, and then ob-serves stochastic weights of these items and re-ceives their sum as a payoff. In this paper, we consider efficient learning in large-scale com-binatorial semi-bandits with linear generaliza-tion, and as a solution, propose two learning algorithms called Combinatorial Linear Thomp-son Sampling (CombLinTS) and Combinatoria