# Stochastic Shortest Path with Adversarially Changing Costs

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

## Key facts

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

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

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes](https://mlsanity.com/paper/2212.05949/) (2022)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [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)
- [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)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2301.13087/) (2023)
- [Online Learning for Stochastic Shortest Path Model via Posterior Sampling](https://mlsanity.com/paper/2106.05335/) (2021)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [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)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Cooperative Online Learning in Stochastic and Adversarial MDPs](https://mlsanity.com/paper/2201.13170/) (2022)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path](https://mlsanity.com/paper/2402.08998/) (2024)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [Convex duality for stochastic shortest path problems in known and unknown environments](https://mlsanity.com/paper/2208.00330/) (2022)
- [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023)

## 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.