Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2026, Vol. 60 Issue (12): 2623-2632    DOI: 10.3785/j.issn.1008-973X.2026.12.008
计算机技术     
基于正交投影的同态状态抽象与策略优化
赵亮(),李永强*(),赵硕
浙江工业大学 信息工程学院，浙江 杭州 310023
Homomorphic state abstraction and policy optimization based on orthogonal projection
Liang ZHAO(),Yongqiang LI*(),Shuo ZHAO
School of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China
 全文: PDF(1381 KB)   HTML
摘要：

针对马尔可夫决策过程（MDP）中现有同态状态抽象方法因依赖伪逆计算而导致的数值不稳定及性能下界松弛问题，提出基于正交投影的同态马尔可夫链构建方法. 通过在编码矩阵中引入正交约束来替代传统最小二乘投影，显著提升了抽象映射的稳定性. 在此框架下，推导得到可计算的策略性能下界，设计策略梯度算法对该下界进行直接优化，从而实现抽象表示与策略参数的联合更新. 结果表明，与7种基线算法相比，本文方法在多种包含对称与复杂拓扑结构的任务中，在收敛速度、稳定性和最终回报上均展现出显著优势；在结构性瓶颈任务中，该方法能够有效抑制训练振荡，同时获得更紧致的性能下界.
关键词： 强化学习;  同态马尔可夫链;  状态抽象;  正交投影;  策略梯度    
Abstract:

An orthogonal projection-based method for constructing homomorphic Markov chains was proposed aiming at the problem of the numerical instability and loose performance lower bounds in homomorphic state abstraction for Markov decision process (MDP), which were caused by pseudo-inverse calculations. Orthogonal constraints were introduced into the encoding matrix to replace the traditional least-squares projection. Then the stability of the abstract mapping was significantly enhanced. A computable policy performance lower bound was derived within this framework. A policy gradient method was designed for the direct optimization of this bound. Then the abstract representations and the policy parameters were jointly updated. Results showed that significant advantages were consistently demonstrated in terms of convergence speed, stability and final returns compared with seven baseline algorithms in various tasks with symmetric and complex topological structures. Training oscillations were effectively suppressed, and a tighter performance lower bound was obtained in structural bottleneck tasks.
Key words: reinforcement learning    homomorphic Markov chain    state abstraction    orthogonal projection    policy gradient
收稿日期: 2025-12-15 出版日期: 2026-10-21
CLC:  TP 181  
基金资助: 国家自然科学基金资助项目（U2341216）.
通讯作者: 李永强     E-mail: zl2024@zjut.edu.cn;yqli@zjut.edu.cn
作者简介: 赵亮（2002—），男，硕士生，从事强化学习的研究. orcid.org/0009-0005-8795-2008.E-mail：zl2024@zjut.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
赵亮
李永强
赵硕

引用本文:

赵亮,李永强,赵硕. 基于正交投影的同态状态抽象与策略优化[J]. 浙江大学学报(工学版), 2026, 60(12): 2623-2632.

Liang ZHAO,Yongqiang LI,Shuo ZHAO. Homomorphic state abstraction and policy optimization based on orthogonal projection. Journal of ZheJiang University (Engineering Science), 2026, 60(12): 2623-2632.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2026.12.008    或    https://www.zjujournals.com/eng/CN/Y2026/V60/I12/2623

图 1  不同马尔可夫链之间的关系示意图
任务名称任务说明
随机模型[25]转移密度为10%~100%，奖励为0~1.0
弱耦合MDP[26]由具有‘簇内转移稠密、簇间转移稀疏’特征的不相交状态簇构成的复杂系统
四室网格世界(Room)[27]动作成功率为0.8的持续任务
双队列管理问题[28]涉及9种联合操作的串行服务器负载平衡问题[29]
表 1  实验任务设置与参数说明
任务名称参数设置
$|{S}| $$ |{A}| $
随机模型$ 100 $$10 $
弱耦合MDP$ 100 $$ 10 $
四室网格世界(Room)$ 100 $$ 10 $
双队列管理问题$ 100 $$ 10 $
表 2  各基准任务状态和动作空间配置
图 2  不同抽象率的策略性能与下界的对比
图 3  本文方法与 EBHPG 在不同任务下的性能及下界差异对比
图 4  大状态空间中不同方法的性能对比
1 赵威, 张万枝, 侯加林, 等 基于多智能体强化学习的农业机器人路径规划方法[J]. 浙江大学学报(工学版), 2025, 59 (7): 1492- 1503
Zhao Wei, Zhang Wanzhi, Hou Jialin, et al A path planning method based on multi-agent reinforcement learning for agricultural robots[J]. Journal of Zhejiang University(Engineering Science), 2025, 59 (7): 1492- 1503
2 高洪伟, 尚秉旭, 张鑫康, 等 基于可达集和强化学习的智能汽车决策规划[J]. 浙江大学学报(工学版), 2025, 59 (9): 1996- 2004
Gao Hongwei, Shang Bingxu, Zhang Xinkang, et al Decision-making and planning of intelligent vehicles based on reachable sets and reinforcement learning[J]. Journal of Zhejiang University(Engineering Science), 2025, 59 (9): 1996- 2004
3 汤佳伟, 郭铁铮, 闻英友 基于强化学习的Kubernetes云边协同计算调度算法[J]. 浙江大学学报(工学版), 2025, 59 (11): 2400- 2408
Tang Jiawei, Guo Tiezheng, Wen Yingyou Computing scheduling algorithm for Kubernetes cloud-edge synergy based on reinforcement learning[J]. Journal of Zhejiang University(Engineering Science), 2025, 59 (11): 2400- 2408
4 Azar M G, Munos R, Kappen H J Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model[J]. Machine Learning, 2013, 91 (3): 325- 349
doi: 10.1007/s10994-013-5368-1
5 Gao Bin, Pavel L On passivity, reinforcement learning, and higher order learning in multiagent finite games[J]. IEEE Transactions on Automatic Control, 2021, 66 (1): 121- 136
doi: 10.1109/TAC.2020.2978037
6 Sidford A, Wang Mengdi, Wu Xian, et al Variance reduced value iteration and faster algorithms for solving Markov decision processes[J]. Naval Research Logistics, 2023, 70 (5): 423- 442
doi: 10.1002/nav.21992
7 Aoki M Some approximation methods for estimation and control of large-scale systems[J]. IEEE Transactions on Automatic Control, 1978, 23 (2): 173- 182
doi: 10.1109/TAC.1978.1101705
8 Lastman G, Sinha N A comparison of the balanced matrix method and the aggregation method of model reduction[J]. IEEE Transactions on Automatic Control, 1985, 30 (3): 301- 304
doi: 10.1109/TAC.1985.1103941
9 Li Haitao, Liu Yang, Wang Shunli, et al State feedback stabilization of large-scale logical control networks via network aggregation[J]. IEEE Transactions on Automatic Control, 2021, 66 (12): 6033- 6040
doi: 10.1109/TAC.2021.3057139
10 Sahabandu D, Moothedath S, Allen J, et al RL-ARNE: a reinforcement learning algorithm for computing average reward Nash equilibrium of nonzero-sum stochastic games[J]. IEEE Transactions on Automatic Control, 2024, 69 (11): 7824- 7831
doi: 10.1109/TAC.2024.3403693
11 杜晓昕, 王浩, 崔连和, 等 基于聚类和探测精英引导的蜻蜓算法[J]. 浙江大学学报 (工学版), 2022, 56 (5): 977- 986
Du Xiaoxin , Wang Hao, Cui Lianhe, et al Dragonfly algorithm based on clustering and probe elite guidance[J]. Journal of Zhejiang University (Engineering Science), 2022, 56 (5): 977- 986
12 Bertsekas D P, Castanon D A Adaptive aggregation methods for infinite horizon dynamic programming[J]. IEEE Transactions on Automatic Control, 1989, 34 (6): 589- 598
doi: 10.1109/9.24227
13 Li Lihong, Walsh T J, Littman M L. Towards a unified theory of state abstraction for MDPs [C] // Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics. Fort Lauderdale: Florida Atlantic University, 2006: 531–539.
14 Whitehead S D, Ballard D H Learning to perceive and act by trial and error[J]. Machine Learning, 1991, 7 (1): 45- 83
doi: 10.1023/A:1022619109594
15 Abel D, Hershkowitz D, Littman M L. Near optimal behavior via approximate state abstraction [C] // International Conference on Machine Learning, 2016: 2915–2924.
16 Ravindran B. An algebraic approach to abstraction in reinforcement learning [D]. Amherst: University of Massachusetts Amherst, 2004: 1-182.
17 Ferns N, Panangaden P, Precup D Bisimulation metrics for continuous Markov decision processes[J]. SIAM Journal on Computing, 2011, 40 (6): 1662- 1714
doi: 10.1137/10080484X
18 Van der Pol E, Worrall D E, Van Hoof H, et al. MDP homomorphic networks: Group symmetries in reinforcement learning [C] // Advances in Neural Information Processing Systems. Red Hook: Curran Associates, Inc. 2020, 33: 4199–4210.
19 Zhao Shuo, Li Yongqiang, Feng Yu, et al. Homomorphic mappings for value-preserving state aggregation in Markov decision processes [PP/OL]. arXiv (2025-10-11)[2025-12-01]. https://arxiv.org/abs/2510.09965.
20 Mahadevan S, Maggioni M Proto-value functions: a Laplacian framework for learning representation and control in Markov decision processes[J]. Journal of Machine Learning Research, 2007, 8: 2169- 2231
21 Geist M, Scherrer B. Off-policy learning with linear function approximation [C] // Proceedings of the 31st International Conference on Machine Learning, 2014: 262–270.
22 Ravindran B, Barto A G. Approximate homomorphisms: a framework for non-exact minimization in Markov decision processes [C] // Proceedings of the 5th International Conference on Knowledge Based Computer Systems. Mumbai: Allied Publishers, 2004.
23 Bao Bing, Yin Baoqun , Xi Hongsheng. Infinite-horizon policy-gradient estimation with variable discount factor for Markov decision process [C] //3rd International Conference on Innovative Computing Information and Control. Dalian: IEEE, 2008: 584–584.
24 Ferns N, Precup D. Bisimulation metrics are optimal value functions [C] // Proceedings of the Conference on Uncertainty in Artificial Intelligence. Quebec City: AUAI Press, 2014: 210–219.
25 Forghieri O, Castel H, Hyon E, et al. Progressive state space disaggregation for infinite horizon dynamic programming [C] // Proceedings of the 34th International Conference on Automated Planning and Scheduling. Banff: AAAI Press, 2024, 34(1): 221–229.
26 Sutton R S, Precup D, Singh S Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning[J]. Artificial Intelligence, 1999, 112 (1/2): 181- 211
doi: 10.1016/s0004-3702(99)00052-1
27 Sutton R S, Barto A G. Reinforcement learning: an introduction [M]. Cambridge: MIT Press, 2018.
28 Ohno K, Ichiki K Computing optimal policies for controlled tandem queueing systems[J]. Operations Research, 1987, 35 (1): 121- 126
doi: 10.1287/opre.35.1.121
29 Tournaire T, Jin Y, Aghasaryan A, et al. Factored reinforcement learning for auto-scaling in tandem queues [C] // Proceedings of the IEEE/IFIP Network Operations and Management Symposium. Budapest: IEEE, 2022: 1–7.
30 Ayoub A, Jia Z, Szepesvari C, et al. Model-based reinforcement learning with value-targeted regression [C] // Proceedings of the 37th International Conference on Machine Learning, 2020: 463–474.
31 Chen Guanting, Gaebler J D, Peng M, et al. An adaptive state aggregation algorithm for Markov decision processes [PP/OL]. arXiv (2021-07-23)[2025-12-01]. https://arxiv.org/abs/2107.11053.
32 Ishfaq H, Cui Qiwen, Nguyen V, et al. Randomized exploration in reinforcement learning with general value function approximation [C]// Proceedings of the 38th International Conference on Machine Learning, 2021: 4607–4616.
[1] 连远锋,范树玉,张本哲,王森. 融合几何约束特征提取与多奖励协同优化的仿生步态控制[J]. 浙江大学学报(工学版), 2026, 60(9): 1862-1871.
[2] 宋莉,宛袁玉,宋明黎. 基于混合空洞注意力机制的图卷积强化学习[J]. 浙江大学学报(工学版), 2026, 60(9): 1980-1990.
[3] 邢海军,施怡沁,王麒玮,杨晓,庄世杰. 基于灵活性资源的配电网故障恢复研究综述[J]. 浙江大学学报(工学版), 2026, 60(9): 2059-2076.
[4] 曹宁博,万启超,赵利英,李梓萌,黄宝林. 集成多智能体强化学习和最大压强控制的混行交叉口协同控制[J]. 浙江大学学报(工学版), 2026, 60(8): 1819-1831.
[5] 罗桥,陈俊,耿杰,唐朝阳,傅春耘. 基于行车信息的混合动力汽车能量管理策略综述[J]. 浙江大学学报(工学版), 2026, 60(7): 1539-1556.
[6] 陈浪,刘增力,赵宣植. 基于自适应课程强化学习的多无人艇对抗围捕决策[J]. 浙江大学学报(工学版), 2026, 60(7): 1369-1380.
[7] 陈勇,杜习之,姜一炜,易文超,裴植,纪祖臻. 考虑劣化维护的单机调度深度强化学习模型和算法[J]. 浙江大学学报(工学版), 2026, 60(7): 1528-1538.
[8] 商益铭,杜昌平,杨睿,方天睿,杜泽安,郑耀. 动态环境无人机导航的安全分层强化学习框架[J]. 浙江大学学报(工学版), 2026, 60(6): 1240-1250.
[9] 张艺炜,崔鑫,赵庆慧,陈燕. 无人机辅助车联网NOMA协同缓存优化[J]. 浙江大学学报(工学版), 2026, 60(6): 1289-1298.
[10] 汪洋,刘红超,田池,吴兵,张笛. 航线交换机制下多船避碰的策略学习与博弈决策[J]. 浙江大学学报(工学版), 2026, 60(5): 964-976.
[11] 杨青青,唐润朋,彭艺. 通信感知一体化系统中的联合波形与相移设计[J]. 浙江大学学报(工学版), 2026, 60(4): 906-914.
[12] 宋莉,宛袁玉,金苍宏,宋明黎. 基于对抗图生成的动态蒙特卡洛强化学习[J]. 浙江大学学报(工学版), 2026, 60(12): 2613-2622.
[13] 刘沛丰,杨凡,黄杰,余成波. 基于超图神经网络的车联网资源分配方法[J]. 浙江大学学报(工学版), 2026, 60(11): 2472-2481.
[14] 李幸星,杨凡,黄杰,赖显智,姚凤航,蔡杰良,张妮. 面向车联网差异化干扰的联邦强化学习资源管理[J]. 浙江大学学报(工学版), 2026, 60(10): 2207-2214.
[15] 辛垚辉,李永强,冯宇,胡磊. 随机方差缩减的递归动量策略梯度方法[J]. 浙江大学学报(工学版), 2026, 60(10): 2247-2258.