# Policy Optimization for Stochastic Shortest Path arXiv: https://arxiv.org/abs/2202.03334 ยท HTML: https://mlsanity.com/paper/2202.03334/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 38 references that are in the map. - First posted on arXiv 7 Feb 2022. ## Builds on (most cited first, 24 of 24) - [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017) - [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019) - [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020) - [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019) - [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018) - [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020) - [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021) - [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021) - [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020) - [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021) - [No-Regret Exploration in Goal-Oriented Reinforcement Learning](https://mlsanity.com/paper/1912.03517/) (2019) - [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021) - [Dynamic Regret of Policy Optimization in Non-stationary Environments](https://mlsanity.com/paper/2007.00148/) (2020) - [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021) - [Stochastic Shortest Path with Adversarially Changing Costs](https://mlsanity.com/paper/2006.11561/) (2020) - [Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case](https://mlsanity.com/paper/2102.05284/) (2021) - [Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition](https://mlsanity.com/paper/2012.04053/) (2020) - [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021) - [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021) - [Online Learning for Stochastic Shortest Path Model via Posterior Sampling](https://mlsanity.com/paper/2106.05335/) (2021) - [Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP](https://mlsanity.com/paper/2112.09859/) (2021) - [Nearly Optimal Policy Optimization with Stable at Any Time Guarantee](https://mlsanity.com/paper/2112.10935/) (2021) ## Built on by (most cited first, 13 of 13) - [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023) - [Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization](https://mlsanity.com/paper/2302.06834/) (2023) - [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022) - [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023) - [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022) - [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023) - [A Unified Algorithm for Stochastic Path Problems](https://mlsanity.com/paper/2210.09255/) (2022) - [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024) - [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025) - [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023) - [Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem](https://mlsanity.com/paper/2508.13963/) (2025) - [Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework](https://mlsanity.com/paper/2605.10671/) (2026) - [Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees](https://mlsanity.com/paper/2608.17703/) (2026) ## Abstract (arXiv) Policy optimization is among the most popular and successful reinforcement learning algorithms, and there is increasing interest in understanding its theoretical guarantees. In this work, we initiate the study of policy optimization for the stochastic shortest path (SSP) problem, a goal-oriented reinforcement learning model that strictly generalizes the finite-horizon model and better captures many applications. We consider a wide range of settings, including stochastic and adversarial environments under full information or bandit feedback, and propose a policy optimization algorithm for each setting that makes use of novel correction terms and/or variants of dilated bonuses (Luo et al., 2021). For most settings, our algorithm is shown to achieve a near-optimal regret bound. One key technical contribution of this work is a new approximation scheme to tackle SSP problems that we call textitstacked discounted approximation and use in all our proposed algorithms. Unlike the finite-horizon approximation that is heavily used in recent SSP algorithms, our new approximation enables us to learn a near-stationary policy with only logarithmic changes during an episode and could lead to an exponential improvement in space complexity.