mlsanityData to 7 Oct 2026

Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality

arXiv 2206.04921 ↗First posted 10 Jun 2022cs.LG cs.AI stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

Goal-oriented Reinforcement Learning, where the agent needs to reach the goal state while simultaneously minimizing the cost, has received significant attention in real-world applications. Its theoretical formulation, stochastic shortest path (SSP), has been intensively researched in the online setting. Nevertheless, it remains understudied when such an online interaction is prohibited and only historical data is provided. In this paper, we consider the offline stochastic shortest path problem when the state space and the action space are finite. We design the simple value iteration-based algorithms for tackling both offline policy evaluation (OPE) and offline policy learning tasks. Notably, our analysis of these simple algorithms yields strong instance-dependent bounds which can imply worst-case bounds that are near-minimax optimal. We hope our study could help illuminate the fundamental statistical limits of the offline SSP problem and motivate further studies beyond the scope of current consideration.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 30 of its 47 references that are in the map. First posted on arXiv 10 Jun 2022.

Builds on

30 of 47 references.

References · 30

  1. 2019Solving Rubik's Cube with a Robot Handcited by 699
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  5. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  9. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  10. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  11. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  12. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
18 more
  1. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  3. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  4. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  5. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  6. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  7. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  8. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  9. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  10. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  11. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  12. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  13. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  14. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  15. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  16. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  17. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  18. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 0; 2024: 0; 2025: 1.

3 papers.

  1. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  2. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  3. 2025Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problemcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory
  2. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  3. 2021You Only Evaluate Once: a Simple Baseline Algorithm for Offline RL
  4. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
  5. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  6. 2023Selective Uncertainty Propagation in Offline RL
  7. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
  8. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints