Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret

1 Introduction

• Online SSP learning seeks low regret when transition dynamics and costs are initially unknown and episodes end only when the goal is reached.Episode length is not predetermined or bounded and depends on agent behavior.Source: §1 · pp. 1–2
• The minimax target is regret of order B⋆√(SAK), up to logarithmic factors and lower-order terms.The cited lower bound is Ω(B⋆√(SAK)); K is the episode count, S the state count, A the action count, and B⋆ bounds optimal-policy expected cost from any state.Source: §1 · p. 2
• Earlier online-SSP bounds retained lower-order dependence on T⋆ or B⋆/cmin, while the finite-horizon reduction by Cohen et al. required prior T⋆ and B⋆ knowledge.The introduction states that no existing analysis satisfied its horizon-free criterion.Source: §1 · pp. 2–3
• EB-SSP perturbs empirical costs with an exploration bonus and biases empirical transitions toward the goal, making all policies proper under the biased transitions.The bias decays over time and contributes only a lower-order regret term; the method operates directly on the non-truncated SSP model.Source: §1 · p. 3
• EB-SSP is presented as the first online-SSP algorithm to combine the minimax regret rate with parameter-free operation.It does not require prior knowledge of T⋆ or B⋆.Source: §1 · p. 3
• EB-SSP is reported to achieve nearly horizon-free regret in positive-cost cases, when no almost-sure zero-cost cycles exist, and with an order-accurate estimate of T⋆.These guarantees retain the minimax rate; the paper describes them as the first nearly horizon-free bounds beyond finite-horizon MDPs.Source: §1 · pp. 3–4

2 Preliminaries

• An SSP is modeled as a finite-state, finite-action MDP with a start state, a goal state, transition probabilities, and costs in [0, 1].The goal is absorbing and has zero cost.Source: §2 · p. 4
• A proper policy reaches the goal with probability 1 from every state, and the setup assumes at least one such policy exists.For nonnegative costs, adding a small positive cost perturbation supports the proper-policy optimality argument.Source: §2 · pp. 4–5
• The objective is to minimize expected cumulative cost until the goal; an episode may fail to terminate if the agent does not reach it.The agent begins each episode at the initial state, with both costs and transitions unknown.Source: §2 · pp. 4–5
• B⋆ bounds the optimal proper policy's expected cost from any state, while T⋆ bounds its expected time to reach the goal, with B⋆≤T⋆.The optimal proper policy is stationary and deterministic under the stated conditions, and its value function uniquely solves the optimality equations.Source: §2 · p. 5

• The initial algorithm assumes an estimate B ≥ max{B⋆, 1}; it uses η = 0 for known positive costs and otherwise specifies a positive cost perturbation.Source: §3 · p. 5
• EB-SSP refreshes empirical costs and transitions and recomputes a greedy policy whenever state-action visits double, rather than waiting for an episode to end.Source: §3 · p. 5
• VISGO starts from zero values and iterates its operator until successive value vectors differ by at most ϵVI, then outputs value and Q estimates.Source: §3 · p. 6
• Transition skewing gives every state-action pair a nonzero probability of reaching the goal, making all policies proper and avoiding value-iteration divergence on improper empirical models.Source: §3 · p. 7
• With B ≥ B⋆, VISGO maintains optimistic Q estimates and terminates after finite iterations; its operator is contractive despite value-dependent bonuses.Source: §3 · p. 7
• EB-SSP has near-linear-in-T runtime, with T polynomially bounded in K; achieving log(K) computational complexity in SSP while parameter-free remains open.Source: §3 · p. 7

4 Main Results

• Theorem 3’s main-order regret has nearly minimax dependence on B⋆, S, A, and K, with only logarithmic dependence on T.This intermediate guarantee assumes B ≥ max{B⋆, 1} and conditions of Lemma 2; it also depends on possibly unbounded T.Source: §4 · pp. 7–8

4.1 Regret Bounds for B = B⋆

• With positive costs, EB-SSP is nearly minimax and horizon-free, with T⋆ ≤ B⋆/cmin appearing only in logarithms.The same properties hold under the weaker alternative assumption of no almost-sure zero-cost cycles.Source: §4.1 · p. 8
• Without an estimate of T⋆, choosing η = K−n yields a nearly minimax bound with a T⋆-dependent additive term that vanishes as K grows.A larger n can shrink that additive term, at the cost of a larger multiplicative constant.Source: §4.1 · p. 9
• With an order-accurate estimate of T⋆, EB-SSP’s regret is nearly minimax and depends only logarithmically on T⋆.Corollary 8 uses η = (T ⋆K)−1 and B = B⋆.Source: §4.1 · p. 9

4.2 Regret Bounds for Unknown B⋆with Parameter-Free EB-SSP

• Parameter-free EB-SSP removes the need for B⋆ and retains the bounds of Corollaries 5, 6, 8, and 11 up to logarithmic and lower-order terms.Its proxy eB is increased on episode starts, cost thresholds, and when VISGO’s value range exceeds eB.Source: §4.2 · pp. 9–10

5 Conclusion

• EB-SSP is nearly minimax and parameter-free without prior knowledge of B⋆ or T⋆; in several cases its regret depends only logarithmically on T⋆.The paper notes that T⋆ may be arbitrarily larger than B⋆ when instantaneous costs are small.Source: §5 · p. 10

A T⋆can be arbitrarily larger than B⋆, S, A

• In the illustrated SSP, B⋆ = 1 while T⋆ = Ω(S/pmin), so the gap can grow arbitrarily large as pmin approaches zero.A horizon-free bound’s logarithmic dependence on pmin can therefore be much tighter than polynomial dependence.Source: A T⋆can be arbitrarily larger than B⋆,… · p. 14, Figure 1 · p. 14

B An Alternative Assumption on the SSP Problem: No Almost-Sure Zero-Cost Cycles

• Assumption 10 is weaker than positive costs and ensures that any non-goal trajectory of length S + 1 accumulates at least c† with probability at least q†.The constants c† and q† need not be known by the agent, though spelling out suitable values can be challenging.Source: B An Alternative Assumption on the SSP… · p. 15
• Under Assumption 10, EB-SSP’s regret is nearly minimax and horizon-free, with logarithmic dependence on the inverse of c† and q†.The guarantee uses B = B⋆ ≥ 1 and η = 0; the algorithm need not know or estimate c† or q†.Source: B An Alternative Assumption on the SSP… · p. 15

C Full Statement of Corollary 8

• Corollary 8’s stated setup assumes an order-accurate T⋆ estimate and runs EB-SSP with B = B⋆ and η = (T ⋆K)−1.The estimate is bounded using unknown constants υ, λ, and ζ; these equal 1 when T⋆ is known.Source: C Full Statement of Corollary 8 · p. 15

D Proof of Theorem 3

• The proof analyzes Algorithm 1 with η = 0, assuming B ≥ max{B⋆, 1} and the conditions of Lemma 2.Source: D Proof of Theorem 3 · p. 16

D.1 High-Probability Event

• The high-probability event E is defined as the intersection of E1, E2, and E3.Source: §D.1 · p. 16
• The event components concern estimation errors for values, costs, and transition probabilities across state-action pairs.Source: §D.1 · p. 16
• A union bound gives probability at least 1 − δ for the combined event: E1 and E2 hold with probability at least 1 − 2δ/3, and E3 at least 1 − δ/3.The proof uses concentration for E1 and E2 and Bennett’s inequality for E3.Source: §D.1 · p. 16

D.2 Analysis of a VISGO Procedure

• VISGO preserves optimistic Q-values at every iteration and, for any positive precision, stops in finite time near a fixed point.The result is established with high probability; the stopping iterate satisfies an error bound that scales with the requested precision.Source: §D.2 · p. 16, §D.2.3 · p. 17

D.2.1 Properties of the slightly skewed transitions eP

• The skewed transitions make every policy proper for any bounded cost function, and the associated Bellman operator is a sup-norm contraction.The construction adds goal-reaching probability, interpretable as a state-action-dependent discount factor; the added probability decays inversely with visits.Source: §D.2.1 · pp. 16–17

D.2.2 Important auxiliary function f and its properties

• The auxiliary function f is monotone in its value argument and contractive when the transition distribution assigns positive probability to the goal.Its contraction modulus is 1 − p(g), which is less than 1 when p(g) > 0.Source: §D.2.2 · p. 17

D.2.3 Optimism of VISGO

• Conditioned on event E, VISGO’s output Q-values are optimistic when the bound B is at least B⋆.The proof uses induction over inner iterations, the transition-skewing bias bound, and properties of f.Source: §D.2.3 · p. 17

D.2.4 Finite-time near-convergence of VISGO

• VISGO’s iterates are non-decreasing and bounded above by V⋆, so they converge; the operator is contractive with modulus 1 − ν.Here ν is the minimum goal-reaching probability across state-action pairs under the skewed transitions.Source: §D.2.4 · p. 18
• The contraction guarantees that successive iterates differ by at most ϵVI after finitely many iterations, giving an approximate fixed point.The stated iteration threshold depends logarithmically on max{B⋆, 1}/ϵVI.Source: §D.2.4 · p. 18
• With the specified precision and a lower bound on ν, VISGO’s iteration count and EB-SSP’s total computational complexity are polynomially bounded.The passage gives log(1/ϵVI) = O(SA log(T)) and at most O(SA log T) VISGO procedures.Source: §D.2.4 · p. 18

D.3 Interval Decomposition and Notation

• An interval ends when the goal is reached or a state-action visit count doubles, which triggers an update.Intervals are indexed by m, and the values and empirical quantities used for interval m are those at its beginning.Source: §D.3 · p. 18

D.4 Bounding the Bellman Error

• The Bellman-error analysis decomposes the transition-value difference into skewing bias and empirical transition-estimation terms, bounded using Lemmas 14 and 17 and event E.The decomposition also includes a deviation term involving V^m − V⋆, controlled by event E.Source: §D.4 · pp. 18–19

D.5 Regret Decomposition

• The analysis bounds a transformed regret over any initial set of intervals; at the full interval count M, that quantity equals the true regret over K episodes.This lets the proof handle arbitrary interval prefixes, including the parameter-free case without an available estimate B ≥ B⋆.Source: §D.5 · p. 19

D.5.1 The X1(M ′) term

• The X1 contribution is treated as a martingale and bounded with a high-probability inequality.The passage says its bound reduces to bounding X4.Source: §D.5.1 · p. 20

D.5.2 The X3(M ′) term

• The X3 analysis relates cost variance to the cumulative cost and the magnitude of X3, with logarithmic factors in elapsed time and confidence.The supplied bound includes log2(T_M′) and ln(2/δ).Source: §D.5.2 · p. 20

D.5.3 The X2(M ′) term

• The X2 bound covers estimated-cost and VISGO-precision contributions; its analysis normalizes value functions by B⋆ and splits over intervals.The passage describes bounding βm, applying a pigeonhole principle, and bounding these two regret contributions.Source: §D.5.3 · pp. 20–21

D.5.4 Putting Everything Together

• The combined bound is eR_M′ ≤ X1(M′) + X2(M′) + X3(M′) + 2B⋆SA log2(T_M′), and choosing M′ = M concludes the regret proof.At M, the transformed regret equals the true regret over the first K episodes.Source: §D.5 · p. 19, §D.5.4 · p. 21

E.1 Proofs of Lemmas 14, 16, 17, 18, 19, 20

• The transition-skewing bias in value estimates decreases inversely with the number of visits to a state-action pair.The proof uses that the skewed transition probabilities to non-goal states do not exceed their empirical counterparts.Source: §E.1 · pp. 21–22
• The auxiliary function f is monotone and contractive when the transition distribution has positive goal probability.Its contraction modulus is 1 − p(g).Source: §E.1 · p. 22
• Conditioned on event E, VISGO’s Q-estimates remain optimistic, and its value iterates are non-decreasing and bounded above by V⋆.The proof of optimism uses induction and the bounds associated with event E.Source: §E.1 · pp. 23–24
• The skewed-model operator eL is a contraction with modulus 1 − ν, where ν is the minimum goal probability across state-action pairs.The proof obtains the global modulus by taking the maximum over state-action pairs.Source: §E.1 · p. 24
• Conditioned on event E, the interval values satisfy a Bellman-error bound for each state-action pair.The proof bounds both signs of the Bellman residual using optimism, the Bellman optimality equation, and concentration terms.Source: §E.1 · pp. 25–26

E.2 Additional lemmas

• The additional interval-count argument bounds the starting-state values by 2SA log2(T_M′) times the largest interval value norm.The proof counts at most 2SA log2(T_M′) intervals ending when a visit count doubles.Source: §E.2 · p. 27

E.3 Full proof of the bound on X2(M′)

• The X2(M′) proof bounds its summations separately, using VISGO’s doubling property to count occurrences in O(SA log2(TM′)) and martingale concentration across logarithmic scales.The proof also bounds the number of triggers by O(SA log2(TM′/(SA))) and applies a union bound over logarithmic scales.Source: §E.3 · pp. 28, 30, 31, F Technical Lemmas · p. 33

F Technical Lemmas

• The technical lemmas provide anytime concentration inequalities for bounded variables and martingales, alongside auxiliary inequalities used in the proofs.These include an anytime version of Bennett’s inequality and martingale concentration results.Source: F Technical Lemmas · pp. 33–34

G Computational Complexity of EB-SSP

• EB-SSP has total computational complexity O(TS^2A · SA log(B⋆T) · SA log T), which is polynomially bounded and near-linear in T.The passage also notes that T is polynomially bounded in K in the cases discussed in Section 4.1.Source: G Computational Complexity of EB-SSP · pp. 34–35

H Unknown B⋆: Parameter-Free EB-SSP

• The parameter-free EB-SSP variant removes the requirement that a bound B ≥ B⋆ be known to tune the exploration bonus.It initializes an estimate B̃ = 1 and uses phases; the estimate increases automatically with episode index and doubles when a phase ends.Source: H Unknown B⋆: Parameter-Free EB-SSP · p. 35, §H.1 · p. 35

H.1 Algorithm and Intuition

• Each PHASE can halt when cumulative phase cost exceeds a computable threshold or when a VISGO value-function range exceeds B̃.At phase termination B̃ doubles; at each new episode it is also raised to at least the episode-index-based estimate.Source: §H.1 · p. 35
• The cost threshold is designed to be exceeded at most once when eB ≥ B⋆, while remaining a tight enough regret bound when eB < B⋆.The VISGO range threshold eB is designed not to be exceeded with high probability when eB ≥ B⋆, and to guarantee finite-time near-convergence when eB < B⋆.Source: §H.1 · p. 35

H.2 Regret Guarantee of Parameter-Free EB-SSP

• With probability at least 1 − δ, parameter-free EB-SSP extends the known-B⋆ regret guarantee to unknown B⋆, paying only logarithmic and lower-order terms.The theorem is stated as extending Theorem 3; its bound after K episodes is compared with the known-B⋆ bound.Source: §H.2 · p. 36

H.3 Proof of Theorem 9

• ceil(log2(B⋆)) + 1 bounds the number of phases, because a phase starting with eB ≥ B⋆ cannot halt under the high-probability event.Optimism prevents both the cumulative-cost and VISGO-range halting conditions in such a phase.Source: §H.3 · pp. 36–37
• Before episode κ⋆, the estimate eB never exceeds 2B⋆, and the proof bounds cumulative cost and regret using this estimate and the phase count.The first regime ends at κ⋆, defined by the analysis of the episode-driven estimate increments.Source: §H.3 · p. 38
• After κ⋆, eB ≥ B⋆ and at most two phases occur; the regret analysis adapts the interval decomposition to account for phase termination.In this regime, the proof reuses collected statistics and adds a term 2B⋆SA log2(TM′) + B⋆ to the regret decomposition.Source: §H.3 · pp. 38–39
• With probability at least 1−δ, Theorem 9 bounds parameter-free EB-SSP regret by combining contributions from the two regimes.The supplied passage states that the regret is bounded but omits the bound’s expression.Source: §H.3 · p. 39
• The parameter-free scheme adds only horizon-free lower-order terms B⋆, S, and A, unlike cited unknown-diameter schemes whose lower-order dependence is on D.The proof accommodates the increasing estimate by substituting episode-specific Bk values in the analysis; the βm bound remains unchanged.Source: §H.3 · pp. 36, 39