# (Almost) Free Incentivized Exploration from Decentralized Learning Agents

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 27 Oct 2021.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Incentivizing Exploration with Selective Data Disclosure](https://mlsanity.com/paper/1811.06026/) (2018)
- [Multi-armed Bandits with Compensation](https://mlsanity.com/paper/1811.01715/) (2018)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [Incentivizing Exploration with Heterogeneous Value of Money](https://mlsanity.com/paper/1512.08427/) (2015)
- [Incentivized Exploration for Multi-Armed Bandits under Reward Drift](https://mlsanity.com/paper/1911.05142/) (2019)
- [Incentivizing Exploration in Linear Bandits under Information Gap](https://mlsanity.com/paper/2104.03860/) (2021)

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

- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [MERMAIDE: Learning to Align Learners using Model-Based Meta-Learning](https://mlsanity.com/paper/2304.04668/) (2023)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)

## Abstract (arXiv)

Incentivized exploration in multi-armed bandits (MAB) has witnessed increasing interests and many progresses in recent years, where a principal offers bonuses to agents to do explorations on her behalf. However, almost all existing studies are confined to temporary myopic agents. In this work, we break this barrier and study incentivized exploration with multiple and long-term strategic agents, who have more complicated behaviors that often appear in real-world applications. An important observation of this work is that strategic agents' intrinsic needs of learning benefit (instead of harming) the principal's explorations by providing "free pulls". Moreover, it turns out that increasing the population of agents significantly lowers the principal's burden of incentivizing. The key and somewhat surprising insight revealed from our results is that when there are sufficiently many learning agents involved, the exploration process of the principal can be (almost) free. Our main results are built upon three novel components which may be of independent interest: (1) a simple yet provably effective incentive-provision strategy; (2) a carefully crafted best arm identification algorithm for rewards aggregated under unequal confidences; (3) a high-probability finite-time lower bound of UCB algorithms. Experimental results are provided to complement the theoretical analysis.