# On the convergence of optimistic policy iteration for stochastic shortest path problem

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

## Key facts

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

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

- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure](https://mlsanity.com/paper/2102.00030/) (2021)
- [On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs](https://mlsanity.com/paper/2209.02864/) (2022)
- [Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates](https://mlsanity.com/paper/2606.10580/) (2026)
- [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024)
- [Stochastic Path Planning in Correlated Obstacle Fields](https://mlsanity.com/paper/2509.19559/) (2025)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)
- [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)

In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and TD(λ) methods for the policy evaluation step under the condition that the termination state will eventually be reached almost surely.