Venue: NeurIPS 2021 Conference

Reviews:

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

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

The paper is written and organized very well, and almost, typo-free. It admits a clear and precise presentation and is overall a nice read. 

Despite these strengths, I have some concerns detailed below:

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

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

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

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

Some minor comments follow. 

Line 474: $\tilde s_0$ ---- > $\tilde s_{\mathrm{init}}$ 

Line 879: Taking … initiate ---- > … initiates 

Line 140: after-state ---- > the term “next-state” seems to be more common in the literature. 

Line 271: two parameter ---- > two parameters 

limitations_and_societal_impact: Please pay attention to my detailed comments above.
review_title: null

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

The 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. 
The 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?). 

First, 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. 
While 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)? 
The 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? 

Second, 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. 

Minor 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).
limitations_and_societal_impact: Yes
review_title: null

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

However, 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.

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

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

Additional concerns:
1.  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} $?

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

3. Recent SSP papers did not assume deterministic cost function. I think this paper should address stochastic cost function explicitly to match them.

Post-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.
limitations_and_societal_impact: yes
review_title: null

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

Quality: The technical part of the paper looks correct.

Clarity: The paper is very clearly written and the idea is well presented.

Significance: 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.
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.
review_title: null

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)