The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity

Mark Sellke () and Aleksandrs Slivkins ()
Additional contact information
Mark Sellke: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
Aleksandrs Slivkins: Microsoft Research, New York, New York 10012

Operations Research, 2023, vol. 71, issue 5, 1706-1732

Abstract: We consider incentivized exploration : a version of multiarmed 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 because of 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.”

Keywords: Revenue Management and Market Analytics; revenue management and market analytics; information design; Bayesian persuasion; multiarmed bandits; Bayesian incentive compatibility; Bayesian regret (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2401 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:5:p:1706-1732

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().