文件名称：贝叶斯奖励在线匹配-研究论文
文件大小：732KB
文件格式：PDF
更新时间：2024-06-29 20:27:29
Online Matching Bayesian
我们在本文中研究了一个在线匹配问题，其中一个*平台需要将一些有限的资源与随时间顺序到达的不同用户组进行匹配。 每个匹配选项的奖励取决于资源类型和用户到达的时间段。 假设匹配的奖励是未知的，而是从先验已知的概率分布中提取的。 然后，平台需要根据对匹配结果的实时观察，在线学习真正的奖励。 *平台的目标是在不违反资源容量限制的情况下最大化所有匹配的总奖励。 我们将此与贝叶斯奖励的匹配问题表述为具有预算约束的马尔可夫多臂*问题，其中每个臂对应一对资源和一个时间段。 我们设计了我们的算法，首先通过一个宽松的线性程序分别为每个单臂找到策略，然后通过明智的选择标准和精心设计的拉动命令将这些策略组合在一起。 我们证明了我们算法的预期回报至少是最优算法的预期回报 $(\sqrt{2}-1)/2$。 特别是在单一资源的情况下，我们证明该比率至少为 $\sqrt{2}-1$。 我们还设计了数值实验来验证我们算法的性能保证，并将该算法与替代启发式算法进行比较，以说明该算法在各种设置下的良好和稳健的性能。