# Incentivized Exploration of Non-Stationary Stochastic Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 44 references that are in the map.
- First posted on arXiv 16 Mar 2024.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Multi-armed Bandits with Compensation](https://mlsanity.com/paper/1811.01715/) (2018)
- [Bayesian Exploration with Heterogeneous Agents](https://mlsanity.com/paper/1902.07119/) (2019)
- [Incentivizing Exploration with Heterogeneous Value of Money](https://mlsanity.com/paper/1512.08427/) (2015)
- [Optimal Algorithm for Bayesian Incentive-Compatible Exploration](https://mlsanity.com/paper/1810.10304/) (2018)
- [Incentivized Exploration for Multi-Armed Bandits under Reward Drift](https://mlsanity.com/paper/1911.05142/) (2019)
- [Learning User Preferences to Incentivize Exploration in the Sharing Economy](https://mlsanity.com/paper/1711.08331/) (2017)

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

- [Incentivized Lipschitz Bandits](https://mlsanity.com/paper/2508.19466/) (2025)
- [Multi-Agent Lipschitz Bandits](https://mlsanity.com/paper/2602.16965/) (2026)
- [Learning from Local Walks on Dynamic Graphs with Bandit Feedback](https://mlsanity.com/paper/2607.10571/) (2026)

## Abstract (arXiv)

We study incentivized exploration for the multi-armed bandit (MAB) problem with non-stationary reward distributions, where players receive compensation for exploring arms other than the greedy choice and may provide biased feedback on the reward. We consider two different non-stationary environments: abruptly-changing and continuously-changing, and propose respective incentivized exploration algorithms. We show that the proposed algorithms achieve sublinear regret and compensation over time, thus effectively incentivizing exploration despite the nonstationarity and the biased or drifted feedback.