In standard reinforcement learning, an agent usually operates within a fixed timeframe (finite-horizon) or with a discount factor that diminishes the value of future rewards. However, the Stochastic Shortest Path (SSP) problem is different: the agent’s episode only ends when it reaches a specific goal state. This makes SSP a more natural model for tasks like navigation or robotics, but it introduces a significant theoretical hurdle: if the agent doesn't pay a price for every step it takes, it might never find the goal.
The Problem of Zero-Cost Loops
The core challenge in SSP is ensuring that the agent actually reaches the goal. In most theoretical frameworks, this is guaranteed by assuming a strictly positive minimum cost ($c_{min} > 0$) for every action taken in a non-goal state.
As Andrea Tirinzoni and Matteo Pirotta demonstrate in Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path, this isn't just a technical convenience—it is a fundamental requirement for learnability. If an environment allows for zero-cost actions, an agent cannot distinguish between a path that eventually reaches the goal and a cycle that traps it in a zero-cost loop forever. Without a "penalty" for staying in the loop, the agent has no incentive to leave it, and the sample complexity required to find an optimal policy can become infinite.
Why $c_{min}$ Dominates Complexity Bounds
Because zero-cost transitions create "blind spots" for the learner, early algorithms for SSP had performance guarantees (regret bounds) that scaled with $1/c_{min}$. When the cost of an action is very small, these bounds explode, suggesting that the problem becomes exponentially harder as costs approach zero.
This sensitivity appears across various settings:
- Heuristic Search: Eric A. Hansen and Ibrahim Abdoulahi showed in Efficient Bounds in Heuristic Search Algorithms for Stochastic Shortest Path Problems that $c_{min}$ is essential for bounding sub-optimality and ensuring convergence in search-based planners.
- Function Approximation: When moving to large-scale problems using linear features, Daniel Vial and Sanjay Shakkottai found that regret bounds degrade significantly if the minimum cost is near zero, as seen in Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation.
- Partial Observability: In the most extreme case, Krishnendu Chatterjee proved in Optimal Cost Almost-sure Reachability in POMDPs that if costs can be zero or negative in a POMDP, the problem of finding an optimal cost becomes mathematically undecidable.
Eliminating the Dependency
Recent research has focused on "breaking" this dependency on $c_{min}$ to create algorithms that work even when some actions are free. The strategy is often to replace the global $c_{min}$ requirement with more sophisticated variance-aware analysis or approximations.
In Near-optimal Regret Bounds for Stochastic Shortest Path, Aviv Rosenberg and Yishay Mansour utilized variance-sensitive Bernstein confidence sets to achieve regret bounds that match lower bounds without relying on $c_{min}$. Similarly, Liyu Chen and Haipeng Luo introduced implicit finite-horizon approximation in Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path. This technique treats the SSP as a sequence of finite-horizon problems with an increasing horizon, allowing the agent to learn effectively even in the presence of zero-cost actions.
The most recent breakthrough in this direction is the LEVIS++ algorithm by Qiwei Di and Quanquan Gu. In Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path, they use a recursive high-order moment variance estimator to finally eliminate the $c_{min}$ requirement in linear mixture MDPs, reaching the theoretical limits of what can be learned in goal-oriented environments.