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

• URL: http://arxiv.org/abs/2506.01685v1
• Date: Mon, 02 Jun 2025 13:50:00 GMT
• Title: Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
• Authors: Benjamin Schiffer, Mark Sellke,
• Abstract summary: A principal aims to explore and learn over time by interacting with a sequence of self-interested agents.<n>The main challenge in incentive-compatible algorithms for this problem is to gather a moderate amount of initial data.<n>We show that these barriers to exploration disappear under mild geometric conditions on the set of available actions.
• Score: 7.751607497318266
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 \emph{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.

Related papers

• Model-Free Active Exploration in Reinforcement Learning [53.786439742572995]
  We study the problem of exploration in Reinforcement Learning and present a novel model-free solution. Our strategy is able to identify efficient policies faster than state-of-the-art exploration approaches.
  arXiv  Detail & Related papers  (2024-06-30T19:00:49Z)
• Open-set Face Recognition with Neural Ensemble, Maximal Entropy Loss and Feature Augmentation [1.8047694351309207]
  Open-set face recognition refers to a scenario in which biometric systems have incomplete knowledge of all existing subjects. This work introduces a novel method that associates an ensemble of compact neural networks with a margin-based cost function. We carry out experiments on well-known LFW and IJB-C datasets where results show that the approach is able to boost closed and open-set identification rates.
  arXiv  Detail & Related papers  (2023-08-23T18:22:03Z)
• Small Object Detection via Coarse-to-fine Proposal Generation and Imitation Learning [52.06176253457522]
  We propose a two-stage framework tailored for small object detection based on the Coarse-to-fine pipeline and Feature Imitation learning. CFINet achieves state-of-the-art performance on the large-scale small object detection benchmarks, SODA-D and SODA-A.
  arXiv  Detail & Related papers  (2023-08-18T13:13:09Z)
• Incentivizing Exploration with Linear Contexts and Combinatorial Actions [9.15749739027059]
  In incentivized bandit exploration, arm choices are viewed as recommendations and are required to be Bayesian incentive compatible. Recent work has shown under certain independence assumptions that after collecting enough initial samples, the popular Thompson sampling algorithm becomes incentive compatible. We give an analog of this result for linear bandits, where the independence of the prior is replaced by a natural convexity condition.
  arXiv  Detail & Related papers  (2023-06-03T03:30:42Z)
• Implicit representation priors meet Riemannian geometry for Bayesian robotic grasping [5.533353383316288]
  In this study, we explore the use of implicit representations to construct scene-dependent priors. Results from both simulation and physical benchmarks showcase the high success rate and promising potential of this approach.
  arXiv  Detail & Related papers  (2023-04-18T08:08:14Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
  We combine adaptive sample size and importance sampling techniques for pairwise learning, with convergence guarantees for nonsmooth convex pairwise loss functions. We demonstrate that sampling opposite instances at each reduces the variance of the gradient, hence accelerating convergence.
  arXiv  Detail & Related papers  (2022-08-08T11:51:01Z)
• Incentivizing Combinatorial Bandit Exploration [87.08827496301839]
  Consider a bandit algorithm that recommends actions to self-interested users in a recommendation system. Users are free to choose other actions and need to be incentivized to follow the algorithm's recommendations. While the users prefer to exploit, the algorithm can incentivize them to explore by leveraging the information collected from the previous users.
  arXiv  Detail & Related papers  (2022-06-01T13:46:25Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• Simulation-Assisted Decorrelation for Resonant Anomaly Detection [1.5675763601034223]
  A growing number of weak- and unsupervised machine learning approaches to anomaly detection are being proposed. One of the examples is the search for resonant new physics, where a bump hunt can be performed in an invariant mass spectrum. We explore two solutions to this challenge by incorporating minimally prototypical simulation into the learning.
  arXiv  Detail & Related papers  (2020-09-04T14:02:15Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.