The Minimum Cost Constraint in Stochastic Shortest Path Problems

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 218 papers28 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 16 papers
  2. Version 1 · 2026-10-04 · 18 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_minimum_cost_dependency_0707eade,
  title = {minimum cost dependency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimum-cost-dependency/rdr_0707eade40824cbfb0ca441f89569c51},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_minimum_cost_constraint_in_stochasti_0707eade_v1,
  title = {The Minimum Cost Constraint in Stochastic Shortest Path Problems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-minimum-cost-constraint-in-stochastic-shortest-path-problems/rdr_0707eade40824cbfb0ca441f89569c51/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}