在资源有限下，用单峰偏好优化用户与选项的匹配，提升长期收益。
Bandits with Single-Peaked Preferences and Limited Resources
- 利用单峰偏好结构设计高效匹配算法
- 在线学习中实现近似最优的累积奖励，误差为 $\tilde O(UKT^{2/3})$
- 适合有排序偏好、资源受限的推荐或调度场景
我们研究一个在线随机匹配问题：算法在 $T$ 轮内依次将 $U$ 个用户匹配到 $K$ 个臂，目标是在预算约束下最大化累积奖励。在无结构假设下，计算最优匹配是 NP-hard 的，导致在线学习不可行。为此，我们聚焦于单峰偏好——社会选择理论中常见的结构，即用户的偏好在共同的臂序上呈单峰分布。我们设计了一个高效的离线预算匹配算法，并将其转化为在线算法，达到 $ ilde O(UKT^{2/3})$ 的遗憾。该方法依赖于一种基于 PQ 树的顺序近似技术。若单峰结构已知，我们进一步提出一种类似 UCB 的高效算法，实现 $ ilde O(U oot{2}{TK})$ 的遗憾界。
原文摘要 · Abstract (English)
We study an online stochastic matching problem in which an algorithm sequentially matches $U$ users to $K$ arms, aiming to maximize cumulative reward over $T$ rounds under budget constraints. Without structural assumptions, computing the optimal matching is NP-hard, making online learning computationally infeasible. To overcome this barrier, we focus on single-peaked preferences -- a well-established structure in social choice theory, where users' preferences are unimodal with respect to a common order over arms. We devise an efficient algorithm for the offline budgeted matching problem, and leverage it into an efficient online algorithm with a regret of $\tilde O(UKT^{2/3})$. Our approach relies on a novel PQ tree-based order approximation method. If the single-peaked structure is known, we develop an efficient UCB-like algorithm that achieves a regret bound of $\tilde O(U\sqrt{TK})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。