PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric

arXiv:2604.16111v1cs.LGstat.ML

TL;DR

The paper asks how many generative-model samples are needed to learn an ε-optimal policy in SSPs, especially when zero costs can permit improper optimal policies. It derives matching near-tight bounds and algorithms for positive costs, and restricted guarantees for zero costs, while identifying assumptions and parameter dependencies that limit the result’s scope.

  • Problem

    The paper studies whether ε-optimal SSP policies can be learned with bounded generative-model sample complexity, including when cmin = 0 and optimal policies may be improper.

  • Method

    The paper derives PAC sample-complexity bounds and develops two algorithms: one for strictly positive costs and one using restricted proper-policy optimality for arbitrary costs.

  • Results

    The positive-cost algorithm matches the unit-cost lower bound in ε, A, and B⋆ terms, while the zero-cost algorithm provides guarantees under restricted proper-policy optimality.

  • Takeaways & Limitations

    When cmin = 0, unrestricted SSP learning may have unbounded sample complexity, whereas bounded-hitting-time restrictions enable learnability guarantees.

  • Takeaways & Limitations

    The zero-cost guarantee is restricted to policies with controlled hitting time, and the discussion leaves improving the ΓS state dependence as an open question.

Abstract

from arXiv · show

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 $S$ states, $A$ 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.

1. Introduction

The paper studies sample complexity for computing near-optimal policies in SSPs with a generative model. It develops two algorithms addressing positive costs and zero-cost settings, where unknown effective horizons complicate accuracy guarantees.

  • 1. Introduction: The paper studies computing near-optimal SSP policies when the learner can sample transitions and rewards at any state-action pair.This generative-model setting is the paper’s focus.
  • 1. Introduction: The first algorithm handles strictly positive costs and adapts its sample complexity to the unknown range of the optimal value function.It returns an ε-optimal policy for any SSP with strictly positive cost function.
  • 1. Introduction: The second algorithm allows zero costs by restricting ε-optimality to proper policies whose expected hitting time is controlled relative to the SSP-diameter.Without this restriction, the optimal policy may be improper and may never reach the goal.
  • 1. Introduction: Unknown effective horizons allow model-estimation errors to accumulate indefinitely, preventing arbitrary accuracy without additional control.Unlike discounted MDPs, SSPs have no known horizon parameter analogous to 1/(1 −γ).

2. Preliminaries

The preliminaries define SSPs as cost-minimization problems ending at an absorbing goal state, with proper policies reaching that goal almost surely. They formalize value, structural quantities, the generative-model question, and separate positive-cost from zero-cost objectives.

  • SSP formulation: An SSP has finite state and action spaces, known costs, unknown transitions, and an absorbing zero-cost goal state.The learner receives transition samples from a generative model for any state-action pair.
  • SSP formulation: A proper policy reaches the goal with probability 1 from every state, while an improper policy fails this requirement.At least one proper policy is assumed to exist.
  • SSP formulation: The policy value is its expected cumulative cost-to-go, and the objective is to find a policy minimizing this value.Improper policies can have an unbounded value-function component.
  • Key quantities: B⋆ is the maximum optimal value over states, Γ is the maximum transition support size, and cmin is the minimum non-goal cost.Under the stated assumptions, B⋆ ≤ D < +∞, where D is the SSP-diameter.
  • Online-to-batch limitation: Regret-to-PAC conversion is inadequate because SSP regret need not ensure proper deployed policies or guarantees for every initial state.Regret analyses may use multiple potentially improper policies within an episode and provide guarantees only under a starting-state distribution.
  • Two cases: The analysis distinguishes cmin > 0, with standard sup-norm PAC optimality, from cmin = 0, where optimality is restricted to proper policies.For zero minimum cost, unrestricted sample complexity may be unbounded because estimation errors can propagate indefinitely.
  • Restricted optimality: For cmin = 0, the restricted policy class Πθ contains only proper policies when θ is finite, while Π+∞ = Π.The restriction is defined using the SSP-diameter, which is unknown to the agent; θ is supplied as an additional parameter.

3. A first approach: Simulation Lemma for SSP

The simulation-lemma approach transfers guarantees from a nearby SSP model to the true model under properness and positive costs, yielding preliminary sample-complexity bounds. Its guarantees are more delicate than in discounted MDPs because the required model accuracy depends on the policy's value and minimum cost.

  • Simulation lemma: The SSP simulation lemma considers nearby transition models whose distributions differ by at most η in L1 for every state-action pair.The model class P_η(p) contains models satisfying the stated per-transition L1 accuracy condition.
  • Simulation lemma: Under positive costs, if both models admit a proper policy and π is proper in p′, then π is also proper in p.The lemma additionally provides a value-function guarantee under these assumptions.
  • Comparison with discounted MDPs: Unlike the discounted-MDP simulation lemma, the SSP guarantee requires a condition coupling η with π's value function in the perturbed model.The discounted comparison assumes bounded rewards and gives a direct guarantee for any policy, whereas SSP requires the additional condition.
  • Comparison with discounted MDPs: As c_min decreases, the required transition accuracy becomes stricter because SSP trajectory length is controlled by ||V^π||_∞/c_min rather than a known discount horizon.This ratio upper-bounds the policy's expected goal-reaching time.
  • Resulting bounds: Directly combining the simulation lemma with the proposed algorithms yields preliminary sample-complexity bounds, which variance-aware refinements subsequently improve.The refinements remove a B_⋆/c_min factor from the main ε^-2 term when c_min > 0 and reduce the zero-cost dependence from ε^-4 to ε^-3.

4. Main Result

The paper develops generative-model algorithms for SSPs, using extended value iteration and adaptive sampling to handle both strictly positive and potentially zero costs. It provides PAC guarantees for positive costs and restricted-optimality guarantees for arbitrary costs, including zero-cost cases.

  • Algorithmic framework: The algorithms estimate transition probabilities from generative-model samples and use extended value iteration rather than directly solving the estimated SSP-MDP.Direct value iteration on the estimated model may fail because that model need not admit a proper optimal policy.
  • Strictly positive costs: The positive-cost algorithm adaptively searches for the unknown range B⋆ of the optimal value function using a doubling scheme.The SEARCH subroutine increases its guess until the optimistic value provides a valid upper bound.
  • Strictly positive costs: Theorem 1 establishes that, for cmin > 0, the positive-cost algorithm is (ε, δ)-optimal with a sample complexity bounded by the paper’s stated expression.The guarantee applies to cost functions in [cmin, 1] and uses the allocation function specified by Eq. 6.
  • Strictly positive costs: The analysis proves that the optimistic policy is proper in both the optimistic and true models, enabling control of the difference between their value functions.The proof combines concentration, the SSP simulation lemma, optimism, and the doubling guarantee ∆ ≤ 2B⋆.
  • Strictly positive costs: SSP analysis obtains a pseudo-discounting effect because the probability of not reaching the goal decays exponentially under a proper policy, although DMDP analyses cannot be applied directly.The paper instead uses SSP-specific tools such as interval decomposition to bound the relevant sums.
  • Arbitrary costs: For cmin = 0, the second algorithm perturbs costs and returns an (ε, δ, θ)-optimal policy with the sample-complexity guarantee stated in Theorem 2.Taking θ = ε^-1 yields accuracy relative to the optimal proper policy asymptotically, but worsens the ε-dependence to eO(ε^-4).

5. Discussion

The discussion compares SSP sample-complexity bounds with discounted and finite-horizon settings, highlighting tight unit-cost scaling, a potentially worse state dependence, and unresolved questions about key dependencies.

  • Comparison with related settings: Ω(SA(B⋆)^3/ε^2) lower-bounds unit-cost SSP sample complexity, matching Theorem 1 in ε, A, and B⋆.This follows by embedding discounted MDPs into SSPs using 1/(1−γ)=B⋆.
  • Comparison with related settings: ΓS can reach S^2, making SSP state dependence potentially worse than the linear dependence for discounted MDPs.The mismatch also appears between SSP and finite-horizon regret bounds.
  • Comparison with related settings: The ΓS dependence stems from accurately estimating the transition kernel across the state-action space.This identifies the source of the potentially quadratic state dependence.
  • Algorithmic implications: After sample collection, Algorithms 1 and 3 guarantee ε-optimal planning across their respective cost-function regimes.Algorithm 1 covers cmin > 0, while Algorithm 3 covers cmin = 0 with finite θ.
  • Comparison with related settings: B⋆/cmin plays the SSP role of effective horizon, while variance-aware analysis removes one B⋆/cmin factor from the main sample-complexity term.The comparison connects SSP horizon dependence to discounted and finite-horizon analogues.
  • Open questions: Whether the cmin dependence in Theorem 1 is unavoidable remains unresolved.A finite-horizon regret-to-PAC analogy is used to investigate, rather than settle, this question.

Appendix A. High-probability Event

The appendix defines a high-probability event controlling confidence intervals uniformly over time, state-action pairs, and successor states, then conditions the analysis on that event.

  • Event definition: E is the event on which the required confidence inequalities hold uniformly over time and state transitions.The event is defined for every t ≥ 1, state-action pair, and next state.
  • Event definition: The remainder of the analysis assumes that E holds.This turns the high-probability confidence statement into the standing condition for subsequent results.
  • Probability guarantee: P(E) ≥ 1−δ.The probability guarantee follows from the empirical Bernstein-based confidence intervals.

Appendix B. Extended Value Iteration for SSP

The SSP-specific EVI scheme constructs plausible transition models from confidence sets and returns a policy that is greedy with respect to an optimistic value-iteration solution.

  • Inputs and model construction: EVI takes collected samples, known positive costs, and a value-iteration precision μVI as input.The input is an SSP instance with cmin > 0 and state-action sample counters.
  • Inputs and model construction: The plausible model set constrains each transition probability to its confidence interval while forcing the goal state to be absorbing.The true SSP belongs to this set with probability at least 1−δ.
  • Extended value iteration: EVI applies an extended Bellman operator to compute the lowest optimistic value among plausible SSP models.The operator is applied iteratively starting from the zero vector.
  • Extended value iteration: The iteration stops when successive value vectors differ by at most μVI in sup norm.The returned policy is the optimistic greedy policy with respect to the final iterate.

Appendix C. Useful Results

These results establish properness and value-function control for policies and models used in the SSP analysis, including exponential goal-reaching tails under bounded values.

  • Model comparison: The optimistic policy’s value remains controlled because the optimistic and true value functions are related through the model comparison lemmas.The proof transfers properness and component-wise value bounds between transition models.
  • Model comparison: The model-comparison argument uses Bellman-operator monotonicity to derive component-wise inequalities between value functions.Combining the two directional inequalities yields the final comparison bound.
  • Properness and Bellman properties: If a vector upper-bounds a policy’s Bellman update, the policy is proper and its value function is bounded by that vector.For proper policies, the value function is also the unique Bellman-equation solution.
  • Goal-reaching behavior: A proper policy with Vπ(s) ≤ d has tail probability at most 2e^(-m/(4d)) for cumulative cost exceeding m.When cmin > 0, cost m also bounds the number of steps by m/cmin.
  • Approximation control: Choosing μVI := εcmin makes the value-iteration approximation error proportional to ε.The resulting iterate satisfies ev ≤ V⋆ + ε/3 under the stated construction.

C.1. Procedure to Estimate an Upper Bound of the SSP-Diamater

The D-SUBROUTINE estimates an upper bound on the SSP diameter using optimistic models, progressively increasing scales, and increasingly accurate transition estimates. It terminates after logarithmically many iterations and returns a controlled optimistic estimate.

  • Guarantees: log2(D(1 + ε)) + 1 inner iterations are sufficient before termination.The stopping scale is finite because the optimistic value norm is bounded by D and W grows strictly geometrically.
  • Guarantees: The output bD satisfies D ≤ bD ≤ (1 + 2ε(1 + ε))(1 + ε)D.The estimate is defined from the final optimistic value norm and its accuracy parameter.
  • Procedure: The optimistic value vector satisfies ev ≤ minπ Vπ component-wise under the optimism event.This optimism property is used throughout the subroutine analysis.
  • Procedure: The routine doubles W each iteration and sets the transition-estimation accuracy to η = εW.It collects additional samples until the empirical transition model meets the required confidence set.
  • Guarantees: The total sample complexity is bounded by a Bernstein-based expression.The final accuracy relation ηj ≤ ε∥evj∥∞ and the lower bound εD/2 ≤ ηj determine the sample requirement.

Appendix D. Proof of Thm. 1

The proof of Theorem 1 controls the learned policy’s value by combining optimistic-model guarantees, variance-aware transition estimation, and interval-based analysis. These arguments establish ε-optimality once the stated sampling requirements hold.

  • Proof of Theorem 1: The algorithm terminates with an estimate Δ satisfying ∥ev∥∞ ≤ Δ ≤ 2B⋆.The stopping rule doubles Δ, while optimism bounds the previous optimistic value by B⋆.
  • Policy guarantee: The candidate policy eπ is proper in the true model and has value bounded component-wise by 2Δ.The simulation lemma and Theorem 1’s supporting inequalities establish properness and the value bound.
  • Concentration analysis: Variance-aware analysis bounds transition-estimation errors using empirical Bernstein inequalities and the shifting trick.The proof applies triangle inequalities, concentration bounds, and Cauchy–Schwarz-style variance control.
  • Interval analysis: Intervals accumulate cost up to Δ, have length at most 2Δ/cmin, and separate variance accumulation from goal-reaching probabilities.The analysis bounds whole-interval variance by O(B⋆^2) and controls non-termination probabilities through the value bound.
  • Conclusion: V ≤ eV + 2ε/3, and Lemma 8 then yields V ≤ V⋆ + ε under the required sampling conditions.This is the proof’s final component-wise performance guarantee.

Appendix E. Proof of Thm. 2

The proof of Theorem 2 perturbs costs upward to obtain a positive minimum-cost setting, applies Theorem 1 there, and transfers the resulting guarantee back to the restricted policy class. This yields ε-optimality relative to that class.

  • Cost perturbation: The proof replaces each cost by c′ν(s, a) = max{c(s, a), ν}, ensuring every perturbed cost is at least ν.The perturbation uses ν = ε/(2θ bD).
  • Perturbed model: Applying Theorem 1 in the perturbed model gives Vν ≤ V⋆ν component-wise.The positive minimum cost enables direct use of the preceding theorem.
  • Restricted policy class: The reference policy π§ minimizes value over Πθ and has expected hitting time bounded by θDs ≤ θ bD.Its perturbed-model value and hitting time provide the comparison policy for the proof.
  • Conclusion: The final transfer gives V ≤ V§ + ε for the policy returned by Alg. 3.The true costs are no larger than the perturbed costs, allowing the perturbed guarantee to imply the restricted-class guarantee.
Loading 2604.16111v1…