Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper investigates the problem of regret minimization of the stochastic shortest path, which is actively studied in the recent two years. The main contribution is a novel algorithm that enjoys nearly minimax optimal regret, matching the existing lower bound up to some log factors. Furthermore, the algorithm, as well as its variant, enjoy other desired properties, including parameter-free (does not require the knowledge of $B_\star$ or $T_\star$) and horizon-free (does not depend on $T_\star$)
main_review: post rebuttal: I am fine with the authors' rebuttal and keep my score as it is.

===================

This paper investigates an important problem in modern RL theory -- regret minimization for the stochastic shortest path. The problem itself is actively studied in the recent two years. The recent work [Rosenberg et al., 2020] gives a nearly optimal regret bound for this problem, yet the algorithm requires an unknown parameter $B_\star$ and also suffers from a $\sqrt{S}$ suboptimality gap. The paper resolves the two issues by proposing some interesting ideas. From my point of view, the paper is of high quality and the overall presentation is good to follow. I would be happy to recommend the acceptance. Several comments are listed below for the authors' further clarification.

(1) The idea of skewed transition probability is very interesting. As stated in the paper (Line 208), such a skewing guarantees that all policies are proper in the policy class. It would be appreciated if the authors can provide more specific explanations for this argument. In addition, I found the trick related to the recent work on adversarial SSP [Chen et al. 2021], in which the authors use a skewed occupancy measure space. It would be interesting to have some discussions.

(2) The parameter-free part is another important contribution of this paper. However, I have to say that the presentation in the main paper is too thin to understand... (due to page constraints). I remember that there will be an extra page in the camera-ready stage, so the authors are encouraged to add more details, especially about the two-phase adaptation, once got accepted. Furthermore, I am curious that whether a two-layer method could be useful for eliminating the unknown $B_\star$? The paper [Chen et al. 2021] uses such a mechanism (with multi-scale experts) to remove the prior knowledge of $T_\star$. I would be happy to see some discussions on this point.

(3) The "horizon-free" claim, in my opinion, is not quite strong. In particular, as stated in the table, when achieving minimax optimal and parameter-free, there is actually a factual dependence on $T_\star$. I would suggest less emphasis in this regard.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work studies the problem of learning stochastic shortest path (SSP) with unknown transition. The authors propose a model-based parameter-free algorithm EB-SSP which achieves the minimax regret rate O(B sqrt(SAK)), where B is the expected cumulative cost of the optimal policy, without prior knowledge of B or T (the expected time-to-goal of the optimal policy). The authors further consider several cases where the regret only has a logarithmic dependence on T. 
main_review: 1. Contribution

To the best of my knowledge, EB-SSP is the first parameter-free algorithm that achieves O(B sqrt(SAK)) regret. This algorithm is designed upon recent advances in episodic MDPs (e.g. Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019) and specifically the Bernstein-type exploration bonus. Importantly, the author adopts the idea of the MVP algorithm of Zhang et al. (2020a) to preserve the monotonicity property of Bellman update, which helps achieve tighter regret bounds. Besides, by slightly biasing the empirical transitions, the algorithm ensures that all induced polices are proper with contributing to a lower order extra term. Such technique is widely used in many tasks.  

On the other hand, the discussion of various cases is meaningful and inspiring. 

2. Weaknesses

Despite the algorithm efficiency, I haven't found any specific weak points of this paper.
limitations_and_societal_impact: This work is pure theoretical and does not have any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper develop an algorithm that achieves minimax optimal regret for SSP with stochastic costs. Notably, the algorithm is completely parameter-free, and also horizon-free (logarithmic dependency on $T_{\star}$ even in the lower order term). 
main_review: This paper resolves an important problems in SSP with stochastic costs: removing the extra $\sqrt{S}$ factor in the leading term. What's even more exciting is that they push $1/c_{\min}$ dependency into log terms. This is a very strong result, as $1/c_{\min}$ can be arbitrarily large in SSP and can only be handled by perturbation, in which case most of algorithms end up with sub-optimal regret bound. Thanks to the strong result, the upper bound $B$ can be as large as $O(\sqrt{K})$, making it easy to achieve parameter-free.
The paper is also well written and easy to follow. I appreciate author's effort on carefully discussing each scenario and the consequent regret bound.

The only short shortcoming is that the horizon-free analysis seems to be directly adopted from Zhang et al. [2020a], thus has limited novelty. However, the result of this paper is quite exciting and complete, and I suggest accepting this paper.

Questions:
1. Is the perturbation on transition really necessary? It seems to be an artifact of analysis.
2. Can the algorithm be extended to linear function approximation?
limitations_and_societal_impact: This work is mainly theoretically and has no foreseeable societal impact.
review_title: null

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

The results of this paper are very impressive. 
It gives the first parameter-free algorithm that is able to achieve minimax optimal regret, compared to Rosenberg et al. (2020) which is parameter-free but is not minimax optimal (extra $\sqrt{B^* S} $)  and compared to Cohen et al. (2021) that is minimax optimal but needs to know $T^*$ and $B^*$.
Moreover, the algorithm enjoys graceful dependence on $T^*$ (i.e., logarithmic in some cases) compared to polynomial dependence in previous work.

Against:

My main concern with this paper is that it is not written in a way that lets readers understand the theoretical analysis of the algorithm.
I think that this paper does a great job presenting the problem, related work, algorithm (including algorithmic novelties) and main results. However, the analysis and the proof techniques are almost non-existent in the main paper and do not focus on the new technical contributions of the paper. Therefore, I think that the chance that a reader could learn these contributions and that they will affect future work is very limited. Moreover, it was very hard for me to follow the analysis in the appendix without the intuition that proof sketches are supposed to give (this is the reason why I cannot say with absolute certainty whether the proofs are correct). In my opinion this paper could have much more impact on the theoretical community (this is clearly a paper for this community),  if the authors clearly conveyed the main ideas behind the proofs and the intuition behind the analysis.

Specifically, I found the proof sketch of theorem 3 impossible to understand. It lists some facts (that  I could not combine into a proof) without giving a high level idea about what goes on in this proof. This especially goes for the techniques of Zhang et al. (2020a) - the authors do not explain what are those techniques, how they are used and what changes are needed so they work in SSP (and not finite-horizon).

To me it looks like some of the analysis sketch should have focused on properties (1) and (2) of the VISCO procedure. As the authors state, VISCO is the main contribution of this paper (and definitely the most interesting one) and these two properties are the essential components that make the analysis work. However, there is no sketch of this analysis and it is very hard to understand how these properties are proved and how they affect the analysis. 

Instead of the analysis, I think the authors put too much focus on the exact form of the regret bound in various cases, which I did not find useful. This goes especially for the "General Costs and Order-Accurate Estimate of $T^*$ Available" which diminishes from the importance of the algorithm's regret bound in my opinion, as it (kind of) eliminates the need to be parameter-free since there is an estimate of $T^*$, although the algorithm does not require this knowledge really. I think that the authors should put less emphasis on those cases, state the main theorem in corollary 6 and say how it is stronger if costs are positive or an estimate of $T^*$ is available.

A smaller concern is the computational complexity of the algorithm. While it is polynomial and this is clearly not the focus of the paper, I noticed that $\epsilon_{VI} $ grows linearly with the number of timesteps (right?) and that the VISCO operator is $(1 - \nu^2) $-contracting for $\nu$ which is the minimal transition probability to the goal of the skewed transition function. Doesn't this mean that each computation of the optimistic policy takes time polynomial in $K$ (since $\nu $ might be $1/K$)? This is quite problematic (and also appears in some optimistic algorithms for linear finite-horizon MDPs).
I wonder if the algorithm can be made more efficient at the expense of worse regret, by skewing the transitions by $1/\sqrt{n}$ or maybe something else. Do you think this is possible? If so, looks like a good discussion to add.
In general, I think that a discussion about the computational complexity is important so readers can understand that maybe improvements can be made there. This is kind of hidden right now and appears deep in the appendix.

Post rebuttal: I thank the authors for these clarifications, and hope that they will be incorporated into the camera-ready version. I am keeping my original positive score.
limitations_and_societal_impact: Yes.
review_title: null

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