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

• URL: http://arxiv.org/abs/2510.09965v1
• Date: Sat, 11 Oct 2025 02:40:03 GMT
• Title: Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes
• Abstract summary: Homomorphic Policy Gradient (HPG) guarantees optimal policy equivalence under sufficient conditions.<n>EBHPG balances computational efficiency and the performance loss induced by aggregation.
• Score: 32.156826903097134
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Performance-Driven Environment Abstraction with Multi-Timescale Learning [14.594941665205148]
  We study performance-driven environment abstraction for decision-making in large Markov decision processes.<n>We model abstraction as a controlled approximation obtained by aggregating the state space.<n>For a fixed partition, we establish a performance guarantee that separates value-function approximation error from the loss introduced by action sharing.
  arXiv  Detail & Related papers  (2026-06-16T00:19:23Z)
• High-dimensional reliability-based design optimization using stochastic emulators [0.0]
  This paper proposes a novel RBDO framework based on a simulator viewpoint.<n>Under this formulation, the system response conditioned on a given design is modeled directly through its output distribution.<n>The proposed method yields substantial computational gains, particularly in high-dimensional settings.
  arXiv  Detail & Related papers  (2026-04-07T12:01:50Z)
• Improving monotonic optimization in heterogeneous multi-agent reinforcement learning with optimal marginal deterministic policy gradient [18.64288030584699]
  heterogeneous multi-agent reinforcement learning (MARL)<n>Objectively replace the sequentially computed $Q_psi*(s,a_1:i)$ with the Optimal Marginal Q function $phi_psi*(s,a_1:i)$ derived from Q-functions.<n>Generalized Q Critic (GQC) as the critic function, employing pessimistic uncertainty-constrained loss to optimize different Q-value estimations.
  arXiv  Detail & Related papers  (2025-07-14T07:16:01Z)
• Convergence of Policy Mirror Descent Beyond Compatible Function Approximation [66.4260157478436]
  We develop theoretical PMD general policy classes where we strictly assume a weaker variational dominance and obtain convergence to the best-in-class policy.<n>Our main notion leverages a novel notion induced by the local norm induced by the occupancy- gradient measure.
  arXiv  Detail & Related papers  (2025-02-16T08:05:46Z)
• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) aims to classify both base and novel images using labeled base data. Current approaches inadequately address the intrinsic optimization of the co-occurrence matrix $barA$ based on cosine similarity. We propose a Non-Negative Generalized Category Discovery (NN-GCD) framework to address these deficiencies.
  arXiv  Detail & Related papers  (2024-10-29T07:24:11Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  We present the first finite time global convergence analysis of policy gradient in the context of average reward Markov decision processes (MDPs) Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $Oleft(frac1Tright),$ which translates to $Oleft(log(T)right)$ regret, where $T$ represents the number of iterations.
  arXiv  Detail & Related papers  (2024-03-11T15:25:03Z)
• On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA [21.9585534723895]
  We show that, given a suitable iterate between the GPMs generated by at least geometrically bound to some threshold, the GPMs decrease to some threshold with the residual part of certain "-resi decomposition" In this paper, we demonstrate the superior performance with sub-Gaussian noise settings using the PCA technique.
  arXiv  Detail & Related papers  (2023-12-06T11:41:17Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  We study episodic two-player zero-sum Markov games (MGs) in the offline setting. The goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori.
  arXiv  Detail & Related papers  (2022-02-15T15:39:30Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  We study a planning problem for POMDPs where the system dynamics and measurement channel model is assumed to be known. We find optimal policies for the approximate belief model under mild non-linear filter stability conditions. We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound.
  arXiv  Detail & Related papers  (2020-10-15T00:37:51Z)
• Risk-Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance [3.062772835338966]
  This paper investigates the optimization problem of an infinite stage discrete time Markov decision process (MDP) with a long-run average metric. A performance difference formula is derived and it can quantify the difference of the mean-variance combined metrics of MDPs under any two different policies. A necessary condition of the optimal policy and the optimality of deterministic policies are derived.
  arXiv  Detail & Related papers  (2020-08-09T10:35:35Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  We address the problem of policy evaluation in discounted decision processes, and provide Markov-dependent guarantees on the $ell_infty$error under a generative model. We establish both and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms.
  arXiv  Detail & Related papers  (2020-03-16T17:15:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.