Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem
This work addresses a foundational problem in reinforcement learning that affects various cost-criteria formulations, though it appears incremental with improvements over existing methods.
The authors tackled the Stochastic Shortest Path (SSP) problem in reinforcement learning by proposing two tabular algorithms and one function approximation algorithm, showing asymptotic almost-sure convergence and reporting superior performance compared to other convergent RL algorithms in tabular settings and reliable performance in function approximation settings.
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.