Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
Authors: Liyu Chen
Mehdi Jafarnia-Jahromi
Rahul Jain
Haipeng Luo
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
stochastic shortest path
regret minimization

Abstract: We introduce a generic template for developing regret minimization algorithms in the Stochastic Shortest Path (SSP) model, which achieves minimax optimal regret as long as certain properties are ensured. The key of our analysis is a new technique called implicit finite-horizon approximation, which approximates the SSP model by a finite-horizon counterpart only in the analysis without explicit implementation. Using this template, we develop two new algorithms: the first one is model-free (the first in the literature to our knowledge) and minimax optimal under strictly positive costs; the second one is model-based and minimax optimal even with zero-cost state-action pairs, matching the best existing result from [Tarbouriech et al., 2021b]. Importantly, both algorithms admit highly sparse updates, making them  computationally more efficient than all existing algorithms. Moreover, both can be made completely parameter-free.

Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
Liyu Chen
Mehdi Jafarnia-Jahromi University of Southern California
University of Southern California liyucOusc.
onjafanniuuse
Rahul Jain
Haipeng Luo
University of Southern California rahul. rahul.jain@hun jainjusc.
University of Southern California haipengl@usc.. edu
Abstract
We introduce generic template for developing regret minimization algorithms the Stochastic Shortest Path (SSP) model, which achieves minimax optimal regret as long as certain properties are ensured. The key of our analysis is new technique called implicit finite-horizon approximation, which approximates the SSP model counterpart only the analysis without explicit implementation. Using this template, we develop two new algorithms: the first one is model-frea (the first in the literature to our knowledge) and minimax optimal under strictly positive costs; the second one is model-based and minimax optimal even with zero-cost state-action pairs, matching the best existing result from [Taarourricch et al., 2021b]. Importantly, both algorithms admit highly sparse updates, making them computationally more efficient than all existing algorithms. Moreover, both can be made completely parameter-free.
by
Introduction
We study the Stochastic Shortest Path (SSP) model, where agent aims to reach goal state with minimum cost in a stochastic environment. SSP well-suited for modeling many real-world applications, such robotic manipulation, navigation, and others. Although it is widely studied empirically (e.g., [Andrychowicz et al., 2017, Nasiriany et al., 2019]) and in optimal control theory (e.g.. [Bertsekas and Tsitsiklis, 1991, Bertsekas and Yu, 20131), it has received less attention under the regret minimization setting where a learner needs to learn the environment and improve her policy on-the-fly fly through repeated interaction. Specifically, the problem proceeds in K episodes. In each episode, the learner starts at a fixed initial state, sequentially takes action, suffers some cost, and transits to the next state, until reaching predefined goal state. The performance of the learner is measured by her regret, which is the difference between her total costs and that of the best policy.
Tarbouriech al. [2020a] develop the first regret minimization algorithm for SSP with regret bound of Ó(D3/2S / AK/Cmui where D is the diameter, S is the number of states, A is the number of actions, and Cain is the minimum cost among all state-action pairs. Cohen et al. [2020] improve over their results and give a near optimal regret bound of ((B.SVAK), where B, < D is the largest expected cost of the optimal policy starting from any state. Even more recently, Cohen et al. [2021] achieve minimax regret of /SAK) through finite-horizon reduction technique, and concurrently Tarbouriech et al. [2021b] also propose minimax optimal and parameter- free algorithms. Notably, all existing algorithms model-based with space complexity ((S² A). Moreover, they all
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

update the learner's policy through full-planning (a term taken from [Efroni et al., 2019]), incurring a relatively high time complexity.
In this work, we further advance the state-of-the-art by proposing a generic template for regret minimization algorithms in SSP (Algorithm 1), which achieves minimax optimal regret as long as some properties are ensured. By instantiating our template differently, we make the following two key algorithmic contributions:
In Section 4, we develop the first model-free SSP algorithm called LCB-ADVANTAGE-SSTT (Algorithm 2). Similar to most model-free reinforcement learning algorithms, A.B-ADDANTAGE- SSP does not estimate the transition directly, enjoys space complexity of Ó(SA), and also takes only O (1) time to update certain statistics in each step, making it highly efficient algorithm. It achieves regret bound of ÖBB VSK + S A/cmin). which is minimax optimal when Cuin > O. Moreover, it can be made parameter-free without worsening the regret bound.
In Section 5, we develop another simple model-based algorithm called SVI-SSP (Algorithm 3), which achieves minimax regret Ö v VSKK + 12.S2A A) even when Cmin O, matching the best existing result by Tarbouriech et al. [2021b].* Notably, compared to their algorithm (as well as other model-based algorithms), SVI-SSP is computationally much more efficient since it updates each acteon pair only logarithmically many times, and each update only performs one-step planning (again, term taken from [Efroni al., 2019]) opposed to full-planning (such value iteration or extended value iteration); see more concrete time complexity comparisons in Section 5. SVI-SSP can also be made parameter-free following the idea of ('Tarbouriech et al., 2021b).
We include summary of regret bounds of all existing SSP algorithms as well as more complexity comparisons in Appendix A.
Techniques Our main technical contribution is new analysis framework called implicit finit- horizon approximation (Section 3), which is the key to analyze algorithms developed from our template. The high level idea is to approximate an SSP instance by finite-horizon counterpart. However, the approximation only happens the analysis, a key difference compared to [Chen et al., 2021, Chen and Luo, 2021, Cohen et al., 2021] that explicitly implement such an approximation in their algorithms. As a result, our method not only avoids blowing up the space complexity by a factor of the horizon, but also allows one to derive horizon-free regret bound (more explanation to follow).
In order to achieve the minimax optimal regret, our model-free algorithm ACB-ADVANTAGE- uses key variance reduction idea via a reference-advantage decomposition by [Zhang et al., 2020b]. However, crucial distinctions exist. For example, we update the reference value function more frequently instead of only one time, which helps reduce the sample complexity and improve the lower-order term in the regret bound. We also maintain an empirical upper bound on the value function in a doubling manner, which is the key to eventually make the algorithm parameter-free. On the other hand, for our model-based algorithm SVI-SSP, we adopt a special Bernstein-style bonus term and bound the learner's total variance via recursion, taking inspiration from [Tarbouriech et al., 202 lb, Zhang et al., 2020a].
Empirical Evaluation We support our theoretical findings with experiments in Appendix H. Our model-free algorithm demonstrates a better convergence rate compared to vanilla Q learning with naive e-greedy exploration. Our model-based algorithm has competitive performance compared to other model-based algorithms, while spending the least amount of time in updates.
Related Work For a detailed comparison of existing results for the same problem, refer the readers to [Tarbouriech et al., 2021b, Table 1] as well as our Table 1. There are also several works [Rosenberg and Mansour, 2020, Chen et al., 2021, Chen and Luo, 2021] that consider the even more challenging SSP setting where the cost function is decided by an adversary and can change over time. Apart from regret minimization, Tarbouriech et al. [2021 a] study the sample complexity of SSP with generative model; Lim and Auer [2012] and Tarbouriech et al. [2020b] investigate exploration problems involving multiple goal states (multi-goal SSP).
Depending on the available prior knowledge, the final bounds achieved by SVI-SSP are slightly different, but they all match that of SSP. See [Tarbouriech et al., 2021b, Table 1] for more details.

---

The special case of SSP with fixed horizon has been studied extensively, for both stochastic costs (e.g.. [Azar et al.. 2017, Jin et al., 2018, Efroni al., 2019, Zanette and Brunskill, 2019, Zhang et al., 2020a]) and adversarial costs (e.g., [Neu et al., 2012, Zimin and Neu, 2013, Rosenberg and Mansour, 2019, Jin et al., 2020J). Importantly, recent works [Wang et al., 2020, Zhang et al., 2020a] find that when the cost for each episode is at most constant, it is in fact possible to obtain regret bound with only logarithmic dependency on the horizon. Tarbouriech et al. [2021b] generalize this concept to SSP and define horizon-free regret as bound with only logarithmic dependence on the expected hitting time of the optimal policy starting from any state (which is bounded by B./Cmin). They also propose the first algorithm with horizon-free regret for SSP, which is important for arguing minimax optimality even when Cmin = O. Notably, our model-based algorithm SVI-SSP also achieves horizon-free free regret (but the model-free one does not).
2 Preliminaries
An SSP instance is defined by a Markov Decision Process (MDP) M (S,A, Siits 9, C, P). where S is the state space, A is the action space, Smit E S is the initial state, and & S is the goal state. When taking action a in state s, the learner suffers a cost drawn in an i.i.d manner from an unknown distribution with mean c(s, a) E [o, 1] and support [Cmin 1] (Cmin 2 0), and then transits to the next state E S+ = S J {g) with probability Ps.a(s' We assume that the transition and the cost. mean c are unknown to the learner, while all other parameters are known.
The learning process goes as follows: the learner interacts with the environment for episodes. In the k-th episode, the learner starts in initial state Sinit, sequentially takes an action, suffers a cost, and transits to the next state until reaching the goal state g. More formally, at the i-th step of the k-th episode, the learner observes the current state of (with of = sma)) takes action of. suffers a cost ci and transits to the next state o ~ Pat An episode ends when the current state is g, and we define the length of episode k as Ix. such that 54 54,+1 - g.
Learning Objective At a high level, the learner's goal is to reach the goal with a small total cost. (stationary and deterministic) policy : S - A is
To this end, we focus proper policies mapping that assigns an action (s)) to each state s E S, and it is proper if the goal is reached with probability 1 when following (that is, taking action (s) whenever in state s). Given proper policy
π, one can define the cost-to-go function V S - [0, oo) as V*(()= = E EL P: = = where the expectation is with respect to the randomness of the cost 64 incurred at state-action pair (st, (s:),, next state 8/+1 (s)) and the number of steps I before reaching g. The optimal proper policy x* then defined as a policy such that V= (s) minæen (*((s) for all s E S, where II is the set of all proper policies assumed to be nonempty. The formal objective of the learner is then to minimize her regret against n², the difference between her total cost and that of the optimal proper policy, defined as
K
I+
RK
K V*((innt,,
1=1 am
where we use V* as a shorthand for V=* -The minimax optimal regret is known to Ö(B. where B, max,es (*), and S = || and A = |.A| are the numbers of states (including the goal state) and actions respectively [Cohen et al., 2020].
Bellman Optimality Equation For a proper policy n, the corresponding action-value function [V* Q² 8 x A [0, 30) is defined as (²{ssa) = c(s, a) EewP, [V (s')]. Similarly, we use Q* as a shorthand for Q=*.. is known that nT satisfics the Bellman optimality equation: V*(s)= = minae (s(saa) a) for all E [Bertsekas and Tsitsiklis, 1991].
Assumption on Cmin Similar to many previous works, our analysis requires Cmin being known and
strictly positive. When Cmin is unknown or known to be 0, a simple workaround is to solve modified SSP instance with all observed costs clipped to if they are below some >> O, so that Cmin = > 0. Then the regret in this modified SSP is similar to that in the original SSP up to an additive term of order (e K)) [Tarbouriech et al., 2020a]. Therefore, throughout the paper we assume that Gmin is known and strictly positive unless explicitly stated otherwisc.
3

---

Algorithm A General Algorithmic Template for SSP
Initialize: 0, 81 f- Sinits Q1s a) 0 for all (s,a) E x A.
for k = 1..... K do
repeat
Increment time step t 1.
2
Take action az = argmin, (s;; a), suffer cost ct, transit to and observe 84 Update Q (so that it satisfies Property and Property 2).
s + 9 then 8141 6 8/: else 8141 f- Sinits break.
Record T (that is, the total number of steps).
Other Notations For simplicity, we use CK = Ek= Σ of in the analysis to denote the total
costs suffered by the learner over K episodes. For a function X S - RR and a distribution P over St, denote by PX- Es- (S)), PX* [[ (S) and V(P, = VAR [S)] the expectation, second moment, and variance of (S) respectively where S is drawn from P. For a scalar z, define (z)+ = max(xr, (x, 0}, and denote by [x], = 2 =1 and | 12 = 2 210gg #J the closest power of two upper and lower bounding x respectively. For an integer m, [m] denotes the set
m.. In pseudocode, _ y is shorthand for the increment operation r + x. + y.
3 Implicit Finite-Horizon Approximation
In this section, we introduce main analytical technique, that is, implicitly approximating the SSP problem with a mnte-horiizon counterpart. We start with a general template of our algorithms shown in Algorithm 1. For notational convenience, episodes as one single sequence (8t, Or, (.) for ( = 1, , T, where 8, E S is one of the non-goal state, de E AA is the action taken at St, and et is the resulting cost incurred by the learner. Note that the goal state is never included in this sequence (since no action is taken there), and we also use the notation s/ S+ to denote the next-state following (sc, de), so that S141 is simply s! unless s/ = g (in which case 1 is reset to the initial state Sinit); see Line 4.
concatenate state-action-cost trajectories of all
The template follows rather standard idea for many reinforcement learning algorithms: maintain an (optimistic) estimate Q of the optimal action-value function Q", and act greedily by taking the action with the smallest estimate: a argmin, (s+ a); Line 2. The key of the analysis is often to bound the estimation error (*,, ax) ((+, at), which is relatively straightforward setting (where the discount factor controls the growth of the error) finite-horizon setting (where the error vanishes after a fixed number of steps), but becomes highly non-trivial for SSP due to the lack of similar structures.
a discounted
A natural idea is to explicitly solve a discounted problem or a finite-horizon problem that approximates the original SSP well enough. Unfortunately, both approaches are problematic: approximating an undiscounted MDP by a discounted one often leads to suboptimal regret (Wei et al., 2020]; on the other hand, while explicitly approximating SSP with finite-horizon problem can lead to optimal regret [Chen et al., 2021, Cohen et al., 2021], it greatly increases the space complexity of the algorithm, and also produces non-stationary policies, which is unnatural and introduces unnecessary complexity since the optimal policy in SSP is stationary.
Therefore, we propose to approximate the original SSP instance M with a finite-horizon counterpart M implicitly (that is, only in the analysis). We defer the formal definition of M Appendix C, which is similar to those in [Chen et al., 2021, Cohen et al., 2021] and corresponds to interacting with the original SSP for H steps (for some integer H) and then teleporting the goal. All we need the analysis are the optimal value function Vi and optimal action-value function Q of M for each step h [H) which can be defined recursively without resorting to the definition of M:
(7 a) a(s, + Ps.a Vi-
Vit min Q7 (s, a)
(1)

---

with (s a) = 0 for all a)² Intuitively, Q7 approximates Q" well when H is large enough. This formally summarized the lemma below, whose proof similar to prior works (see Appendix C). Lemma 1. For any value of H. (ir(s, a) S (= a) holds for all (s, a). For any 3 E (0, 1), if H 2 1B ln(2/ + 1, then (7 a) I (s, + B.3 holds for all (s,a). a).
Caii
In the remaining discussion, we fix a particular value of H. To carry out the regret analysis, we now specify two general requirements of the estimate Q. Let Qe be the value of Q at the beginning of time step (that is, the value used in finding at). Then Q. needs to satisfy:
Property (Optimism). With high probability, Qr a) S Q" (s,a) holds for all (8, a) and t 2 1. Property 2 (Recursion). There exists "bonus overhead" EH > O and an absolute constant d 0 such that the following holds with high probability:
T Σ ((((s) a.) - Qe(s). S E1 +
T >
(1+1)
(V()) Qe(ss, at))+
H
for Q Qi and V Vn- = (1=1...... H) as well as =" and V V
Property is standard and can usually be ensured by using a certain "bonus" term derived from concentration equalities in the update. These bonus terms on (st, ax) accumulate into some bonus overhead in the final regret bound, which exactly the role of ÊH in Property 2. In both of our algorithms, Err has a leading-ordes term O(BB,SACK) and a lower-order term that increases in H.
Property 2 is a key property that provides a recursive form of the estimation error and allows us to connect it to the
approximation. This is illustrated through the following two lemmas. Lemma 2. Property 2 implies Et= (Q7, (st, at) Qe(s.. a0)4 O (HÉn).
Proof. With Q = QH and V V Property 2 implies
T
T
d (Qnnss a.) Qe(s), S EH + (1+
Σ
(Vi-1(s:) Qe(s),
H
t=1
$ EH + (1+ d
Σ
(QH ((HH-1((), - Qi(ss, az))+
H
t=1
where in the last step we use the optimality of V from Eq. (I). Repeatedly applying this argument, we eventually arrive at ET (Q7, a.) - (e(s;,a)); I H (1 $ En + (1 4)* H ( oe) - (((8),a))) Q6(s:: ae) = 0 and (1 + H) 4)" S ed (an absolute constant).
0 OHEH), where the last step uses the facts
Lemma 3. For any 3 E (0, 1), if 2 1B ln(2/8) then Property and Property 2 together
Omtn
imply Σi= 1 ax) V* (st) O (3Cx + EH).
Proof. Applying Property 2 with Q = Q and V = V*, we have ET= ae) - Qe(s,, a.))+ S εH + (1 $ ET=(('' equation V*(a,) = min, Q*(s;, a), and the fact Qx 0z) min, (s a) (by the definition of at), the arguments within the clipping operation (.) are all non-negative and thus the clipping can be removed. Rearranging terms then gives
(,(s), a.)) Now note that by Property 1, the Bellman optimality
d
(*r, (st) S En
+
Σ
(v)) (((s),
H
t=1
< En + d (Q) Qe(s), H
(optimality of V*)
2 Note that our notation is perhaps unconventional compared to most works on mite-horiionn MDPs, where O usually refers to our Q We make this switch since we want to highlight the dependence on H for Qi- Note that En might be a random variable. In fact, often depends on Cx.
5

---

It remains to bound the last term using the finite-horizon approximation Q7 as proxy:
(0 ar)(
Σ Q (s,, (sr, + Qu oz) Qr(s),
= (TB.B + HεH);
where the last step uses Lemma and Lemma 2. Importantly, this term is finally scaled by djH, which, together with the fact TB.
" < Gmin T I Ck. proves the claimed bound.
Readers familiar with the literature might already recognize the term Σ (s, az) (s:) considered in Lemma which is closely related the regret. Indeed, with this lemma, we can conclude a regret bound for our generic algorithm.
Theorem 1. For any B E (0, if H 2 4B. ln(2/8) + 1, then Algorithm 1 ensures (with high probability) Rg- = Ô (VB,CK + B. + 3Cx + EH).
cmin
Proof. We first decompose the regret follows, which holds generally for any algorithm:
K
Rk=
c -
v
K
I
T
(*()t) + V = = > (Ms
k=
i=1
1=1
Σ
- (c- + Σ (v - Pan V*)
Σ (s) V*
(2)
The first and the second term are the sum of martingale difference sequence (since s is drawn from Ps,,a, and can be bounded by Ô (vCx) and Ô (VBB,CC BB + B.) respectively using concentration inequalities; see Lemma 4, Lemma 35, and Lemma 5. The third term can be bounded using Lemma directly, which finishes the proof.
To get sense of the regret bound in Theorem 1, first note that since 1/B only appears in logarithmic term of the required lower bound of H, one can pick to be small enough so that the term 30k is dominated by others. Moreover, εи is Õ BV,VBBSACC, plus some lower-order term Pи (which as mentioned is the case for our algorithms), then by solving a quadratic /Ck, the regret bound of Theorem implics Rx- = O /SKK + PH). which is minimax optimal (ignoring PH)!
Based on this analytical technique, it remains to design algorithms satisfying the two required properties. the following sections, we provide two such examples, leading the first model-free SSP algorithm and an improved model-based SSP algorithm.
4 The First Model-free Algorithm: LCB-ADVANTAGE-SSE
In this section, we present a model-free algorithm (the first in the literature) called CB--ADVANTAGE SSP that falls into our generic template and satisfies the required properties. It is largely inspired by the state-of-the-an model-free algorithm ACB-ADVANTAGE [Zhang et al., 2020b] for the finite- horizon problem. The pseudocode is shown in Algorithm 2, with only the lines instantiating the update rule of the Q estimates numbered. Importantly, the space complexity of this algorithm is only O (S)) since we do not estimate the transition directly conduct explicit finite-horizon reduction, and the time complexity is only O (1) in each step.
Specifically, for each state-action pair a), divide the samples received when visiting (s, a) into consecutive stages of exponentially increasing length, and only update Q(s, a) at the end of stage. The number of samples ej in stage is defined through e H and 6j+1 [(1 + 1/H)e, for some parameter H. Further define L {Fy)seN+ with F, = E 6c which contains all the indices indicating the end of some stage. As mentioned, the algorithm only updates Q(s, a) when the

---

Algorithm 2 LCB-ADVANNAGG--SSP
Parameters: horizon HI, threshold 0*, and failure probability E (0,1).
Define: L' = =E where E = = 6, = and ej+1 = [(1= [11+1/Hee
Initialize: t 0,
Sjnit, B 1, 1, for all (s.a), + 0,, 0
Initialize: for all (s, a), Q(s, a) + 0, ((s) + 0, (Td(s) V(s) -
Initialize: for all (s, a). nd (s, t 0, of (s.a) + (s, 0,0(s, + O, v(s, t 0.
for k 1..... K do
repeat
Increment time step - 1. Take action de = argmin (=t,, a), suffer cost ct, transit to and observe o/-
Increment visitation counters: n = ((s ar) $ 1,m = M(s, ar) $ 1.
Update global accumulators: (5e ae) $ vod(s(),, (s)))) & (o)(
2
Ö(s,, az) F
Update local accumulators: (1) E V(s(), mlst, ai) $ V(*)) - (s)(,s),, o(s), z (V(s)) (s))).
n E L then
Compute + 256 In io (4SAB; cost estimator é = Ō(scaae) bonuses +
5
2v
B2L
+ and t-
nd (stiae)/n in- (e)) u+V
olssaa)mmmm (u(er 1t
4B +
3B
m
m
(s0, <- max c+ ((arsee) - UV Q(s) at)
((s, < max c+ (onna)) + m(senae) b, Q(s,)))))
m
Vsa:) min. ((sr. a).
Vs:) > then B (V
10
Reset local accumulators: v(si, az) + 0, p(se, uz) < 0, 0,0(s,, + 0, 0(M + 0.
if >
N(t, a) is power of two not larger than 0r then (re(s)) V(8.).
; 7 y then 8141 &- 8/; else 8141 +- 8inits break.
total number of visits to (s, a) falls into the set C* (Line 4). The algorithm also maintains an estimate V for V*, which always satisfies (ss) min, (ss, a) (Line 8), and importantly another reference value function yee whose role and update rule are to be discussed later.
In addition, some local and global accumulators are maintained in the algorithm. Local accumulators only store information related the current stage. These include: (s, a). the number of visits to (s, a) within the current stage; v(s, a), the cumulative value of V(s") within the current stage, where represents the next state after each visit to (s, a); and finally p(s, a) and (s, a), the cumulative values of V(s') Vre and its square respectively within the current stage (Line 3). These local accumulators are reset to zero at the end of each stage (Line 10).
On the other hand, global accumulators store information related to all stages and are never reset. These include: (s, a). the number of visits to (8, a) from the beginning; Č(s, a), total cost incurs at (s, a) from the beginning; and (s, a) and (s, a), the cumulative value of (re( and its square respectively from the beginning, where again s' represents the next state after each visit to (s, a) (Line 2).
We are now ready to describe the update rule of Q. The first update, Line 6, is intuitively based on the equality Q*(s,a) a) = c(s, a) + P..a V* and uses v(s,, a) (s, a) as an estimate for Pa.. V* together with a (negative) bonus '' derived from Azuma's 's inequality (Line 5). As mentioned, the bonus is necessary to ensure Property 1 (optimism) so that
always lower confidence bound of Q* (hence the name "LCB"). Note that this update only uses data from the current stage (roughly 1/ H fraction of the entire data collected so far), which leads to an extra / H factor in the regret.
7

---

To address this issue, Zhang et al. [2020b] introduce variance reduction technique via reference- advantage decomposition, which we borrow here leading to the second update rule in Line 7. This is intuitively based on the decomposition P. V. Ps.a Viet + (V. - - Viet), where Ps.a V is approximated by 1 a)/N(s, a) and Pa.a(V* -vref is approximated by a(s,a)/M(ss, a). In addition, a "variance-aware bonus term b is applied, which derived from a tighter Freedman's inequality (Line 5). The reference function V is some snapshot of the past value of V, and is guaranteed to be (cmin) close to V* on a particular state as long as the number of visits to this state exceeds some threshold 0 = (B² S S./ (iin) (Line 11). Overall, this second update rule not only removes the extra v H factor as in [Zhang et al., 2020b], but also turns some terms of order (VVT) into ((VCk) in our context, which is important for obtaining the optimal regret.
Despite the similarity, we emphasize several key differences between our algorithm and that of [Zhang et al., 2020b]. First, [Zhang et 2020b] maintains a different Q estimate for each step of an episode (which is natural for finite-horizon problem), while we only maintain one Q estimate (which is natural for SSP). Second, we update the reference function (s) whenever the number of visits to s doubles (while still below the threshold 9"; see Line 11), instead of only updating once as in [Zhang et al.. 2020b]. We show in Lemma 8 that this helps reduce the sample complexity and leads to a smaller lower-order term in the regret. Third, since there no apriori known upper bound on V (unlike the finite-horizon setting), we maintain an empirical upper bound B (in a doubling manner) such that (s) < < 2B, (Line 9), which is further used in computing the bonus terms and b'. This is important for eventually developing a warameter-free algorithm.
In Appendix D, we show that Algorithm 2 indeed satisfies the two required properties.
Theorem 2. Let = AB_ In A + 172 for 3 =
Cmin 2B.SAK and 0* Ô B.
be de- 3 and
-im fined in Lemma 8, then Algorithm 2 satisfies Property I and Property 2 with d EH = Ô (( (VB.SACK+ + B² S²A
Gmin
Proof Sketch. The proof of Property largely follows the analysis of [Zhang et al., 2020b, Proposition 4] for the designed bonuses. To prove Property 2, similarly to [Zhang al., 2020b] we can show:
T Σ
- Qc(s,, ax)) -(((),))))
S EH
P Pare ", (V Vir,)+:
where me is the value of used in computing Qi(sr, a.), and le,i is the i-th time step the agent visits
(8t, 0t) among those m, steps. Now it suffices to show that Σt=1 mi 5 Pa are (V V% S
(1+ #) ET V((s:))+. which is proven in Lemma 13.
As direct corollary of Theorem 1, we arrive at the following regret guarantee.
Theorem 3. With the same parameters as in Theorem 2, with probability at least 1 1 6066 Algorithm 2 ensures Rg Ö δ (B./SAK
B²
We make several remarks on our results, First, while Algorithm requires setting the two parameters H and 6* in terms of B. to obtain the claimed regret bound, one can in fact achieve the exact same bound without knowing B, by slightly changing the algorithm. The high level idea is first apply the doubling trick from Tarbouriech et al. [2021b] to determine logarithmically many different values of H and 0* simultaneously, each leading to a different update rule for Q and yeef. This only increases the time and space complexity by logarithmic factor, without hurting the regret (up to log factors). Details are deferred to Section D.5.
upper bound on B., then try
Second, as mentioned in Section 2, when Cmin is unknown or Cmin = 0, one can clip all observed costs to e if they are below e > 0, which introduces an additive regret term of order O (eK). By picking to be of order K-1/5 our bound becomes Ô 4/5) ignoring other parameters. Although most existing works suffer the same issue, this is certainly undesirable, and our second algorithm to be introduced in the next section completely avoids this issue by having only logarithmic dependence on 1/c C/min
8

---

Algorithm 3 SVI-SSP
Parameters: horizon H. value function upper bound B, and failure probability à E (0. 1).
Define: <=? where Bg E'=1 C; eg = [3g]. and č = 1, 1,4 = Eg + e/.
Initialize: <- 0, Sinit-
Initialize: for all (s, a, (.,8) n(,, t 10, (,n(s, 0. (() + 0. V(s) - 0. C(s, a) +- 0.
for k = 1...., K do
repeat
Increment time step - 1. Take action 0, - argmin Q5+r, a), suffer cost cr, transit to and observe s/c ns:,, at) & 1, n(s,, az, s()) $ C(st, 0z) _
Update accumulators:
2
n E C then
Update empirical transition: Ps Ps (s') n(serae.s)) for all s'.
Compute
20 2SAn 63
cost estimator à Ō(s,a) and bonus b
max 7
V(P. ,, V22
n er V b, a().
49
+
((s) at) maxfc + P
(ss) f argmin, ((s..
s # then 8141 t s/: else 8141 t Smits break.
Finally, we point that, just as the finite-horizon case, the variance reduction technique is crucial for obtaining the minimax optimal regret. For example, if one instead uses an update rule similar to the (suboptimal) Q-learning algorithm of [Jin al., 2018], then this is essentially equivalent to removing the second update (Line 7) of our algorithm. While this still satisfies Property 2, the bonus overhead εn would be vH times larger, resulting in suboptimal leading term in the regret.
5 An Optimal and Efficient Model-based Algorithm: SVI-SSP
In this section, we propose simple model- algorithm called SVI-SSP (Sparse Value Iteration for SSP) following our template, which not only achieves the minimax optimal regret even when Cmin matching the state-of-the-ard by a recent work [Tarbouriech al., 2021b], but also admits highly sparse updates, making it more efficient than all existing model-based algorithms. The pseudocode is in Algorithm again with only the lines instantiating the update rule for numbered.
Similar to Algorithm 2, SVI-SSP divides samples of each (s, a) into consecutive stages of (roughly) exponentially increasing length, and only update (s, a) at the end of stage (Line 2). However, the number of samples Ej in stage j is defined slightly differently through e, = [ē ē = 1, and Cy+1 = ē + H7 éj for some parameter H. In the long run, this is almost the same as the scheme used in Algorithm 2, but importantly, it forces more frequent updates at the beginning for example, one can verify that é₁ =... Cи = 1, meaning that Qs,, a) is updated every time (s, a) is visited for the first H visits. This slight difference turns out to be important to ensure that the lower-order term in the regret has no poly( ()) dependence, as shown in Lemma 16 and further discussed in Remark 3. More intuition the design of this update scheme is provided in Section E.
The update rule for Q is very simple (Line 5). It is again based on the equality Q" a) c(s, a) V*,, but this time uses P.. V b as approximation for P'.aV where Pa.. is the empirical transition directly calculated from two counters ns, a) and rı(s, a, s') (number of visits to (s, a) and (s, a,s') respectively). V is such that Vss) min, Q(s, a), and b is special bonus term (Line 4) adopted from (Tarbouriech et al., 2021b, Zhang et al., 2020a] which ensures that Q is an optimistic estimate of Q* and also helps remove poly(H) dependence in the regret.
SVI-SSP exhibits a unique structure compared to existing algorithms. In each update, modifies only one entry of Q (similarly to model-free algorithms), while other model-based algorithms such as ('Tarbouriech et al., 2021b] perform value iteration for every entry of Q repeatedly until convergence (concrete time complexity comparisons to follow). We emphasize that implicit finite-horizon

---

analysis is indeed the key to enable us to derive regret guarantee for such sparse value iteration algorithm. Specifically, Appendix E, we show that SVI-SSP satisfies the two required properties. then Algorithm 3 satisfies Property| I and Property 2 with d= and εн OVVB,SCCK + BS A + 3Ck), where the dependence on H. in En is hidden in logarithmic terms.
Theorem 4. If B 2 B. and H = 4B In( () + 1 2 for B 284
Cmin
Cuin
Proof Sketch. The proof of Property largely follows the analysis of (TTaroorrichh et al., 2021b, Lemma 15]. To prove Property 2, we first show
()))))))))++ X ŞH +E P-(V- v. where 4 is the last time step Q(st, at) is updated. Then, the remaining main steps are shown below with all details deferred to the corresponding key lemmas:
P.(VV Vi,) 2
1 H
P.(V - Vi)+
(Lemma 16)
1
Σ (st) v((ot))+ +
1+ H
Σ (P. 12) - Vi)=
T
(st) vo(st))+ + EH.
(Lemmaa 22 and Lemma 21)
which completes the proof.
Again, as a direct corollary of Theorem 1, we arrive at the following regret guarantee.
Theorem 5. With the same parameters as in Theorem 4, with probability at least 1 - 1225, Algorithm 3
ensures Rg= = Ö(B.VSAK + BS? A).
Setting B = B.. our bound becomes Ó(B.VSAK + B,S² which minimax optimal even when Cmin is unknown Cmin (this is because the dependence on 1/Cmin is only logarithmic, and one can clip all observed costs to if they are below = 1/K K in this case without introducing Poly(K) overhead to the regret). When B, is unknown, bouriech et al. [2021b] to obtain almost the same bound (with only the lower-order term increased to δ (B. 5 A)); see Section E.5 for details.*
the same doubling trick from Tar-
Comparison with EB-SSP ['Tarbouricch et al., 2021b] Our regret bounds match exactly the state- of-the-art by Tarbouriech et al. [2021b]. Thanks to the sparse update, however, SVI-SSP has a much better time complexity. Specifically, for SVI-SSP, each (s, a) is updated most ((H) = ((B./cmma)) times (Lemma 16), and each update takes (SS) time, leading to total complexity Ô A/emin). On the other hand, for EB-SSP, although each (s, a) only causes ((1) updates, each update runs value iteration on all entries of Q until convergence, which takes Ö(B5s" / /..... iterations (see their Appendix C) and leads to total complexity Ö(B A/22.n)) much larger than ours.
Comparison with ULCVI [Cohen et al., 2021] Another recent work by Cohen al. [2021] using explicit knite-horizon approximation also achieves minimax regret but requires the knowledge of some hitting time of the optimal policy. Without this knowledge, their bound has large /cinn dependence in the lower-order term just as our model-free algorithm. Our results in this section show that implicit finite-horizon approximation has advantage over explicit approximation apart from reducing space complexity: the former does not necessarily introduce poly H) dependence even for the lower-order term, while the latter does under the current analysis.
Acknowledgments and Disclosure of Funding
LC thanks Chen-Ye Yu Wei for many helpful discussions. HL is supported by NSF Award IIS- and Google Faculty Research Award. MJ and RJ's research is supported by NSF CCF-C811222 181222. NSF EECCS-18111 1810447 and ONR 100014-20-1-2255 awards.
"We note that this doubling trick is in fact also applicable to Algorithm 2. However, the specific approach we propose for this algorithm in Section D.5 is better in the sense that it does not worsen the regret all.
10

---

References
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, volume 30, 2017.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595, 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.
Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. In International Conference on Machine Learning, 2021.
Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference On Learning Theory, 2021.
Alon Cohen, Haim Kaplan, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret bounds for stochastic shortest path. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 8210-8219. PMLR, 2020.
Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path. In Neural Information Processing Systems, 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, volume 32. Curran Associates, Inc., 2019.
Yonathan Efroni, Nadav Merlis, Aadirupa Saha, and Shie Mannor. Confidence-butde budget matching for sequential budgeted learning. In International Conference on Machine Learning, 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11)4). 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Advances in neural information processing systems, pages
2018.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference on Machine Learning, pages 4860 4869, 2020.
Chung-Was Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: high- high-probability data-dependent regret bounds for adversarial bandits and MDPs. In Advances in Neural Information Processing Systems, volume 33, pages 15522-15533, Curran Associates, Inc., 2020.
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.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
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, 2012.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the 36th International Conference on Machine Learning, pages 5478-5486 2019.

---

Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. arXiv preprint 1xXi::2006.1/5111 2020.
Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference on Machine Learning, pages 1428-94337 PMLR, 2020a.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Improved sample complexity for incremental autonomous exploration in MDPs. In Advances in Neural Information Processing Systems, volume 33, pages 11273-11 11284. Curran Associates, Inc., 2020b.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Sample complexity bounds for stochastic shortest path with generative model. In Algorithmic Learning Theory, pages 1157-1178. PMLR. 2021a.
Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret. In Neural Information Processing Systems, 2021b.
Ruosong Wang, Simon Š Du, Lin Yang, and Sham Kakade. Is long horizon RL more difficult than short horizon RI.? Advances in Neural Information Processing Systems, 33, 2020.
Chen- Yu Wei, Mehdi Jafarnia Jahromi, 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, pages 10170-10180. PMLR, 2020.
Huizhen Yu and Dimitri P Bertsekas. On boundedness of Q-learning iterates for stochastic shortest path problems. Mathematics of Operations Research, (8(2):209-227,222 2013.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. In Proceedings of the 36th International Conference Machine Learning, pages 7304-7312, 2019.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference On Learning Theory, 2020a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantaann decomposition. In Advances in Neural Information Processing Systems, volume 33, pages 15198-15207. Curran Associates, Inc., 2020b.
Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems, pages 1583-1591, 2013.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] see Related Work
(c) Did you discuss any potential negative socictal impacts of your work? [N/A] This work mainly theoretical, and we do not foresee any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
12

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] see Appendix H (same for questions (b)-(d)
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mF6a4gfL0A", "reviewer": "Reviewer_HJ7d", "summary": "This paper presents an algorithmic template for the SSP model that unifies algorithms based on value optimism. Then, two instances of the template are presented and analyzed. The first instance is a model-free algorithm (the first for SSP) that achieves optimal regret but only when all costs are strictly positive. The second is a model-based algorithm that achieves optimal regret without any assumption on the cost. This algorithm enjoys improved computational complexity by performing 1-step planning instead of full-planning (also the first for SSP). ", "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": "Overall this is a really good paper but I need to mention that I did not have the time to fully check the proofs in the appendix. \nThe theoretical guarantees of the algorithms are strong, and their computational and space complexity are especially impressive (I have some concerns regarding computational complexity, see next). \nThe technical contribution is also promising. The implicit usage of finite-horizon is able to benefit both from recent reductions to finite-horizon and from parameter-free and horizon-free guarantees of Tarbouriech et al. [2021b].\n\nHowever, there are still quite a few things that I think could be presented better/improved in the final version of this paper. I think that they can be fixed after the rebuttal, but I stress that these should be addressed if the authors wish for this paper to really have an impact.\n\nWhile the paper is beautifully written up until section 4, the rest of it is hard to follow and does not focus on the right things in my opinion. For starters, while algorithm 1 is very useful, I found algorithms 2,3 highly confusing since they are too technical. I would remove them and keep just the explanations that you have in the text. After all, they just specify the exploration bonuses and related computations that are familiar to most readers from other RL settings. For this reason, I would not have focused on the description of these computations, I think that they are much less interesting in the context of SSP. Instead, I think the focus should be on how to prove properties 1 and 2 for these two algorithms, i.e., how do you take these finite-horizon techniques and use them in the context of SSP. This is not described at all, and I think it is the most important contribution after you already explained so nicely the template of the algorithm and analysis. On a related note, maybe there is a better way (could be less formal) to define $e_j$, $\\tilde e_j$ and $E_j$? it is hard to comprehend these definitions and they don't give the intuition about this exponentially growing stage lengths.\n\nI have some concerns regarding $c_{min} $. First, the computational complexity grows with $1/ c_{min} $. when $c_{min} = 0$ this becomes polynomial in $K$. I know that this is similar to previous work, but here you state that your algorithms are very efficient and admit highly sparse updates. This is certainly not the case when $c_{min} = 1/poly(K) $ so you should be more accurate about that. Second, again when $c_{min} $ is small the regret of the model-free algorithm has a huge additive term that will be dominant in many cases. My main question here is (this one also goes for the complexity): Can you fix $H $ to be smaller than $B_* / c_{min} $ and get alternative guarantees? With explicit reduction to finite-horizon this is possible, and I think this is crucial for your result to be more meaningful in the general case. A related concern here is if this template is completely \"implicit\". This is definitely a big step towards implicit analysis of SSP using finite-horizon, but since $H $ is an explicit parameter, there is more work that could be done here and I think that this is something that should be discussed in order to encourage future work on the subject. \n\nAdditional concerns:\n1.  I think that the empirical evaluation only hurts the results of this paper. Since experiments are not standard in these regret minimization papers, their results should be more clear. I think the experiments presented here only draw theory and practice further apart in the context of RL, as they show that the \"simple\" algorithms are good enough. However, this is due to picking the \"wrong\" examples. Also, note that in grid world $c_{min} = 1 $! For random MDP what was $c_{min} $?\n\n2. I have a small concern regarding the implicit finite-horizon analysis. $\\xi_H $ is a random variable that depends on the total cost of the agent in $K $ episodes. However, the analysis refers to it as something that depends solely on $H $. I did not find a problem in the analysis, but I am a little concerned about this (as $\\xi_H $ is also not bounded). I think that denoting it as a function of the total cost could make this part more clear and avoid any issues. Also, $\\delta $ needs to be picked small enough (also as a function of the agent's total cost) and this is not mentioned in the theorems.\n\n3. Recent SSP papers did not assume deterministic cost function. I think this paper should address stochastic cost function explicitly to match them.\n\nPost-rebuttal: I am keeping my positive score. I hope that the important clarifications discussed with Reviewer WgWg will be incorporated in the camera-ready version.", "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": "3.5"}, "extra_text": {}}, {"review_id": "jP6GFlKJfyw", "reviewer": "Reviewer_qWsp", "summary": "The authors propose a generic template for regret minimization algorithms in SSP. They develop the first efficient model-free SSP algorithm. They introduced a technique called implicit finite-horizon approximation, which approximates the SSP model by a finite-horizon counterpart implicitly.", "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": "Originality: This paper proposed a technique that can be used to analyze the SSP problem. Although the major contribution, which to me is the algorithm LCB-advantage, borrows idea from the well known result of Zhang et al 2020, adpating this result to the SSP setting is still a non-trivial task in my opinion. Also, this should be the first model-free algorithm for SSP. So I think this is a successful adaption of the known technique to a new problem.\n\nQuality: The technical part of the paper looks correct.\n\nClarity: The paper is very clearly written and the idea is well presented.\n\nSignificance: This is a good contribution to the SSP problem which is an important direction in theoretical reinforcement learning. The proposed algorithm as I know is the first model-free algorithm for SSP.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "For SSP, one specifically important question is why the algorithm halts (i.e. reach the goal state) in finite time with high probability for each episode. I did not see any discussion on this point in the paper. Even though this follows from the finite regret of the algorithm, the authors should elaborate this point explicitly in the main text. \n ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "iT7-5sG5W1a", "reviewer": "Reviewer_WgWg", "summary": "The paper introduces a generic template for regret minimization in SSP (stochastic shortest path). It instantiates it with 1) a model-free algorithm (the first for SSP) that achieves the minimax rate under positive costs, and 2) a model-based algorithm that matches the best existing regret rate and admits sparse updates.", "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": "The paper is clear, well written and well executed. While other works have also recently studied regret minimization for tabular SSP, the submission makes some relevant contributions on this setting.\n\nThe paper proposes a generic template for regret minimization for SSP based on an implicit finite-horizon approximation. The template is sound, easy to follow and allows to decompose the analysis between algorithm-agnostic aspects and algorithm-specific aspects. \nThe paper mentions that explicit finite-horizon approximation (as done in prior works) “unavoidably introduces poly(H) dependence even for the lower-order term”: could the authors explain why this is the case? (i.e., is there a reason why using horizon-free techniques in the finite-horizon reduction would prevent obtaining a horizon-free bound for SSP?). \n\nFirst, the template is instantiated to obtain the first model-free algorithm for SSP. This is a strong contribution. Indeed, the analysis of model-free SSP induces the technical challenge of how to handle the error propagation across time steps (this does not appear in the layered structure of finite-horizon MDPs). The proposed template can nicely handle this propagation. \nWhile the algorithm is largely inspired from UCB-Advantage [Zhang et al., 2020b], it performs a few necessary modifications and can be made parameter-free. The authors mention that their “smoother” update of the $V^{\\text{ref}}$ function leads to a lower-order term in the regret: out of curiosity, could you quantify the improvement obtained by this technique (both in SSP and in finite-horizon MDPs)? \nThe regret bound is minimax optimal when costs are positive. While there is a poor additive dependence on $1/c_{\\min}$ which leads to a general $K^{4/5}$ bound, this issue of poor lower order terms w.r.t. the horizon appears in all existing model-free algorithms. Does the extension to unknown stochastic costs (mentioned in footnote 1) require the knowledge of $c_{\\min}$ (which appears in the definition of the horizon $H$ in Algorithm 2) or can it be somehow adaptive to it? \n\nSecond, the template is instantiated in a model-based fashion. The proposed algorithm and analysis are tightly connected to that of the recent algorithm EB-SSP [Tarbouriech et al., 2021b] (e.g., similar exploration bonus, recursion-based analysis, parameter-free scheme), and the obtained regret bound is the same. The main difference lies in the focus on the time complexity (with one-step updates), which is an interesting component w.r.t. existing SSP algorithms (and most other model-based algorithms) that perform full-planning. For instance the update scheme is novel (compared to the one in [Zhang et al., 2020a]) and allows to maintain the horizon-free regret. \n\nMinor comment/suggestion: there are some parts where the authors could perhaps be slightly more precise in the presentation for non-familiar readers. It could be mentioned on top of page 13 that the $\\widetilde{O}$ notation in the analysis usually includes $\\log(T)$ terms, with $T$ the total time steps which is a random variable in SSP but can be easily handled under positive costs. Also the passage from $c_{\\min}$ > 0 to $c_{\\min}$ = 0, while standard and already performed in prior works, could be more carefully written: indeed as explained in [Tarbouriech et al., 2021b], doing the cost perturbation leads to different final bounds (some horizon-free, others not) depending on the prior knowledge available: in this sense, the statement in introduction “SVI-SSP achieves minimax regret $\\widetilde{O}(B \\sqrt{SAK} + B_{\\star} S^2 A)$ even when $c_{\\min} = 0$” (line 44-45) could be clarified, as it seems this requires either knowledge of a loose estimate of $T_{\\star}$ or that $K \\gtrsim T_{\\star}$. The paper could perhaps report in the appendix more complete bounds, arguments or references to specific passages of prior works that share them (so as not to crowd the main paper with quite standard technicalities already discussed in previous works).", "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.5"}, "extra_text": {}}, {"review_id": "Cr_cX-aAmsP", "reviewer": "Reviewer_U8Kt", "summary": "This paper presents algorithms for the stochastic shortest path (SSP) problem with unknown stochastic transitions but “known and deterministic” costs. The first algorithm, LCB-Advantage-SSP, is the first model-free for SSP with provable regret. When the minimal cost $c_{\\min}$ is non-zero, the algorithm achieves the minimax-optimal regret. Notably, LCB-Advantage-SSP has a lower computational complexity compared to existing model-based algorithms for SSP. The second algorithm, SVI-SSP, is a model-based algorithm achieving the minimax-optimal regret even when $c_{\\min} = 0$, while requiring less computational complexity in comparison to existing algorithms.", "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": "The paper investigates a concrete and interesting RL problem, which received increasing attention during the last two years, though early literature outside of RL, for the fully specified case, abound and date back to decades ago. From a practical standpoint, I believe SSP is at least as significant as the fixed-horizon episodic RL. \n\nExisting literature already present some minimax-optimal algorithms for SSP, but are all model-based, to my best knowledge, which may incur rather high computational costs. Thus, by presenting the first model-free algorithm for SSP, which happens to be minimax-optimal under $c_{\\min}>0$, the paper provides a nice addition to the literature. The second algorithm also makes a further step in advancing state-of-the-art, as it requires less computation than state-of-the-art.\n\nThe paper is written and organized very well, and almost, typo-free. It admits a clear and precise presentation and is overall a nice read. \n\nDespite these strengths, I have some concerns detailed below:\n\n- While assuming prior knowledge on the cost/reward function has become sort of standard practice in theoretical RL, relaxing this is not always easy or straightforward, notably for model-free algorithms. I am wondering for unknown and “stochastic” costs, what the right way to initialize $Q$ in Algorithm 1 would be. I’m afraid that we may need to know $c_{\\min}$ (or some LB on that), to maintain optimism. I may ask the authors to explain this. This may entail further clarification (or refinement) of the remark in the footnote of page 3. If true, the claims in the abstract and introduction should be refined accordingly and explicitly. \n\n- I found it really strange that poly-log terms were made hidden in the $\\widetilde O$ throughout (even in the appendix). It is fine to use $\\widetilde O$ to arrive at a concise regret bound hiding both numerical constants and poly-log terms. But doing the same practice may not be a good idea for the appendix. At least for the leading-term in the regret bound, it makes sense to report all the constants and logarithmic terms involved. As reviewer, I would have liked to check such dependencies, but it seems that you left it as an exercise to me (and future readers). This is sadly the case for all the bounds and I am afraid that this could partially violate 2(b) in the Checklist. \n\n- As there already exist a couple of minimax-optimal algorithms for SSP, it might render necessary to compare their corresponding regret bounds in terms of the second-order terms. In particular, those terms in the case of LCB-Advantage-SSP seem to have a prohibitive dependence on $c_{\\min}$ and $B_\\star$, which could be refined via a sharper analysis. This could be of importance from a statistical efficiency perspective, as in the low-K regime, one may not easily ignore the second-order terms. \n\nThis is a well-written paper tackling an interesting problem. But I believe these limitations need to be addressed before acceptance. I would be happy to read the authors responses to my raised comments, and upon convincing responses/promises I would consider increasing my score. \n\nSome minor comments follow. \n\nLine 474: $\\tilde s_0$ ---- > $\\tilde s_{\\mathrm{init}}$ \n\nLine 879: Taking … initiate ---- > … initiates \n\nLine 140: after-state ---- > the term “next-state” seems to be more common in the literature. \n\nLine 271: two parameter ---- > two parameters \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please pay attention to my detailed comments above. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a framework for the analysis of tabular SSP problems which is used to prove regret bound for both model-based and model-free algorithms. The model-based algorithm matches the best-known rate while allowing sparse updates. More interesting, the paper introduces the first model-free algorithm for this setting. The paper is solid, novel and interesting. It is a valuable contribution to the conference.

While the reviewers all agree on the value of this paper, they provided relevant suggestions. Please take them into consideration in the revised version.
Decision: Accept (Poster)