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

arXiv: https://arxiv.org/abs/2510.09965 · HTML: https://mlsanity.com/paper/2510.09965/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 11 Oct 2025.

## Builds on (most cited first, 14 of 14)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Continuous MDP Homomorphisms and Homomorphic Policy Gradient](https://mlsanity.com/paper/2209.07364/) (2022)
- [Spectral State Compression of Markov Processes](https://mlsanity.com/paper/1802.02920/) (2018)
- [Policy Gradient Methods in the Presence of Symmetries and State Abstractions](https://mlsanity.com/paper/2305.05666/) (2023)
- [On Passivity, Reinforcement Learning and Higher-Order Learning in Multi-Agent Finite Games](https://mlsanity.com/paper/1808.04464/) (2018)
- [Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions](https://mlsanity.com/paper/2202.13046/) (2022)
- [Demystifying Linear MDPs and Novel Dynamics Aggregation Framework](https://mlsanity.com/paper/2410.24089/) (2024)
- [A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Models](https://mlsanity.com/paper/2304.04916/) (2023)
- [An Adaptive State Aggregation Algorithm for Markov Decision Processes](https://mlsanity.com/paper/2107.11053/) (2021)
- [Control Synthesis for Permutation-Symmetric High-Dimensional Systems With Counting Constraints](https://mlsanity.com/paper/1706.07863/) (2017)

## Abstract (arXiv)

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.