# Topological Value Iteration Algorithms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2014.

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

- [Topological Experience Replay](https://mlsanity.com/paper/2203.15845/) (2022)
- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Deflated Dynamics Value Iteration](https://mlsanity.com/paper/2407.10454/) (2024)
- [Heuristic Search for Multi-Objective Probabilistic Planning](https://mlsanity.com/paper/2303.14363/) (2023)
- [Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives](https://mlsanity.com/paper/2304.09930/) (2023)
- [Efficient Constraint Generation for Stochastic Shortest Path Problems](https://mlsanity.com/paper/2604.01855/) (2026)
- [Reductive MDPs: A Perspective Beyond Temporal Horizons](https://mlsanity.com/paper/2205.07338/) (2022)
- [Topology-Guided Modular Actor-Critic Learning for Continuous Systems under Temporal Objectives](https://mlsanity.com/paper/2304.10041/) (2023)
- [Efficient Constraint Generation for Stochastic Shortest Path Problems](https://mlsanity.com/paper/2401.14636/) (2024)
- [A Model for Optimal Resilient Planning Subject to Fallible Actuators](https://mlsanity.com/paper/2405.11402/) (2024)
- [Algorithms for Deciding the Safety of States in Fully Observable Non-deterministic Problems: Technical Report](https://mlsanity.com/paper/2603.15282/) (2026)
- [Spectral Prioritized Sweeping in Nonstationary Reinforcement Learning](https://mlsanity.com/paper/2609.06186/) (2026)

## Abstract (arXiv)

Value iteration is a powerful yet inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, ILAO* and variants of RTDP are state-of-the-art ones. These methods use reachability analysis and heuristic search to avoid some unnecessary backups. However, none of these approaches build the graphical structure of the state transitions in a pre-processing step or use the structural information to systematically decompose a problem, whereby generating an intelligent backup sequence of the state space. In this paper, we present two optimal MDP algorithms. The first algorithm, topological value iteration (TVI), detects the structure of MDPs and backs up states based on topological sequences. It (1) divides an MDP into strongly-connected components (SCCs), and (2) solves these components sequentially. TVI outperforms VI and other state-of-the-art algorithms vastly when an MDP has multiple, close-to-equal-sized SCCs. The second algorithm, focused topological value iteration (FTVI), is an extension of TVI. FTVI restricts its attention to connected components that are relevant for solving the MDP. Specifically, it uses a small amount of heuristic search to eliminate provably sub-optimal actions; this pruning allows FTVI to find smaller connected components, thus running faster. We demonstrate that FTVI outperforms TVI by an order of magnitude, averaged across several domains. Surprisingly, FTVI also significantly outperforms popular heuristically-informed MDP algorithms such as ILAO*, LRTDP, BRTDP and Bayesian-RTDP in many domains, sometimes by as much as two orders of magnitude. Finally, we characterize the type of domains where FTVI excels --- suggesting a way to an informed choice of solver.