mlsanityData to 14 Oct 2026

Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem

arXiv 2508.13963 ↗First posted 19 Aug 2025cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

11 of 44 references.

References · 11

  1. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  2. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  3. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  4. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  5. 2021High-Accuracy Model-Based Reinforcement Learning, a Surveycited by 13
  6. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  7. 2015A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusionscited by 7
  8. 2017The Stochastic Shortest Path Problem : A polyhedral combinatorics perspectivecited by 7
  9. 2022Actor-Critic or Critic-Actor? A Tale of Two Time Scalescited by 7
  10. 2014Variations on the Stochastic Shortest Path Problemcited by 3
  11. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Mathematical methods of reinforcement learning
  2. 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning
  3. 2026Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning
  4. 2025Reinforcement Learning with Random Time Horizons
  5. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
  6. 2023Understanding Reinforcement Learning Algorithms: The Progress from Basic Q-learning to Proximal Policy Optimization
  7. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game