# Incentivizing Combinatorial Bandit Exploration

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 15 of 15)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Incentivizing Exploration with Selective Data Disclosure](https://mlsanity.com/paper/1811.06026/) (2018)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Economic Recommendation Systems](https://mlsanity.com/paper/1507.07191/) (2015)

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

- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [When Are Two Lists Better than One?: Benefits and Harms in Joint Decision-making](https://mlsanity.com/paper/2308.11721/) (2023)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [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)

## Abstract (arXiv)

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.