Linear Occupancy Homomorphisms for Discounted Markov Decision Processes
Abstract
We introduce linear occupancy homomorphisms (LOHs), a class of Markov decision process (MDP) transformations that defines the MDP homomorphism over the feasible occupancy measure space of MDPs. In contrast to classic MDP homomorphism frameworks, which are defined through mappings over the state and state-action spaces, LOHs map between occupancy measure spaces and are representable as linear transformation matrices that expose important structural properties of the homomorphism itself. For this class of MDP transformations, we derive finite dimensional linear inequality constraints that certify when a candidate transformation matrix is a valid LOH and derive the corresponding transformed MDP. We further establish a connection between LOHs, soft MDP homomorphisms, and factored matrix robust MDPs. When the linear transformation matrix is invertible, we prove that the original MDP is equivalent to a constrained MDP after the homomorphic transformation, and derive necessary and sufficient conditions under which the LOH preserves the optimal value. We illustrate the benefits of LOHs in two settings: improving robust MDP solutions by transforming nonrectangular parameter uncertainty sets into homomorphic rectangular MDPs, and decomposing a large MDP into smaller independent MDPs.
Related
- Differential Properties of Objective and Value Functions for Discounted Markov Decision Processes with Finite State and Action Sets
- Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
- Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
- Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
BibTeX
@misc{liu2026linear,
title = {{Linear Occupancy Homomorphisms for Discounted Markov Decision Processes}},
author = {Yihan Liu and Sarah H. Q. Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07441},
eprint = {2610.07441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07441},
}
RIS
TY - UNPB
TI - Linear Occupancy Homomorphisms for Discounted Markov Decision Processes
AU - Yihan Liu
AU - Sarah H. Q. Li
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.07441
UR - https://arxiv.org/abs/2610.07441
AB - We introduce linear occupancy homomorphisms (LOHs), a class of Markov decision process (MDP) transformations that defines the MDP homomorphism over the feasible occupancy measure space of MDPs. In contrast to classic MDP homomorphism frameworks, which are defined through mappings over the state and state-action spaces, LOHs map between occupancy measure spaces and are representable as linear transformation matrices that expose important structural properties of the homomorphism itself. For this class of MDP transformations, we derive finite dimensional linear inequality constraints that certify when a candidate transformation matrix is a valid LOH and derive the corresponding transformed MDP. We further establish a connection between LOHs, soft MDP homomorphisms, and factored matrix robust MDPs. When the linear transformation matrix is invertible, we prove that the original MDP is equivalent to a constrained MDP after the homomorphic transformation, and derive necessary and sufficient conditions under which the LOH preserves the optimal value. We illustrate the benefits of LOHs in two settings: improving robust MDP solutions by transforming nonrectangular parameter uncertainty sets into homomorphic rectangular MDPs, and decomposing a large MDP into smaller independent MDPs.
ER -