用强化学习解决图上资源博弈问题，自动适应复杂结构。
Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs
- 将多步图资源博弈建模为马尔可夫决策过程，结合动作位移矩阵保证合法性
- DQN与PPO在各类图结构上均超越基线策略，对战自学习模型时胜率稳定50%
- 能有效利用图结构优势，即使初始资源不利也能动态调整策略
图上博弈资源分配（GRAG）涉及两名玩家在多个步骤中争夺图上关键节点，该问题被建模为多步军官布洛托游戏（MCBG）。由于动态动作空间和图结构约束，寻找最优策略极具挑战。为此，我们将MCBG形式化为马尔可夫决策过程（MDP），并采用深度Q网络（DQN）和近端策略优化（PPO）等强化学习方法。为满足图约束，引入动作位移邻接矩阵，在每一步动态生成合法动作集。我们在多种图结构和初始资源分布下评估了强化学习性能，对比随机、贪心及已学习的强化学习策略。实验结果表明，DQN与PPO始终优于基线策略，并在与自学习策略对抗时收敛至50%的平衡胜率。尤其在非对称图中，强化学习智能体成功利用结构优势，即使在初始资源不利条件下仍能自适应调整分配策略。
原文摘要 · Abstract (English)
Game-theoretic resource allocation on graphs (GRAG) involves two players competing over multiple steps to control nodes of interest on a graph, a problem modeled as a multi-step Colonel Blotto Game (MCBG). Finding optimal strategies is challenging due to the dynamic action space and structural constraints imposed by the graph. To address this, we formulate the MCBG as a Markov Decision Process (MDP) and apply Reinforcement Learning (RL) methods, specifically Deep Q-Network (DQN) and Proximal Policy Optimization (PPO). To enforce graph constraints, we introduce an action-displacement adjacency matrix that dynamically generates valid action sets at each step. We evaluate RL performance across a variety of graph structures and initial resource distributions, comparing against random, greedy, and learned RL policies. Experimental results show that both DQN and PPO consistently outperform baseline strategies and converge to a balanced $50\%$ win rate when competing against the learned RL policy. Particularly, on asymmetric graphs, RL agents successfully exploit structural advantages and adapt their allocation strategies, even under disadvantageous initial resource distributions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。