# Bayesian Incentive-Compatible Bandit Exploration

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2015.

## Built on by (most cited first, 30 of 53)

- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [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)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [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)
- [Accounting for AI and Users Shaping One Another: The Role of Mathematical Models](https://mlsanity.com/paper/2404.12366/) (2024)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Networked Restless Multi-Armed Bandits for Mobile Interventions](https://mlsanity.com/paper/2201.12408/) (2022)
- [Bandit Social Learning: Exploration under Myopic Behavior](https://mlsanity.com/paper/2302.07425/) (2023)
- [Incentivizing Exploration in Linear Bandits under Information Gap](https://mlsanity.com/paper/2104.03860/) (2021)
- [Designing an Automatic Agent for Repeated Language based Persuasion Games](https://mlsanity.com/paper/2105.04976/) (2021)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [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)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [SelectMix: Enhancing Label Noise Robustness through Targeted Sample Mixing](https://mlsanity.com/paper/2509.11265/) (2025)
- [Incentivizing Compliance with Algorithmic Instruments](https://mlsanity.com/paper/2107.10093/) (2021)
- [Collaborative Multi-agent Stochastic Linear Bandits](https://mlsanity.com/paper/2205.06331/) (2022)
- [Learning the Optimal Recommendation from Explorative Users](https://mlsanity.com/paper/2110.03068/) (2021)
- [(Almost) Free Incentivized Exploration from Decentralized Learning Agents](https://mlsanity.com/paper/2110.14628/) (2021)
- [Learning from a Learning User for Optimal Recommendations](https://mlsanity.com/paper/2202.01879/) (2022)
- [Decongestion by Representation: Learning to Improve Economic Welfare in Marketplaces](https://mlsanity.com/paper/2306.10606/) (2023)
- [Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2312.07929/) (2023)

## Abstract (arXiv)

Individual decision-makers consume information revealed by the previous decision makers, and produce information that may help in future decisions. This phenomenon is common in a wide range of scenarios in the Internet economy, as well as in other domains such as medical decisions. Each decision-maker would individually prefer to "exploit": select an action with the highest expected reward given her current information. At the same time, each decision-maker would prefer previous decision-makers to "explore", producing information about the rewards of various actions. A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance the exploration and exploitation so as to maximize social welfare. We formulate this problem as a multi-armed bandit problem (and various generalizations thereof) under incentive-compatibility constraints induced by the agents' Bayesian priors. We design an incentive-compatible bandit algorithm for the social planner whose regret is asymptotically optimal among all bandit algorithms (incentive-compatible or not). Further, we provide a black-box reduction from an arbitrary multi-arm bandit algorithm to an incentive-compatible one, with only a constant multiplicative increase in regret. This reduction works for very general bandit setting that incorporate contexts and arbitrary auxiliary feedback.