# Monte Carlo Tree Search for Verifying Reachability in Markov Decision Processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2018.

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

- [Formally-Sharp DAgger for MCTS: Lower-Latency Monte Carlo Tree Search using Data Aggregation with Formal Methods](https://mlsanity.com/paper/2308.07738/) (2023)
- [Exact Model-Free Policy Iteration for Co-safe LTL Planning](https://mlsanity.com/paper/2608.05047/) (2026)

## Abstract (arXiv)

The maximum reachability probabilities in a Markov decision process can be computed using value iteration (VI). Recently, simulation-based heuristic extensions of VI have been introduced, such as bounded real-time dynamic programming (BRTDP), which often manage to avoid explicit analysis of the whole state space while preserving guarantees on the computed result. In this paper, we introduce a new class of such heuristics, based on Monte Carlo tree search (MCTS), a technique celebrated in various machine-learning settings. We provide a spectrum of algorithms ranging from MCTS to BRTDP. We evaluate these techniques and show that for larger examples, where VI is no more applicable, our techniques are more broadly applicable than BRTDP with only a minor additional overhead.