The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
This addresses the problem of incentivizing exploration in bandit settings for algorithm designers, offering a solution with bounded performance loss, though it builds incrementally on prior work.
The paper tackles incentivized exploration in multi-armed bandits, where self-interested agents control arm choices, and shows that Thompson Sampling is incentive-compatible with sufficient initial data, limiting performance loss to initial rounds. It provides matching upper and lower bounds for sample complexity, typically polynomial in arms and exponential in belief strength.
We consider incentivized exploration: a version of multi-armed bandits where the choice of arms is controlled by self-interested agents, and the algorithm can only issue recommendations. The algorithm controls the flow of information, and the information asymmetry can incentivize the agents to explore. Prior work achieves optimal regret rates up to multiplicative factors that become arbitrarily large depending on the Bayesian priors, and scale exponentially in the number of arms. A more basic problem of sampling each arm once runs into similar factors. We focus on the price of incentives: the loss in performance, broadly construed, incurred for the sake of incentive-compatibility. We prove that Thompson Sampling, a standard bandit algorithm, is incentive-compatible if initialized with sufficiently many data points. The performance loss due to incentives is therefore limited to the initial rounds when these data points are collected. The problem is largely reduced to that of sample complexity: how many rounds are needed? We address this question, providing matching upper and lower bounds and instantiating them in various corollaries. Typically, the optimal sample complexity is polynomial in the number of arms and exponential in the "strength of beliefs".