# Prior-Agnostic Incentive-Compatible Exploration

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 24 Feb 2026.

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

- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [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)
- [Mechanisms for a No-Regret Agent: Beyond the Common Prior](https://mlsanity.com/paper/2009.05518/) (2020)
- [Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses](https://mlsanity.com/paper/2502.12564/) (2025)
- [Bayesian Exploration with Heterogeneous Agents](https://mlsanity.com/paper/1902.07119/) (2019)
- [Efficient Prior-Free Mechanisms for No-Regret Agents](https://mlsanity.com/paper/2311.07754/) (2023)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Economic Recommendation Systems](https://mlsanity.com/paper/1507.07191/) (2015)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [Near-optimal Per-Action Regret Bounds for Sleeping Bandits](https://mlsanity.com/paper/2403.01315/) (2024)

## Abstract (arXiv)

In bandit settings, optimizing long-term regret metrics requires exploration, which corresponds to sometimes taking myopically sub-optimal actions. When a long-lived principal merely recommends actions to be executed by a sequence of different agents (as in an online recommendation platform) this provides an incentive misalignment: exploration is "worth it" for the principal but not for the agents. Prior work studies regret minimization under the constraint of Bayesian Incentive-Compatibility in a static stochastic setting with a fixed and common prior shared amongst the agents and the algorithm designer. We show that (weighted) swap regret bounds on their own suffice to cause agents to faithfully follow forecasts in an approximate Bayes Nash equilibrium, even in dynamic environments in which agents have conflicting prior beliefs and the mechanism designer has no knowledge of any agents beliefs. To obtain these bounds, it is necessary to assume that the agents have some degree of uncertainty not just about the rewards, but about their arrival time -- i.e. their relative position in the sequence of agents served by the algorithm. We instantiate our abstract bounds with concrete algorithms for guaranteeing adaptive and weighted regret in bandit settings.