Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
Authors: Jean Tarbouriech
Runlong Zhou
Simon Shaolei Du
Matteo Pirotta
Michal Valko
Alessandro Lazaric
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: regret minimization
stochastic shortest path
reinforcement learning theory
minimax optimal

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 $\widetilde{O}(B_{\star} \sqrt{S A K})$, where $K$ is the number of episodes, $S$ is the number of states, $A$ is the number of actions and $B_{\star}$ 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_{\star}$, nor of $T_{\star}$, 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_{\star}$ is available) where the regret only contains a logarithmic dependence on $T_{\star}$, thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.

Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
Jean Tarbouriech" Facebook Al Research & Inria Lille jean. tarbouriech@gmail com
Runlong Zhou" Tsinghua University zhouruullougrector@gaaa...cc com
Simon S. Du University of Washington & Facebook Al Research ssduêcs. washington. edu
Matteo Pirotta
Facebook AI Research Paris
pirottaffb.c com
Michal Valko
Alessandro Lazaric Facebook Al Research Paris lazaric0fb com
Deep Paris
valkkom@deepiid..c com
Abstract
We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks minimize the expected cost accumulated before reaching a goal state. We design 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 converge. We prove that EB-SSP achieves the minimax regret rate O(B.VSAL where K is the number of episodes, S the number of states, 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 free, i.c., it does not require any prior knowledge of B., nor T., which bounds the expected time-to-goal the optimal policy from any state. Furthermore, illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of T, is available) where the regret only contains logarithmic dependence T., thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.
Introduction
Stochastic shortest path (SSP) is a goal-oriented reinforcement learning (RL) setting where the agent aims to reach 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 (c.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 performance close
"quul contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

as possible to the optimal policy x², that is, the agent should achieve low regrer (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 learning algorithm in online SSP.
Minimax. The information-theonee theooreic lower bound on the regret is Q(B. VSAK) [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, 2 1).
Desired property 1:
An algorithm for online SSP is (nearly) minimax optimal if its regret is bounded by Ö(B.VSAN up to logarithmic factors and lower-order terms.
Desired property 2: Parameter-free. Another relevant dimension is the amount of prior knowl- edge required by the algorithm. While the knowledge of S, A, and the cost (or reward) range [0, 1] is standard across segret-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. S T, always holds since the cost range is [0, 1J. 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 lower-order term. An algorithm for online SSP is (nearly) horizon-free if its regret depends only logarithmically T..
Our definition extends the property of so-called horizon-free bounds recently uncovered in finite- horizon MDPs with total reward bounded by 1 [Wang et al., 2020a, Zhang et al., 202 la.b.. These bounds depend only logarithmically any policy terminates. Such notion of horizon would clearly he 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.
the horizon H, which is the number of time steps by which
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 reviews the existing work on online learning in SSP. The setting was first studied by Tarbouriech et al. [2020a] who gave parameter-free algorithm with a (KK3/2) regret guarantee. Rosenberg et al. [2020] then improved this result by deriving the first order-optimal algorithm with regret Ö(B² SvAK) the parameter-free case and /AK) if B, is known (to tune cost perturbation appropriately). Both approaches model-optimistic, 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 black- box reduction from SSP to mnite-horizon MDPs. It successively tackles finite-horizon problems with horizon set to H = (2(T.) and costs augmented by terminal cost set to Cи (s) 52 B, I(s & 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 regret bound of O B. SAKK L, + 5 ALL5), with L, = log( NTT,SAA-1 (with probability at least 8). It achieves a nearly minimax- optimmll rate, however it relies on both T, and B. prior knowledge to tune the horizon and terminal cost in the reduction, respectively.'
We refer the reader to Neu and Burke [2020] for details on the differences and interplay between model-optimistic and value-optimistic approaches.
As 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 Cain case general costs with a perturbation argument, their regret guarantce worsens from Ö(vK + c ) to O(Kr4/5) because of the poor additive dependence on emin-

---

Horizon- Free
Algorithm
Regret
Minimax
Parameters
[Tarbouriech et al., 2020a]
Ōx((2(1))
No
None
No
Ö(B,SVAK + +T.
No
B.
No
[Rosenberg et al., 2020]
ÖBB +T.B.S²A)
No
None
No
[Cohen et al., 2021] (concurrent work)
Ö(B.VSAK + +
Yes
B., T.
No
ÖBBVSAK B.S
B.,
ÖBB.SAK BBS A pay(()))
Yes
No
This work
B..SAK + S
Yes
T.
Yes
ÖBB.VSAK B A
Yes
None
No
Lower Bound
(((B.SAK))
Table Regret comparisons of algorithms online SSP (we assume for simplicity that B. 2 1). The notation Ō omits logarithmic factors and ÖR only reports the dependence in K. Regret is the performance metric of Eq. I. Minimax: Whether the regret matches the /SA)) lower bound [Rosenberg et al., 2020], up to logarithmic and lower-order terms. Parameters: The parameters that the algorithm requires as imput: either both B. and T.,
of them, only logarithmically on T. "If K is known in advance, the additive term T. T./ /poly(K) has a denominator that polynomial in K, so becomes negligible for large values of (if K is unknown, the additive term is T.). See Sect. 4 for the full statements of our bounds.
(i.e.. parameter-free) Horizon-Free: Whether the regret bound depends
Finally, all existing bounds contain lower-order dependencies either on T. in the case of general costs, B./mmin in the case of positive costs lower bounded by Gmin (note that T, /mmin 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), new algorithm for online SSP. It in- troduces 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 tran- sitions towards reaching the goal from each state-action pair with positive probability. Under these biased transitions, all policies are fact proper (i.e., they eventually reach the goal with probability starting from any state). We decay the bias over time in 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 model-optimistic approach² [Tarbouriech al., 2020a, Rosenberg et al., 2020], and it does not rely on reduction from SSP to finite-horizon [Cohen et al., 2021] (i.c., we operate the level of the non-truncated SSP model);
EB-SSP is the first algorithm to achieve the minimax regret rate of Ö(B, ((B.SAA)) 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. XTς for some unknown constants A. 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
3

---

relying on T, and B., its regret is A), 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 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-exploitttio dilemma in tabular MDPs has been extensively studied in imite-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 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].² Tarbouriech et al. [2021] study the sample complexity of SSP with 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., multi- goal SSP or goal-conditioned RL) were analyzed by Lim and Auer [2012], Tarbouriech et al. [2020b].
2 Preliminaries
An SSP problem an MDP M := AS, so. g).g), where S the finite state space with cardinal- ity S. A is the finite action space with cardinality A, and So E 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 cost drawn i.i.d. from a distribution on [0, 1 with expectation c(s. a), and the next state s' E S' is selected with probability ((s'(s,a) a) (where Eves: P(s'ls, a) 1). The goal state g absorbing and zero-cost, i.e., P(glg, a) and c(g, a) 0 for any action a.
For notational convenience, let Ps.a == P(- a). P...s == P(s'ls, a). For any two vectors X, Y of size S¹, we write their inner product as XY = E.es (s), we denote by X2 the vector let
| |lo == max,es ((s)). |X| Fg = max.es (s)) and if X is probability distribution on S', then V(X,Y) = E.es X()) (s) (E.ss EEs X(s){(s))²
X(S)) (2))?
A stationary and deterministic policy π. S - A is a mapping from state s to action x(s). A policy ı 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 Uproper 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., Ippperr A 0.
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 Q-function are defined as
V*((s: = lim
E
Σ
ci(s, (s:)) 81 = ]). Q" (s. = lim E
Σ ci(s,, ((s))) 81 = s, =(1)
T-2000
T-
where e E 1). is the (instantaneous) cost incurred at time at state-action pair (st, (st)), and the expectation is w.r.t. the random sequence of states generated by executing I starting from state s E S (and taking action E in the second case). Note that / may have unbounded components if π never reaches the goal. For a proper policy (*))) and Q (s, a) are finite for any 8, a. By definition of the goal, we set (*(g) = Q" (g. a) = for all policies π and actions a. Finally, we
regret in SSP to be /SAK + B,SA) (by analogy with the conjecture of Menard et al. [2021] for finite- muite-horizon MDPs), which shows the tightness of our bound up an S' lower-order factor.
'We conjecture the optimal
A different line of work (e.g. Neu et al., 2010, 2012, Rosenberg and Mansour, 2019a,b, Jin et al., 2020, Jin and Luo, 2020J studies horte-horizon MDPs with adversarial costs (sometimes called online loop-free SSP), where episode ends after fixed number of H steps (as opposed to lasting long the goal is reached).

---

denote by T the expected time that π takes to reach starting at state s; in particular, if π is proper then T (s) finite for all s, yet if is improper there must exist least one s such that T (s) = co.
Equipped with Asm. and an additional condition on improper policies defined below, one can derive important properties on the optimal policy n² that minimizes the value function component-we wise.
Lemma 2 (Bertsekas and Tsitsiklis, 1991;Yu and Bertsekas, 2013). Suppose that Asm. I holds and that for every improper policy n' there exists at least one state s E 8 such that V (s) +oc. Then the optimal policy nt stationary, deterministic, and proper. Moreover, V* V=* is the unique solution of the optimality equations V LV* and (s) < +00 for any s E S, where for any vector V E & the optimal Bellman operator L is defined as LV(s) == min (){s,a)= + Pa.VV.. 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 and V (s) = m Q* a), for all (s.a) E S x 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 instantancous costs are strictly positive. To deal with the case of non-negative costs, we can introduce a small additive perturbation 1) E (0, 1] all costs to yield new (strictly positive) cost function Cy,(s, a) max s. a), n). In this cost-perturbie we get an optimal policy म that is stationary, deterministic and proper and has finite value function VI Taking the limit as 17 + O, we have that म + π and V + V**, where n 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. hold.
MDP, the conditions of Lem. 2 hold so
Learning formulation. We consider the learning problem where the agent does not have any prior knowledge of the cost function or transition function P. Each episode starts at the initial state so (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
K
RK
&
- K. min (=*()), Elllgape
(1)
k=1
where 1 is the time needed to complete episode k and ct is the cost incurred in the h-th step of episode k when visiting (sh, ). If there exists k such that _ is infinite, then we define Rx = co.
Throughout we denote the optimal proper policy by x² and (s) = V" (s) = min V*((s) (s) and (*, a) Q= as mil QT a) for all (s, a). Let B. 0 bound the values
of V*, i.e., B, == msx (s). Note that Q* a) S 14 B,. Also let T. > 0 bound the expected
time-to-goal of the optimal policy, i.e., T. == max.ss T (s). We see that B, S T. < t00.
3 Main Algorithm
We introduce our algorithm EB-SSP (Exploration Bonus for SSP) in Alg. 1. takes as input the state-action space S x A and confidence level 8 E (0, 1). For now it considers that an estimate B such that B 2 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 small cost perturbation 7) E [o, 1] (cf. lines 3, 12 in Alg. 1) - either r = 0 if the agent is aware that all costs are already positive, otherwise careful choice of 17 > 0 is provided in Sect. 4.
Our algorithm builds on 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 action pair doubled, the algorithm updates the empirical cost and transition probability of this state-action pair, and computes 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 why we perform the policy update instantancously when the doubling condition is met.
5

---

Algorithm 1: Algorithm EB-SSP
Input: S, 8o E E;; g $ S, A,
Input:
an estimate guaranteeing 2 max B.; 11 (see Sect. 4.2 and App. H not available).
Optional input: cost perturbation E [0.
Specify: Trigger set +- {25-1 - -.2,,..., Constants 0₁ = 6, o2 = 36, C3 2v2, cs = 2v/2
For (s, ) E 8 x A x S', set ((s,a) + 0; n(s,a) + 0; a() - 0: Pa,n.a' + 0;
((s,a) 0; (( <- 0: (s. < 0; (s) <-0.
Set initial time step <- 1 and trigger index 0.
for episode k 2......d.
Set 9. + 5p
while $: F do
Take action d, arg arg.aiigg a4 (ss a). incur cost e, and observe next state 8141 P(-(st,
11
Set (s,a,8 8'..) < (st, 8141, max (ct, and ++1 ((s, + B(s, a) N(s,a,))) + a1)
12
Set N(s, a) (s.
13
(s, E E then
14
W Update triggered: VISGO procedure.
15
Set (et,(s)))) + + I[N 2 2] N(s.o)
20(a.)) + [[N(s, a) = 1]0(s, and (() +.
For s' E Ps. <- N(s, a, s'N((,, n(s, N(s. a). and P. Pao.or as Eq.
16
17
S
- 2 2 (SA) and 0. y() - 0. v(-1) - t00.
For all (s, 5 A, set (s, + max(n(s. 13 and ta.a In [25 (o.)1²)
while || -(- |o evi do
For all (+, E S A, sel
(1+2)) (s,a) + 6(V(), s, a,,
Wsee Eq. for bomus expression
(2)
@ + max (ā(s,0) + P(.v(()) (s, 0},
(3)
v(+)((s) (s) min ((++1) (s,
(4)
Set ((+41) (g) and i e 1+1.
Set Q - Q V <- v()
23
The main algorithmic component lies in how 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 /(0) = 0, iteratively computes ((+1) = [V(() for carefully defined operator É. ends when a stopping condition met, specifically once [|{(++)) - || S Evr for a precision level Evi > 0 (specified later), and it outputs the values /(i+1) (and Q-values Q(++1)). We now explain how we design E and then provide some intuition. Let P and be the current empirical transition probabilities and costs, and let n(ssa a) be the current number of visits to state-action pair (s, a) (and n+ (s, a) max (n,s, a), })). We first define transition probabilities P that are slightly skewed towards the goal w.r.t. P. as follows
n(s,a) +1 .... Tis'
n(s,a) P
Ps.a.''
a(s,a)+ a) +1
Given the estimate B, specific positive constants C1, C2 C3, and state-action dependent logarithmic term ls.a, we then define the exploration bonus function, for any state-action pair (s, A and
vector V E S' such that V(g) = O, as follows
6(V, a) max { (
V(P.a. V)LeR nt as)
Bis C2 nt(ss
ass n ())
B BVSi
+ cst
+ ci 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 E as
[v(s) (s) = max { min (A(s.a) a) + P..V -(V, a)). 0).
(7)
We see that E promotes optimism in two different ways:

---

On the empirical cost function ?, via the bonus (Eq. 6) that intuitively lowers the costs to ė b; On the empirical transition function P, via the transitions P (Eq.5) 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) standard in 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 P may diverge. Our simple transition skewing actually guarantees that all policies decaying the extra goal-reaching probability inversely with n(s, a), we can tightly control the gap between P and and ensure that it only accounts for a lower-order regret term (cf. last term of Eq. 6).
approaches, the second (ii) SSP-specific,
proper in P, for any fixed and bounded cost function." By
Equipped with these two sources of optimism, as long as B 2 B,, we are able to prove that 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 (s,a) & (s) Vi O,
(2) Finite-time near-convergence. VISGO terminates within finite number of iteration steps (note
that the final iterate V(J) approximates the fixed point of & up to an error scaling with év1).
To satisfy (1), we derive similarly to MVP [Zhang et al., 2021a] a monotonicity property for the operator E, which is achieved by carefully tuning the constants c C22 C3, C4 in the bonus of Eq. 6. On the other hand, the requirement (2) is SpP-spec,fie, since it is not needed in finite-horizon where value iteration requires exactly H backward induction steps. Without bonuses, the design of Í would have directly entailed that Σ 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 a cost function that varies across iterates. By directly analyzing L, we establish that it is contractive with modulus p == V < where v := min, Ps.a.g 0. This contraction property guarantees polynomially bounded number of iterations before terminating, i.e., (2).
Remark (Computational complexity). Denote by T the accumulated time within the K episodes. By the stopping condition [| | Evi. the choice of évi and the p-contraction of the operator E with p < - 1/T, any VISGO procedure is guaranteed to stop an iteration i < log(max( B., /c/)////111- VISGO procedures, we see that the total computational complexity of EB-SSP is near-linear in T. where is bounded polynomially w.r.t. K as shown in the various cases Sect. 4.1 (see App. G for details). Therefore EB-SSP computationally efficient. Note that its poly () complexity is limitation shared by all existing parameter-free algorithms in SSP. On the other hand, the algorithm of Cohen al. [2021] can obtain a log( K) computational complexity but only with T, prior knowledge: without it, using the upper bound T, < B_/Cunnn Crnnn where e 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 have log(K) computational complexity while staying parameter-free.
= O log(T max B.. 1))). Since there are at most O A log T)
4 Main Results
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 2 max B., and that the conditions of Lem. 2 hold. Then with probability least 8 the regret of SSP (Alg. I with r) = 0) can be bounded by
Rx = - +B.JSKK log
max B., 1JSAAA
mmxx B., 1)SAT
B.JSAK
+ BS² BSS Alog²
8
8
with T the accumulated time within the K episodes.
'In fact this transition skewing implies that an SSP problem defined on P is equivalent discounted RL problem, with a varying state-acti action dependent discount factor. Also note that different albeit mildly related purposes, a perturbation trick is sometimes used in regret minimization for everage-rewart MDPs [e.g.. Fruit et al., 2018, Qian et al., 2019], where 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 fnite-time.
7

---

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. 2 1. For simplicity, when tuning the cost perturbations later, we assume as in prior works [e.g.. Rosenberg et al., 2020, Chen 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: 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()) F(d).... ..... (see Lem. 24 and 25), and recursively bound F(i)'s 's variance by 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 I O(vX3 + Ck) or X2 I Õ(VX, + Ck), Cx), 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 c and it is important to combine them so that we can make Cw appear explicitly. Ultimately, we obtain a regret bound scaling as Rx- = Ö((V + L)vSACK)). Since the regret in SSP is defined as Rx = Cx K (*()) we obtain a quadratic inequality in CK, which we solve to get the Ö(V(B3 + B.)SAK) regret bound.
X1 (error on the optimistic V-
4.1 Regret Bounds for B = B.
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.
O Positive Costs. We first focus the case of positive costs.
Assumption 4. All costs are lower bounded by a constant Cmii > O 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 I C//minn By simplifying the bound of Thm. 3 as C' & B.K + Rx S O(BSS AK BB SSTSSAA A/8)) we loosely obtain that T = O O A K²K (c2in 5))- Corollary 5. Under Asm. 4, rumning EB-SSP (Alg. 1) with B B, and 17 = 0 gives the following
regret bound with probability at least 1 -
Rx = o B. B.V log
(BBSA) C
+ B.. Alog"
K KBBAA) C
The bound of Cor. 5 only depends polynomially on K, S, B.. We note that T. S 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 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 neg-negetive costs, with no assump- tion 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), m) for 17 E (0, 1] gives the bound of Cor. 5 with Cuinn 17, B. < B, + T/T, and an additive bias of 1/T, K. We then pick to balance these terms.
'Oteerwise, all later hounds hold by replacing B. with max BA, 1}, except for the B. factor in the leading term that becomes VB. This matches the lower bound of Cohen et al. [2021] of ((VB. SAK) for B. < 1.
8

---

Corollary 6. Let L == log( [T, (KT,SAE Running EB-SSP (Alg. 1) with B = B. and n = K for any choice of constant n gives the following regret bound with probability at least 6
Rx = On..OBB.SARK +
T. Kn-1 +
n.. nT. Kn-1/2 + n²B
This bound can be decomposed as (i) a VK leading term and (ii) an additive term that depends on T, and vanishes as K + +oo (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- 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.
D General Costs and Order-Accurate Estimate of T, Available. We now consider that an order- accurate estimate of T, is available. It may be a constant lower-bound approximation away from T,, or polynomial upper-bound approximation away from T..
Assumption 7. The agent has prior knowledge of quantity T. that verifies L. S T. S XI for v. some unknown constants X. 1. (Note that v = X 5= when T. is known.)
We now tune the cost perturbation rj using T.. Specifically, selecting 1j := (T_K)-1 ensures that the bias satisfies T/T,K So= O(1). We thus obtain the following guarantee (see App. C for the explicit dependencies on the constant terms v, X, which only appear as multiplicative and additive factors).
Corollary 8. Under Asm. 7, running EB-SSP (Alg. 1) with B = B, and = (T.K)-I gives the
following regret bound with probability at least 1 -8
Rx 0 o B. B.VSAK log
KT,SA 8
KTTSA
+ ABoS
This bound depends polynomially on K, S. A, B., and only logarithmically on T.. Thus under general costs with an order-accurate estimate of T., EB-SSP regret is (nearly) minimax and horizon-free.
We can compare Cor. with the concurrent result of Cohen et al. [2021]. Their regret bound scales as O D(B.VSAK VSKL + TA5² with L = log( KT.5 A8-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. I T, and the gap between the two may be arbitrarily large (see e.g.. App. A), especially when some instantancous 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 Z 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 for Zhang al. [2021a]) is assumed to be known to the agent. In SSP, if the agent does not have valid estimate B > B. then it may design an under-specified exploration bonus which cannot guarantce 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.
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 7 is whenever new episode k begins, specifically we set B <- max ( B, Vke A1/2)}, which ensures that B 2 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
"Note that Qian et al. [2019] raised an open question whether it is possible to design an exploration bonus strategy in setting where no prior knowledge of the "optimal range" is available. Indeed their approach in average-reward MDPs relies prior knowledge of an upper bound on the optimal bias span.

---

exclusively rely on the end of an episode trigger for increasing B. Our second condition to increase B is to set B t- 2B whenever the cumulative cost exceeds carefully defined threshold (that depends on B. S, A, 8 and the current episode and time indexes k and which are all computable quantities). Since the regret 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 (ii) at each VISGO iteration i and |l > 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 < 3 (first regime), and by the regret bound of Thm. when B 2 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" unknown). The full pseudo-code and analysis of parameter-fres free EB-SSP deferred to App. H.
Theorem (Extension of Theorem 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
Rx = -0 R' log
O
(BSSAT)
[BSAAT)
+ 5 A Algg
8
where T is the cumulative time within the K episodes and R& 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. implies that we can remove the condition of B 2 max ( Bx, 13 Thm. 3, i.e., we make the statement parameter-free. Hence, all the regret bounds from Sect. 4.1 in the case of known B2 (i.e., 5or.5, 6, 8, 11) still hold up to additional logarithmic and lower-order terms when B, is unknown.
Conclusion
We introduced EB-SSP, the first algorithm for online SSP to be simultaneously nearly minimax- optimal and parameter-fre (i.e., it does not need to know T, nor B.). Also in various cases its regret is nearly horizon-free with only 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 instanta- neous costs 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 al., 2021 b,,
do impose a known constraint on the total cost of trajectory.
An interesting question raised by our paper is whether it is possible to simultancously achieve minimax, parameter-free free and horizon-fiee 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.
Acknowledgement
SSD gratefully acknowledges the funding from NSF Award's 101-01 and DMS-2134106.
References
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pages 263-272. JMLR. org, 2017.
Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint arXiv: 2012.
Dimitri Bertsekas. Dynamic programming and optimal control, volume 2. 1995.
Dimitri P Bertsekas. Linear network optimization: algorithms and codes. Mit Press, 1991.
10

---

Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):880-59)) 1991.
Dimitri P Bertsekas and Huizhen Yu. Stochastic shortest path problems under weak conditions. Lab. for Information and Decision Systems Report LIDS-P-2909, MIT, 2013.
Blai Bonet. On the speed of convergence of value iteration stochastic shortest-path problems. Mathematics of Operations Research, 32(2):35-3373 2007
Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. arXiv preprint arXiv:2102.05288 2021.
Liyu Chen, Haipeng Luo, and Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference on Learning Theory, pages 1180-1215. PMLR, 2021.
Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path. arXiv preprint vrXiv:2133.13056, 2021.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In Advances Neural Information Processing Systems, 2019.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient Stas-span-constraan exploration-exploittton in reinforcement learning. In International Conference on Machine Learning, pages 1578-1586. PMLR, 2018.
Matthieu Guillot and Gautier Stauffer. The stochastic shortest path problem: polyhedral combina- torics perspective. European Journal of Operational Research, 285(1):1488-1) 158, 2020.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Ap)):153311600 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873, 2018.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860-488 4869. PMLR, 2020.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in Neural Information Processing Systems, 33, 2020.
Andrey Kolobov, Mausam, Daniel Weld, and Hector Geffner. Heuristic search for generalized stochastic shortest path mdps. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 21, 2011.
Shiau Hong Lim and Peter Auer. Autonomous exploration for navigating in mdps. In Conference on Learning Theory, pages 40-1. JMLR Workshop and Conference Proceedings, 2012.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. arXiv preprini arXiv:0907.37700, 2009.
Pierre Menard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum q-learning: Correcting the bias without forgetting. In Proceedings of the 38th International Conference on Machine Learning, pages 7609-7618, PMLR, 2021.
Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 1392-1403, 2020..
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-path problem. In COLT, volume 2010, pages 231-243, Citeseer, 2010.

---

Gergely Neu, Andras Gyorgy, and Csaba Szepesvári The adversarial stochastic shortest path problem with unknown transition probabilities. In Artificial Intelligence and Statistics, pages 805-813. PMLR, 2012.
Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Exploration bonus for regret minimization in discrete and continuous average reward mdps. In Advances in Neural Information Processing Systems, pages 4891-4900, 2019.
Aviv Rosenberg and Yishay Mansour. Online convex optimization adversarial markov decision processes. In International Conference Machine Learning, pages 4478- PMLR, 2019a.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32:2212-2221 2019b.
Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI-21, pages 2936-2942, 2021.
Aviv Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pages 8210-8219. PMLR, 2020.
Max Simchowitz and Kevin G. Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, volume 32, pages 1151-1166 2019.
Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference Machine Learning, pages 9428-9437. PMLR, 2020a.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Improved sample complexity for incremental autonomous exploration mdps. In Advances in Neural Information Processing Systems, volume 33, pages 1 1123--12280 2020b.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Sample complexity bounds for stochastic shortest path with a generative model. In Algorithmic Learning Theory, pages 1157-1178. PMLR, 2021.
Ruosong Wang, Simon S. Du, Lin F. Yang, and Sham M. Kakade. Is long horizon RL more difficult than short horizon RL? In Advances in Neural Information Processing Systems, 2020a.
Yuanhao Wang, Kefan Dong, Xiaoyu Chen, and Liwei Wang. Q-learning with ucb exploration is sample efficient for infiite-horizon mdp. In International Conference on Learning Representations, 2020b.
Chen- Yu Wei, Mehdi JafarniaJaarroi,, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward markov decision processes. In International Conference on Machine Learning, 2020.
Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint arXiv:2102. 04692, 2021.
Huizhen Yu and Dimitri P Bertsekas. On boundedness of q-learning iterates for stochastic shortest path problems. Mathematics of Operations Research, 38(2):209-227, 2013.
Andrea Zanette and Emma Brunskill. Tighter problem regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia referencce-dvvnnaae decomposition. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. Conference on Learning Theory, pages 4528 4531. PMLR, 2021a.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-free free bound for linear mixture mdp. arXiv preprint 1rX1::2101.12745. 2021b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In Proceedings of the 38th International Conference on Machine Learning, pages 12653-12662. PMLR, 2021c
13


Reviews:
[{"review_id": "xMhGNZG_7xl", "reviewer": "Reviewer_rqFE", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Contribution\n\nTo the best of my knowledge, EB-SSP is the first parameter-free algorithm that achieves O(B sqrt(SAK)) regret. This algorithm is designed upon recent advances in episodic MDPs (e.g. Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019) and specifically the Bernstein-type exploration bonus. Importantly, the author adopts the idea of the MVP algorithm of Zhang et al. (2020a) to preserve the monotonicity property of Bellman update, which helps achieve tighter regret bounds. Besides, by slightly biasing the empirical transitions, the algorithm ensures that all induced polices are proper with contributing to a lower order extra term. Such technique is widely used in many tasks.  \n\nOn the other hand, the discussion of various cases is meaningful and inspiring. \n\n2. Weaknesses\n\nDespite the algorithm efficiency, I haven't found any specific weak points of this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is pure theoretical and does not have any potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "Y2GtXJaA4MM", "reviewer": "Reviewer_ZDHq", "summary": "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "For:\n\nThe results of this paper are very impressive. \nIt gives the first parameter-free algorithm that is able to achieve minimax optimal regret, compared to Rosenberg et al. (2020) which is parameter-free but is not minimax optimal (extra $\\sqrt{B^* S} $)  and compared to Cohen et al. (2021) that is minimax optimal but needs to know $T^*$ and $B^*$.\nMoreover, the algorithm enjoys graceful dependence on $T^*$ (i.e., logarithmic in some cases) compared to polynomial dependence in previous work.\n\nAgainst:\n\nMy main concern with this paper is that it is not written in a way that lets readers understand the theoretical analysis of the algorithm.\nI think that this paper does a great job presenting the problem, related work, algorithm (including algorithmic novelties) and main results. However, the analysis and the proof techniques are almost non-existent in the main paper and do not focus on the new technical contributions of the paper. Therefore, I think that the chance that a reader could learn these contributions and that they will affect future work is very limited. Moreover, it was very hard for me to follow the analysis in the appendix without the intuition that proof sketches are supposed to give (this is the reason why I cannot say with absolute certainty whether the proofs are correct). In my opinion this paper could have much more impact on the theoretical community (this is clearly a paper for this community),  if the authors clearly conveyed the main ideas behind the proofs and the intuition behind the analysis.\n\nSpecifically, I found the proof sketch of theorem 3 impossible to understand. It lists some facts (that  I could not combine into a proof) without giving a high level idea about what goes on in this proof. This especially goes for the techniques of Zhang et al. (2020a) - the authors do not explain what are those techniques, how they are used and what changes are needed so they work in SSP (and not finite-horizon).\n\nTo me it looks like some of the analysis sketch should have focused on properties (1) and (2) of the VISCO procedure. As the authors state, VISCO is the main contribution of this paper (and definitely the most interesting one) and these two properties are the essential components that make the analysis work. However, there is no sketch of this analysis and it is very hard to understand how these properties are proved and how they affect the analysis. \n\nInstead of the analysis, I think the authors put too much focus on the exact form of the regret bound in various cases, which I did not find useful. This goes especially for the \"General Costs and Order-Accurate Estimate of $T^*$ Available\" which diminishes from the importance of the algorithm's regret bound in my opinion, as it (kind of) eliminates the need to be parameter-free since there is an estimate of $T^*$, although the algorithm does not require this knowledge really. I think that the authors should put less emphasis on those cases, state the main theorem in corollary 6 and say how it is stronger if costs are positive or an estimate of $T^*$ is available.\n\nA smaller concern is the computational complexity of the algorithm. While it is polynomial and this is clearly not the focus of the paper, I noticed that $\\epsilon_{VI} $ grows linearly with the number of timesteps (right?) and that the VISCO operator is $(1 - \\nu^2) $-contracting for $\\nu$ which is the minimal transition probability to the goal of the skewed transition function. Doesn't this mean that each computation of the optimistic policy takes time polynomial in $K$ (since $\\nu $ might be $1/K$)? This is quite problematic (and also appears in some optimistic algorithms for linear finite-horizon MDPs).\nI wonder if the algorithm can be made more efficient at the expense of worse regret, by skewing the transitions by $1/\\sqrt{n}$ or maybe something else. Do you think this is possible? If so, looks like a good discussion to add.\nIn general, I think that a discussion about the computational complexity is important so readers can understand that maybe improvements can be made there. This is kind of hidden right now and appears deep in the appendix.\n\nPost rebuttal: I thank the authors for these clarifications, and hope that they will be incorporated into the camera-ready version. I am keeping my original positive score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Kzh5KDH5LRx", "reviewer": "Reviewer_P4gA", "summary": "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$)", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "post rebuttal: I am fine with the authors' rebuttal and keep my score as it is.\n\n===================\n\nThis paper investigates an important problem in modern RL theory -- regret minimization for the stochastic shortest path. The problem itself is actively studied in the recent two years. The recent work [Rosenberg et al., 2020] gives a nearly optimal regret bound for this problem, yet the algorithm requires an unknown parameter $B_\\star$ and also suffers from a $\\sqrt{S}$ suboptimality gap. The paper resolves the two issues by proposing some interesting ideas. From my point of view, the paper is of high quality and the overall presentation is good to follow. I would be happy to recommend the acceptance. Several comments are listed below for the authors' further clarification.\n\n(1) The idea of skewed transition probability is very interesting. As stated in the paper (Line 208), such a skewing guarantees that all policies are proper in the policy class. It would be appreciated if the authors can provide more specific explanations for this argument. In addition, I found the trick related to the recent work on adversarial SSP [Chen et al. 2021], in which the authors use a skewed occupancy measure space. It would be interesting to have some discussions.\n\n(2) The parameter-free part is another important contribution of this paper. However, I have to say that the presentation in the main paper is too thin to understand... (due to page constraints). I remember that there will be an extra page in the camera-ready stage, so the authors are encouraged to add more details, especially about the two-phase adaptation, once got accepted. Furthermore, I am curious that whether a two-layer method could be useful for eliminating the unknown $B_\\star$? The paper [Chen et al. 2021] uses such a mechanism (with multi-scale experts) to remove the prior knowledge of $T_\\star$. I would be happy to see some discussions on this point.\n\n(3) The \"horizon-free\" claim, in my opinion, is not quite strong. In particular, as stated in the table, when achieving minimax optimal and parameter-free, there is actually a factual dependence on $T_\\star$. I would suggest less emphasis in this regard.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15 hours"}, "extra_text": {}}, {"review_id": "1AgqdxkagnQ", "reviewer": "Reviewer_qhwx", "summary": "This paper develop an algorithm that achieves minimax optimal regret for SSP with stochastic costs. Notably, the algorithm is completely parameter-free, and also horizon-free (logarithmic dependency on $T_{\\star}$ even in the lower order term). ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper resolves an important problems in SSP with stochastic costs: removing the extra $\\sqrt{S}$ factor in the leading term. What's even more exciting is that they push $1/c_{\\min}$ dependency into log terms. This is a very strong result, as $1/c_{\\min}$ can be arbitrarily large in SSP and can only be handled by perturbation, in which case most of algorithms end up with sub-optimal regret bound. Thanks to the strong result, the upper bound $B$ can be as large as $O(\\sqrt{K})$, making it easy to achieve parameter-free.\nThe paper is also well written and easy to follow. I appreciate author's effort on carefully discussing each scenario and the consequent regret bound.\n\nThe only short shortcoming is that the horizon-free analysis seems to be directly adopted from Zhang et al. [2020a], thus has limited novelty. However, the result of this paper is quite exciting and complete, and I suggest accepting this paper.\n\nQuestions:\n1. Is the perturbation on transition really necessary? It seems to be an artifact of analysis.\n2. Can the algorithm be extended to linear function approximation?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is mainly theoretically and has no foreseeable societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "This work is mainly theoretically and has no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes solid contribution to pushing the frontier of the stochastic shortest path problem.
All reviewers support accept strongly.
Decision: Accept (Spotlight)