# Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2013.

## Built on by (most cited first, 10 of 10)

- [Learning Task Informed Abstractions](https://mlsanity.com/paper/2106.15612/) (2021)
- [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022)
- [Learning Action-based Representations Using Invariance](https://mlsanity.com/paper/2403.16369/) (2024)
- [Fairness and Sequential Decision Making: Limits, Lessons, and Opportunities](https://mlsanity.com/paper/2301.05753/) (2023)
- [Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks](https://mlsanity.com/paper/2107.06405/) (2021)
- [An Adaptive State Aggregation Algorithm for Markov Decision Processes](https://mlsanity.com/paper/2107.11053/) (2021)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)
- [Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions](https://mlsanity.com/paper/2505.22147/) (2025)
- [Adaptive state-action abstractions via rate-distortion](https://mlsanity.com/paper/2606.06123/) (2026)
- [Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates](https://mlsanity.com/paper/2608.06762/) (2026)

## Abstract (arXiv)

We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces. We introduce a property of state space partitions which we call epsilon-homogeneity. Intuitively, an epsilon-homogeneous partition groups together states that behave approximately the same under all or some subset of policies. Borrowing from recent work on model minimization in computer-aided software verification, we present an algorithm that takes a factored representation of an MDP and an 0<=epsilon<=1 and computes a factored epsilon-homogeneous partition of the state space. This partition defines a family of related MDPs - those MDPs with state space equal to the blocks of the partition, and transition probabilities "approximately" like those of any (original MDP) state in the source block. To formally study such families of MDPs, we introduce the new notion of a "bounded parameter MDP" (BMDP), which is a family of (traditional) MDPs defined by specifying upper and lower bounds on the transition probabilities and rewards. We describe algorithms that operate on BMDPs to find policies that are approximately optimal with respect to the original MDP. In combination, our method for reducing a large implicit MDP to a possibly much smaller BMDP using an epsilon-homogeneous partition, and our methods for selecting actions in BMDPs constitute a new approach for analyzing large implicit MDPs. Among its advantages, this new approach provides insight into existing algorithms to solving implicit MDPs, provides useful connections to work in automata theory and model minimization, and suggests methods, which involve varying epsilon, to trade time and space (specifically in terms of the size of the corresponding state space) for solution quality.