arXiv:2510.09965cs.LGcs.AI2025-10

提出同态映射框架,实现状态聚合中策略性能无损

Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes

  • 基于同态关系构建状态抽象,保证价值函数线性对应
  • 理论证明在满足条件下可保持最优策略等价性
  • 新算法兼顾效率与性能,适合大规模强化学习问题

状态聚合旨在降低求解马尔可夫决策过程(MDP)的计算复杂度,同时保持原系统的性能。核心挑战在于如何在聚合后的抽象空间中优化策略,使其在原始MDP中仍具最优性,这一性质称为“最优策略等价性”。本文提出一种基于同态概念的抽象框架:当两个马尔可夫链的价值函数呈线性关系时,视为同态。在此理论基础上,建立了最优策略等价性的充分条件。针对该条件不满足的情形,推导出近似误差的上界及目标函数在原始MDP中的性能下界。提出同态策略梯度(HPG)算法,在充分条件下保证最优策略等价;其扩展版本误差有界同态策略梯度(EBHPG)在计算效率与聚合带来的性能损失间取得平衡。实验验证了理论结果,并与七种算法进行了对比。

原文摘要 · Abstract (English)

State aggregation aims to reduce the computational complexity of solving Markov Decision Processes (MDPs) while preserving the performance of the original system. A fundamental challenge lies in optimizing policies within the aggregated, or abstract, space such that the performance remains optimal in the ground MDP-a property referred to as {"}optimal policy equivalence {"}. This paper presents an abstraction framework based on the notion of homomorphism, in which two Markov chains are deemed homomorphic if their value functions exhibit a linear relationship. Within this theoretical framework, we establish a sufficient condition for the equivalence of optimal policy. We further examine scenarios where the sufficient condition is not met and derive an upper bound on the approximation error and a performance lower bound for the objective function under the ground MDP. We propose Homomorphic Policy Gradient (HPG), which guarantees optimal policy equivalence under sufficient conditions, and its extension, Error-Bounded HPG (EBHPG), which balances computational efficiency and the performance loss induced by aggregation. In the experiments, we validated the theoretical results and conducted comparative evaluations against seven algorithms.

强化学习状态聚合同态映射策略优化

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