Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work considers the stochastic shortest path (SSP) problem with linear function approximation. The authors propose an algorithm which they refer to as LEVIS, and provide a regret guarantee of order $R_K = O\left(\left(B^{1.5}d \sqrt{K/c_{\min}}  + \frac{B^2d^2}{c_{\min}} \right) \log^2(KBd/c_{\min}\delta) \right)$. The algorihtm relies on the principle of optimism in face of uncertainty. Finally, the authors also provide a minimax lower bound on the expected regret of order $\Omega(dB_\star \sqrt{K})$.
main_review: 
**Strengths.**

  - The problem of SSP with linear function approximation is a natural extension of the SSP problem in the tabular case and there is not much work on this. Therefore, I think it is interesting to study such a problem. 
  - The overall presentation of this paper is great and the theoretical results appear to be sound and clear as far as I have checked.
 - The authors provide also a minimax lower bound which is very much appreciated. 

**Weaknesses.**

  -  The analysis and technical tools used for sequential decision-making problems under the linear structure assumption are by now becoming quite standard. The current work applies such analysis and tools to the SSP problem in an immediate manner. Therefore, this work lacks in terms of originality and novelty. The authors discuss the use of Bernstein-type inequality for the tabular case. It would be a great addition if a bound similar in spirit could be derived for the linear case. Furthermore, perhaps the authors could also highlight the technical challenges arising in this setting.
 - The provided regret bounds appear to be loose than what one would expect.For example:  (i) the regret bound has a dependency of order $\log^2(KBd^2/\delta)$, while one would expect a dependency of order $\sqrt{\log(KBd^2/\delta)}$ (as in linear bandits for instance); (ii) The authors did not discuss the low order dependencies appearing in the additive term in the regret bound $ \frac{B^2d^2}{c_\min} \log2(KBd^2/\delta)$. I would be curious to know whether $d^2$ could be brought down to $d$ and whether the dependency on $c_{\min}$ could be avoided?
  - The proposed algorithm requires as input an upper bound $B$ on the unknown $B_\star$, and a regularisation parameter $\lambda$, and cost perturbation $\rho$. The authors do not discuss how these parameters should be chosen. More specifically, I am curious to know how should $B$ be chosen?
  - The authors provide an algorithm with a regret upper bound in high probability while the provided lower bound is for the expected regret. This is a standard practice in the literature but it remains an unsatisfactory presentation since one would hope to get a lower bound for regret in high probability. Perhaps the author could comment on this.
summary_of_the_review: My recommendation of the paper is based on the following (more details in the main review):
- (+) I appreciate such a study because there is a lack of existing work on SSP with linear function approximation as far as I can tell (except the work of Vial et al. 2021).
- (-) My first concern is that I do not see any novelty or significant contribution on the technical front. Most of the technical tools and ideas used are borrowed from prior work with minor changes. 
- (-) My second concern is that the obtained guarantee appears to have some loose dependencies on the problem parameters and confidence parameter $\delta$. A discussion on such dependencies is lacking, especially in the low-order terms appearing in the regret upper bound (Theorem 1). 
- (-) My third concern is that the proposed algorithm requires certain inputs which might rely on unknown quantities. The authors did not clarify how these inputs should be chosen.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the stochastic shortest path (SSP) problem, a particlar RL problem, where a cost function $c(s,a)$ is associated with a state-action pair. A cost-to-go (value function) is defined as the total expected cost of reaching a goal state from an initial state. Then an episodic regret is used to measure the performance. This framework seems to have been considered in several existing works including Cohen et al. (2021) and Tarbouriech et al. (2020b), in a tabular setting. This paper considers the SSP problem under a a "linear
mixture" model of the transition kernel. A model based algorithm is introduced using optimistic estimators of optimal Q function where the stimated Q function is updated through a subroutine called Extended Value Interation (EVI). Upper bounds and a lower bound on regret are proven. 
main_review: Strengths:

The paper is overall well written. The problem formulation and Assumptions are clearly presented. It is in general easy to follow the paper.

There is an extensive literature review and references to many related works on SSP and mixture models.

The formulation of the SSP problem under linear mixture models seems novel.


Weaknesses:

Although the paper is well written in general, there are places where the writing can improve:
- the rationale behind some steps borrowed from the existing work is not clear. I think some explanations can help the paper to be self-contained. For example the use of discount factor q in the bottom of page 6,  perturbation trick, the criteria of doubling determinant
-  The term action-value function is used for Q function, but later it is changed to Q function

The theoretical results (which is the main contribution of the paper as there are no experiments), although new, seem to be a natural mix of existing ideas. In fact the confidence intervals used for the linear mixture models seem to be the classic confidence ellipsoids first introduced in the context of linear bandits, which have been used in various linear bandit and RL problems. Overall, the algorithmic and analytical contributions seem to be adapting the results of (Zhou et al., 2021a;b) to the SSP setting. I am not certain if this constitutes a major contribution. I appreciate it if authors can provide more details on the challenges of their analysis beyond the existing work.

I am not familiar with the motivation behind assuming a linear mixture model. It seems to make more sense to mix random variables rather than distributions. As mentioned by authors, the mixture may not even be a distribution. Can authors comment on the motivation of this model?

It seems that the bounds can still significantly improve.

- Assuming a $c_{min}>0$ allows the assumption of $B=O(B^*)$. That trivially removes the dependence on the length of the episode. Please let me know if this is correct.
- As mentioned by the authors, standard Bernstein-type variation of confidence intervals can be used to further improve the regret bounds.  





summary_of_the_review: The authors consider SSP frameork under the linear mixture models (that is particular structure for the transition kernel). Adapting ideas from recent works on linear mixture modes in other settings to SSP setting, a model based algorithm is presented and its regret bounds are provided.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the linear mixture SSP problem, where the transition kernel is a mixture of unknown models. This paper builds on ideas from recent results in RL with linear function approximation and uses these to introduce a new setting: linear mixture SSP problem + new algorithm, LEVIS for this setting. 

Algorithm: 
LEVIS is similar to UCB/UCLK style algorithms, however instead of updating the policy every time, the updating is delayed/lazy until either the volume of the feature set (measured by the determinant) grows by a constant factor or a constant multiple of time passes. To update the policy, a subroutine EVI is used which is a slight variation of the optimistic planning. Here the optimistic Q function is multiplied by a $1 - 1/t < 1$ factor to ensure the contraction property while only adding a small additive bias.

This work has three contributions:
1. New Setting and Algorithm: Introduces a new setting for SSP problem: linear mixture SSP problem and a novel algorithm LEVIS for this setting.
2. Upper bound: Under assumption that cost is lower bounded by $c_{\textrm{min}}>0$, LEVIS achieves $O(B_*^{1.5} d \sqrt{K/c_{\textrm{min}}})$ regret. When $c_{\textrm{min}}=0$, a weaker bound is provided $O(K^{2/3})$.
3. Lower bound: Any algorithm for linear mixture SSP problem must have a regret at least $\Omega(d B_* \sqrt{K})$. This is optimal in factors of $d$ and $K$ when $c_{\textrm{min}}>0$.
main_review: This work is a nice extension of ideas from RL with linear function approximation to the SSP problem and provides a new setting + new algorithm with upper bound on regret and almost matching lower bounds in some settings.

Detailed Comments:
1. Algorithm: 
    1. The algorithm, LEVIS, is very simple, easy to follow and clean. 
    2. I especially liked the exposition in Section 4, which goes over the subtle details in the algorithm and places the contribution of the paper in relation to known works.

2. Proof Sketch
    1. In my opinion, Proof of Theorem 5.2 is not insightful and probably should be moved to Appendix.
    2. Instead, I think it will be useful to add more technical detail to paragraph about ``Bounding $E_1$ and $E_2$'' and defining the notation for this discussion. Especially, it will be useful to place the technical contribution of this paper in relation to known techniques like elliptical potential lemma (in more technical detail than Section 4).

3. Minor Issues:
    1. T is only explicitly defined in Section 5.1 but is used in Section 4.
    2. Mapping j() is only defined in the appendix but is used in Equation 6.1.
    3. In proof of lemma C.1, it will be useful to define $P_{m,h}$ under equation C.1, instead of defining it after its used later. But overall the proofs are very detailed.

4. Verified Proofs:
I tried to verify all the proofs. For some proofs, I only skimmed through the proof and followed the general steps, without verifying each step. Note that even when I state that I have verified a proof, it is still possible that I did not catch a subtle issue.

    1. Lemma 6.3: Verified. 
    2. Lemma B.1: Verified.
    3. Lemma B.2: Verified.
    4. Lemma C.1: Verified. 
    5. Lemma C.2: Verified
    6. Theorem 5.4: Skimmed at high level without verifying all steps. 
summary_of_the_review: I think overall this is a good paper building on ideas from RL with linear function approximation to SSP setting. There are subtle issues with extending these ideas to SSP which this paper resolves.
review_title: null

Meta-review: This paper studies the stochastic shortest path (SSP) problem with a linear approximation to the transition model. The authors propose a doubling algorithm for regret minimization in this setting and bound its regret. This is a theory paper with no experiments.

This paper received three borderline reviews. All reviewers agreed on its strengths and weaknesses during the discussion. The strengths are that the paper is well written and that the results are novel. The weaknesses are that the proposed solution is standard and analyzed using standard tools. The reviewers noted departures from the standard analyses but these seem to be minor technical issues. Therefore, although well executed, this paper lacks novelty. No reviewer argued for the acceptance of this paper and therefore it is rejected.
Decision: Reject