用图神经网络学习动态匹配的最优策略,能根据实时情况自动决策何时匹配。
Learning Optimal Dynamic Matching via Graph Neural Networks

- 基于强化学习构建图神经网络模型,学习匹配时机与对象的最优策略。
- 在肾配型等场景中,相比传统规则提升匹配效率,尤其在信息不确定时表现更好。
- 适合研究动态资源分配、智能匹配系统的人参考,可直接用于实际调度场景。
动态匹配市场需要决定何时匹配以及与谁匹配:即时匹配虽可获益,但会移除可能带来更优未来机会的参与者。本文提出一种基于价值的强化学习框架,用于有限、演化的加权图上的该问题。研究了无限周期连续时间模型,包含随机到达、节点类型转移、边生成和外生退出。证明了事件时间约简:无需损失最优性,规划者只需在每次外生事件后立即行动,然后等待下一次事件。进一步表明,最优边级Q函数可通过后决策残差图上的单一延续值函数刻画,将学习目标从状态-动作值简化为图值。精确动作选择仍需组合优化;本文用图神经网络近似该值函数,通过时序差分学习训练,并在前向贪心匹配启发式中使用。在二元类型基准中,所学策略显著优于即时匹配和阈值贪心规则,能保留共用节点以应对稀有高价值匹配,仅在池子较厚时才进行低价值匹配。在肾配对捐赠基准中,当退出不可预测时性能接近即时贪心,在预警可靠时恢复患者匹配逻辑,且在中间预警概率下优于即时贪心与患者贪心中的更优者。结果表明,残差图价值学习可生成依赖状态的动态匹配策略,能自适应已实现的连通性与退出信息。
原文摘要 · Abstract (English)
Dynamic matching markets require decisions about whom to match and when: matching now yields value but removes participants who may create better future opportunities. We develop a value-based reinforcement-learning framework for this problem on finite, evolving weighted graphs. We study an infinite-horizon continuous-time model with stochastic arrivals, node-type transitions, edge realizations, and exogenous exits. We prove an event-time reduction: without loss of optimality, the planner acts immediately after each exogenous event and then waits for the next one. We further show that the optimal edge-wise $Q$-function is characterized by a single continuation-value function on post-decision residual graphs, reducing the learned object from state-action values to graph values. Exact action selection still requires combinatorial matching optimization; we approximate the value with a graph neural network, train it by temporal-difference learning, and use it in a forward-greedy matching heuristic. In a binary-type benchmark, the learned policy substantially outperforms immediate and threshold-greedy rules by preserving common nodes for rare arrivals of valuable matches while forming lower-value matches only in thick pools. In a kidney paired donation benchmark, it performs similarly to immediate greedy when exits are unpredictable, recovers the logic of patient matching when warnings are reliable, and outperforms the better of Immediate Greedy and Patient Greedy across intermediate warning probabilities. These results show that residual-graph value learning yields state-dependent dynamic matching policies that adapt to realized connectivity and exit information.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。