# Exploration and Incentives in Reinforcement Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 71 references that are in the map.
- First posted on arXiv 28 Feb 2021.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Incentivizing Exploration with Selective Data Disclosure](https://mlsanity.com/paper/1811.06026/) (2018)
- [Greedy Algorithm almost Dominates in Smoothed Contextual Bandits](https://mlsanity.com/paper/2005.10624/) (2020)
- [Competing Bandits: The Perils of Exploration Under Competition](https://mlsanity.com/paper/2007.10144/) (2020)
- [Economic Recommendation Systems](https://mlsanity.com/paper/1507.07191/) (2015)
- [Optimal Algorithm for Bayesian Incentive-Compatible Exploration](https://mlsanity.com/paper/1810.10304/) (2018)

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

- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023)
- [Algorithmic Censoring in Dynamic Learning Systems](https://mlsanity.com/paper/2305.09035/) (2023)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Improved Online Learning Algorithms for CTR Prediction in Ad Auctions](https://mlsanity.com/paper/2403.00845/) (2024)
- [Truthful mechanisms for linear bandit games with private contexts](https://mlsanity.com/paper/2501.03865/) (2025)
- [Competitive Multi-armed Bandit Games for Resource Sharing](https://mlsanity.com/paper/2503.20975/) (2025)
- [Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts](https://mlsanity.com/paper/2506.01685/) (2025)
- [Microeconomic Foundations of Multi-Agent Learning](https://mlsanity.com/paper/2601.03451/) (2026)
- [Collaborating in Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2605.13145/) (2026)
- [On Incentivized Exploration beyond Bayesianism and Full-Information](https://mlsanity.com/paper/2607.18300/) (2026)

## Abstract (arXiv)

How do you incentivize self-interested agents to textitexplore when they prefer to textitexploit? We consider complex exploration problems, where each agent faces the same (but unknown) MDP. In contrast with traditional formulations of reinforcement learning, agents control the choice of policies, whereas an algorithm can only issue recommendations. However, the algorithm controls the flow of information, and can incentivize the agents to explore via information asymmetry. We design an algorithm which explores all reachable states in the MDP. We achieve provable guarantees similar to those for incentivizing exploration in static, stateless exploration problems studied previously. To the best of our knowledge, this is the first work to consider mechanism design in a stateful, reinforcement learning setting.