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

arXiv: https://arxiv.org/abs/2002.00558 · HTML: https://mlsanity.com/paper/2002.00558/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2020.

## Built on by (most cited first, 26 of 26)

- [Competition, Alignment, and Equilibria in Digital Marketplaces](https://mlsanity.com/paper/2208.14423/) (2022)
- [Bayesian Persuasion for Algorithmic Recourse](https://mlsanity.com/paper/2112.06283/) (2021)
- [Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online Platforms](https://mlsanity.com/paper/2401.09804/) (2024)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Bandit Social Learning: Exploration under Myopic Behavior](https://mlsanity.com/paper/2302.07425/) (2023)
- [Incentive-Aware Recommender Systems in Two-Sided Markets](https://mlsanity.com/paper/2211.15381/) (2022)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [Incentivized Exploration of Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2403.10819/) (2024)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)
- [Improved Online Learning Algorithms for CTR Prediction in Ad Auctions](https://mlsanity.com/paper/2403.00845/) (2024)
- [Incentivized Lipschitz Bandits](https://mlsanity.com/paper/2508.19466/) (2025)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (2024)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [Exploration and Persuasion](https://mlsanity.com/paper/2410.17086/) (2024)
- [Truthful mechanisms for linear bandit games with private contexts](https://mlsanity.com/paper/2501.03865/) (2025)
- [Incentivized Collaboration in Active Learning](https://mlsanity.com/paper/2311.00260/) (2023)
- [Incentive-Aware Synthetic Control: Accurate Counterfactual Estimation via Incentivized Exploration](https://mlsanity.com/paper/2312.16307/) (2023)
- [Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts](https://mlsanity.com/paper/2506.01685/) (2025)
- [Prior-Agnostic Incentive-Compatible Exploration](https://mlsanity.com/paper/2602.20465/) (2026)
- [Learning from Local Walks on Dynamic Graphs with Bandit Feedback](https://mlsanity.com/paper/2607.10571/) (2026)
- [Thompson Sampling Is 2-Competitive for Mistakes](https://mlsanity.com/paper/2607.12389/) (2026)
- [On Incentivized Exploration beyond Bayesianism and Full-Information](https://mlsanity.com/paper/2607.18300/) (2026)

## Abstract (arXiv)

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".