# Bayesian Exploration: Incentivizing Exploration in Bayesian Games

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

## Key facts

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

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

- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [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)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Multi-Receiver Online Bayesian Persuasion](https://mlsanity.com/paper/2106.06480/) (2021)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [Risk-Sensitive Bayesian Games for Multi-Agent Reinforcement Learning under Policy Uncertainty](https://mlsanity.com/paper/2203.10045/) (2022)
- [Incentive-Aware Recommender Systems in Two-Sided Markets](https://mlsanity.com/paper/2211.15381/) (2022)
- [Algorithmic Censoring in Dynamic Learning Systems](https://mlsanity.com/paper/2305.09035/) (2023)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [Incentivizing Compliance with Algorithmic Instruments](https://mlsanity.com/paper/2107.10093/) (2021)
- [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)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Incentivized Bandit Learning with Self-Reinforcing User Preferences](https://mlsanity.com/paper/2105.08869/) (2021)
- [Human-in-the-loop Learning for Dynamic Congestion Games](https://mlsanity.com/paper/2404.15599/) (2024)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (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)
- [Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion](https://mlsanity.com/paper/2109.12445/) (2021)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [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)
- [Learning with Limited Shared Information in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2502.15338/) (2025)
- [Competitive Multi-armed Bandit Games for Resource Sharing](https://mlsanity.com/paper/2503.20975/) (2025)

## Abstract (arXiv)

We consider a ubiquitous scenario in the Internet economy when individual decision-makers (henceforth, agents) both produce and consume information as they make strategic choices in an uncertain environment. This creates a three-way tradeoff between exploration (trying out insufficiently explored alternatives to help others in the future), exploitation (making optimal decisions given the information discovered by other agents), and incentives of the agents (who are myopically interested in exploitation, while preferring the others to explore). We posit a principal who controls the flow of information from agents that came before, and strives to coordinate the agents towards a socially optimal balance between exploration and exploitation, not using any monetary transfers. The goal is to design a recommendation policy for the principal which respects agents' incentives and minimizes a suitable notion of regret. We extend prior work in this direction to allow the agents to interact with one another in a shared environment: at each time step, multiple agents arrive to play a Bayesian game, receive recommendations, choose their actions, receive their payoffs, and then leave the game forever. The agents now face two sources of uncertainty: the actions of the other agents and the parameters of the uncertain game environment. Our main contribution is to show that the principal can achieve constant regret when the utilities are deterministic (where the constant depends on the prior distribution, but not on the time horizon), and logarithmic regret when the utilities are stochastic. As a key technical tool, we introduce the concept of explorable actions, the actions which some incentive-compatible policy can recommend with non-zero probability. We show how the principal can identify (and explore) all explorable actions, and use the revealed information to perform optimally.