# Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 2 Jun 2025.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Prior-free and prior-dependent regret bounds for Thompson Sampling](https://mlsanity.com/paper/1304.5758/) (2013)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Incentivizing Exploration with Selective Data Disclosure](https://mlsanity.com/paper/1811.06026/) (2018)
- [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019)
- [First-Order Bayesian Regret Analysis of Thompson Sampling](https://mlsanity.com/paper/1902.00681/) (2019)
- [Multi-armed Bandits with Compensation](https://mlsanity.com/paper/1811.01715/) (2018)
- [Bayesian Exploration with Heterogeneous Agents](https://mlsanity.com/paper/1902.07119/) (2019)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Fairness Incentives for Myopic Agents](https://mlsanity.com/paper/1705.02321/) (2017)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [Incentivising Exploration and Recommendations for Contextual Bandits with Payments](https://mlsanity.com/paper/2001.07853/) (2020)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)
- [Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets](https://mlsanity.com/paper/2402.12868/) (2024)

## Abstract (arXiv)

In the incentivized exploration model, a principal aims to explore and learn over time by interacting with a sequence of self-interested agents. It has been recently understood that the main challenge in designing incentive-compatible algorithms for this problem is to gather a moderate amount of initial data, after which one can obtain near-optimal regret via posterior sampling. With high-dimensional contexts, however, this initial exploration phase requires exponential sample complexity in some cases, which prevents efficient learning unless initial data can be acquired exogenously. We show that these barriers to exploration disappear under mild geometric conditions on the set of available actions, in which case incentive-compatibility does not preclude regret-optimality. Namely, we consider the linear bandit model with actions in the Euclidean unit ball, and give an incentive-compatible exploration algorithm with sample complexity that scales polynomially with the dimension and other parameters.