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

2025/06/02 by Mark Sellke, Schiffer, Benjamin, Sellke, Mark
Economics, Econometrics and Finance · Engineering · #Capital Investment and Risk Analysis #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reservoir Engineering and Simulation Methods

paper · pdf · doi:10.48550/arxiv.2506.01685

openalex publication_date 2025/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets
• Incentivized Exploration via Filtered Posterior Sampling
• Incentivizing Exploration with Linear Contexts and Combinatorial Actions
• Incentivizing Combinatorial Bandit Exploration
• Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning
• An entropic generalization of Caffarelli's contraction theorem via covariance inequalities
• Linear Bandits on Uniformly Convex Sets
• Exploration and Incentives in Reinforcement Learning
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
• Incentivising Exploration and Recommendations for Contextual Bandits with Payments
• Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
• Introduction to Multi-Armed Bandits
• Information Design: A Unified Perspective
• Bayesian Exploration with Heterogeneous Agents
• First-Order Bayesian Regret Analysis of Thompson Sampling
• Incentivizing Exploration with Selective Data Disclosure
• Multi-armed Bandits with Compensation
• An Information-Theoretic Analysis for Thompson Sampling with Many Actions
• Sparsity, variance and curvature in multi-armed bandits
• Fairness Incentives for Myopic Agents
• High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm
• Bayesian Exploration: Incentivizing Exploration in Bayesian Games
• Bayesian Incentive-Compatible Bandit Exploration
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Log-concavity and strong log-concavity: a review
• An Information-Theoretic Analysis of Thompson Sampling
• Prior-free and prior-dependent regret bounds for Thompson Sampling
• Learning to Optimize Via Posterior Sampling
• Learning to Optimize via Posterior Sampling
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Towards minimax policies for online linear optimization with bandit feedback
• Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument

Related

• Incentivizing Exploration with Linear Contexts and Combinatorial Actions
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
• Incentivizing Combinatorial Bandit Exploration
• When and why randomised exploration works (in linear bandits)
• Incentivized Lipschitz Bandits