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

Abstract:
We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks to minimize the expected cost accumulated before reaching a goal state. We design a novel model-based algorithm EB-SSP that carefully skews the empirical transitions and perturbs the empirical costs with an exploration bonus to induce an optimistic SSP problem whose associated value iteration scheme is guaranteed to converge. We prove that EB-SSP achieves the minimax regret rate Õ(B? √ SAK), where K is the number of episodes, S is the number of states, A is the number of actions, and B? bounds the expected cumulative cost of the optimal policy from any state, thus closing the gap with the lower bound. Interestingly, EB-SSP obtains this result while being parameter-free, i.e., it does not require any prior knowledge of B?, nor of T?, which bounds the expected time-to-goal of the optimal policy from any state. Furthermore, we illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of T? is available) where the regret only contains a logarithmic dependence on T?, thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.

text: √ SAK), where K is the number of episodes, S is the number of states, A is
the number of actions, and B? bounds the expected cumulative cost of the optimal policy from any state, thus closing the gap with the lower bound. Interestingly, EB-SSP obtains this result while being parameter-free, i.e., it does not require any prior knowledge of B?, nor of T?, which bounds the expected time-to-goal of the optimal policy from any state. Furthermore, we illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of T? is available) where the regret only contains a logarithmic dependence on T?, thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.

heading: 1 Introduction
text: Stochastic shortest path (SSP) is a goal-oriented reinforcement learning (RL) setting where the agent aims to reach a predefined goal state while minimizing its total expected cost [Bertsekas, 1995]. In particular, the interaction between the agent and the environment ends only when (and if) the goal state is reached, so the length of an episode is not predetermined (nor bounded) and it is influenced by the agent’s behavior. SSP includes both finite-horizon and discounted Markov Decision Processes (MDPs) as special cases. Moreover, many common RL problems can be cast under the SSP formulation, such as game playing (e.g., Atari games) or navigation (e.g., Mujoco mazes).
We study the online learning problem in the SSP setting (online SSP in short), where both the transition dynamics and the cost function are initially unknown and the agent interacts with the environment through multiple episodes. The learning objective is to achieve a performance as close ∗equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
as possible to the optimal policy π?, that is, the agent should achieve low regret (i.e., the cumulative difference between the total cost accumulated across episodes by the agent and by the optimal policy). We identify three desirable properties for a learning algorithm in online SSP.
• Desired property 1: Minimax. The information-theoretic lower bound on the regret is Ω(B? √ SAK) [Rosenberg et al., 2020], where K is the number of episodes, S is the number
of states, A is the number of actions, and B? bounds the total expected cost of the optimal policy starting from any state (assuming for simplicity that B? ≥ 1). An algorithm for online SSP is (nearly) minimax optimal if its regret is bounded by Õ(B? √ SAK),
up to logarithmic factors and lower-order terms.
• Desired property 2: Parameter-free. Another relevant dimension is the amount of prior knowledge required by the algorithm. While the knowledge of S, A, and the cost (or reward) range [0, 1] is standard across regret-minimization settings (e.g., finite-horizon, discounted, average-reward), the complexity of learning in SSP problems may be linked to SSP-specific quantities such as B? and T?, which denotes the expected time-to-goal of the optimal policy from any state.
An algorithm for online SSP is parameter-free if it relies neither on T? nor B? prior knowledge.
• Desired property 3: Horizon-free. A core challenge in SSP is to trade off between minimizing costs and quickly reaching the goal state. This is accentuated when the instantaneous costs are small, i.e., when there is a mismatch between B? and T?. Indeed, while B? ≤ T? always holds since the cost range is [0, 1], the gap between the two may be arbitrarily large (see e.g., the simple example of App. A). The lower bound stipulates that the regret does depend on B?, while the “time horizon” of the problem, i.e., T? should a priori not impact the regret, even as a lower-order term. An algorithm for online SSP is (nearly) horizon-free if its regret depends only logarithmically on T?.
Our definition extends the property of so-called horizon-free bounds recently uncovered in finitehorizon MDPs with total reward bounded by 1 [Wang et al., 2020a, Zhang et al., 2021a,b]. These bounds depend only logarithmically on the horizon H , which is the number of time steps by which any policy terminates. Such notion of horizon would clearly be too strong in the more general class of SSP, where some (even most) policies may never reach the goal, thus having unbounded time horizon. A more adequate notion of horizon in SSP is T?, which bounds the expected time of the optimal policy to terminate the episode starting from any state.
Finally, while the previous properties focus on the learning aspects of the algorithm, another important consideration is computational efficiency. It is desirable that a learning algorithm has run-time complexity at most polynomial in K,S,A,B?, and T?. All existing algorithms for online SSP, including the one proposed in this paper, meet such requirement.
Related Work. Table 1 reviews the existing work on online learning in SSP. The setting was first studied by Tarbouriech et al. [2020a] who gave a parameter-free algorithm with a Õ(K3/2) regret guarantee. Rosenberg et al. [2020] then improved this result by deriving the first order-optimal algorithm with regret Õ(B3/2? S √ AK) in the parameter-free case and Õ(B?S √ AK) if B? is known (to tune cost perturbation appropriately). Both approaches are model-optimistic,2 drawing inspiration from the ideas behind the UCRL2 algorithm [Jaksch et al., 2010] for average-reward MDPs.
Concurrently to our work, Cohen et al. [2021] propose an algorithm for online SSP based on a blackbox reduction from SSP to finite-horizon MDPs. It successively tackles finite-horizon problems with horizon set to H = Ω(T?) and costs augmented by a terminal cost set to cH(s) = Ω(B?I(s 6= g)), where g denotes the goal state. This finite-horizon construction guarantees that its optimal policy has a similar value function to the optimal policy in the original SSP instance up to a lower-order bias. Their algorithm comes with a regret bound of O(B? √ SAKL+ T 4?S
2AL5), with L = log(KT?SAδ−1) (with probability at least 1 − δ). It achieves a nearly minimax-optimal rate, however it relies on both T? and B? prior knowledge to tune the horizon and terminal cost in the reduction, respectively.3
2We refer the reader to Neu and Pike-Burke [2020] for details on the differences and interplay between model-optimistic and value-optimistic approaches.
3As mentioned by Cohen et al. [2021, Remark 2], in the case of positive costs lower bounded by cmin > 0, their knowledge of T? can be bypassed by replacing it with the upper bound T? ≤ B?/cmin. However, when generalizing from the cmin case to general costs with a perturbation argument, their regret guarantee worsens from Õ( √ K + c−4min) to Õ(K 4/5), because of the poor additive dependence on c−1min.
Finally, all existing bounds contain lower-order dependencies either on T? in the case of general costs, or on B?/cmin in the case of positive costs lower bounded by cmin > 0 (note that T? ≤ B?/cmin, which is one of the reasons why cmin can show up in existing bounds). As such, no existing analysis satisfies horizon-free properties for online SSP.
Contributions. We summarize our main contributions as follows (see also Table 1):
• We propose EB-SSP (Exploration Bonus for SSP), a new algorithm for online SSP. It introduces a value-optimistic scheme to efficiently compute optimistic policies for SSP, by both perturbing the empirical costs with an exploration bonus and slightly biasing the empirical transitions towards reaching the goal from each state-action pair with positive probability. Under these biased transitions, all policies are in fact proper (i.e., they eventually reach the goal with probability 1 starting from any state). We decay the bias over time in a way that it only contributes to a lower-order regret term. See Sect. 3 for an overview of our algorithm and analysis. Note that EB-SSP is not based on a model-optimistic approach2 [Tarbouriech et al., 2020a, Rosenberg et al., 2020], and it does not rely on a reduction from SSP to finite-horizon [Cohen et al., 2021] (i.e., we operate at the level of the non-truncated SSP model); • EB-SSP is the first algorithm to achieve the minimax regret rate of Õ(B? √ SAK) while simulta-
neously being parameter-free: it does not require to know nor estimate T?, and it is able to bypass the knowledge of B? at the cost of only logarithmic and lower-order contributions to the regret;
• EB-SSP is the first algorithm to achieve horizon-free regret for SSP in various cases: i) positive costs, ii) no almost-sure zero-cost cycles, and iii) the general cost case when an order-accurate estimate of T? is available (i.e., a value T ? such that T?υ ≤ T ? ≤ λT ζ ? for some unknown constants
υ, λ, ζ ≥ 1 is available). This property is especially relevant if T? is much larger than B?, which can occur in SSP models with very small instantaneous costs. Moreover, EB-SSP achieves its horizon-free guarantees while maintaining the minimax rate. For instance, under general costs when
relying on T? andB?, its regret is Õ(B? √ SAK+B?S
2A).4 To the best of our knowledge, EB-SSP yields the first set of (nearly) horizon-free bounds beyond the setting of finite-horizon MDPs.
Additional Related Work. Planning in SSP: Early work by Bertsekas and Tsitsiklis [1991], followed by [e.g., Bertsekas, 1995, Bonet, 2007, Kolobov et al., 2011, Bertsekas and Yu, 2013, Guillot and Stauffer, 2020], examine the planning problem in SSP, i.e., how to compute an optimal policy when all parameters of the SSP model are known. Under mild assumptions, the optimal policy is deterministic and stationary and can be computed efficiently using standard planning techniques, e.g., value iteration, policy iteration or linear programming.
Regret minimization in MDPs: The exploration-exploitation dilemma in tabular MDPs has been extensively studied in finite-horizon [e.g., Azar et al., 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Efroni et al., 2019, Simchowitz and Jamieson, 2019, Zhang et al., 2020, Neu and Pike-Burke, 2020, Xu et al., 2021, Menard et al., 2021] and infinite-horizon [e.g., Jaksch et al., 2010, Bartlett and Tewari, 2012, Fruit et al., 2018, Wang et al., 2020b, Qian et al., 2019, Wei et al., 2020].
Other SSP-based settings: SSP with adversarial costs was investigated by Rosenberg and Mansour [2021], Chen et al. [2021], Chen and Luo [2021].5 Tarbouriech et al. [2021] study the sample complexity of SSP with a generative model, as a standard regret-to-PAC conversion may not hold in SSP (as opposed to finite-horizon). Exploration problems involving multiple goal states (i.e., multigoal SSP or goal-conditioned RL) were analyzed by Lim and Auer [2012], Tarbouriech et al. [2020b].

heading: 2 Preliminaries
text: An SSP problem is an MDP M := 〈S,A, P, c, s0, g〉, where S is the finite state space with cardinality S, A is the finite action space with cardinality A, and s0 ∈ S is the initial state. We denote by g /∈ S the goal state, and we set S ′ := S ∪ {g} (thus S′ := S + 1). Taking action a in state s incurs a cost drawn i.i.d. from a distribution on [0, 1] with expectation c(s, a), and the next state s′ ∈ S ′ is selected with probability P (s′|s, a) (where ∑ s′∈S′ P (s
′|s, a) = 1). The goal state g is absorbing and zero-cost, i.e., P (g|g, a) = 1 and c(g, a) = 0 for any action a. For notational convenience, let Ps,a := P (·|s, a), Ps,a,s′ := P (s′|s, a). For any two vectors X,Y of size S′, we write their inner product as XY := ∑ s∈S′ X(s)Y (s), we denote by X
2 the vector [X(1)2, X(2)2, . . . , X(S′)2]>, let ‖X‖∞ := maxs∈S′ |X(s)|, ‖X‖ 6=g∞ := maxs∈S |X(s)|, and if X is a probability distribution on S ′, then V(X,Y ) := ∑ s∈S′ X(s)Y (s) 2− ( ∑ s∈S′ X(s)Y (s)) 2.
A stationary and deterministic policy π : S → A is a mapping from state s to action π(s). A policy π is said to be proper if it reaches the goal with probability 1 when starting from any state in S (otherwise it is improper). We denote by Πproper the set of proper, stationary and deterministic policies. We make the following basic assumption which ensures that the SSP problem is well-posed.
Assumption 1. There exists at least one proper policy, i.e., Πproper 6= ∅.
The agent’s objective is to minimize its expected cumulative cost incurred until the goal is reached. The value function (also called cost-to-go) of a policy π and its associated Q-function are defined as

heading: V π(s) := lim
text: T→∞ E [ T∑ t=1 ct(st, π(st)) ∣∣ s1 = s], Qπ(s, a) := lim T→∞ E [ T∑ t=1 ct(st, π(st)) ∣∣ s1 = s, π(s1) = a],
where ct ∈ [0, 1] is the (instantaneous) cost incurred at time t at state-action pair (st, π(st)), and the expectation is w.r.t. the random sequence of states generated by executing π starting from state s ∈ S (and taking action a ∈ A in the second case). Note that V π may have unbounded components if π never reaches the goal. For a proper policy π, V π(s) and Qπ(s, a) are finite for any s, a. By definition of the goal, we set V π(g) = Qπ(g, a) = 0 for all policies π and actions a. Finally, we
4We conjecture the optimal problem-independent regret in SSP to be Õ(B? √ SAK +B?SA) (by analogy with the conjecture of Menard et al. [2021] for finite-horizon MDPs), which shows the tightness of our bound up to an S lower-order factor.
5A different line of work [e.g. Neu et al., 2010, 2012, Rosenberg and Mansour, 2019a,b, Jin et al., 2020, Jin and Luo, 2020] studies finite-horizon MDPs with adversarial costs (sometimes called online loop-free SSP), where an episode ends after a fixed number of H steps (as opposed to lasting as long as the goal is reached).
denote by Tπ(s) the expected time that π takes to reach g starting at state s; in particular, if π is proper then Tπ(s) is finite for all s, yet if π is improper there must exist at least one s such that Tπ(s) =∞. Equipped with Asm. 1 and an additional condition on improper policies defined below, one can derive important properties on the optimal policy π? that minimizes the value function component-wise. Lemma 2 (Bertsekas and Tsitsiklis, 1991;Yu and Bertsekas, 2013). Suppose that Asm. 1 holds and that for every improper policy π′ there exists at least one state s ∈ S such that V π′(s) = +∞. Then the optimal policy π? is stationary, deterministic, and proper. Moreover, V ? = V π? is the unique solution of the optimality equations V ? = LV ? and V ?(s) < +∞ for any s ∈ S, where for any vector V ∈ RS the optimal Bellman operator L is defined as LV (s) := mina∈A { c(s, a) + Ps,aV } . Also, the optimal Q-value, denoted by Q? = Qπ? , is related to the optimal value function as follows: Q?(s, a) = c(s, a) + Ps,aV ? and V ?(s) = mina∈AQ?(s, a), for all (s, a) ∈ S ×A.
Since we will target the best proper policy, we will handle the second requirement of Lem. 2 as follows [Bertsekas and Yu, 2013, Rosenberg et al., 2020]. First, the requirement is in particular verified if all instantaneous costs are strictly positive. To deal with the case of non-negative costs, we can introduce a small additive perturbation η ∈ (0, 1] to all costs to yield a new (strictly positive) cost function cη(s, a) = max{c(s, a), η}. In this cost-perturbed MDP, the conditions of Lem. 2 hold so we get an optimal policy π?η that is stationary, deterministic and proper and has a finite value function V ?η . Taking the limit as η → 0, we have that π?η → π? and V ?η → V π
? , where π? is the optimal proper policy in the original model that is also stationary and deterministic, and V π? denotes its value function. This enables to circumvent the second condition of Lem. 2 and only require Asm. 1 to hold.
Learning formulation. We consider the learning problem where the agent does not have any prior knowledge of the cost function c or transition function P . Each episode starts at the initial state s0 (the extension to any possibly unknown distribution of initial states is straightforward), and ends only when the goal state g is reached (note that this may never happen if the agent does not reach the goal). We evaluate the performance of the agent after K episodes by its regret, which is defined as
RK := K∑ k=1 Ik∑ h=1 ckh −K · min π∈Πproper V π(s0), (1)
where Ik is the time needed to complete episode k and ckh is the cost incurred in the h-th step of episode k when visiting (skh, a k h). If there exists k such that I
k is infinite, then we define RK =∞. Throughout we denote the optimal proper policy by π? and V ?(s) := V π ?
(s) = minπ∈Πproper V π(s)
and Q?(s, a) := Qπ ?
(s, a) = minπ∈Πproper Q π(s, a) for all (s, a). Let B? > 0 bound the values
of V ?, i.e., B? := maxs∈S V ?(s). Note that Q?(s, a) ≤ 1+B?. Also let T? > 0 bound the expected time-to-goal of the optimal policy, i.e., T? := maxs∈S Tπ ? (s). We see that B? ≤ T? < +∞.

heading: 3 Main Algorithm
text: We introduce our algorithm EB-SSP (Exploration Bonus for SSP) in Alg. 1. It takes as input the state-action space S ×A and confidence level δ ∈ (0, 1). For now it considers that an estimate B such that B ≥ max{B?, 1} is available, and we later handle the case of unknown B? (Sect. 4.2 and App. H). As explained in Sect. 2, the algorithm enforces the conditions of Lem. 2 to hold by adding a small cost perturbation η ∈ [0, 1] (cf. lines 3, 12 in Alg. 1) — either η = 0 if the agent is aware that all costs are already positive, otherwise a careful choice of η > 0 is provided in Sect. 4.
Our algorithm builds on a value-optimistic approach by sequentially constructing optimistic lower bounds on the optimal Q-function and executing the policy that greedily minimizes them. Similar to the MVP algorithm of Zhang et al. [2021a] designed for finite-horizon RL, we adopt the doubling update framework (first proposed by Jaksch et al. [2010]): whenever the number of visits of a state-action pair is doubled, the algorithm updates the empirical cost and transition probability of this state-action pair, and computes a new optimistic Q-estimate and optimistic greedy policy. Note that this slightly differs from MVP which waits for the end of its finite-horizon episode to update the policy. In SSP, however, having this delay may yield linear regret as the episode has the risk of never terminating under the current policy (e.g., if it is improper), which is why we perform the policy update instantaneously when the doubling condition is met.
Algorithm 1: Algorithm EB-SSP 1 Input: S, s0 ∈ S, g 6∈ S, A, δ. 2 Input: an estimate B guaranteeing B ≥ max{B?, 1} (see Sect. 4.2 and App. H if not available). 3 Optional input: cost perturbation η ∈ [0, 1]. 4 Specify: Trigger setN ← {2j−1 : j = 1, 2, . . .}. Constants c1 = 6, c2 = 36, c3 = 2 √ 2, c4 = 2 √ 2. 5 For (s, a, s′) ∈ S ×A× S ′, set N(s, a)← 0; n(s, a)← 0; N(s, a, s′)← 0; P̂s,a,s′ ← 0; θ(s, a)← 0; ĉ(s, a)← 0; Q(s, a)← 0; V (s)← 0. 6 Set initial time step t← 1 and trigger index j ← 0. 7 for episode k = 1, 2, . . . do 8 Set st ← s0 9 while st 6= g do
10 Take action at = arg mina∈AQ(st, a), incur cost ct and observe next state st+1 ∼ P (·|st, at). 11 Set (s, a, s′, c)← (st, at, st+1,max{ct, η}) and t← t+ 1. 12 Set N(s, a)← N(s, a) + 1, θ(s, a)← θ(s, a) + c, N(s, a, s′)← N(s, a, s′) + 1. 13 if N(s, a) ∈ N then 14 \\ Update triggered: VISGO procedure. 15 Set ĉ(s, a)← I[N(s, a) ≥ 2] 2θ(s,a)
N(s,a) + I[N(s, a) = 1]θ(s, a) and θ(s, a)← 0.
16 For s′ ∈ S ′, set P̂s,a,s′ ← N(s, a, s′)/N(s, a), n(s, a)← N(s, a), and P̃s,a,s′ as in Eq. 5. 17 Set j ← j + 1, VI ← 2−j/(SA) and i← 0, V (0) ← 0, V (−1) ← +∞. 18 For all (s, a) ∈ S ×A, set n+(s, a)← max{n(s, a), 1} and ιs,a ← ln ( 12SAS′[n+(s,a)]2
δ
) .
19 while ‖V (i) − V (i−1)‖∞ > VI do 20 For all (s, a) ∈ S ×A, set
b(i+1)(s, a) ← b(V (i), s, a), \\ see Eq. 6 for bonus expression (2) Q(i+1)(s, a) ← max { ĉ(s, a) + P̃s,aV (i) − b(i+1)(s, a), 0 } , (3)
V (i+1)(s) ← min a Q(i+1)(s, a). (4)
21 Set V (i+1)(g) = 0 and i← i+ 1. 22 Set Q← Q(i), V ← V (i).
The main algorithmic component lies in how to compute the Q-values (w.r.t. which the policy is greedy) when a doubling condition is met. To this purpose, we introduce a procedure called VISGO, for Value Iteration with Slight Goal Optimism. Starting with optimistic values V (0) = 0, it iteratively computes V (i+1) = L̃V (i) for a carefully defined operator L̃. It ends when a stopping condition is met, specifically once ‖V (i+1) − V (i)‖∞ ≤ VI for a precision level VI > 0 (specified later), and it outputs the values V (i+1) (and Q-values Q(i+1)). We now explain how we design L̃ and then provide some intuition. Let P̂ and ĉ be the current empirical transition probabilities and costs, and let n(s, a) be the current number of visits to state-action pair (s, a) (and n+(s, a) = max{n(s, a), 1}). We first define transition probabilities P̃ that are slightly skewed towards the goal w.r.t. P̂ , as follows
P̃s,a,s′ := n(s, a)
n(s, a) + 1 P̂s,a,s′ +
I[s′ = g]
n(s, a) + 1 . (5)
Given the estimateB, specific positive constants c1, c2, c3, c4 and a state-action dependent logarithmic term ιs,a, we then define the exploration bonus function, for any state-action pair (s, a) ∈ S ×A and vector V ∈ RS′ such that V (g) = 0, as follows
b(V, s, a) := max { c1 √ V(P̃s,a, V )ιs,a n+(s, a) , c2 Bιs,a n+(s, a) } + c3 √ ĉ(s, a)ιs,a n+(s, a) + c4 B √ S′ιs,a n+(s, a) . (6)
Note that the last term in Eq. 6 accounts for the skewing of P̃ w.r.t. P̂ (see Lem. 14). Given the transitions P̃ and exploration bonus b, we are ready to define the operator L̃ as
L̃V (s) := max {
min a∈A
{ ĉ(s, a) + P̃s,aV − b(V, s, a) } , 0 } . (7)
We see that L̃ promotes optimism in two different ways:
(i) On the empirical cost function ĉ, via the bonus b (Eq. 6) that intuitively lowers the costs to ĉ− b; (ii) On the empirical transition function P̂ , via the transitions P̃ (Eq. 5) that slightly bias P̂ with the
addition of a non-zero probability of reaching the goal from every state-action pair. While the first feature (i) is standard in finite-horizon approaches, the second (ii) is SSP-specific, and is required to cope with the fact that the empirical model P̂ may not admit any proper policy, meaning that executing value iteration for SSP on P̂ may diverge. Our simple transition skewing actually guarantees that all policies are proper in P̃ , for any fixed and bounded cost function.6 By decaying the extra goal-reaching probability inversely with n(s, a), we can tightly control the gap between P̃ and P̂ and ensure that it only accounts for a lower-order regret term (cf. last term of Eq. 6).
Equipped with these two sources of optimism, as long as B ≥ B?, we are able to prove that a VISGO procedure verifies the following two key properties: (1) Optimism: VISGO outputs an optimistic estimator of the optimal Q-function at each iteration step,
i.e., Q(i)(s, a) ≤ Q?(s, a),∀i ≥ 0, (2) Finite-time near-convergence: VISGO terminates within a finite number of iteration steps (note
that the final iterate V (j) approximates the fixed point of L̃ up to an error scaling with VI). To satisfy (1), we derive similarly to MVP [Zhang et al., 2021a] a monotonicity property for the operator L̃, which is achieved by carefully tuning the constants c1, c2, c3, c4 in the bonus of Eq. 6. On the other hand, the requirement (2) is SSP-specific, since it is not needed in finite-horizon where value iteration requires exactly H backward induction steps. Without bonuses, the design of P̃ would have directly entailed that L̃ is contractive and convergent [Bertsekas, 1995]. However, our variance-aware exploration bonuses introduce a subtle correlation between value iterates (i.e., b depends on V in Eq. 6), which leads to a cost function that varies across iterates. By directly analyzing L̃, we establish that it is contractive with modulus ρ := 1− ν < 1, where ν := mins,a P̃ s,a,g > 0. This contraction property guarantees a polynomially bounded number of iterations before terminating, i.e., (2).
Remark 1 (Computational complexity). Denote by T the accumulated time within the K episodes. By the stopping condition ||V (i+1) − V (i)||∞ ≤ VI, the choice of VI and the ρ-contraction of the operator L̃ with ρ ≤ 1 − 1/T , any VISGO procedure is guaranteed to stop at an iteration i ≤ log(max{B?, 1}/ VI)/(1−ρ) = O(TSA log(T max{B?, 1})). Since there are at mostO(SA log T ) VISGO procedures, we see that the total computational complexity of EB-SSP is near-linear in T , where T is bounded polynomially w.r.t.K as shown in the various cases of Sect. 4.1 (see App. G for details). Therefore EB-SSP is computationally efficient. Note that its poly(K) complexity is a limitation shared by all existing parameter-free algorithms in SSP. On the other hand, the algorithm of Cohen et al. [2021] can obtain a log(K) computational complexity but only with T? prior knowledge: without it, using the upper bound T? ≤ B?/cmin, where c−1min becomes poly(K) when applying the cost perturbation trick, also leads to poly(K) complexity. It is an interesting open question whether it is possible in SSP to have log(K) computational complexity while staying parameter-free.

heading: 4 Main Results
text: Besides ensuring the computational efficiency of EB-SSP, the properties of VISGO lay the foundations for our regret analysis (App. D) to yield the following general guarantee.
Theorem 3. Assume that B ≥ max{B?, 1} and that the conditions of Lem. 2 hold. Then with probability at least 1− δ the regret of EB-SSP (Alg. 1 with η = 0) can be bounded by
RK = O (√ (B2? +B?)SAK log ( max{B?, 1}SAT
δ
) +BS2A log2 ( max{B?, 1}SAT
δ
)) ,
with T the accumulated time within the K episodes.
6In fact this transition skewing implies that an SSP problem defined on P̃ is equivalent to a discounted RL problem, with a varying state-action dependent discount factor. Also note that for different albeit mildly related purposes, a perturbation trick is sometimes used in regret minimization for average-reward MDPs [e.g., Fruit et al., 2018, Qian et al., 2019], where a non-zero probability of reaching an arbitrary state at each state-action is added to guarantee that all policies are unichain and that value iteration variants nearly converge in finite-time.
Thm. 3 is an intermediate result for the regret of EB-SSP, as it depends on the random and possibly unbounded total number of steps T executed over K episodes, it requires the possibly restrictive second condition of Lem. 2, and it relies on the parameter B being properly tuned. Nonetheless, it already displays interesting properties: 1) The dependence on T is limited to logarithmic terms; 2) The parameter B only affects the lower order term, while the main order term naturally scales with the exact range B?; 3) Up to dependence on T , the main order term displays minimax optimal dependencies on B?, S, A, and K.
Throughout the rest of the section, we consider for ease of exposition that B? ≥ 1.7 For simplicity, when tuning the cost perturbations later, we assume as in prior works [e.g., Rosenberg et al., 2020, Chen et al., 2021, Chen and Luo, 2021] that the total number of episodes K is known to the agent (this knowledge can be eliminated with the standard doubling trick).
Proof idea of Thm. 3. We decompose the regret into three parts: X1 (error on the optimistic V - values), X2 (Bellman error) and X3 (cost estimation error), and among them the major part is X2. Later, X1 and X2 introduce the intermediate quantities X4 (variance of the optimistic V -values) and X5 (variance of the differences V ? − V ), which are bounded using the recursion technique generalized from Zhang et al. [2021a], where we normalize the values by 1/B? to avoid an exponential blow-up in the recursions. At a high-level, the key idea is to calculate errors of different orders, F (1), F (2), . . . , F (d), . . . (see Lem. 24 and 25), and recursively bound F (i)’s variance by a sublinear function of F (i+ 1). Throughout the proof, we bound quantities by solving inequalities that contain the unknown quantities on both sides, such as X3 ≤ Õ( √ X3 + CK) or X2 ≤ Õ( √ X2 + CK), where the random variable CK denotes the cumulative cost over the K episodes. Indeed, the analysis at each time step t brings out the instantaneous cost ct and it is important to combine them so that we can make CK appear explicitly. Ultimately, we obtain a regret bound scaling as RK = Õ(( √ B? + 1) √ SACK). Since the regret in SSP is defined as RK = CK −KV ?(s0), we
obtain a quadratic inequality in CK , which we solve to get the Õ( √ (B2? +B?)SAK) regret bound.

heading: 4.1 Regret Bounds for B = B?
text: First we assume that B = B? (i.e., the agent has prior knowledge of B?) and we instantiate the regret achieved by EB-SSP under various conditions on the SSP model.
Positive Costs. We first focus on the case of positive costs. Assumption 4. All costs are lower bounded by a constant cmin > 0 which is unknown to the agent.
Asm. 4 guarantees that the conditions of Lem. 2 hold. Moreover, denoting by C the cumulative cost over K episodes, the total time satisfies T ≤ C/cmin. By simplifying the bound of Thm. 3 as C ≤ B?K +RK ≤ O(B?S2AK · √ B?TSA/δ), we loosely obtain that T = O(B3?S
5A3K2/(c2minδ)). Corollary 5. Under Asm. 4, running EB-SSP (Alg. 1) with B = B? and η = 0 gives the following regret bound with probability at least 1− δ
RK = O ( B? √ SAK log ( KB?SA
cminδ
) +B?S 2A log2 ( KB?SA
cminδ
)) .
The bound of Cor. 5 only depends polynomially on K,S,A,B?. We note that T? ≤ B?/cmin and that this upper bound only appears in the logarithms. Under positive costs, the regret of EB-SSP is thus (nearly) minimax and horizon-free. Furthermore, in App. B we introduce an alternative assumption on the SSP problem (which is weaker than Asm. 4) that considers that there are no almost-sure zero-cost cycles. In this case also, the regret of EB-SSP is (nearly) minimax and horizon-free.
General Costs and T? Unknown. Now we handle the case of non-negative costs, with no assumption other than Asm. 1. We use a cost perturbation argument to generalize the results from positive to general costs (similar to Tarbouriech et al. [2020a], Rosenberg et al. [2020]). As reviewed in Sect. 2, this circumvents the second condition of Lem. 2 (which holds in the cost-perturbed MDP) and target the optimal proper policy in the original MDP up to a bias scaling with the cost perturbation. Indeed, running EB-SSP with costs cη(s, a)← max{c(s, a), η} for η ∈ (0, 1] gives the bound of Cor. 5 with cmin ← η, B? ← B? + ηT? and an additive bias of ηT?K. We then pick η to balance these terms.
7Otherwise, all later bounds hold by replacing B? with max{B?, 1}, except for the B? factor in the leading term that becomes √ B?. This matches the lower bound of Cohen et al. [2021] of Ω( √ B?SAK) for B? < 1.
Corollary 6. Let L := log ( KT?SAδ −1). Running EB-SSP (Alg. 1) with B = B? and η = K−n for any choice of constant n > 1 gives the following regret bound with probability at least 1− δ
RK = O ( nB? √ SAKL +
T? Kn−1
+ nT? √ SAL
Kn−1/2 + n2B?S
2AL2 ) .
This bound can be decomposed as (i) a √ K leading term and (ii) an additive term that depends on T? and vanishes as K → +∞ (we omit the last term that does not depend polynomially on either K or T?). Note that the second term (ii) can be made as small as possible by increasing the choice of exponent n in the cost perturbation, at the cost of the multiplicative constant n in (i). Equipped only with Asm. 1, the regret of EB-SSP is thus (nearly) minimax, and it may be dubbed as horizon-vanishing when K is given in advance, insofar as it contains an additive term that depends on T? and that becomes negligible for large values of K (if K is unknown in advance, the application of the doubling trick yields an additive term (ii) scaling as T?). We now show that the trade-off between (i) and (ii) can be resolved with loose knowledge of T? and leads to a horizon-free bound.
General Costs and Order-Accurate Estimate of T? Available. We now consider that an orderaccurate estimate of T? is available. It may be a constant lower-bound approximation away from T?, or a polynomial upper-bound approximation away from T?.
Assumption 7. The agent has prior knowledge of a quantity T ? that verifies T?υ ≤ T ? ≤ λT ζ ? for some unknown constants υ, λ, ζ ≥ 1. (Note that υ = λ = ζ = 1 when T? is known.)
We now tune the cost perturbation η using T ?. Specifically, selecting η := (T ?K)−1 ensures that the bias satisfies ηT?K ≤ υ = O(1). We thus obtain the following guarantee (see App. C for the explicit dependencies on the constant terms υ, λ, ζ which only appear as multiplicative and additive factors).
Corollary 8. Under Asm. 7, running EB-SSP (Alg. 1) with B = B? and η = (T ?K)−1 gives the following regret bound with probability at least 1− δ
RK = O ( B? √ SAK log ( KT?SA
δ
) +B?S 2A log2 ( KT?SA
δ
)) .
This bound depends polynomially onK,S,A,B?, and only logarithmically on T?. Thus under general costs with an order-accurate estimate of T?, EB-SSP’s regret is (nearly) minimax and horizon-free.
We can compare Cor. 8 with the concurrent result of Cohen et al. [2021]. Their regret bound scales as O(B? √ SAKL + T 4?S
2AL5) with L = log(KT?SAδ−1) under the assumptions of known T? and B? (or tight upper bounds of them), which imply that the conditions of Cor. 8 hold. The bound of Cor. 8 is strictly tighter, since it always holds that B? ≤ T? and the gap between the two may be arbitrarily large (see e.g., App. A), especially when some instantaneous costs are very small.
4.2 Regret Bounds for Unknown B? with Parameter-Free EB-SSP
We now introduce a parameter-free version of EB-SSP that bypasses the requirement of B ≥ B? (line 2 of Alg. 1). Note that the challenge of not knowing the range of the optimal value function does not appear in finite-horizon MDPs, where the bound H (or 1 for Zhang et al. [2021a]) is assumed to be known to the agent. In SSP, if the agent does not have a valid estimate B ≥ B?, then it may design an under-specified exploration bonus which cannot guarantee optimism. The case of unknown B? is non-trivial: it appears impossible to properly estimate B? (since some states may never be visited) and it is unclear how a standard doubling trick may be used.8
Parameter-free EB-SSP initializes a proxy B̃ = 1 and increases it over the learning interaction according to a carefully defined schedule. We need to ensure that the proxy B̃ does not remain below B? for too long, since in this case, the regret may keep growing linearly. Thus, our first condition to increase B̃ is whenever a new episode k begins, specifically we set B̃ ← max{B̃, √ k/(S3/2A1/2)}, which ensures that B̃ ≥ B? for large enough episodes. However, this is not enough: indeed notice that when B̃ < B?, the agent may never reach the goal and thus get stuck in the episode, so we cannot
8Note that Qian et al. [2019] raised an open question whether it is possible to design an exploration bonus strategy in a setting where no prior knowledge of the “optimal range” is available. Indeed their approach in average-reward MDPs relies on prior knowledge of an upper bound on the optimal bias span.
exclusively rely on the end of an episode as a trigger for increasing B̃. Our second condition to increase B̃ is to set B̃ ← 2B̃ whenever the cumulative cost exceeds a carefully defined threshold (that depends on B̃, S, A, δ and the current episode and time indexes k and t, which are all computable quantities). Since the regret is upper bounded by the cumulative cost, this second condition prevents the learner from accumulating too large regret when B̃ < B?. Finally, we introduce a third condition to increase B̃ in order to ensure the computational efficiency, since VISGO may diverge when B̃ < B? (specifically, we track the range of the value V (i) at each VISGO iteration i and if ‖V (i)‖∞ > B̃, then we terminate VISGO and increase B̃ ← 2B̃). At a high-level, the analysis of the scheme proceeds as follows: we bound the regret by the cumulative cost when B̃ < B? (first regime), and by the regret bound of Thm. 3 when B̃ ≥ B? (second regime). Note that this two-regime decomposition is only implicit (i.e., at the level of analysis), since the agent is unable to know in which regime it is (since B? is unknown). The full pseudo-code and analysis of parameter-free EB-SSP is deferred to App. H. Theorem 9 (Extension of Theorem 3 to unknown B?). Assume the conditions of Lem. 2 hold. Then with probability at least 1−δ the regret of parameter-free EB-SSP (Alg. 2, App. H) can be bounded by
RK = O ( R?K log ( B?SAT
δ
) +B3?S 3A log3 ( B?SAT
δ
)) ,
where T is the cumulative time within the K episodes and R?K bounds the regret after K episodes of EB-SSP in the case of known B? (i.e., the bound of Thm. 3 with B = B?).
Thm. 9 implies that we can remove the condition of B ≥ max{B?, 1} in Thm. 3, i.e., we make the statement parameter-free. Hence, all the regret bounds from Sect. 4.1 in the case of known B? (i.e., Cor. 5, 6, 8, 11) still hold up to additional logarithmic and lower-order terms when B? is unknown.

heading: 5 Conclusion
text: We introduced EB-SSP, the first algorithm for online SSP to be simultaneously nearly minimaxoptimal and parameter-free (i.e., it does not need to know T? nor B?). Also in various cases its regret is nearly horizon-free with only a logarithmic dependence on T?, thus exponentially improving over existing bounds w.r.t. the dependence on T?, which may be arbitrarily larger than B? when instantaneous costs are small. The horizon-free property is perhaps even more meaningful in the goal-oriented setting than in finite-horizon MDPs (with total reward bounded by 1) [e.g., Wang et al., 2020a, Zhang et al., 2021a,b], as we do not impose a known constraint on the total cost of a trajectory.
An interesting question raised by our paper is whether it is possible to simultaneously achieve minimax, parameter-free and horizon-free regret for SSP under general costs. Another direction can be to build on our approach (e.g., the VISGO procedure) to derive tight sample complexity bounds in SSP, which as explained by Tarbouriech et al. [2021] do not directly ensue from regret guarantees.

heading: Acknowledgement
text: SSD gratefully acknowledges the funding from NSF Award’s IIS-2110170 and DMS-2134106.

Review summaries:
This paper investigates the problem of regret minimization of the stochastic shortest path, which is actively studied in the recent two years. The main contribution is a novel algorithm that enjoys nearly minimax optimal regret, matching the existing lower bound up to some log factors. Furthermore, the algorithm, as well as its variant, enjoy other desired properties, including parameter-free (does not require the knowledge of $B_\star$ or $T_\star$) and horizon-free (does not depend on $T_\star$)

This paper studies regret minimization in stochastic shortest paths. It presents an algorithm with regret that is: minimax optimal, parameter-free and horizon-free (in various cases). Here, horizon-free refers to logarithmic dependence in the expected time of the optimal policy (that replaces the horizon in finite-horizon problems).

This work studies the problem of learning stochastic shortest path (SSP) with unknown transition. The authors propose a model-based parameter-free algorithm EB-SSP which achieves the minimax regret rate O(B sqrt(SAK)), where B is the expected cumulative cost of the optimal policy, without prior knowledge of B or T (the expected time-to-goal of the optimal policy). The authors further consider several cases where the regret only has a logarithmic dependence on T.