针对上下文匹配市场,提出自适应贝叶斯算法,有效降低玩家后悔值。
Adaptive Bandit Algorithms for Contextual Matching Markets

- 基于上下文偏好差距设计自适应匹配策略
- 随机场景下实现对数级后悔上界,对抗场景下达次线性后悔
- 适用于动态匹配市场,尤其适合有上下文依赖的推荐系统
我们研究匹配市场的贝叶斯学习问题,其中玩家与臂构成市场两端,玩家效用关于臂的上下文呈线性关系。每轮中,新臂以可观测上下文到来,算法将其匹配给玩家,目标是使每个玩家对稳定匹配基准的后悔最小化。这种上下文结构带来显著复杂性:微小的上下文变化可能仅轻微改变某玩家效用,却完全重构底层基准,导致其他玩家出现大幅后悔。我们分别在随机上下文(来自潜在分布)和对抗上下文(任意)两种情形下提出解决方案。对于随机情形,引入新的最小偏好差距以刻画学习难度,并设计全自适应算法,获得实例相关、多项式对数级的后悔上界;在温和分布假设下,还建立了匹配的实例无关后悔上界与下界。对于对抗情形,提出一个在任意上下文中仍有效的可计算后悔度量,并通过自适应算法实现实例无关的次线性后悔边界。
原文摘要 · Abstract (English)
We study bandit learning in matching markets, where players and arms constitute the two market sides, and the players' utilities are linear in the arm contexts. In each round, new arms arrive with observable contexts. Then, the algorithm matches them to players, aiming to minimize each player's regret against a stable matching benchmark. This contextual structure creates significant complexity: subtle context shifts can slightly alter one player's utility while completely reconfiguring the underlying benchmark, causing large regret spikes for others. We address this in two settings: stochastic contexts, drawn from a latent distribution, and adversarial contexts, which may be arbitrary. For the stochastic case, we introduce a novel minimum preference gap to capture learning difficulty and provide a fully adaptive algorithm with an instance-dependent poly-logarithmic regret upper bound. We also establish matching instance-independent regret upper and lower bounds under a mild distributional assumption. For the adversarial setting, we propose a tractable regret notion that remains valid under arbitrary contexts and achieves an instance-independent sublinear regret bound via an adaptive algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。