# A Unified Algorithm for Stochastic Path Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 31 references that are in the map.
- First posted on arXiv 17 Oct 2022.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [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)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [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)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [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)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP](https://mlsanity.com/paper/2112.09859/) (2021)
- [Policy Optimization for Stochastic Shortest Path](https://mlsanity.com/paper/2202.03334/) (2022)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality](https://mlsanity.com/paper/2206.04921/) (2022)

## Built on by (most cited first, 1 of 1)

- [Risk-averse Total-reward MDPs with ERM and EVaR](https://mlsanity.com/paper/2408.17286/) (2024)

## Abstract (arXiv)

We study reinforcement learning in stochastic path (SP) problems. The goal in these problems is to maximize the expected sum of rewards until the agent reaches a terminal state. We provide the first regret guarantees in this general problem by analyzing a simple optimistic algorithm. Our regret bound matches the best known results for the well-studied special case of stochastic shortest path (SSP) with all non-positive rewards. For SSP, we present an adaptation procedure for the case when the scale of rewards B_star is unknown. We show that there is no price for adaptation, and our regret bound matches that with a known B_star. We also provide a scale adaptation procedure for the special case of stochastic longest paths (SLP) where all rewards are non-negative. However, unlike in SSP, we show through a lower bound that there is an unavoidable price for adaptation.