Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets

📄 arXiv: 2606.10979v1 📥 PDF

作者: Yi Chen, Rushuai Yang, Qiang Chen, Dongyan, Huo

分类: cs.AI

发布日期: 2026-06-09

💡 一句话要点

提出Bellman-Taylor评分解码以解决状态依赖的MDP问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 马尔可夫决策过程 深度强化学习 状态依赖 评分解码 排队网络控制 优化算法 操作约束

📋 核心要点

  1. 现有的深度强化学习算法难以处理状态依赖的可行动作集，限制了其在复杂决策过程中的应用。
  2. 提出Bellman-Taylor评分解码框架，通过将策略学习转移到评分空间，解决了动作可行性问题。
  3. 在排队网络控制问题中，所提方法在小规模实例中表现接近最优，并在大规模系统中显著提升性能。

📝 摘要（中文）

许多运筹学中的马尔可夫决策过程（MDP）具有状态依赖的可行动作，这些动作由各种操作约束隐式定义。这使得标准深度强化学习（DRL）算法难以应用，因为这些算法通常假设固定的有限动作目录或简单的欧几里得空间。本文提出了Bellman-Taylor评分解码框架，将策略学习转移到欧几里得评分空间，同时通过动作解码器强制执行可行性。通过标准DRL算法优化诱导的潜在评分MDP，而无需通过解码器进行微分。我们提供了性能保证，表明该方法的最优性差距分解为结构近似误差和算法学习误差。最后，我们将该框架应用于排队网络控制问题，策略学习了一种状态依赖的基于索引的调度规则。数值实验表明，在小实例中表现接近最优，并在大系统中显著优于基准。

🔬 方法详解

问题定义：本文旨在解决状态依赖的马尔可夫决策过程中的可行动作集问题。现有的深度强化学习方法通常假设动作集是固定的，无法适应复杂的操作约束，导致性能下降。

核心思路：论文提出的Bellman-Taylor评分解码框架通过将策略学习转移到一个欧几里得评分空间，允许在不直接处理动作可行性约束的情况下进行优化。该设计使得可以利用标准的DRL算法进行优化，而无需对解码器进行微分。

技术框架：整体架构包括三个主要模块：首先，使用Taylor展开构建最优动作值函数的评分表示；其次，通过动作解码器将评分映射回可行动作；最后，利用标准DRL算法优化潜在评分MDP。

关键创新：该方法的创新在于将策略学习转移到评分空间，并通过解码器确保动作的可行性。这一设计与传统方法的根本区别在于不再依赖于固定的动作集。

关键设计：在技术细节上，论文中使用了特定的损失函数来优化评分与实际动作之间的映射，并设计了适应性网络结构以处理复杂的状态空间。

📊 实验亮点

在排队网络控制问题的实验中，所提方法在小规模实例中实现了接近最优的性能，并在大规模系统中相比基准方法显著提高了性能，展示了该框架在实际应用中的有效性和优势。

🎯 应用场景

该研究的潜在应用领域包括复杂的调度问题、资源分配和动态系统控制等。通过有效处理状态依赖的可行动作集，Bellman-Taylor评分解码框架能够在实际操作中提供更优的决策支持，提升系统效率和响应能力，具有重要的实际价值和未来影响。

📄 摘要（原文）

Many Markov decision processes (MDPs) in operations research have feasible actions that are state dependent and defined implicitly by various operational constraints. These features make it difficult to use standard deep reinforcement learning (DRL) algorithms, whose action interfaces typically assume either a fixed finite action catalog or a simple Euclidean space. Motivated by a Taylor expansion of the optimal action-value function, we propose Bellman--Taylor score decoding, a framework that moves policy learning to a Euclidean score space while enforcing feasibility through an action decoder. The induced latent-score MDP then can be optimized by standard DRL algorithms without differentiating through the decoder. We provide a performance guarantee showing that the optimality gap of this approach decomposes into a structural approximation error and an algorithmic learning error. Lastly, we apply this framework to a queueing network control problem, where the policy essentially learns a state-dependent index-based dispatching rule. Numerical experiments show near-optimal performance in small instances and considerable improvements over benchmarks in larger systems.