# Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 11 of its 44 references that are in the map.
- First posted on arXiv 19 Aug 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [On the Convergence of SARSA with Linear Function Approximation](https://mlsanity.com/paper/2202.06828/) (2022)
- [High-Accuracy Model-Based Reinforcement Learning, a Survey](https://mlsanity.com/paper/2107.08241/) (2021)
- [Policy Optimization for Stochastic Shortest Path](https://mlsanity.com/paper/2202.03334/) (2022)
- [A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions](https://mlsanity.com/paper/1502.01953/) (2015)
- [The Stochastic Shortest Path Problem : A polyhedral combinatorics perspective](https://mlsanity.com/paper/1702.03186/) (2017)
- [Actor-Critic or Critic-Actor? A Tale of Two Time Scales](https://mlsanity.com/paper/2210.04470/) (2022)
- [Variations on the Stochastic Shortest Path Problem](https://mlsanity.com/paper/1411.0835/) (2014)
- [Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality](https://mlsanity.com/paper/2206.04921/) (2022)

## Abstract (arXiv)

In this paper we propose two algorithms in the tabular setting and an algorithm for the function approximation setting for the Stochastic Shortest Path (SSP) problem. SSP problems form an important class of problems in Reinforcement Learning (RL), as other types of cost-criteria in RL can be formulated in the setting of SSP. We show asymptotic almost-sure convergence for all our algorithms. We observe superior performance of our tabular algorithms compared to other well-known convergent RL algorithms. We further observe reliable performance of our function approximation algorithm compared to other algorithms in the function approximation setting.