# Performance Guarantees for Homomorphisms Beyond Markov Decision Processes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2018.

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

- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [On the Convergence of Bounded Agents](https://mlsanity.com/paper/2307.11044/) (2023)
- [Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction](https://mlsanity.com/paper/2310.06513/) (2023)
- [Reducing Planning Complexity of General Reinforcement Learning with Non-Markovian Abstractions](https://mlsanity.com/paper/2112.13386/) (2021)

## Abstract (arXiv)

Most real-world problems have huge state and/or action spaces. Therefore, a naive application of existing tabular solution methods is not tractable on such problems. Nonetheless, these solution methods are quite useful if an agent has access to a relatively small state-action space homomorphism of the true environment and near-optimal performance is guaranteed by the map. A plethora of research is focused on the case when the homomorphism is a Markovian representation of the underlying process. However, we show that near-optimal performance is sometimes guaranteed even if the homomorphism is non-Markovian. Moreover, we can aggregate significantly more states by lifting the Markovian requirement without compromising on performance. In this work, we expand Extreme State Aggregation (ESA) framework to joint state-action aggregations. We also lift the policy uniformity condition for aggregation in ESA that allows even coarser modeling of the true environment.