Incentivizing Combinatorial Bandit Exploration
Consider a bandit algorithm that recommends actions to self-interested users
in a recommendation system. The users are free to choose other actions and need
to be incentivized to follow the algorithm's recommendations. While the users
prefer to exploit, the algorithm can incentivize them to explore by leveraging
the information collected from the previous users. All published work on this
problem, known as incentivized exploration, focuses on small, unstructured
action sets and mainly targets the case when the users' beliefs are independent
across actions. However, realistic exploration problems often feature large,
structured action sets and highly correlated beliefs. We focus on a
paradigmatic exploration problem with structure: combinatorial semi-bandits. We
prove that Thompson Sampling, when applied to combinatorial semi-bandits, is
incentive-compatible when initialized with a sufficient number of samples of
each arm (where this number is determined in advance by the Bayesian prior).
Moreover, we design incentive-compatible algorithms for collecting the initial
samples.