mlsanityData to 14 Oct 2026

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

arXiv 2510.09965 ↗First posted 11 Oct 2025cs.LG cs.AI stat.MLcited by 0

Not on the map. Why?

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.

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

14 of 49 references.

References · 14

  1. 2015Trust Region Policy Optimizationcited by 2,580
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  3. 2017Near Optimal Behavior via Approximate State Abstractioncited by 66
  4. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  5. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  6. 2022Continuous MDP Homomorphisms and Homomorphic Policy Gradientcited by 27
  7. 2018Spectral State Compression of Markov Processescited by 18
  8. 2023Policy Gradient Methods in the Presence of Symmetries and State Abstractionscited by 9
  9. 2018On Passivity, Reinforcement Learning and Higher-Order Learning in Multi-Agent Finite Gamescited by 8
  10. 2022Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functionscited by 6
  11. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4
  12. 2023A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Modelscited by 3
2 more
  1. 2021An Adaptive State Aggregation Algorithm for Markov Decision Processescited by 2
  2. 2017Control Synthesis for Permutation-Symmetric High-Dimensional Systems With Counting Constraintscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning
  2. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet
  3. 2024Policy Gradient for Robust Markov Decision Processes
  4. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  5. 2026Low-Complexity Policy Tessellations in Structured Markov Decision Processes
  6. 2025A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
  7. 2026Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
  8. 2024Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs