在1比特反馈下识别高分项，算法逼近理论最优。
Quantile Multi-Armed Bandits with 1-bit Feedback
- 用噪声二分查找估计分位数收益
- 样本复杂度上界与下界仅差对数因子
- 适合通信受限的决策场景
本文研究一种涉及风险敏感性和通信约束的最佳臂识别变体。学习者目标是识别具有最高分位数回报的臂，而代理（观察回报）与学习者（选择动作）之间的通信被限制为每次臂拉动仅1比特反馈。我们提出一种算法，以噪声二分查找作为子程序，使学习者可通过1比特反馈估计分位数回报。我们推导出该算法的实例相关上界，并针对特定实例提供算法无关的下界，两者在温和条件下仅差对数因子，或在某些低错误概率标度下甚至相差常数因子。该下界即使在无通信约束时也成立，因此我们得出结论：将反馈限制在1比特对样本复杂度的标度影响极小。
原文摘要 · Abstract (English)
In this paper, we study a variant of best-arm identification involving elements of risk sensitivity and communication constraints. Specifically, the goal of the learner is to identify the arm with the highest quantile reward, while the communication from an agent (who observes rewards) and the learner (who chooses actions) is restricted to only one bit of feedback per arm pull. We propose an algorithm that utilizes noisy binary search as a subroutine, allowing the learner to estimate quantile rewards through 1-bit feedback. We derive an instance-dependent upper bound on the sample complexity of our algorithm and provide an algorithm-independent lower bound for specific instances, with the two matching to within logarithmic factors under mild conditions, or even to within constant factors in certain low error probability scaling regimes. The lower bound is applicable even in the absence of communication constraints, and thus we conclude that restricting to 1-bit feedback has a minimal impact on the scaling of the sample complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。