mlsanityData to 14 Oct 2026

Stochastic Shortest Path with Adversarially Changing Costs

arXiv 2006.11561 ↗First posted 20 Jun 2020cs.LG stat.MLcited by 28

Not on the map. Why?

Abstract (arXiv)

Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. In this paper we present the adversarial SSP model that also accounts for adversarial changes in the costs over time, while the underlying transition function remains unchanged. Formally, an agent interacts with an SSP environment for K episodes, the cost function changes arbitrarily between episodes, and the transitions are unknown to the agent. We develop the first algorithms for adversarial SSPs and prove high probability regret bounds of widetilde O (√K) assuming all costs are strictly positive, and widetilde O (K3/4) in the general case. We are the first to consider this natural setting of adversarial SSP and obtain sub-linear regret for it.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). First posted on arXiv 20 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 8; 2023: 8; 2024: 2; 2025: 1.

28 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  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. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  6. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  7. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  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. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  11. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  12. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
16 more
  1. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  2. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  3. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  4. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  5. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  6. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  7. 2023Learning and Collusion in Multi-unit Auctionscited by 5
  8. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4
  9. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  10. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  11. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  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. 2022Convex duality for stochastic shortest path problems in known and unknown environmentscited by 0
  16. 2023Layered State Discovery for Incremental Autonomous Explorationcited by 0