Minimax Regret for Stochastic Shortest Path
Authors: Alon Cohen
Yonathan Efroni
Yishay Mansour
Aviv Rosenberg
Venue: NeurIPS 2021 Poster (2021)
Keywords: regret minimization
stochastic shortest path
reinforcement learning
online learning

Abstract: We study the Stochastic Shortest Path (SSP) problem in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent has no prior knowledge about the costs and dynamics of the model. She repeatedly interacts with the model for $K$ episodes, and has to minimize her regret. In this work we show that the minimax regret for this setting is $\widetilde O(\sqrt{ (B_\star^2 + B_\star) |S| |A| K})$ where $B_\star$ is a bound on the expected cost of the optimal policy from any state, $S$ is the state space, and $A$ is the action space. This matches the $\Omega (\sqrt{ B_\star^2 |S| |A| K})$ lower bound of Rosenberg et al. [2020] for $B_\star \ge 1$, and improves their regret bound by a factor of $\sqrt{|S|}$. For $B_\star < 1$ we prove a matching lower bound of $\Omega (\sqrt{ B_\star |S| |A| K})$. Our algorithm is based on a novel reduction from SSP to finite-horizon MDPs.  To that end, we provide an algorithm for the finite-horizon setting whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.

Minimax Regret for Stochastic Shortest Path
Alon Cohen
Yonathan Efroni Microsoft Research, New York Jonathan. efroni www.tthnnneeeeriiieieee @gmall com
Tel-Aviv University and Google Research, Tel Aviv a alloncohenngooogle.coom com
Yishay Mansour
Aviv Rosenberg Tel-Aviv University avivzos0078gmaill
Tel-Aviv University and Google Research, Tel Aviv mansour@tau. ac.1l
Abstract
We study the Stochastic Shortest Path (SSP) problem in which an agent has to reach a goal state minimum total expected cost. In the learning formulation of the problem, the agent has no prior knowledge about the costs and dynamics of the model. She repeatedly interacts with the model for K episodes, and has to minimize her regret. In this work we show that the minimax regret for this setting is O(V(B) B, ((SIAII) where B. is a bound on the expected cost of the optimal policy from any state, is the state space, and A is the action space, This matches the Su( v B ()) lower bound of Rosenberg al. (020 for B, 2 1, improves their regret bound by a factor of VISI. For B, < 1 we prove a matching lower bound of [2( B, (SI Our algorithm based on novel reduction from SSP to finite-horizon MDPs. To that end, we provide an algorithm for the finite- horizon setting whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.
Introduction
We study the stochastic shortest path (SSP) problem which an agent aims reach predefined goal state while minimizing her total expected cost. This is one of the most basic models of reinforcement learning (RL) that includes both finite-horizon and discounted Markov Decision Processes (MDPs) as special cases. In addition, SSP captures wide variety of realistic scenarios such as car navigation, game playing and drone flying.
We study an online version of SSP in which both the immediate costs and transition distributions of the model are initially unknown to the agent. The agent interacts with the model for K episodes, in each of which she attempts to reach the goal state with minimal cumulative cost. A main challenge in the online model is found when instantaneous costs are small. For example, any learning algorithm that attempts to myopically minimize the accumulated costs might get caught in a cycle with zero cost and never reach the goal state. Nonetheless, even if the costs are not zero, only very small, the agent must be able to trade off the need to minimize costs with that of reaching the goal quickly.
The online setting originally suggested by Tarbouriech al. 2020 who gave algorithm with 2( regret guarantee. In follow-up work, Rosenberg et al. 2020 improved the previous bound ISB,ISI /AIK), where S is the state space, the action space, and B, is an upper bound on the total expected cost of the optimal policy when initialized any state. Rooenberg et al. [2020) also provide lower bound of Q(B, C.BB.ISSAIIA VSSIAIK)- leaving gap of VISI between the upper and lower bounds. In this work, unlike the previously mentioned works that assume the cost function deterministic
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and known, we consider the case where the costs are i..dd and initially unknown. We prove upper and lower bounds for this case, proving that the optimal regret is of order O /BB B. )ISIAIKK)
The algorithms of both Tarbouriech et al. [2020] , Rosenberg al. 2020 were based on a direct application of the "Optimism in the Face of Uncertainty" principle to the SSP model, following the ideas behind the UCRL2 algorithm (Jaksch et al. 2010] for average-
MDPs. In this work we take a different approach. We propose novel black box reduction to finite-horizon MDPs, showing that the SSP problem is not harder than the finite-horizon setting assuming prior knowledge on the expected time it takes for the optimal policy to reach the goal state. While the reduction itself is simple, the analysis is highly nontrivial as one has to show that the goal state is indeed reached in every episode without incurring excessive costs in the process.
The idea of reducing SSP to finite-horizon was previously used by Chen al. 2020 Chen and Luo [ for SSP with adversarially changing costs. However, they run one finite-horizon episode in every SSP episode and then simply try to reach the goal as fast as possible, while we restart new finite-horizon episode every H steps. This modification is what enables us to obtain the optimal and improved dependence in the number of states.
In addition, we provide a new algorithm for regret minimization in finite-horizon MDPs called ULCVT. We show that (for large enough number of episodes) its regret depends polynomially on the expected cost of the optimal policy B., and only logarithmically on the horizon length H. This implies that the correct measure for the regret is the expected cost of the optimal policy and not the length of the horizon. We note that regret with logarithmic dependence in the horizon H was also obtained by Zhang et al. [2020], yet they make much stronger assumption: that the cumulative cost of every trajectory is bounded by 1. In contrast, we only assume that the expected cost of the optimal policy is bounded by some constant B., while other policies may suffer a cost of H.
Our reduction, when combined with our finite-horizon algorithm ULCVI, guarantees SSP regret of OLV(B. + B. )SHAAI,). This matches the lower bound of Rosenberg et al. [220]] for B. > 1 up to logarithmic factors. However, their lower bound does not hold for B. I suggesting that this is not the correct rate in this case. Indeed, we prove a tighter lower bound of Ω(( (SIAAI)) for B. < 1, showing that our regret guarantees are minimax optimal in all cases.
As final remark we note that, following our work. Tarbouriech et al. [021] were able to obtain a comparable regret bound for SSP without prior knowledge of the optimal policy's 's expected time to reach the goal state.
1.1 Additional related work
Planning for stochastic shortest path. Early work by Bertsekas and Tsitsiklis [191] studied planning in SSPs, i.e., computing the optimal strategy efficiently when parameters are known. Under certain assumptions, they established that the optimal strategy a deterministic stationary policy and can be computed efficiently using standard planning algorithms, e.g., Value Iteration and LP.
Adversarial stochastic shortest path. Rosenberg and Mansour (200 presented stochastic shortest path with adversarially changing costs. Their regret bounds were improved by [Chnn et al.) (2020), Chen and Luo [202T] using reduction to online loop-free SSP (see next paragraph). As mentioned before, reduction is different and therefore able remove the extra VISI factor in the regret.
Regret minimization in MDPs. There is vast literature on regret minimization in RL that mostly builds on the optimism principle. Most literature focuses on the tabular setting jaksch et al. 2010
Azar et al. 2017 Jin et al.) 2018 Fruit et al. 2018 Zanette and Brunskill 2019 Efroni et al. 2019 Simchowitz and Jamieson, 2019]. but recently it was extended to function approximation under
various assumptions (Yang and Wang 2019 Jin et al. 20206 Zanctte et al. 2020a|b).
Online loop-free SSP. A different line of work considers finite-horizon MDPs with adversarially
changing costs [Neu et al., [2100] 2012, Zimin and Neu [2013] Rosenberg and Mansour [201b]a
et al.
2020a
C Cai et al., 2020 Shani et al.] [020 Lancewicki et 2 Lee et al. 2020 Uin and
Luo
2020). They refer to horizon adversarial MDPs as online loop-free SSP. This is not to be
confused with our setting in which the interaction between the agent and the environment ends only
when (and if) the goal state reached, and not after a fixed number of steps H. See Rosenberg and
Mansour 2020
Chen et al. (2200) for discussion the differences between the models.

---

2 Preliminaries and main results
An instance of the SSP problem is defined by MDP .M PS,A,P.C. Smiit where is a finite state space and A is finite action space. The agent begins at an initial state Smit E S, and ends her interaction with M by arriving the goal state g (where g $ S). Whenever she plays action a in state s, she pays a cost C E [0, 1J drawn i.i.d. from a distribution with expectation c(s, a) E [0, 1] and the next state s' S U {g] is chosen with probability P(s' I s,a). Note that the transition function satisfies Erescle) P(s' ss a) = for every (s, a) E S x
Proper policies. A stationary and deterministic policy π : S A is a mapping that selects action (s)) whenever the agent is state A policy is called proper if playing according to ensures that the goal state reached with probability when starting from any state (otherwise it is improper). In SSP, the agent has two goals: (a) reach the goal state; (b) minimize the total expected cost. To facilitate the first goal, we make the basic assumption that there exists at least one proper policy. In particular, the goal state is reachable from every state, which is clearly necessary assumption.
Any policy π induces a cost-to-go function J + [0, oo]. The cost-to-go at state s defined by (s) = lim Ex EE' c(s, a,) I Sinit = s]. where the expectation is taken w.r.t the random sequence of states generated by playing according to when the initial state is s. For a proper policy ı, it follows that (x) is finite for all s E S. However, note that (s) may be finite even if x is improper. We additionally denote by (s) the expected time it takes for i to reach starting at state
s; in particular, if π is proper then (s) is finite for all s E S, and i is improper there must exist some state such that (*)s)= = 0o.
Learning formulation. Here, the agent does not have any prior knowledge of the cost function e or transition function P. She interacts with the model in episodes: each episode starts at the fixed initial state Sinit T and ends when the agent reaches the goal state g (note that she might never reach the goal state). Success is measured by the agent's 's regret over K such episodes, that is the difference between her total cost over the K episodes and the total expected cost of the optimal proper policy:
Rx
C
K
min T
(Smm).
where 1 is the time it takes the agent to complete episode k (which may be infinite), C/ is the cost suffered in the i-th step of episode k when the agent visited state-action pair (sf, af,, and Iprroer is the set of all stationary, deterministic and proper policies (that is not empty by assumption). In the case CC.
that 1 is infinite for some k, we define Rx
We denote the optimal proper policy by π². "F= (Smi) = arg min
J" (Smit) Moreover, let B, > 0 xEllyaper mninneellpug be an upper bound on the values of J= and let T, > O be upper bound on the times 7 i.e., B. 2 max,es Jx (s) and T. 2 max,es T (s). Finally, let D = max,es min (s) be the diamdiem, and note that B, DD
2.1 Summary of our results
In Section 3 we present a novel black-box reduction from SSP to finite-horizon MDPs (Algorithml that yields / K regret bounds when combined with a certain class of optimistic algorithms for regret minimization in finite-horizon MDPs that we call admissible (Definition]) [D. The regret analysis for the reduction is described in Section 4 and Section [5] we present an admissible algorithm for regret minimization in finite-horizon MDPs called ULCVI. We show that it guarantees the following optimal regret in the finite-horizon setting (stated formally in Theorem [.I). Note that (for large enough number of episodes) this bound depends only on the expected cost of the optimal policy and not on the horizon H.
Theorem 2.1. Running ULCVI (Algorithm) probability at least 5, a regret bound of
in Section in a finite-hhoizzon MDP guarantees, with
( B. ISIIAIM log
MHISIAAI
+ 1H* 3/2 MHISIAAI
8
'The initial state is fixed for simplicity of presentation, but it can be chosen adversarially at the beginning of every episode. Without any change to the algorithm analysis, the same guarantees hold.
3

---

for any number of episodes M 2 simultaneously
Combining ULCVI with our reduction yields the following minimax optimal regret bound for SSP. Theorem 2.2. Running the reduction in Algorithm
7 with the finite-hrrizon regret minimization
algorithi ULCVI ensures, with probability at least 8,
Rx = ( (VBR + B. JISIAII log
KT, KTAIIIAA
+ B KT,ISIAI
5
8
Remark 1. An important observation is that this regret bound is meaningful even for small K. Unlike finite-horizon MDPs, where linear regret trivial in SSP ensuring finite regret is not easy. Our regret bound also implies that if we play for only one episode, i.c. are only interested in the time it takes reach the goal state, then will take at most B(T time steps do so.
Remark 2. Note that our algorithm needs to know an upper bound on T. in advance. However, all costs are strictly positive (i.e., at least Cmin > 0), then there is a trivial upper bound of B./Cmin- In this case, our algorithm keeps an optimal regret bound for large enough K, since the bound on T. only appears in the additive factor. Some previous work used a perturbation argument to generalize their results from the Cmin case to general costs (Tarbouriech et al. 2020. Rosenberg et al., 2020 Rosemberg and Mansour, 2020]. In our case, it will not work since the dependence on 1/Cmin in the additive term too large. This may be an inherent shortcoming of using Enite-horizon reduction to solve SSPs, as it also appears in the works Chen al. [2020), Chen and Luo [2021) for the adversarial setting.
In practice, one can think of T. parameter of the algorithm that controls computational complexity and the number of steps to complete K episodes. By choosing the parameter T, = x for example,
Remark 3.
guarantee that the regret bound of Theorem 2.2 holds against the best proper policy with expected time to the goal of at most x (assuming there exists one). and we can also guarantee that the total computational complexity of the algorithm is O(x log K) (see Remark 5). Furthermore, the algorithm will take at most Ō(xK poly(x, ISI, lAI)) steps to complete K episodes.
Remark 4. While the additive term in our regret bound is standard for most cases, it becomes large when B. is extremely small because of the dependence B This was not an issue previous work (Tarbouriech et al. 2020 Rooenberg et al. [2020) since they assumed that the costs are deterministic and known. We believe that this dependence is an artifact of our analysis that may be avoided with a more careful definition of W (see Definition I that depends
the actual cost in each state-action pair and not just B.. Nevertheless, the main focus of this paper is on establishing that the minimax optimal regret for SSP is θ(v (B, B, JSSIAIK), and not on optimizing lower order terms. By that also show that this is the minimax optimal regret for finite-horizon which is independent of the horizon H (up to logarithmic factors). Tightening the additive term and climinating its dependence in B. left as an interesting future direction.
In Appendix D we prove that our regret bound is indeed minimax optimal. To complement the Ω(B, VISIAIKK lower bound of |Rosenberg al. [2020) that assumes B, 2 we provide the following tighter lower bound for the case that B, I.
Theorem 2.3. Let B, < 1. There exists an SSP problem instance M = AS c, Sints g) in which JR (s) < B. for all s E S, ISI > 2, IAI 2, K > B,ISAAI, such the expected regret of any learner after K episodes satisfies
E[Rx| N
V
/LIIIAII..
32
3 A black-box reduction from SSP to finite-horizon
Our algorithm takes as input algorithm A for regret minimization in finite-horizon MDPs, and uses it to perform black-box reduction. The algorithm is depicted below as Algorithm I
The algorithm breaks the individual time steps that comprise each of the K episodes into intervals of // time steps. If the agent reaches the goal state before // time steps, we simply assume that she stays in g until I/ time steps are elapsed. We see each interval as one episode of a finite-horizon model M AS H, č, 2,)), where $ = =SU (g) and êj S + R is set of terminal costs defined by

---

(s)) 8 * g), where [[s is the indicator function that equals 1 s 8 and 0 otherwise.
Moreover, P, are the natural extensions of P, the goal state. That is, c(s, a) (s # g) and
P(s' s,,))
$
P(s' ls,a)
1.
= g, = g: s g, #
0.
The horizon H (which we will set to be roughly T.) is chosen such that the optimal SSP policy will reach the goal state in H time steps with high probability (recall that the expected hitting time of the optimal policy is bounded by T,). The additional terminal cost is there encourage the agent to reach the goal state within H steps, which otherwise is not necessarily optimal with respect to the planning horizon.
Algorithm 1 REDUCTION FROM SSP TO UNITE-HORIZON MDP
1: input: state sapce S, action space A, initial state Smits goal state g, confidence parameter 5, number of episodes K, bound on the expected cost of the optimal policy B., bound on the expected time of the optimal policy T. and algorithm A for regret minimization in finite-horizon MDPs.
2: initialize A with state space S S J {g), action space A, horizon H 8T, log(8K), confidence parameter 8/4, terminal costs (5) 8B,1 # g) and bound on the expected cost of the optimal policy 9B,.
3: initialize intervals counter m +- 0 and time steps counter 1 +-
4: for k = I....,K do
5: set <- Sinit-
6: while s, #g g do
7:
set m m + 1, feed initial state s, A and obtain policy T" { : A Alm
8:
for 1= 1....... H do
9:
play action a: = (s;),,, suffer cost C, c(s,, and set 5/ S,, dff = a. Cj C.- observe next state s41 ~ P(- s,, a,) and set f f 1
10:
if s, = then
12:
pad trajectory to be of length H and BREAK.
end 14: end for
15:
set sf/+1 = Sy.
16:
feed trajectory U² = (s' .f...... (H.)) and costs (C 1/4 to A.
17:
end while
18:
end for
The algorithm A is initialized with the state and action spaces as in the original SSP instance, the horizon length H, a confidence parameter 5/4, a set of terminal costs õ and a bound on the expected cost of the optimal policy in the finite-horizon model 9B., At the beginning of each interval, it takes as input an initial state and outputs policy to be used throughout the interval. In the end of the interval it receives the trajectory and costs observed through the interval.
Note that while Algorithm T may run any finite-horizon regret minimization algorithm, the analysis require that A possesses some properties (that most optimistic algorithms already have) in order to establish our regret bound. We specifically require A to be an admissible algorithm- a model-based optimistic algorithm for regret minimization in finite-horizon MDPs, e.g., UCBVI [Azar al. 2017 and EULER [Zanette and Brunskill, 2019]. Admissible algorithms are defined formally as follows.
Definition 1. A madel-based algorithm A for regret minimization in finite hatte-horizon MDPs is called admissible if, when running with confidence parameter there is a good event that holds with probability at least 1 - 8, under which the following hold:
(i) A provides anytime regret guarantees without prior knowledge of the number of episodes, and when the initial state of each episode is arbitrary. The regret bound that A guarantees for M episodes is denoted by (MM, for some non-decreasing function R.
(ii) The policy n" that A picks in episode m is greedy with respect to an estimate of the optimal policy's Q-function.
(iii) The algorithm's estimate 1t" of Tr (the cost-to-go function associated with the optimal policy) is optimistic, i.c., (s) < (s) for every e S and h I.....
5

---

(iv) A computes J using estimates eth, PM of the cost function è and the transition function P. respectively. There exists Wa which is function of H, ISI, lAI such that: if state-action pair (s,a) a) was visited at least WA log MINSIA times, then (s, (s. a) c(s, I B,/H and ( ss P(- s. al11 I 1/(9H).
Using an admissible algorithm in Algorithm I enables us to bound the total number of intervals, thus ensuring that the agent reaches the goal state in almost every interval. This because, as A is optimistic, it will try to avoid the terminal cost (which is suffered in all states except for by reaching the goal state. In addition, A will succeed in doing so once has a good enough estimation of the transition function. Armed with the notion of admissibility, in the sequel we prove the following regret bound for any admissible algorithm A. The proof Theorem 2.2 is now given by combining Theorem 3.1 with the regret bound of ULCVI in Theorem 2.1
Theorem 3.1. Let A be an admissible algorithm for regret minimization in finite-horizon MDPs and denote its regret in M episodes by RA(M). Then, running Algorithm 1 probability at least 1
with A ensures that, with
KT, KT,SSIAK
4K + 10'ISAAAA log Rx S RA
8
+0 20(118 [V (B.+ log
KT. KSAAAAAAA
KT, KT,ISIAAWA
where WA is a quantity that depends on the algorithm A and on ISI, |AI, H.
Remark 5 (Computational complexity). Our reduction directly inherits the computational complexity of the finite-hore horizon algorithm A in M episodes, where M R K + poly(ISI, IAI, T.) by Lemma 44. The computational complexity of ULCVI is O(HISTiAII log(MH)), and therefore our optimal regret for SSP is achieved in total computational complexity of OTT.ISPLAP log" K7, (7.ISIA!) which is only logarithmic in the number of episodes.
3.1 Unknown expected optimal cost B,
Inspired by techniques for estimation of the SSP-diameter in the adversarial SSP literature [Rosenberg and Mansour 2020 Chen and Luo 2021]. in Appendix C we show that our reduction does not need know B. in advance, but can instead estimate it on the fly.
We can obtain reasonable estimate (up to a constant multiplicative factor) of the cost-to-go from state by running the SSPs (that does not need to know B.) with initial state s for roughly 7:1SP episodes. Thus, we can apply reduction while utilizing our first visits to each state order estimate its cost-to-go.
algorithm of Rosenberg et al. [0200] for regret minimization in
We operate in phases where each phase ends when some state visited at least 71ISPIAI times, and all states that were not visited enough are treated as the goal state. Once we reach poorly visited state, we simply run an episode of the corresponding Bernsteir-SSS algorithm. Notice that this comes at computational cost that is independent of the number of episodes K (since we use Bernstein SSP for a small number of episodes), and in Appendix C we show that achieves similar regret bounds with only an additional additive factor of O(TA)SPLAA).
Regret analysis
In this section we prove Theorem 3.1 Below we give a high-level overview of the proofs and defer the details to Appendix [A] We start the analysis with regret decomposition that states that the SSP regret can be bounded by the sum of two terms: the expected regret of the finite-horizon algorithm, and the deviation of the actual cost in each interval from its expected value. To that end, the notations: M for the total number of intervals, L = (s"", ....a"............... sh ag s5 ) for the trajectory visited in interval m, C.. for the cost suffered in step of interval m, Th for the policy chosen by A for interval m, and Jr. (s) for the expected state in time step h.
cost when playing policy æ starting from

---

Lemma 4.1. For H = 8T, log(8K), we have the following bound on the regret of Algorithm !
M
H
Rx RA(M) +
Σ mPF1
Σ A=1
C +
- (69) B..
(1)
The bound in Eq. is comprised of two summands and an additional constant. The first summand an upper bound on the expected finite-hrrizon regret which we acquire by the admissibility of A (Definition] D. Note that this bound is in terms of the number of intervals M (i.e., the number of finite-horizon episodes) which is random variable and not necessarily bounded. In what follows we show that, using the admissibility of A. we can actually bound M by the number of SSP episodes K plus a constant that depends on w', ISI, IAI, T, (but not on K). The second summand Eq. ① relates to the deviation of the total finite-horizon cost from its expected value.
The proof of Lemma 4.1 builds on two key ideas. The first that, by setting H be O(T, log K), we ensure that the expected cost of the optimal policy in the SSP model M is close to that in the finite-horizon model M. The second idea is that if the agent does not reach the goal state in certain interval, then she must suffer the terminal cost in the finite-hor horizon model. Therefore, although in a single episode there may be many intervals in which the agent does not reach the goal state, can upper bound the cost in these extra intervals in M by the corresponding terminal costs in M.
Next, we bound the deviation the actual cost in each interval from its expected value which appears the second summand in Eq. [Ι). The bound due to the following lemma.
Lemma 4.2. Assume that the reduction is performed using admissible algorithm A. Then, the following holds with probability at least 3//s.
M +TR++BAn Mog 5 ASAAA =0(
MKT,
Σ Ch + ( (o'"))))))) =
5
The key observation here relies on the notion of unknown state-action pairs - pairs that were not visited at least WA times. After W.A visits to some state-action pair s.a, we have a reasonable estimate of the next-state distribution P(- I s. a) therefore we can show that the expected accumulated cost in an interval until reaching an unknown state-action pair or the goal state is of order B,. Moreover, the second moment of this cost of order B², B.. Thus, using Freedman inequality, we bound the deviation by Ō( / an unknown state-action pair the goal state (there are roughly ISIlAA such intervals).
(BC + B)) plus a cost of O(H) for each "bad" interval in which we do not reach
Lastly, we need to bound the number of intervals to obtain regret bound in terms of and not M (notice that M is a random variable that is not bounded a-priori).
Lemma 4.3. Assume that the reduction is performed using an admissible algorithm A. Then, with probability least 38/s, M < 4K 10 log(KT,ISlAAlwa,
The proof shows that in every interval there is a constant probability to reach either the goal state or an unknown state-action pair. Leveraging this observation with concentration incquality, we can bound the number of intervals by O(K (SIIAAI)..
We can now prove a bound on the regret of Algorithm using any admissible algorithm A.
Proof of Theorem 3.1 The regret bound of A, Lemmas and 4.3 all hold with probability least 1 8, via union bound. Using Lemmas 4.1 and 4.2 we can write
Rx S RA(M) (B. + +
M lSLAllgg
MKT,ISIAI
+ B..
5
8
Finally, we use Lemma 4.3 to bound M by 4K + 10 I81AW
5 ULCVI: an admissible algorithm for finite-horizon MDPs
In this section we present the Upper Lower Confidence Value Iteration algorithm (ULCVI; Algo- rithm 2 for regret minimization in knite-horizon MDPs, This result holds independently of our SSP
7

---

Algorithm 2 UPPER LOWER CONFIDENCE VALUE ITERATION (ULCVI)
1: input: state space S, action space A, horizon H. confidence parameter 6, terminal costs and upper bound on the expected cost of the optimal policy B..
2: initialize: rs
0, (s,
Os," a) O, (s, 0
3: initialize: (s,, a) (s, 0, ("s'ss, a) = I[ss = s) (
4: initialize: Pl PlantingTrigeerrr true.
5: for ı = 1.2.... do
6: observe initial state sT.
7: if "Fllannnngrgigerr = true then
8: set 11th (s, N (s. a), n (s, + Nmm (s.a.s) ass, (sas')
9:
set pm assls, + max[Te L (..o) 2m (s. f maxi (s V(s, ass.a.s).
(a,(a))
10:
compute (1)) via OPTIMISTIC- VALUE ITERATION (Algorithm 3).
11: set PllnningTriggee
false.
12: else
(s. t (ss set pm- (s'ls, a) + pm (s'ls, em t- (s, as,
set (s, a) 2 n
14:
set (s) Th (s) for all E Sand I.....H.
16:
end if
set (s. 1 a). Ns
N' (s.a.s), (s. "aaa.ss.C""ss.... (s.a) V(s.a,s)
18:
for h == I,.., do
pick action of = nh )
20:
suffer cost C2 ~ 2( x and observe next state 1h11 ~ P(- 1ss (.).
21:
update visits counters (. af") +- ns""" (a))) (Sh . t- (s (1r))
22:
update accumulated cost (s . (x) < Ch (hhhah (a)) Ch.
23:
(s"" a(r) 2 mh (s a then set PetPlninggTrigger
24:
true.
25:
end if
26:
end for
27: Suffer terminal cost (5()).))
28:
end for
algorithm. Since the algorithm is similar to previous optimistic algorithms for the finite-horizon setting, e.g., UCBVI [Azar et al.) [017)] and ORLC [Dann et al.] [019], we defer the analysis to technical novelty bounding the regret in terms of the optimal value function and not the horizon.
Appendix B and focus
In each episode the ULCVI algorithm maintains optimistic lower bound (s) and a pessimistic upper bound (s) on the cost-to-go function of the optimal policy JJ)s), and acts greedily with respect to the optimistic estimates. These optimistic and pessimistic estimates are computed based on the empirical transition function pm-1(s' s, a) and the empirical cost function (m. a) to which add exploration bonus b"" a) + b" a), where b" handles the approximation error in the transitions and b" handles the approximation error in the costs. The bonuses are defined as follows,
Var aa (C)m b""(s = V max (1 1, n (s,a)) a))
5Ln
+ max max -s.
Var (Lt Mom
B. Ep (.b. 1 -m (s'),,
(s,
max (1, n (s, max 1 (x, 16H²
where Lm = 3 log(3ISIAl/fmm/) is a logarithmic factor and " (s. a) is the number of visits to (s. in the first m episodes. Furthermore, Var -- (Cr)
(C) is the empirical variance of the observed costs in (s.a) in the first episodes + Lastly, the term Varpe is the variance of the next state value Li= from state-action pair (s, as, calculated via the empirical transition model, i.e., Varp- (1 Ep- [iL -Eperrtta (s')1²
"The empirical variance of nt numbers .i.....an is detined 1 (a ! a)²

---

Algorithm 3 OPTIMISTIC- VALUE ITERATION
1: input: n==1,, pm- p0--,,---1,, čg. B..
2: initialize [i- (5) cy(s) for all S.
3: for h = H. H.,-l........ do
4: for E do
5: for a E do
6: set the bonus (s, (s, a) + bf a) defined in Eq. Q2 compute optimistic and pessimistic Q-functions:
7:
-* = @*..aa) = (m. (s. 81 a) Ep bhal (s
( (s, (s, a) + E (ha
8:
end for
9: (s) E arg min _7
10:
(s) max (s. (s) (Ts
11: end for
12:
end for
For improved computational complexity, we compute the optimistic policy only in episodes in which the number of visits some state-action pair was doubled. This ensures that the number of optimistic policy computations grows only logarithmically with the number of episodes, i.c., it is bounded by log((H), Since each optimal policy computation costs O(HISPIAI) in the inite-horizon MDP model, our algorithm enjoys total computational complexity of O(HISI LAI log(MH)).
For clarity, we keep the notation of the finite-horizon MDP as M (S H,H.H, Cy). and let B. max,,, (s) where jr is the value function of policy (in the case of our SSP reduction this parameter is simply 9B, by Lemma A. This implies that 2y(s) S B, for every s, and for simplicity. assume that B, H. Thus, the maximal total cost in episode is bounded by H B < 2H. In Appendix
B we prove the following high probability regret bound.
Theorem 5.1. ULCVI (Algorithm 2
is admissible with the following guarantees:
(i) With probability at least the regret bound of ULCVI
RULCVI = 0 VBB, + +., log
MHISIA
+ H HHB IISPIAl 3/2 MHISIAI
8
for any number of episodes M 2 1.
(ii) WULcvi ((HHB:21S))
Our analysis resembles the one in Efroni et al. 2021], I. and is adapted to the stationary MDP setting (i.e., the transition function does not depend on the time step h). and to the setting where have costs instead of rewards, and terminal costs (which do not appear in previous work). By the definition of the algorithm and the regret bound in Theorem 5.I it is clear that properties (i)-(iii) in Definition [ of admissible algorithms hold. For property (iv). we use standard concentration inequalities and the definition of the bonuses in Eq. 2 in order to show it holds for WULCVI O(H* B,"SS).
To obtain a regret bound whose leading term depends on B, and not H, we start with standard regret analysis for optimistic algorithms that establishes the regret scales with the square-root of the variance the value functions of the agent's policies, i.c.,
RULCVI (M) VISIAI
Varmeugu))(1 H H
up to logarithmic factors and lower order terms. This can be further bounded by the second moment of the cumulative cost in each episode as follows,
M E
))
RULCVI $ VISIIA
Σ
Σ CF A==
1m
+ H1 B

---

where U is the sequence of state-action pairs observed up to episode m. Leveraging our techniques for the SSP reduction (but independently). we show that the second moment of the cumulative cost until an unknown state-action pair is reached can be bounded by O B.). Therefore, we have at most O(H' B:HHB:"ISPLA) episodes in which we bound the second moment trivially by O(H?), and in the rest of the episodes we can bound it by O(B,, + B.). Together this yields the theorem as follows,
RUL.CVIM (M) x ViSIAAI + B.MM + HP H*B, S VBB, + B.)ISIAMM HH
Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union's sHorizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation(grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University
References
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017.
Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-59) 1991.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pages 1294-1294. PMLR, 2020.
Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. arXiv preprint arXiv:2102.05220 2021.
Liyu Chen, Haipeng Luo, and Chen-Yu Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. arXiv preprint arXiv:2012.0400: 2020.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountablc reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for bosel-based reinforcement learning with greedy policies. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information P Processing Systems 2019, NeurlPS 2019, December 2019, Vancouver, BC, Canada, pages 12203-12213, 2019.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. arXiv preprint arXiv:2008.0603 2020.
Yonathan Efroni, Nadav Merlis, Aadirupa Saha, and Shie Mannor. Confidence-budget matching for sequential budgeted learning. arXiv preprint arXiv:2102.033000 2021.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrainee exploration-exxlooiaaion in reinforcement learning. arXiv preprint 182.v:1802.044000 2018.
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. q-learning provably efficient?
In Advances in Neural Information Processing Systems, pages 4863-4873, 2018.
10

---

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 PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function upproximation. In Conference on Learning Theory, pages 2137-2144 2020b.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in neural information processing systems, 2020.
Tal Lancewicki, Aviv Rosenberg, and Yishay Mansour. Learning adversarial markov decision processes with delayed feedback. arXiv preprint arXiv:2012. 148433 2020.
Chung- Being-Weille Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: prso-prbbbbilityy data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 2020.
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-por -oottest-pathh problem. In COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pages 231-243, 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, 2012.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Advances in Neural Information Processing Systems, pages 2209-2218, 2019a.
Aviv Rosenberg and Yishay Mansour. Online convex optimization adversarial markov decision processes. In International Conference Machine Learning, pages 5478-5486, 2019b.
Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs, 2020.
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-8211 (2-8219, PMLR, 2020.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613. PMLR, 2020.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, pages 1153-1162, 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, 2020.
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. arXiv preprint arXiv:2104. 11 186, 2021.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. arXiv preprint arXiv: 0e1.19902077779 2019.
Andrea Zanette and Emma Brunskill. Tighter -ebeededde regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. International Conference on Artificial Intelligence and Statistics, pages 1954-1964, 2020a.
11

---

Andrea Zanette, Alessandro Lazaric. Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. arXiv preprint arXiv:2003.00155 2020b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. arXiv preprini S.Kiv:2009.135000 2020.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 1583-1591, 2013.
12


Reviews:
[{"review_id": "l7kGZpt8rci", "reviewer": "Reviewer_tvpW", "summary": "As the title suggests, this paper established the minimax regret for the stochastic shortest path (SSP) problem. Specifically, given a state space S, action space A, an upper bound B_\\star on the total cost of the shortest path, the rate-optimal regret (up to logarithmic factors) with K episodes is of the order \\Theta(sqrt((B_\\star^2 + B_\\star)SAK)). This result improves over the prior result by a factor of sqrt(S) in the upper bound, as well as a factor of sqrt(B_\\star) in the lower bound if B_\\star < 1. The main contributions of this paper are: \n\n1. The authors proposed a novel black-box reduction from SSP to finite-horizon MDPs, which holds for a general class of finite-horizon MDP regret minimization algorithms. \n\n2. Similar to the celebrated optimistic algorithms, in finite-horizon MDP the authors proposed the ULCVI algorithm for regret minimization, where the key technical novelty is to upper bound the regret in terms of the optimal value function instead of the horizon. \n\n3. For B_\\star < 1 the authors also proved a matching minimax lower bound. ", "questions": "", "limitations": "", "rating": 7, "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": "I like this paper. This paper completely characterized the minimax regret for the SSP problem, in terms of the optimal dependence on all parameters (S,A,K,B_\\star). Although the reduction idea is very intuitive, the analysis is still technical, and the authors extracted widely applicable conditions such that the reduction holds. The ULCVI algorithm for regret minimization in finite-horizon MDPs are could be of interest on its own. The writing is also very clear. \n\nJust some minor comments: \n\n1. Section 3.1 discussed the case of unknown B_\\star, then how about unknown T_\\star if there is no meaningful c_\\min? Remark 2 partially addressed this question, but I'd like to see whether there is a technical idea to tackle it provably or currently we can only do practical tricks. \n\n2. Could you provide a comparison with the additional terms in the SSP literature? \n\n3. Page 3, Line 117: technically speaking B_\\star \\le D may not hold as B_\\star is only an upper bound. \n\nPost-rebuttal feedback: \n\nThanks to the authors for the response, and I've also read other reviewers' comments. This paper settles the minimax regret for the stochastic shortest path problem, which I think is a solid contribution and recommend it for acceptance.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "gi9JyJX63bD", "reviewer": "Reviewer_3R87", "summary": "This paper proposes an algorithm that achieves minimax regret $O(\\sqrt{(B_{\\star}^2+B_{\\star})SAK})$ for SSP with stochastic costs. Their algorithm is based on a novel reduction from general SSP to a loop-free MDP, and a new finite horizon algorithm whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.", "questions": "", "limitations": "", "rating": 6, "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 question of SSP with stochastic costs: removing the extra $\\sqrt{S}$ factor in the leading term.\nThe proposed loop-free reduction is simple and its analysis is insightful. The matching lower bound is quite interesting from my perspective. The writing is mostly clear and easy to follow.\n\nThere are two main shortcomings of this work in my opinion: 1. the obtained result seems to have a worse constant term compared to Tarbouriech et al. [2021] which has logarithmic dependency on the horizon even in the lower order term. Moreover, their method does not require loop-free reduction. Do you think the techniques  of Tarbouriech et al. [2021] can be applied here to achieve horizon-free regret?\n2. the finite horizon algorithm seems to be a simple extension of EULER [Zanette and Brunskill, 2019], thus has limited novelty.\n\nOverall, I think the problem studied in this paper is important and the results are complete. Thus, I think it is an acceptable submission.\n\n**Questions**\n1. Can the proposed method be directly extended to linear function approximation?\n2. Can you elaborate why the loop-free reduction used in Chen and Luo [2021] is not applicable here? It seems to me that if we run Bernstein-SSP at the end of the finite horizon MDP an set $H_2=2B_{\\star}$, we are also able to get the optimal regret bound. Moreover, the constant term becomes $O(B_{\\star}^{3/2}S^2A)$, which has no dependency on $T_{\\star}$?\n\n**Reference**\n\n[Zanette and Brunskill, 2019]: Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds", "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": {}}, {"review_id": "KoK538ExTXk", "reviewer": "Reviewer_WiEG", "summary": "The paper proposed a novel reduction from stochastic shortest path (SSP) to finite-horizon Markov decision process (MDP). Based on this approach, the paper proposes a model-based algorithm, showing that the minimax regret is $\\tilde{O}(\\sqrt{(B_{\\star}^2+B_{\\star})|S||A|K})$, where where $B_{\\star}$ is a bound on the expected cost of the optimal policy from any state, $S$ is the state space, and $A$ is the action space. This upper bound attains the lower bound $\\Omega(\\sqrt{B_{\\star}^2|S||A|K})$ for $B_{\\star} \\ge 1$. The paper also prove a matching lower bound $\\Omega(\\sqrt{B_{\\star}|S||A|K})$ for $B_{\\star} < 1$. In addition, the paper provides a new algorithm for regret minimization in finite-horizon MDPs and the regret depends only logarithmically on the horizon length.", "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": "Strengths: \n\n1. The paper proposes a novel black-box reduction from SSP to finite-horizon MDPs.\n \n2. The paper improves the minimax regret bound by $|S|$.\n \n3. The paper proves a tighter lower bound for $B_{\\star}<1$ and the upper bound matches the lower bound in both cases, $B_{\\star}<1$ and $B_{\\star}\\ge 1$.\n \n4. The regret bound depends only logarithmically on the horizon.\n\n5. The paper considers the case where the costs are i.i.d. and initially unknown instead of deterministic and known cost function.\n\nWeaknesses\n\n1. The proposed reduction approach only supports model-based algorithms, which also need to satisfy some additional conditions.\n \n2. In the statement of Theorem 2.3, the lower bound $\\Omega(\\sqrt{B_{\\star}|S||A|K})$ is for the case $B_{\\star}\\le 1/2$. What if $1/2 < B_{\\star} < 1$?\n \n3. The algorithm needs to have the knowledge of $T_{\\star}$, which is the upper bound on the expected time steps of the optimal policy, as mentioned in Remark 2, Page 4.\n\nOther comments: \n \n1. Page 3, Line 124-126: The reviewer thinks that the regret depends logarithmically on the horizon $H$ from the theorem.\n\n2. Page 5, Algorithm 1: Is the terminal cost $\\hat{c}_f$ occurred at $h=H$ or $h=H+1$ for each interval? In Algorithm 1, only $c(s_t,a_t)$ are fed to the algorithm $\\mathcal{A}$. It is not clear whether $\\hat{c}_f$ is included. The reviewer thinks that more details should be included in Algorithm 1.\n\n3. Page 8, Line 304-307: $B_{\\star}$ is already defined by the upper bound on the cost of the optimal policy for the SSP as in Line 116, but here is another definition. The reviewer thinks that it is very confusing. Also, in Line 306, it is not clear why we can assume $B_{\\star} \\le H$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "9dSxLK1Heu5", "reviewer": "Reviewer_f8JW", "summary": "The paper focuses on the problem of stochastic shortest path. The authors provide a regret bound of $\\tilde{O}(\\sqrt{({B_*}^2+B_*)SAK })$ , which matches the lower bound up to log terms. Besides, the authors show a lower bound of $\\Omega(\\sqrt{B_* SAK})$ when $B_*< 1$. Their results hold even in the case $B_*$ is unknown.", "questions": "", "limitations": "", "rating": 6, "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": "Pros\nThe final regret bound is tight up to logarithmic terms and the algorithm can work without knowing $B_*$.\n\nCons\nThe algorithm is mainly based on previous algorithms for finite-horizon RL and most techniques are similar. That is, the novelty is not enough.\n\nOther questions:\n1. Have you ever tried the algorithm with only $\\underline{J}$? In this way the analysis could be simplified a lot since there is no need to deal with the gap between $\\underline{J}$ and $\\bar{J}$. In particular, given the knowledge of $B_*$, we can restrict $\\underline{J}$ to $[0, B_*]$ to avoid dependence on $H$.\n\n2. Is the parameter $T_*$ necessary in the algorithm? Moreover, can we avoid the dependence on $T_*$ (even in the lower order terms)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "There is no apparent ethical issues.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes solid contribution to the stochastic shortest path problem.
Reviewers are all in favor of acceptance.
Please do incorporate all the suggestions from the reviews into the final version.

Decision: Accept (Poster)