Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2026, Vol. 60 Issue (12): 2623-2632    DOI: 10.3785/j.issn.1008-973X.2026.12.008
    
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
Download: HTML     PDF(1381KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 15 December 2025      Published: 21 October 2026
CLC:  TP 181  
Fund:  国家自然科学基金资助项目（U2341216）.
Corresponding Authors: Yongqiang LI     E-mail: zl2024@zjut.edu.cn;yqli@zjut.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Liang ZHAO
Yongqiang LI
Shuo ZHAO
Cite this article:

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.

URL:

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


基于正交投影的同态状态抽象与策略优化

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


关键词： 强化学习,  同态马尔可夫链,  状态抽象,  正交投影,  策略梯度 
Fig.1 Schematic diagram of relationship between different Markov chains
任务名称任务说明
随机模型[25]转移密度为10%~100%，奖励为0~1.0
弱耦合MDP[26]由具有‘簇内转移稠密、簇间转移稀疏’特征的不相交状态簇构成的复杂系统
四室网格世界(Room)[27]动作成功率为0.8的持续任务
双队列管理问题[28]涉及9种联合操作的串行服务器负载平衡问题[29]
Tab.1 Experimental task configurations and parameter descriptions
任务名称参数设置
$|{S}| $$ |{A}| $
随机模型$ 100 $$10 $
弱耦合MDP$ 100 $$ 10 $
四室网格世界(Room)$ 100 $$ 10 $
双队列管理问题$ 100 $$ 10 $
Tab.2 State and action space scales across benchmark tasks
Fig.2 Comparison of strategy performance and lower bound at different abstraction rate
Fig.3 Comparison of performance and lower bound difference between proposed method and EBHPG under different tasks
Fig.4 Performance comparison of different methods in large state space
[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] Yuanfeng LIAN,Shuyu FAN,Benzhe ZHANG,Sen WANG. Bio-inspired gait control integrating geometric constraint feature extraction and multi-reward cooperative optimization[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(9): 1862-1871.
[2] Li SONG,Yuanyu WAN,Mingli SONG. Graph convolutional reinforcement learning via hybrid dilated attention mechanism[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(9): 1980-1990.
[3] Haijun XING,Yiqin SHI,Qiwei WANG,Xiao YANG,Shijie ZHUANG. Review on distribution system restoration based on multiple flexible resources[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(9): 2059-2076.
[4] Ningbo CAO,Qichao WAN,Liying ZHAO,Zimeng LI,Baolin HUANG. Collaborative control of mixed traffic intersections integrating multi-agent reinforcement learning and maximum pressure control[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(8): 1819-1831.
[5] Qiao LUO,Jun CHEN,Jie GENG,Chaoyang TANG,Chunyun FU. Review of energy management strategies for hybrid electric vehicles based on driving information[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(7): 1539-1556.
[6] Lang CHEN,Zengli LIU,Xuanzhi ZHAO. Decision-making for multi-USV adversarial encirclement based on adaptive curriculum reinforcement learning[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(7): 1369-1380.
[7] Yong CHEN,Xizhi DU,Yiwei JIANG,Wenchao YI,Zhi PEI,Zuzhen JI. Deep reinforcement learning models and algorithms for single-machine scheduling considering deteriorated maintenance[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(7): 1528-1538.
[8] Yiming SHANG,Changping DU,Rui YANG,Tianrui FANG,Ze’an DU,Yao ZHENG. Safe hierarchical reinforcement learning framework for dynamic UAV navigation[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(6): 1240-1250.
[9] Yiwei ZHANG,Xin CUI,Qinghui ZHAO,Yan CHEN. Collaborative content caching optimization in UAV-assisted internet of vehicle based on NOMA[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(6): 1289-1298.
[10] Yang WANG,Hongchao LIU,Chi TIAN,Bing WU,Di ZHANG. Multi-ship collision avoidance via route exchange mechanism: strategy learning and game-theoretic decision making[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(5): 964-976.
[11] Qingqing YANG,Runpeng TANG,Yi PENG. Joint waveform and phase shift design in integrated sensing and communication systems[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(4): 906-914.
[12] Li SONG,Yuanyu WAN,Canghong JIN,Mingli SONG. Dynamic Monte-Carlo reinforcement learning based on adversarial graph generation[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(12): 2613-2622.
[13] Peifeng LIU,Fan YANG,Jie HUANG,Chengbo YU. Resource allocation method in vehicular networks based on hypergraph neural networks[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(11): 2472-2481.
[14] Xingxing LI,Fan YANG,Jie HUANG,Xianzhi LAI,Fenghang YAO,Jieliang CAI,Ni ZHANG. Federated reinforcement learning for resource management in vehicular networks with differentiated interferences[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(10): 2207-2214.
[15] Yaohui XIN,Yongqiang LI,Yu FENG,Lei HU. Stochastic variance-reduced recursive momentum policy gradient method[J]. Journal of ZheJiang University (Engineering Science), 2026, 60(10): 2247-2258.