Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem

• URL: http://arxiv.org/abs/2508.13963v1
• Date: Tue, 19 Aug 2025 15:55:07 GMT
• Title: Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem
• Authors: Soumyajit Guin, Shalabh Bhatnagar,
• Abstract summary: In this paper we propose two algorithms for the Shortest Path (SSP) problem.<n>SSP problems form an important class of problems in Reinforcement Learning (RL)<n>We show approximation almost-sure convergence for all our algorithms.
• Score: 6.682382456607199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Robust Algorithm for Non-IID Machine Learning Problems with Convergence Analysis [2.4462606119036456]
  We propose an improved numerical algorithm for solving minimax problems based on nonsmooth optimization, quadratic programming and iterative process.<n>Such an algorithm can be widely applied in various fields such as robust optimization, imbalanced learning, etc.
  arXiv  Detail & Related papers  (2025-07-01T14:41:59Z)
• Quantum and classical correlations in shrinking algorithms for optimization [0.0]
  We use quantum computing to solve optimization problems (COPs)<n>In this work, we extend and analyze algorithms that solve COPs by recursively shrinking them.<n>We compare the performance of the algorithms equipped with correlations from the quantum approximate optimization algorithm (QAOA) as well as the classical linear programming (LP) and semi-definite programming (SDP) relaxations.
  arXiv  Detail & Related papers  (2024-04-26T08:29:04Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation [11.345796608258434]
  We provide performance guarantees for a variant of simulation-based policy iteration for controlling Markov decision processes. We analyze two algorithms; the first algorithm involves a least squares approach where a new set of weights associated with feature vectors is obtained via at least squares at each iteration. The second algorithm involves a two-time-scale approximation algorithm taking several steps of gradient descent towards the least squares solution.
  arXiv  Detail & Related papers  (2022-10-13T20:16:19Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Online Robust Reinforcement Learning with Model Uncertainty [24.892994430374912]
  We develop a sample-based approach to estimate the unknown uncertainty set and design a robust Q-learning and robust TDC algorithm. For the robust Q-learning algorithm, we prove that it converges to the optimal robust Q function, and for the robust TDC algorithm, we prove that it converges to some stationary points. Our approach can be readily extended to robustify many other algorithms, e.g., TD, SARSA, and other GTD algorithms.
  arXiv  Detail & Related papers  (2021-09-29T16:17:47Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  We study reinforcement learning with linear function approximation. Existing algorithms only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees. We propose a new algorithm called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with high probability.
  arXiv  Detail & Related papers  (2021-06-22T08:48:56Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
  This paper introduces a new algorithm that combines the major features of RGAs and Shortest Path Tree Algorithm (SPTA) to deal with the Clustered Shortest-Path Tree Problem (CluSPT) To evaluate the performance of the proposed algorithm, Euclidean benchmarks are selected.
  arXiv  Detail & Related papers  (2020-05-05T08:34:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.