提出新方法解决状态相关动作空间的强化学习难题
Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets
- 将策略学习转至欧氏得分空间，通过解码器保证动作可行性
- 理论证明性能差距由结构误差和学习误差构成，可量化分析
- 在排队网络控制中实现近优性能，大系统优于传统基准
运筹学中的许多马尔可夫决策过程（MDPs）具有依赖状态的可行动作集，且通常由各类运营约束隐式定义。这使得标准深度强化学习（DRL）算法难以应用，因其动作接口通常假设固定有限动作集或简单的欧几里得空间。受最优动作值函数泰勒展开启发，我们提出贝尔曼-泰勒得分解码框架：将策略学习转移至欧氏得分空间，同时通过动作解码器强制可行性。由此生成的潜在得分MDP可直接用标准DRL算法优化，无需对解码器进行反向传播。我们提供了性能保障，表明该方法的最优性差距可分解为结构性近似误差与算法学习误差。最后，我们将此框架应用于排队网络控制问题，发现策略本质上学习了一种状态相关的基于指数的调度规则。数值实验显示，在小规模实例中达到近最优性能，在大规模系统中显著优于基准方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。