# Reductive MDPs: A Perspective Beyond Temporal Horizons

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 46 references that are in the map.
- First posted on arXiv 15 May 2022.

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

- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case](https://mlsanity.com/paper/2102.05284/) (2021)
- [Topological Value Iteration Algorithms](https://mlsanity.com/paper/1401.3910/) (2014)
- [On the Complexity of Value Iteration](https://mlsanity.com/paper/1807.04920/) (2018)
- [The Stochastic Shortest Path Problem : A polyhedral combinatorics perspective](https://mlsanity.com/paper/1702.03186/) (2017)
- [Unique End of Potential Line](https://mlsanity.com/paper/1811.03841/) (2018)
- [Reachability and safety objectives in Markov decision processes on long but finite horizons](https://mlsanity.com/paper/1911.05578/) (2019)
- [Structured Reachability Analysis for Markov Decision Processes](https://mlsanity.com/paper/1301.7361/) (2013)

## Abstract (arXiv)

Solving general Markov decision processes (MDPs) is a computationally hard problem. Solving finite-horizon MDPs, on the other hand, is highly tractable with well known polynomial-time algorithms. What drives this extreme disparity, and do problems exist that lie between these diametrically opposed complexities? In this paper we identify and analyse a sub-class of stochastic shortest path problems (SSPs) for general state-action spaces whose dynamics satisfy a particular drift condition. This construction generalises the traditional, temporal notion of a horizon via decreasing reachability: a property called reductivity. It is shown that optimal policies can be recovered in polynomial-time for reductive SSPs -- via an extension of backwards induction -- with an efficient analogue in reductive MDPs. The practical considerations of the proposed approach are discussed, and numerical verification provided on a canonical optimal liquidation problem.