在几何条件满足时，激励探索可实现高效学习。
Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
- 基于动作集的几何特性设计激励相容算法
- 样本复杂度仅多项式增长，突破指数瓶颈
- 适用于高维线性上下文场景的高效探索
在激励探索模型中，决策者需通过与一系列自利代理人的交互来持续探索和学习。近期研究发现，设计激励相容算法的主要挑战在于获取适量初始数据；一旦获得，即可通过后验采样实现近最优后悔率。然而，在高维上下文中，这一初始探索阶段的样本复杂度可能呈指数级增长，除非能外部获取初始数据。本文证明：当可用动作集满足温和几何条件时，激励相容性不会阻碍后悔率最优性。具体而言，考虑动作位于欧几里得单位球中的线性上下文带模型，我们提出一种激励相容的探索算法，其样本复杂度关于维度及其他参数为多项式级别。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。