面向状态依赖可行动作集的马尔可夫决策过程的Bellman-Taylor Score Decoding

# 贝尔曼-泰勒分数解码：用于状态依赖可行动作集马尔可夫决策过程的解码方法  
来源：https://arxiv.org/html/2606.10979  
Yi Chen, Rushuai Yang, Qiang Chen, Dongyan \(Lucy\) Huo  
香港科技大学工业工程与决策分析系  

## 1 引言  

近年来，深度强化学习（DRL）已成为序列决策问题中最成功的算法范式之一。通过将强化学习算法与具有表达力的神经网络函数逼近相结合，DRL 在许多人工智能领域取得了显著的实证成功，例如游戏博弈、机器人控制和自动驾驶赛车（Mnihet al.,2015 (https://arxiv.org/html/2606.10979#bib.bib15); Rajeswaranet al.,2018 (https://arxiv.org/html/2606.10979#bib.bib1); Wurmanet al.,2022 (https://arxiv.org/html/2606.10979#bib.bib4); Tanget al.,2025 (https://arxiv.org/html/2606.10979#bib.bib9)）。这些成功表明，DRL 可以成为从仿真或交互数据中学习复杂控制策略的强大工具，尤其是在精确动态规划在计算上不可行的情况下。  

运筹学（OR）中的许多序列决策问题可以自然地建模为马尔可夫决策过程（MDP）。例如库存控制、排队控制和资源分配。经典动态规划为这些问题提供了一个原则性框架，但随着状态和动作空间的增长，精确求解方法很快变得难以处理。因此，近似动态规划（ADP）和基于仿真的策略优化长期以来一直发挥着重要作用（Bertsekas,2025 (https://arxiv.org/html/2606.10979#bib.bib13); Powell,2011 (https://arxiv.org/html/2606.10979#bib.bib14)）。从数学角度来看，ADP 和 DRL 密切相关：两者都寻求对贝尔曼评估和改进步骤的易处理近似，无论是通过逼近价值函数、动作-价值函数还是策略。这种联系推动了越来越多的工作将 DRL 算法应用于大规模 OR 问题（Delarueet al.,2020 (https://arxiv.org/html/2606.10979#bib.bib35); Dai and Gluzman,2022 (https://arxiv.org/html/2606.10979#bib.bib46); Gijsbrechtset al.,2022 (https://arxiv.org/html/2606.10979#bib.bib48); Harshaet al.,2025 (https://arxiv.org/html/2606.10979#bib.bib36); Xuet al.,2025 (https://arxiv.org/html/2606.10979#bib.bib37); Chenet al.,2026 (https://arxiv.org/html/2606.10979#bib.bib47)）。  

尽管存在这种自然联系，但将现成的 DRL 算法直接应用于运营性 MDP 很少能做到即插即用。一个关键挑战是动作接口。标准的 DRL 实现通常假设动作可以通过简单固定的表示进行枚举、采样和优化。在有限动作问题中，神经网络经常为固定目录中的每个动作输出一个 logit 或值。在连续动作问题中，动作通常表示为固定维度的欧几里得向量，演员网络要么直接输出该向量，要么输出该向量上分布的参数。许多 OR 问题并不符合这两种模板。它们的可行动作通常是状态依赖的、高维的，并且由容量、兼容性和整数性约束隐式定义。  

动作接口的困难是导致运营性 MDP 中成功的 DRL 应用通常需要大量针对具体情况的算法工程化的关键原因。研究人员可能需要设计特定于问题的动作分解、可行性修正、掩码规则或专门的网络架构。这些技术可能有效，但也降低了标准 DRL 求解器作为跨运营性 MDP 可重用工具的程度。从这个意义上说，挑战不仅在于 OR 问题规模大或具有随机性；还在于 OR 模型的自然动作空间通常与标准 DRL 实现预期的动作表示不一致。  

现有文献已在解决此问题方面取得了重要进展。例如，动作表示方法将大型有限动作集嵌入到低维空间中，使得来自一个动作的反馈能够泛化到相似动作（Chandaket al.,2019 (https://arxiv.org/html/2606.10979#bib.bib25); Dulac-Arnoldet al.,2015 (https://arxiv.org/html/2606.10979#bib.bib26)）。可行性保持方法（如掩码、动作消除）可以在存在固定动作目录或简单可行区域时防止执行不可行动作（Huang and Ontañón,2022 (https://arxiv.org/html/2606.10979#bib.bib30); Zahavyet al.,2018 (https://arxiv.org/html/2606.10979#bib.bib31); Phamet al.,2018 (https://arxiv.org/html/2606.10979#bib.bib32)）。最近的一系列工作将强化学习与基于优化的动作选择相结合，要么将学习到的价值信息嵌入到动作选择问题中，要么在策略表示中融入一个优化层（Delarueet al.,2020 (https://arxiv.org/html/2606.10979#bib.bib35); Harshaet al.,2025 (https://arxiv.org/html/2606.10979#bib.bib36); Xuet al.,2025 (https://arxiv.org/html/2606.10979#bib.bib37); Hoppeet al.,2025 (https://arxiv.org/html/2606.10979#bib.bib34)）。这些方法很有价值，但并未完全解决当希望将标准现成 DRL 算法应用于具有状态依赖可行动作集的 MDP 时出现的接口问题。动作表示方法主要针对固定的有限动作目录设计，而许多可行集由约束隐式定义，且可能因太大而无法枚举。掩码和消除也依赖于明确的目录或有限的超集。优化层方法通常将优化得分视为通用的学习效用系数，并需要对该层进行专门的训练。这些方法要么依赖于特定的动作表示，要么依赖于针对特定问题的可行性机制，要么依赖于自定义的基于优化的学习架构。  

在本文中，我们提出了一种新颖的针对具有状态依赖可行动作集的 MDP 的动作接口，称为*贝尔曼-泰勒分数解码*。核心思想是标准化学习接口，而不是运营性动作空间。策略不是直接在非规则的可行动作集上学习，而是在欧几里得空间中学习一个分数向量。然后，动作解码器通过求解原始可行集上的优化问题，将该分数映射为可实现的自然动作。解码器的动机来自动作后贝尔曼延续值（或最优动作-价值函数）的泰勒近似，其中学习到的分数旨在表示动作后系统配置对未来价值的边际影响。这种构造将学习与可行性分离开来。DRL 算法在规则的欧几里得分数空间上运行，而可行性、整数性和组合耦合则由动作解码器处理。一旦指定了解码器，原 MDP 就会诱导出一个潜在分数 MDP，其中动作就是分数向量。然后，标准的连续动作 DRL 算法（例如近端策略优化）可以直接应用于这个诱导问题。重要的是，解码器仅在正向传播中求解，以将采样的分数转换为可行的自然动作。策略梯度更新不需要对解码器进行微分。这与可微优化层方法不同，在后者中，优化器是可训练计算图的一部分，必须通过其梯度或通过代理梯度进行近似。  

所提出的框架并未消除运营性 MDP 固有的困难。相反，它将模型结构限制在解码器中，从而使学习算法保持标准。模型指定了可行动作集、即时奖励以及系统的动作后表示。策略学习状态依赖的分数，解码器将这些分数转换为可行的运营性动作。这为现成的连续动作 DRL 求解器与具有状态依赖、受限且通常是组合动作的 MDP 之间建立了一座桥梁。其权衡在于，解码器诱导的策略类是受限的：原 MDP 中并非每一个可行策略都能由分数解码策略表示。我们的理论分析量化了这一权衡。  

作为该框架的一个应用，我们研究了一个排队网络控制问题。多类别、多服务池排队系统中的动态调度是一个经典且具有实际重要性的问题，应用包括呼叫中心和住院病人溢出管理（Dai and Shi,2019 (https://arxiv.org/html/2606.10979#bib.bib23); Chenet al.,2020 (https://arxiv.org/html/2606.10979#bib.bib8)）。最近的研究也探索了将 DRL 用于此类问题，但成功的实现通常依赖于针对特定问题的动作分解、定制的策略架构或针对排队模型定制的方差减少技术。相比之下，我们的框架允许我们直接应用标准的 PPO 求解器，而无需引入任何额外的特定于问题的算法工程，例如方差减少，而这些在同行的作品中是常见且必要的（Dai and Gluzman,2022 (https://arxiv.org/html/2606.10979#bib.bib46); Donget al.,2025 (https://arxiv.org/html/2606.10979#bib.bib24)）。在这种设置下，贝尔曼-泰勒分数解码本质上成为一种基于学习索引的调度规则：RL 策略学习状态依赖的索引，动作解码器选择总分最大的可行调度动作。通过仿真实验，我们表明得到的解码 PPO 策略在一系列排队实例中优于各种基准。  

总结来说，我们的贡献有三点。  
- •我们为具有状态依赖可行动作集的 MDP 引入了贝尔曼-泰勒分数解码算法框架。该框架将受限的自然动作 MDP 转换为潜在分数 MDP，使得可以在不设计针对可行动作的特定概率分布的情况下应用标准的连续动作 DRL 算法。可行性通过解码器精确保证。  
- •我们提供了一个结构性性能保证，表明我们方法的最优性差距可以分解为结构性逼近误差和来自求解诱导潜在分数 MDP 的算法学习误差。结构性项由动作后延续价值的局部泰勒余项控制，阐明了受限的分数解码策略类何时能够很好地逼近贝尔曼贪婪决策。  
- •我们将该框架应用于一个排队网络控制问题。我们的实现使用潜在分数 MDP 上的标准 PPO 求解器，没有针对排队的特定修改或额外的方差减少机制。数值研究证明了我们方法的优越性能。  

本文剩余部分组织如下。第2节 (https://arxiv.org/html/2606.10979#S2) 回顾相关文献。第3节 (https://arxiv.org/html/2606.10979#S3) 形式化 MDP 设置并介绍背景。第4节 (https://arxiv.org/html/2606.10979#S4) 介绍贝尔曼-泰勒分数解码框架和 PPO 实现，以及性能保证。第5节 (https://arxiv.org/html/2606.10979#S5) 研究一个库存问题作为健全性检查。第6节 (https://arxiv.org/html/2606.10979#S6) 呈现排队网络控制案例研究。第7节 (https://arxiv.org/html/2606.10979#S7) 最后进行总结。  

## 2 相关文献  

### 2.1 深度强化学习与标准动作接口  

对于具有有限状态和动作空间的小规模 MDP，经典动态规划和精确 MDP 方法（包括值迭代、策略迭代和线性规划）提供了精确求解方法（Suttonet al.,1998 (https://arxiv.org/html/2606.10979#bib.bib10)）。然而，当状态和动作空间变大时，由于维数灾难（Bellman,1957 (https://arxiv.org/html/2606.10979#bib.bib11); Powell,2011 (https://arxiv.org/html/2606.10979#bib.bib14)），这些精确方法很快变得计算上不可行。这一挑战催生了关于近似算法的广泛文献，并在近似动态规划方面取得了重大进展（Bertsekas,2025 (https://arxiv.org/html/2606.10979#bib.bib13); Powell,2011 (https://arxiv.org/html/2606.10979#bib.bib14)）。深度强化学习可以视为这种近似范式基于神经网络的扩展，其中价值函数或策略由深度神经网络表示，并从轨迹数据中学习。由于神经网络强大的逼近能力，DRL 在 AI 领域的各种基准问题上取得了显著的实证成功，例如游戏博弈和机器人控制（Mnihet al.,2015 (https://arxiv.org/html/2606.10979#bib.bib15); Rajeswaranet al.,2018 (https://arxiv.org/html/2606.10979#bib.bib1); Wurmanet al.,2022 (https://arxiv.org/html/2606.10979#bib.bib4); Tanget al.,2025 (https://arxiv.org/html/2606.10979#bib.bib9)）。  

一般来说，经典 DRL 算法大致可以分为两类：*基于价值*的方法，包括深度 Q 网络（DQN）及变体（Mnihet al.,2015 (https://arxiv.org/html/2606.10979#bib.bib15)），它们通过神经网络 Q\_θ(s,a) 逼近最优动作-价值函数，并根据 a\_t ∈ argmax_{a∈A(s_t)} Q\_θ(s\_t, a) 选择动作；以及*基于策略*或*演员-评论家*方法，包括近端策略优化（PPO）及变体（Schulmanet al.,2017 (https://arxiv.org/html/2606.10979#bib.bib16)），它们直接参数化策略 π\_θ(a|s)，并使用随机梯度方法（Suttonet al.,1998 (https://arxiv.org/html/2606.10979#bib.bib10)）在 θ 的参数空间（通常是欧几里得空间）上优化期望折扣回报 J(π^θ; ν\_0)。在这两类方法中，深度神经网络作为灵活的函数逼近器，在各种基准问题上展现出强大的实证性能（Rajeswaranet al.,2018 (https://arxiv.org/html/2606.10979#bib.bib1); Wurmanet al.,2022 (https://arxiv.org/html/2606.10979#bib.bib4); Tanget al.,2025 (https://arxiv.org/html/2606.10979#bib.bib9)）。  

然而，标准 DRL 实现中一个常见的隐含假设是它们通常依赖于易处理的动作接口。在离散动作设置中，动作空间通常是规模可控的显式有限动作目录，神经网络为每个候选动作输出一个 logit 或 Q 值（Mnihet al.,2013 (https://arxiv.org/html/2606.10979#bib.bib5),2015 (https://arxiv.org/html/2606.10979#bib.bib15)）。在连续动作设置中，动作通常表示为固定维度的欧几里得向量，策略网络输出概率分布的参数，或直接输出动作向量本身（Schulmanet al.,2017 (https://arxiv.org/html/2606.10979#bib.bib16)）。因此，神经网络架构隐含地假设，一旦给定当前状态，就可以通过简单固定的接口对动作进行评分、采样或优化。  

### 2.2 动作表示与可行性保持策略