# Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 15 references that are in the map.
- First posted on arXiv 29 Jan 2021.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [On the convergence of optimistic policy iteration for stochastic shortest path problem](https://mlsanity.com/paper/1808.08763/) (2018)

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

- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation](https://mlsanity.com/paper/2210.07338/) (2022)
- [Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates](https://mlsanity.com/paper/2606.10580/) (2026)
- [Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts](https://mlsanity.com/paper/2606.15247/) (2026)
- [Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample](https://mlsanity.com/paper/2606.15978/) (2026)

## Abstract (arXiv)

We consider Markov Decision Processes (MDPs) in which every stationary policy induces the same graph structure for the underlying Markov chain and further, the graph has the following property: if we replace each recurrent class by a node, then the resulting graph is acyclic. For such MDPs, we prove the convergence of the stochastic dynamics associated with a version of optimistic policy iteration (OPI), suggested in Tsitsiklis (2002), in which the values associated with all the nodes visited during each iteration of the OPI are updated.