Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
| Authors | Jean Tarbouriech et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2604.16111 |
| Download | |
| Categories | cs.LG, stat.ML |
Abstract
We study the sample complexity of learning an -optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with states, actions, minimum cost c_{\min}, and maximum expected cost of the optimal policy over all states B_{\star}, where any algorithm requires at least Ω(SAB_{\star}^3/(c_{\min}ε^2)) samples to return an -optimal policy with high probability. Surprisingly, this implies that whenever c_{\min} = 0 an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this lower bound with an algorithm that matches it, up to logarithmic factors, in the general case, and an algorithm that matches it up to logarithmic factors even when c_{\min} = 0, but only under the condition that the optimal policy has a bounded hitting time to the goal state.
Engineering Breakdown
Plain English
This paper establishes fundamental sample complexity bounds for learning optimal policies in Stochastic Shortest Path (SSP) problems when you have access to a generative model (a simulator you can query). The authors prove a lower bound of Ω(SAB★³/(c_min·ε²)) samples required to find an ε-optimal policy with high probability, where S is states, A is actions, B★ is the maximum expected cost of the optimal policy, and c_min is the minimum edge cost. A striking finding is that when c_min = 0 (zero-cost edges exist), SSP becomes provably unlearnable, revealing that SSP learning is fundamentally harder than finite-horizon or discounted MDPs. This result closes a theoretical gap and explains why SSP problems present unique algorithmic challenges compared to other RL settings.
Core Technical Contribution
The paper's core contribution is deriving the first rigorous sample complexity lower bounds for SSP with a generative model, revealing the problem's inherent hardness. Unlike finite-horizon MDPs (which scale as Ω(SA/ε²)) or discounted MDPs, SSP requires cubic dependence on the cost horizon B★, capturing the fact that SSP's goal-reaching structure creates fundamentally different learning dynamics. The authors rigorously prove this lower bound through an adversarial construction—building worst-case SSP instances that force any learning algorithm to require at least this many samples. The key insight is that the presence of zero-cost cycles (when c_min = 0) creates cycles of unbounded length that cannot be distinguished from transitions, making the problem unlearnable without additional assumptions.
How It Works
The proof technique constructs an adversarial SSP instance that forces high sample complexity through careful state and action design. The construction creates a problem where the learner must distinguish between two hypotheses about the environment with exponentially small probability of error, requiring many samples to accumulate sufficient confidence. The analysis relates the SSP learning problem to hypothesis testing: the learner must identify the optimal policy among exponentially many candidates, and the minimum-cost parameter c_min controls how easily policies can be distinguished empirically. The cubic dependence on B★ arises because the learner must estimate costs over trajectories that may have length proportional to B★, and all states must be explored to sufficient depth to characterize reachability under the optimal policy. The paper shows this lower bound is tight or near-tight with existing algorithms, establishing the fundamental limits of the problem.
Production Impact
This paper provides engineers with a theoretical foundation for understanding why SSP problems are notoriously hard to solve in practice compared to standard MDP settings. If you're building a robotic navigation system or resource planning optimizer using SSP formulations, this work explains why sample efficiency will be poor—you should expect sample complexity to scale cubically with the problem's cost horizon, not quadratically like in discounted settings. The practical implication is that for SSP problems with large cost horizons or safety-critical domains where samples are expensive, you may need fundamentally different algorithmic approaches (e.g., incorporating domain knowledge, restricting the policy class, or using offline learning) rather than standard online RL algorithms. The negative result about unlearnability when c_min = 0 should guide your problem formulation: ensure your SSP includes positive-cost transitions somewhere (e.g., by adding small epsilon costs to all edges) to avoid hitting the unlearnable regime. This work justifies why practitioners often resort to heuristic or approximate methods rather than pure learning in SSP settings with realistic cost structures.
Limitations and When Not to Use This
The lower bound applies only to algorithms with access to a generative model (arbitrary trajectory sampling), which is stronger than typical online exploration settings—real systems with limited query budgets may face even worse sample complexity. The paper does not provide matching upper bounds for all regimes, so the tightness of the cubic B★ dependence is not fully established, and it remains unclear whether this can be improved algorithmically. The analysis assumes the learner must return an ε-optimal policy with high probability over worst-case instances, but many practical applications may tolerate approximate solutions or probabilistic guarantees with lower confidence. The unlearnable regime (c_min = 0) is a theoretical edge case, but it highlights a sensitivity that practitioners should be aware of: if your problem formulation inadvertently creates cycles of arbitrary low cost, no algorithm will learn effectively without structural modifications.
Research Context
This work extends a classical line of research in reinforcement learning theory that characterizes sample complexity across different MDP settings—prior bounds exist for finite-horizon MDPs and discounted MDPs, but SSP remained largely uncharacterized despite being crucial for goal-reaching tasks. The paper builds on fundamental techniques from hypothesis testing and adversarial lower bounds in online learning, adapting them to the SSP setting where unbounded trajectory lengths create unique technical challenges. The result opens new research directions on whether modified SSP algorithms or additional structure (e.g., strong connectivity assumptions, cost smoothness) can circumvent the hardness, and whether similar cubic dependencies appear in related settings like average-cost MDPs. This work is part of the broader theoretical reinforcement learning agenda of establishing tight sample complexity characterizations for fundamental problem classes.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::