arXiv:2503.01919cs.LGcs.AI2025-03ICLR被引 9

解决复杂组合动作的强化学习,让机器人在多约束下做出更优决策。

Reinforcement learning with combinatorial actions for coupled restless bandits

  • 用神经网络嵌入整数规划,直接优化每步组合动作选择。
  • 在4个新难题上平均比现有方法提升24.8%性能。
  • 适合需要联合决策与复杂约束的现实场景,如资源调度。

强化学习(RL)在解决实际规划问题中应用日益广泛,尤其在处理大状态空间和长时域方面取得进展。然而,许多领域面临的关键瓶颈是现有RL方法难以应对大规模、组合结构的动作空间。在此类场景中,单步可行动作集的表示可能需要复杂的离散优化建模。本文利用将训练好的神经网络嵌入优化问题的最新进展,提出SEQUOIA算法,该算法直接在可行动作空间上优化长期回报。其核心是将Q网络嵌入混合整数规划,以每步选取组合动作。研究聚焦于非独立休息老虎机(restless bandits),这是一类能刻画大量序贯决策问题的模型。我们引入coRMAB,一个包含组合动作且无法分解到各臂的广义休息老虎机类,需直接求解指数级大的联合动作空间。我们在四个含组合约束的新休息老虎机问题上验证SEQUOIA:多重干预、路径约束、二分匹配和容量限制。结果表明,该方法显著优于现有无法同时处理序贯规划与组合选择的方法,在这些困难实例上平均提升24.8%。

原文摘要 · Abstract (English)

Reinforcement learning (RL) has increasingly been applied to solve real-world planning problems, with progress in handling large state spaces and time horizons. However, a key bottleneck in many domains is that RL methods cannot accommodate large, combinatorially structured action spaces. In such settings, even representing the set of feasible actions at a single step may require a complex discrete optimization formulation. We leverage recent advances in embedding trained neural networks into optimization problems to propose SEQUOIA, an RL algorithm that directly optimizes for long-term reward over the feasible action space. Our approach embeds a Q-network into a mixed-integer program to select a combinatorial action in each timestep. Here, we focus on planning over restless bandits, a class of planning problems which capture many real-world examples of sequential decision making. We introduce coRMAB, a broader class of restless bandits with combinatorial actions that cannot be decoupled across the arms of the restless bandit, requiring direct solving over the joint, exponentially large action space. We empirically validate SEQUOIA on four novel restless bandit problems with combinatorial constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints. Our approach significantly outperforms existing methods -- which cannot address sequential planning and combinatorial selection simultaneously -- by an average of 24.8\% on these difficult instances.

强化学习组合优化序贯决策

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。