# An Adaptive State Aggregation Algorithm for Markov Decision Processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 31 references that are in the map.
- First posted on arXiv 23 Jul 2021.

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

- [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)
- [Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations](https://mlsanity.com/paper/1808.03971/) (2018)
- [State Aggregation Learning from Markov Transition Data](https://mlsanity.com/paper/1811.02619/) (2018)
- [Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1910.08151/) (2019)
- [Feature-Based Aggregation and Deep Reinforcement Learning: A Survey and Some New Implementations](https://mlsanity.com/paper/1804.04577/) (2018)
- [Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes](https://mlsanity.com/paper/1302.1533/) (2013)
- [Balancing a CartPole System with Reinforcement Learning -- A Tutorial](https://mlsanity.com/paper/2006.04938/) (2020)

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

- [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022)
- [Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes](https://mlsanity.com/paper/2510.09965/) (2025)

## Abstract (arXiv)

Value iteration is a well-known method of solving Markov Decision Processes (MDPs) that is simple to implement and boasts strong theoretical convergence guarantees. However, the computational cost of value iteration quickly becomes infeasible as the size of the state space increases. Various methods have been proposed to overcome this issue for value iteration in large state and action space MDPs, often at the price, however, of generalizability and algorithmic simplicity. In this paper, we propose an intuitive algorithm for solving MDPs that reduces the cost of value iteration updates by dynamically grouping together states with similar cost-to-go values. We also prove that our algorithm converges almost surely to within (2varepsilon / (1 - γ)) of the true optimal value in the (ℓ^∞) norm, where (γ) is the discount factor and aggregated states differ by at most (varepsilon). Numerical experiments on a variety of simulated environments confirm the robustness of our algorithm and its ability to solve MDPs with much cheaper updates especially as the scale of the MDP problem increases.