mlsanityData to 7 Oct 2026

A Unified Algorithm for Stochastic Path Problems

arXiv 2210.09255 ↗First posted 17 Oct 2022cs.LG stat.MLcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 22 of its 31 references that are in the map. First posted on arXiv 17 Oct 2022.

Builds on

22 of 31 references.

References · 22

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  8. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  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
10 more
  1. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  2. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  3. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  4. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  5. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  6. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  7. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  8. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  9. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  10. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Risk-averse Total-reward MDPs with ERM and EVaRcited by 4