在稀疏更新下优化匹配收益，降低计算开销的同时保持高效性能。
Stochastic Matching Bandits with Rare Optimization Updates
- 采用批量更新策略，仅在极少数轮次执行复杂优化
- 实现近似最优的√T阶后悔上界，计算成本大幅下降
- 适合大规模动态匹配场景，如推荐系统与资源调度
我们提出一种基于多项式对数几率（MNL）选择模型的随机匹配强化学习框架。在该设定中，一侧有 $N$ 个代理，另一侧有 $K$ 个臂，每个臂根据未知偏好从分配池中随机选择一个代理并产生相应奖励，整个过程持续 $T$ 轮。目标是通过最大化成功匹配的累积收益来最小化后悔值。直接方法需每轮求解一个 NP 难的组合优化问题，计算成本过高。为此，我们设计了批量算法，将匹配分配的更新次数限制为 $Θ(\log\log T)$ 次。通过仅在极少数轮次调用昂贵的组合优化，算法显著降低整体计算开销，同时仍能保证 $ ilde{\mathcal{O}}(\sqrt{T})$ 的后悔上界。
原文摘要 · Abstract (English)
We introduce a bandit framework for stochastic matching under the multinomial logit (MNL) choice model. In our setting, $N$ agents on one side are assigned to $K$ arms on the other side, where each arm stochastically selects an agent from its assigned pool according to unknown preferences and yields a corresponding reward over a horizon $T$. The objective is to minimize regret by maximizing the cumulative revenue from successful matches. A naive approach requires solving an NP-hard combinatorial optimization problem at every round, resulting in a prohibitive computational cost. To address this challenge, we propose batched algorithms that strategically limit the number of times matching assignments are updated to $Θ(\log\log T)$ over the entire horizon. By invoking expensive combinatorial optimization only on a vanishing fraction of rounds, our algorithms substantially reduce overall computational overhead while still achieving a regret bound of $\widetilde{\mathcal{O}}(\sqrt{T})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。