# Optimal Algorithm for Bayesian Incentive-Compatible Exploration

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2018.

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

- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Modeling Attrition in Recommender Systems with Departing Bandits](https://mlsanity.com/paper/2203.13423/) (2022)
- [Incentivized Exploration of Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2403.10819/) (2024)
- [Incentivized Lipschitz Bandits](https://mlsanity.com/paper/2508.19466/) (2025)
- [Incentivized Collaboration in Active Learning](https://mlsanity.com/paper/2311.00260/) (2023)
- [On Incentivized Exploration beyond Bayesianism and Full-Information](https://mlsanity.com/paper/2607.18300/) (2026)

## Abstract (arXiv)

We consider a social planner faced with a stream of myopic selfish agents. The goal of the social planner is to maximize the social welfare, however, it is limited to using only information asymmetry (regarding previous outcomes) and cannot use any monetary incentives. The planner recommends actions to agents, but her recommendations need to be Bayesian Incentive Compatible to be followed by the agents. Our main result is an optimal algorithm for the planner, in the case that the actions realizations are deterministic and have limited support, making significant important progress on this open problem. Our optimal protocol has two interesting features. First, it always completes the exploration of a priori more beneficial actions before exploring a priori less beneficial actions. Second, the randomization in the protocol is correlated across agents and actions (and not independent at each decision time).