Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Pros
The final regret bound is tight up to logarithmic terms and the algorithm can work without knowing $B_*$.

Cons
The algorithm is mainly based on previous algorithms for finite-horizon RL and most techniques are similar. That is, the novelty is not enough.

Other questions:
1. 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$.

2. Is the parameter $T_*$ necessary in the algorithm? Moreover, can we avoid the dependence on $T_*$ (even in the lower order terms)?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths: 

1. The paper proposes a novel black-box reduction from SSP to finite-horizon MDPs.
 
2. The paper improves the minimax regret bound by $|S|$.
 
3. 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$.
 
4. The regret bound depends only logarithmically on the horizon.

5. The paper considers the case where the costs are i.i.d. and initially unknown instead of deterministic and known cost function.

Weaknesses

1. The proposed reduction approach only supports model-based algorithms, which also need to satisfy some additional conditions.
 
2. 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$?
 
3. 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.

Other comments: 
 
1. Page 3, Line 124-126: The reviewer thinks that the regret depends logarithmically on the horizon $H$ from the theorem.

2. 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.

3. 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$.

limitations_and_societal_impact: no
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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: 

1. 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. 

2. 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. 

3. For B_\star < 1 the authors also proved a matching minimax lower bound. 
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. 

Just some minor comments: 

1. 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. 

2. Could you provide a comparison with the additional terms in the SSP literature? 

3. Page 3, Line 117: technically speaking B_\star \le D may not hold as B_\star is only an upper bound. 

Post-rebuttal feedback: 

Thanks 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.  
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: This paper resolves an important question of SSP with stochastic costs: removing the extra $\sqrt{S}$ factor in the leading term.
The 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.

There 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?
2. the finite horizon algorithm seems to be a simple extension of EULER [Zanette and Brunskill, 2019], thus has limited novelty.

Overall, I think the problem studied in this paper is important and the results are complete. Thus, I think it is an acceptable submission.

**Questions**
1. Can the proposed method be directly extended to linear function approximation?
2. 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}$?

**Reference**

[Zanette and Brunskill, 2019]: Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
limitations_and_societal_impact: This work is mainly theoretically and has no foreseeable societal impact.
review_title: null

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)