mlsanityData to 7 Oct 2026

Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case

arXiv 2102.05284 ↗First posted 10 Feb 2021cs.LG cs.AIcited by 28

Not on the map. Why?

Abstract (arXiv)

We make significant progress toward the stochastic shortest path problem with adversarial costs and unknown transition. Specifically, we develop algorithms that achieve widetildeO(√S2ADT_star K) regret for the full-information setting and widetildeO(√S3A2DT_star K) regret for the bandit feedback setting, where D is the diameter, T_star is the expected hitting time of the optimal policy, S is the number of states, A is the number of actions, and K is the number of episodes. Our work strictly improves (Rosenberg and Mansour, 2020) in the full information setting, extends (Chen et al., 2020) from known transition to unknown transition, and is also the first to consider the most challenging combination: bandit feedback with adversarial costs and unknown transition. To remedy the gap between our upper bounds and the current best lower bounds constructed via a stochastically oblivious adversary, we also propose algorithms with near-optimal regret for this special case.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). Builds on 15 of its 20 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

15 of 20 references.

References · 15

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  5. 2016Corralling a Band of Bandit Algorithmscited by 99
  6. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  7. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  8. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  9. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  10. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  11. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  12. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
3 more
  1. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  2. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  3. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 9; 2023: 6; 2024: 1; 2025: 3.

28 papers.

Sort:

By area:

  1. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  2. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  3. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  4. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  5. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  6. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  7. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  8. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  9. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  10. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  11. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  12. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
16 more
  1. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  2. 2022GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimationcited by 8
  3. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  4. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  5. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  6. 2021Adaptive Multi-Goal Explorationcited by 4
  7. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  8. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  9. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  10. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  11. 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximationscited by 1
  12. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  13. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  14. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  15. 2022Reductive MDPs: A Perspective Beyond Temporal Horizonscited by 0
  16. 2023Layered State Discovery for Incremental Autonomous Explorationcited by 0