Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a Bayesian incentive-compatible (BIC) exploration algorithm for linear bandits on the unit ball that achieves lambda-spectral exploration with polynomial sample complexity, removing the exponential barrier for initial exploration.
Problem
Incentivized exploration in linear bandits with high-dimensional contexts: prior work needs exponential samples for BIC initial exploration of the action set, preventing efficient incentive-compatible learning.
Approach
Exploits the smoothness/curvature of the unit-ball action set: conditioning on noisy sign signals of the prior mean in a direction increases the conditional mean in that direction multiplicatively (exponential growth), so BIC actions can bootstrap weak initial signals to constant strength, with an eigenvalue-growth lemma ensuring termination in poly(d) steps.
Key results
- Algorithm achieves lambda-spectral exploration with sample complexity bar-lambda (d/(sigma+c_d))^{O(1)} log(1/epsilon_d), polynomial in dimension and logarithmic in epsilon_d.
- Any r-regular uniform prior on a convex body satisfies the assumptions with epsilon_d=(r/3)^d, so the exponential barrier disappears for the unit ball.
- Combining with Thompson sampling gives an end-to-end epsilon-BIC algorithm with Bayesian regret poly(d,1/r,1/epsilon)+O~(d sqrt(T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Euclidean unit ball as the action set under the stated prior assumptions | BIC exploration in linear bandits · Linear bandit, Euclidean unit ball | sample complexity: e^{\Omega(d)} time -> O\left(\log\left(\frac{1}{\cvar \epsilon_d c_d}\right)\left(\frac{d^5}{ \lambda^4\cvar^2} + \frac{ | Helped |
| Use the proposed algorithm to achieve λ-spectral exploration under Assumption [ref] | BIC Exploration · Linear bandit, Euclidean unit ball | sample complexity | Helped |
Surprising findings
- Exponentially small probability of exploring a direction (epsilon_d = (r/3)^d) does not force exponential sample complexity thanks to the curvature of the unit ball.
Limitations
- Analysis specific to unit ball; extension to other smooth bodies left open
- Requires log-concave or non-degeneracy assumptions on prior; no experiments
- End-to-end guarantee is only epsilon-BIC for r-regular priors
Experimental setup
Metrics: sample complexity lambda-spectral exploration
Baselines: Hu et al. (2022) linear incentivized exploration Thompson sampling
Builds on: Thompson sampling incentivized exploration with exponential exploration (Mansour et al.) Bayesian persuasion
Closest papers by meaning
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.89)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.88)
- DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.87)
- Preference-based Pure Exploration (NeurIPS 2024 · similarity 0.87)
- Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.