Learning Stochastic Shortest Path with Linear Function Approximation
Authors: Yifei Min
Jiafan He
Tianhao Wang
Quanquan Gu
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
stochastic shortest path

Abstract: We study the stochastic shortest path (SSP) problem in reinforcement learning with linear function approximation, where the transition kernel is represented as a linear mixture of unknown models. We call this class of SSP problems as linear mixture SSP. We propose a novel algorithm for learning the linear mixture SSP, which can attain a $\tilde O(dB_{\star}^{1.5}\sqrt{K/c_{\min}})$ regret. Here $K$ is the number of episodes, $d$ is the dimension of the feature mapping in the mixture model, $B_{\star}$ bounds the expected cumulative cost of the optimal policy, and $c_{\min}>0$ is the lower bound of the cost function. Our algorithm also applies to the case when $c_{\min} = 0$, where a $\tilde O(K^{2/3})$ regret is guaranteed. To the best of our knowledge, this is the first algorithm with a sublinear regret guarantee for learning linear mixture SSP. In complement to the regret upper bounds, we also prove a lower bound of $\Omega(dB_{\star} \sqrt{K})$, which nearly matches our upper bound.

Under review as a conference paper at ICLR 2022
LEARNING STOCHASTIC SHORTEST PATH WITH LIN- EAR FUNCTION APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
We study the stochastic shortest path (SSP) problem in reinforcement learning with linear function approximation, where the transition kernel is represented as a linear mixture of unknown models. We call this class of SSP problems linear mixture SSP. We propose a novel algorithm for learning the linear mixture SSP, which can attain a ( /K/Cmin) regret. Here K is the number of episodes, d is the dimension of the feature mapping in the mixture model, B, bounds the expected cumulative cost of the optimal policy, and Cuin 0 is the lower bound of the cost function. Our algorithm also applies to the case when Cuin = O, where ((K2/3) regret is guaranteed. To the best of our knowledge, this is the first algorithm with a sublinear regret guarantee for learning linear mixture SSP. In complement the regret upper bounds, we also prove lower bound of LidB, VK), which nearly matches our upper bound.
INTRODUCTION
The Stochastic Shortest Path (SSP) model refers to type of reinforcement learning (RL) problems where an agent repeatedly interacts with a stochastic environment and aims to reach some specific goal state while minimizing the cumulative cost. Compared with other popular RL settings such as episodic and infinite-horizon Markov Decision Processes (MDPs). the horizon length in SSP is random, varies across different policies, and can potentially be infinite because the interaction only stops when arriving at the goal state. Therefore, the SSP model includes both episodic and infinite-horizon MDPs as special cases, and is comparably more general and of broader applicability, In particular, many goal-oriented real-world problems fit better into the SSP model, such as navigation and GO game (Andrychowicz et al., 2017: Nasiriany ct al., 2019).
In recent years, there emerges a line of works on developing efficient algorithms and the corresponding analyses for learning SSP. Most of them consider the episodic setting. where the interaction between
the agent and the environment proceeds in K episodes (Cohen et al., 2020; Tarbouriech et al., 2020a).
For tabular SSP models where the sizes of the action and state space are finite, Cohen et al. (2021)
developed finitehorizon reduction algorithm that achieves the minimax regret Ō (B. (AK)) where B. the largest expected cost of the optimal policy starting from any state, S is the number of states and A is the number of actions. In similar setting. Tarbouriech et al. (2021b) proposed the first algorithm that is minimax optimal, parameter-free and horizon-free at the same time. However, the algorithms mentioned above only apply to tabular SSP problems where the state and action space small. In order to deal with SSP problems with large state and action spaces, function approximation techniques (Yang & Wang, 2019; Jin et al., 2020; Jia et al., 2020; Zhou et al., 2021b; Wang et al., 2020b;a) are needed.
Following the recent line of work on basel-based reinforcement learning with linear function approximation (Modi et al., 2020; Jia et al., 2020, Ayoub et al., 2020; Zhou et al., 2021b), we consider a linear mixture SSP model, which extends the tabular SSP. More specifically, we assume that the transition probability is parametrized by (P(s'Is,a) a) (ø(s')s,, a)), 0*) for all triplet (s, s') e x A x S, where S is the state space and A is the action space. Here we assume that Φ E Rd is a known ternary feature mapping, and 0* Rdd is unknown model parameter vector that needs to be learned. Such a setting has been previously studied for episodic MDPs (Modi et al., 2020; Jia et al., 2020; Ayoub et al., 2020; Cai al., 2020) and infinite-horize discounted MDPs (Zhou et al., 2021b). Nevertheless, algorithms developed in these works do not apply to SSP since the horizon length is random mentioned above.

---

Under review as a conference paper at ICLR 2022
To tackle the challenge of varying horizon length, we propose model-based optimistic algorithm with linear function approximation, dubbed LEVIS, S, for learning the linear mixture SSP. At the core of our algorithm are confidence set of the model parameters and specially designed Extended Value Iteration (EVI) subroutine for computing the optimistic estimate of the value function, which logether guarantee that the algorithm will reach the goal state in every episode. Compared with the EVI subroutine developed for infinite-horizon discounted MDPs (Zhou et al., 2021b), we introduce shrinking factor q = 1/t in our EVI with & being the cumulative number of time steps, which guarantees the convergence of EVI. To compensate for the bias introduced by this shrinking factor, our algorithm performs lazy policy update, which triggered by the doubling of the time interval between two policy updates or the doubling of the determinant of the covariance matrix. With all these algorithmic designs, our algorithm is guaranteed to achieve O(dB, /K/Cmmi) regret when Cmin > O. To the best of our knowledge, this is the first algorithm that enjoys a sublinear regret for linear mixture SSP.
It is worth noting that a recent work by Vial et al. (2021) studied a different linear SSP model that is similar to linear MDPs (Yang & Wang, 2019; Jin et al., 2020), where both the underlying transition probability and cost function are lincar in known d-dimensional feature mapping sO E R ie., (Ps''|s s, a) = (z, a): (s))) and c(s, a) = (vb(s, a), 0), and (+)) and are unknown. They proposed an algorithm with linear function approximation, which achieves Ō( ( K/Cmiu) regret. The linear SSP model is different from our model, and we refer the interested readers Ayoub et al. (2020); Zhou et al. (2021b) for a detailed comparison between these two assumptions. Besides the model difference, Vial et al. (2021) further assumed the feature mapping to be orthonormal order to obtain the ( K) regret. We do not need such restrictive assumptions on the feature mapping, thus algorithm provably works for more general cases.
Our contributions are summarized as follows:
We propose to study a linear mixture SSP model, and devise a novel algorithm, dubbed Lower confidence Extended Value Iteration for SSP (LEVIS), for learning SSP with linear function approximation.
We prove that LEVIS achieves a regret of order Ō(B!. (allldd/K//mniii when Cmin > O and the agent has an arder-accurate estimate 2 B. For the general case where Gmin = 0, our algorithm can achieve ( regret guarantee by using a cost perturbation trick (Tarbouricch et al., 2021b).
We prove that for linear mixture SSP, the regret of any learning algorithms is at least R(d B.B... K). This suggests that when Cmin > 0, our algorithm is optimal with regard to the dimension of the feature mapping d and number of episodes K.
Notation We use lower case letters to denote scalars, and use lower and upper case bold face letters to denote vectors and matrices respectively. For any positive integer n, we denote by [n] the set [l...., For a vector x E Rd, we denote by ||x]] the Manhattan norm and denote by ||x la the Euclidean norm. For a vector E Rd and matrix Σ E Rdxd we define ||*||= vx Σx. For two sequences } and (bx), ), we write a, = (b,,) if there exists an absolute constant C' such that an < Cbn. We use Ó()) to hide the logarithmic factors.
2 RELATED WORK
Online learning in SSP SSP problems can be dated back to (Bertsekas & Tsitsiklis, 1991; Bertsekas & Yu, 2013; Bertsekas, 2012), but is until recently that the regret minimization in online learning of SSP has been studied. In the tabular case, Tarbouriech et al. (2020a) proposed the first algorithm achieving O 5 /AK/////aaaaa /KKCmmin) regret where D is the diameter of SSP2. The regret was further improved to Ö AK) by Rosenberg et al. (2020); Cohen et al. (2020), with an extra vs factor compared with the StB.. VSAK) lower bound (Rosenberg et al., 2020). More recently, the Ö(B. (B.) minimax optimal regret were obtained by Cohen et al. (2021) and Tarbouriech et al. (2020b) independently using different approaches. Specifically, Cohen et al. (2021) reduced SSP to finite-horizon MDP with a large terminal cost assuming B, is known; while Tarbouriech et al. (2021b) avoid such requirement by adaptively estimating B, with a doubling trick, together with
We say is an order-accurate estimate of B*, if there exists some unknown constant k 2 1 such that B. < B < KB.
The diameter an SSP is defined as the longest possible shortest path from any initial state to the goal state.
2

---

Under review as a conference paper at ICLR 2022
value iteration sub-routine ensuring the optimistic estimate of the value function. Our proposed method shares a similar spirit with the latter approach, but for learning SSP with linear function approximation.
The above algorithms are all model-based. Very recently, Chen et al. (2021a) developed the first model- free algorithm for SSP which achieves the minimax optimal regret when the minimum cost among all state-action pairs Cmin is strictly positive. Their method is motivated by the UCB- -CB-AAVANTAGE algorithm (Zhang et al., 2020). For other settings of SSP, (Rosenberg & Mansour, 2020; Chen & Luo, 2021; Chen et al., 2021b) studied the case of adversarial costs. Also, the pioneering work by (Bertsekas & Tsitsiklis, 1991) studied the pure planning problem in SSP where the agent has full knowledge of all the model parameters, and is followed by series of works (Bonet, 2007; Kolobov et al., 2011; Bertsekas & Yu, 2013; Guillot & Stauffer, 2020). On the other hand, Tarbouriech al. (2021a) studied the sample complexity of SSP assuming the access
generative model. Jafarnia-Jahna Jahromi el al. (2021) proposed the first posterior sampling algorithm for SSP, Multi Mulli-goal SSP have also been studied by Lim & Auer (2012); Tarbouriech et al. (2020b).
Linear function approximation Linear MDP is one of the most widely studied models for RL with linear function approximation, which assumes both the transition probability and reward functions are linear functions of known feature mapping (Yang & Wang, 2019; Jin et al., 2020). Representative work in this direction include Du et al. (2019) Zanette et al. (2020); Wang et al. (2020a); He et al. (2021), to mention a few.
Another popular model for RL with linear function approximation is the so-called linear mixture MDP/inear kernel MDP (Yang & Wang, 2020; Modi et al., 2020; Jia et al., 2020; Ayoub et al., 2020; Cai et al., 2020; Zhou et al., 202 lb:a). For the finite-horizon setting, Jia et al. (2020) proposed UCRL-VTR algorithm that achieves (dd HHT) regret bound. Zhou al. (2021a) further improve the result by proposing a UCRL-VTR+ algorithm that attains the nearly minimax optimal regrel O(dH based on novel Bernstein-type concentration inequality. For the discounted infinite horizon setting, Zhou et al. (2021b) proposed UCLK algorithm with OldvT/( 7)²² regret, and also give a (dvTT/(
7)1..5) lower bound. The lower bound is later matched up to logarithmic factors by the UCLK+ algorithm (Zhou et al., 2021a). The SSP model studied in this paper can be seen as an extension of linear mixture MDPs.
PRELIMINARIES
Stochastic Shortest Path An SSP instance is an MDP M AS C, Sim, g}. where and A :
the finite state space and action space respectively. Here Sint denotes the initial state and g S is the goal state. We denote the cost function by c: S x A > [0, 1]. where c(s, a) is the immediate cost of taking action a at state s. The goal state g incurs zero cost, i.e., <gg,a) = 0 for all
A. For any (s', a) E S x A x S, PP(s'|s, |s, a) is the probability to transition to s' given the current state s and action a being taken. The goal state g is an absorbing state, i.e., P(ggg. (ggllg.0o a) = 1 for all action a E A.
Linear mixture SSP In this work, we assume the transition probability function IP to be linear mixture of some basis kernels (Modi et al., 2020; Ayoub et al., 2020; Zhou et al., 2021a).
Assumption 3.1. Suppose the feature mapping & S x A x S Rd is known and pregiven. There exists an unknown vector 0 E Rd with ||0_||2 I d such that (P(s'] Is, a) (Ø(5')s, a), 0*) for any state-action-state triplet (s, a, s') E S x A x S. Moreover, for any bounded function V S B). it holds that (s a)lla S B for all (s. E S A, where Φv (s,a) = Eves a))
For simplicity, for any function V S + R, we denote PV a) = E. ((55'ss for all (s, a) E S A. Therefore, under Assumption 3.1, we have
(s,(s,)) a) = e'ES
= [( V'') = (Øv (s, a),
S'CS
Proper policies A stationary and deterministic policy is mapping म S + A such that the action (s) is taken given the current state s. We denote by (T) the expected time that it takes by following и to reach the goal state starting from s. We say a policy is proper if T (s) oo for any E S (otherwise it is improper). We denote by Iproper the set of all stationary, deterministic and proper policies. We assume that Hpraper is non-empty. which is the common assumption in previous works on online learning of SSP (Rosenberg et al., 2020; Rosenberg & Mansour, 2020; Cohen et al., 2021; Tarbouriech et al., 2021b; Jafarnia-Jahromi et al., 2021; Chen al., 2021a).
3

---

Under review as a conference paper at ICLR 2022
Assumption 3.2. The set of all stationary, deterministic and proper policies is non-emply, i.c. Iepopee # Ø.
Remark 3.3. The above assumption is weaker than Assumption 1 in Vial et al. (2021) which requires that all stationary policies are proper.
For any policy n, define the cost-to-go function (a.k.a., value function) as
A (s) lim E T +00+0
Σ c(s n (s:)) 81 where St+1 ~ P( |st, ((s)))
(s) can possibly be infinite if क is improper. The action-value function of policy it is defined as
(s),aa) = lim E T
(1) +
Σ cla, 1 (st)) 81 s, 01 =
where $2 ~ P(--1s,, a1) and S ~ P( (se)) for all 2 2. Since o(.,) c [0, 11, for any proper
policy и E Ipppper. V and Q" are both bounded functions.
Bellman optimality For any function : S R. we define the optimal Bellman operator L as
CV(s) 1ii-mii(((sss + a)),
(3.1)
aFA
Intuitively speaking, we want to learn the optimal policy x² such that V+()== == V (.) is the unique solution to the Bellman optimality equation V LV and x² minimizes the value function V (s)
component-wise over all policies. It is known that, in order for such n² to exist, one sufficient condition is Assumption 3.2 together with an extra condition that any improper policy has at least one infinite-value statc, i.c., for any π & II properr. there exists some E S s.t. (T)s) too (Bertsekas Tsitsiklis, 1991; Bertsekas additional condition is satisfied in the case of strictly positive cost, where for any state 8 * g and E A, it holds that c(s, a) 2 Cmin- To deal with the case of general cost function, one can adopt the cost perturbation trick (Tarbouriech et al., 202 and consider a modified problem with cost function (p(s, a)= == max(c( (c(s, a), p} for some p > This will introduce an additional cost of order (pT)) to the regret of the original problem, where T is the total number of steps. Therefore, the second condition can be avoided, and we can assume the existence of π..
Yu. 2013; Tarbouriech et al., 2021b). Note that this
Throughout the paper, we denote by B, the upper bound of the optimal value function V i.e., B. := m (s). Also, we define T. = max,es T (s), which is finite under Assumption 3.2. Since the cost is bounded by 1, we have B. < T. < toc. Without loss of generality, we assume that B. > 1. Furthermore, we denote the corresponding optimal action-value function by Q* = = which satisfies the following Bellman equation for all (s, a) S A:
Q*(s,, a) = c(s,a) + PV (s, a), V*(s) min (s, aE
(3.2)
Learning objective Under Assumption 3.1. assume to be known for the case of presentation. We study the episodic setting where each episode starts from a fixed initial state Sinit and ends only the agent reaches the goal state g. Given the total number of episodes, K, the objective of the agent is to minimize the regret over K episodes defined as
Ia CK.i
RK Σ
K V (Sintt)
(3.3)
A=1i-1
where Is is the length of the k-th episode and Ck.s c(SR.is (x,s) is the cost triggered at the i-th step during the k-th episode. Note that Rx might be infinite if some episode never ends.
4 ALGORITHMS
In this section, we propose model-based algorithm named LEVIS, as displayed in Algorithm 1. LEVIS is inspired by the UCLK-type of algorithms originally designed for discounted linear mixture MDPs (Zhou et al., 2021a;b). Our algorithm takes a multi-epoch form, where each episode is divided into epuchs of different lengths (Jaksch et al., 2010; Lattimore & Hutter, 2012). Within each epoch, the agent executes the greedy policy induced by some optimistic estimator of the optimal Q-function. The switch between any two epochs is triggered by doubling criterion, and then the estimated Q-function is updated through an Extend Value Iteration (EVI) sub-routine (Algorithm 2). We now give detailed description of Algorithm 1.
4

---

Under review as a conference paper at ICLR 2022
Algorithm LEVIS
1: Input: regularization parameter X, confidence radius {Bt). cost perturbation p [0, 1}, an estimate B 2 В*
2: Initialize: set t- 1, 0, 0, Eo < XI, < o, Qo(s,)) Vo(s) Vs * g and otherwise
3: for k ,...,, K do
4: Sct St - 8mil
5: while 8t + do
6:
Take action
argminac (s, a), receive cost c(s,, az) and next state 8
P(-|s1, az)
7:
Set E, E + Φv, (st, at He, (st, az)
8:
Set b, t- bi-1 + Φv, (st, at) ( ($(+1)
9:
if ( 2 2det(22)
ort 2 2t, then
10:
Set j t --+1 Sett t, 2
11:
1
0, E,'b,
Set confidence set Cj 00: (0-))(1 s 3,,}
14:
Set Q,(,)) + EV, E3 1, :))
15:
Set Vy(.) + min.ed (,(:a)
16:
end
17: Set t +- ++1
18: end while
19:
end for
Algorithm EVI
1: Input: confidence set C, error parameter e, transition bonus y, cost perturbation p E [0, 1]
2: Initialize: <- and (())) (,,), (.) O, and V-- +o0
3: Set ();))) + (.))
4: if B A o then
5: while [V()) v(i 1100 2 do
6:
(.++))(.))) + (.( + g))-
min (0, (vo(),))
(4.1)
eccns
v(it1)()
+ min Q (6+1))..))
(4.2)
aEA
7:
Set i k- i
8:
end while
9: ((:)) Q (.+))
10: end if
Output: Q(:-))
In Algorithm 1, we maintain two global indices. Index t represents the total number of steps, and EVI sub-routine, where the output of EVI is an updated
index j tracks the number of calls optimistic estimator of the optimal action-value function. Each episode starts from a fixed initial state Smit (Line 4), ends when the goal state g is reached (Line 5) and is decomposed into epochs indexed by the global index Within epoch the agent repeatedly executes the policy induced by the current estimation Q, of the action-value function (Line 6) and updates Σ, and by (Lines and 8). The current epoch ends when the either criterion in Line 9 is triggered, and the EVI subroutine performs an optimistic planning to update the action-value function estimator (Lines 10 to 15).
Update criteria As mentioned before, Algorithm runs in epochs indexed by j. and one epoch ends when either of the two update criteria is triggered (Line 9). The first updating criterion is satisfied once the determinant of Σ, is doubled compared the determinant the end of the previous epoch. This
5

---

Under review as a conference paper at ICLR 2022
is called lazy policy update that has been used in the linear bandits and RL literature (Abbasi- Yadkori et al., 2011; Zhou et al., 2021b), which reflects the diminishing return of learning the underlying transition. One intuition behind the determinant doubling criterion is that the determinant can be viewed as a surrogate measure of the exploration in the feature space. Thus, one only updates the policy when there is enough exploration being made since last update. Moreover, this update criterion reduces the computational cost as the total number of epochs would be bounded by O'log T'. Here T denotes the total number of steps through all K episodes. The doubling visitation criterion used in tabular SSP (Jafarnia-Jahrone et al., 2021; Tarbouriech et al., 2021b) can be viewed as a special case criterion.
of this doubling determinant-
However, the above criterion alone cannot guarantee finite length for each epoch as we do not have that || ( -II is bounded from below, which holds for tabular SSP naturally since at most |S ||A| max.cs, nsss, a) steps suffice to double na(s, a) for at least pair of s, by the pigeonhole principle. To address this problem, we show that we only need to add an extra triggering criterion: t 2 2t.. It turns out that despite of being extremely simple this criterion endows the algorithm with several nice propertics. First, together with the EVI error parameter Ej - 1/tt.. wc can bound the cumulative error from value iterations in epoch by a constant, i.e., (2t, - [z) Cj = 1. Second, it will not increase the total number of epochs since the time step doubling can happen at most (log T) times, which consistent with the first criterion. These two properties together allow us to bound the lotal error from value iteration by (log 7'. Finally, this criterion is fairly easy to implement and has negligible time and space complexity.
Optimistic planning The optimism of Algorithm 1 is realized by the construction of the confidence set C, (Line 11). which fed into the EVI subroutine. We now describe the construction of the Q-function estimator in the EVI sub-routine (Algorithm 2). EVI requires the access to a confidence ellipsoid C, that contains the true model parameter 0* with high probability (Line 13). Here we construct the confidence set Cj centered at the minimizer of the ridge regression problem with confidence radius parameter Br (Line 13). Since not every O E C, defines a valid transition probability function, we further take the intersection between C, and constraint set B defined as follows
B = {0: De<Vss, a), (0(-)s, a), 0) is a probability distribution and (Ø(s'lg. a). 0) 1fs' g]}
Then C, n B is still a confidence set containing the true model parameter 0" with high probability as Or E B. Algorithm requires two additional inputs: optimality gap Ej and discount factor q. The use of is standard, but this discount factor is the key to ensuring convergence of EVI.
Specifically, (4.1) in Algorithm repeatedly conducts one-step value iteration by applying the best possible Bellman operator to the set C, n B. This is motivated by the Bcllman optimality equation in (3.2), and uses mingecrg )v as an optimistic estimate for PVV". However, using this estimate alone cannot guarantee the convergence of EVI because (., Φvco) ) is not contractive map. which al., 2010: Zhou et al., 2021b), but not in SSP.
holds for free in the discounted setting (Jaksch More specifically, in the EVT algorithm for the discounted setting (e.g., Algorithm 2 in (Zhou et al., 2021b)), there is an intrinsic discount factor 0 < 7 < 1, which ensures that the Bellman operator is a contraction. As a result, the value iteration converges in finite number of iterations. However, the Bellman equation of SSP docs not have a discount factor. To address this issue, in (4.1), we introduce an extra 1 yf discount factor ensure the contraction property. Although this causes an additional bias to the estimated transition probability function, we can alleviate it by choosing & properly. In particular, for each epoch j we set q 1/t, (Line 14), and as will be shown, this bias will only introduce an additive term of order Ollog T') in the final regret bound.
Besides the convergence guarantee, the g factor also brings an additional benefit that it biases the estimated transition kernel towards the goal state g, further encouraging optimism. Similar design can also be found in the VISGO value iteration algorithm used by Tarbouricch et al. (2021b). The intuition behind such a design is to ensure the existence of proper policies under the estimated transition probability function. As result, the ouiput of the value iteration, which solves V LV approximately for the Bellman operator L induced by the estimated transition, can induce greedy policy that is proper under the estimated transition.
Regarding the implementation of LEVIS, S, note that the main computational overhead is from EVI, where within each inner iteration we need to solve an optimization problem. Fortunately, the loss function is strongly convex, thus it can be efficiently solved by many convex optimization algorithms.
6

---

Under review as a conference paper at ICLR 2022
5
MAIN RESULTS
In this section, we present the main theoretical results for Algorithm 1. We provide regret upper bounds for both positive cost functions and general cost functions, followed by lower bound.
5.1 UPPER BOUNDS: POSITIVE CoST FUNCTIONS
We first consider a special case where the cost is strictly positive (except for the goal state g). Assumption 5.1. There exists unknown constant Cmin (0, 1) such that c(s, a) Cmin for all 8 E S {g) and a E .A
Let T the total number of steps in Algorithm I, then the above assumption allows us to lower bound the total cumulative cost after the K episodes by Gmin '. Note that this provides a relation between the deterministic K and the random quantity T. To simplify the expression, we assume the agent has access to B, order-accurate estimate of B, satisfying B. < B s <B, for some unknown constant K 2 1. Similar assumptions have also been imposed in previous works (Tarbouricch et al., 2021b; Vial al., 2021).
Theorem 5.2. Under Assumptions 3.1, 3.2 and 5.1, for any > 0, let = O and 3r = for all 2 1, where B 2 B, and X 2 1. Then with probability
B Byd log (4(12 + 13 /A) + V
least 1 8, the regret of Algorithm satisfies
KBd
B2d
KBd
RK = 0 Bl. dv K/Cmin log²
log
(5.1)
C
Canin
Crin
B O(B.), Algorithm 1 attains an Ö(B, 1.5 d. K/Cmiu) regret. The dominating term in (5.1) has an dependency on 1/Cmin- For the tabular SSP, Cohen et al. (2021): Jafarnia-Jahromi et al. (2021); Tarbouriech et al. (2021b) avoid such dependency by using a Bernstein-tyree confidence set. However, it remains an open question whether similar result can be achieved under the linear function approximation setting.
Remark 5.3. If we set the parameter 5 in Theorem 5.2 as 5 1/K and define the high probability event Ω as Theorem 5.2 holds. Then, for the expected regret, we have
E[Rx] - E Rx
[S]] Pr(St] KPr(S2]
KBd
B
KBd
0 B d. K/Cmin log"
log²
Cmin
Cunn
Cunin
which implies Ö(B." 1.5dd/ (K/Cmi)) expected regret.
5.2 UPPER BOUND: GENERAL COST FUNCTIONS
When Assumption 5.1 does not hold, an (K333) regret can be achieved by running Algorithm K-1/33
with
Theorem 5.4. Under Assumptions 3.1 and 3.2, for any > 0, let p = K-1/3 and 3, =
B By log (4(t2 + B²B2/))88) + vdd for all 2 1, where B > B. and > 1. Then with probability at least 1 6, the regret of Algorithm satisfies
Rx O 5 2/3 2/3
+ + B .x)x.
where B B T.-KT.KK T./K and x log² (BB (B/).)
In Theorem 5.4, the regret depends on B instead of B. Note that B is approximately equal to B. when (TT)) and = O(B).. Here T, is defined Section 3 as the maximum expected time it takes for the optimal policy to reach the goal state starting from any state.
The cost perturbation is common trick to deal with the case of general cost functions in the SSP literature (Tarbouriech et al., 2020a; Cohen al., 2020: Tarbouriech et al., 2021b). Similar to Tarbouriech et al. (2020a), the term Cmin is multplicative with K in our regret bound given by
Theorem 5.2. As result, the perturbation can only give ((K2/33 regret in the case of general cost functions. Similarly, the regret bound of learning linear SSP (Vial et al., 2021) also has a multiplicative Cmin Some later work labular SSP (Cohen et al., 2020; Tarbouricch al., 2021b) has shown that possible make the term e additive instead of multiplication, which improves the regret to (1112) for general cost functions. How to get an additive c term in the linear function approximation setting is interesting future direction.
7

---

Under review as a conference paper at ICLR 2022
For the choice of the other parameters in Algorithm 1, by Theorems 5.2 and 5.4, in both the positive and general cost cases. For the upper bound B 2 B., note that assuming a known B is common existing SSP literature (Cohen al., 2021; Vial et al., 2021). Although is possible to deal with an unknown B in the tabular SSP with a doubling trick (Rosenberg et al., 2020; Tarbouriech et al., 2021b), it remains an open question for SSP with linear function approximation.
set À = 1
5.3 LOWER BOUND
We also provide a hardness result for learning linear mixture SSP by proving the lower bound for the expected regret suffered by any deterministic learning algorithms.
Theorem 5.5. Under Assumption 3.1, suppose d 2 2, B. 2 2 and K > (d - 1)3/2 Then for any possibly non-stationary history-dependent policy и, there exists linear mixture SSP instance with parameter 0 such that
dB.vK
0- [Rx] Z
(5.2)
1024
Remark 5.6. The expectation in (5.2) is over the trajectories induced by executing the policy π in the SSP environment parameterized by 0 Note that here we allow the policy и to be non-stationary and history-dependent This is equivalent assuming deterministic learning algorithm, which is sufficient for establishing a lower bound (Cohen et al., 2020).
Remark 5.7. Our instance for the lower bound can be also adapted to a linear SSP instance (Vial ct al., 2021), which yiclds (d K) lower bound. (Sce Remark E.1 for detailed discussion.)
6 PROOF SKETCH OF THE MAIN RESULTS
In this section, we give proof sketch of the main results in Section 5. Due to space limit, we defer the proof the lemmas to the appendix.
1 PROOF OF THEOREM 5.2
In this subsection, we prove Theorem 5.2, which gives the regret upper bound of Algorithm I for positive cost functions. The proof relies on the following intermediate result.
Theorem 6,1. Under Assumption 3.1 and 3.2, for any > 0, let p = 0 and 3 =
B Bydlog (4(t² + BAA//8) + vAd for some B > B. where A > 1 and p 0. Then with probability least 1 6, the regret of Algorithm satisfies
TB2 X
T B2d
R S 63T
dT 1+
+ 7d log
where 7' is the total number of steps.
Remark 6.2. Theorem 6.1 gives an Õ(VT) regret upper bound with respect to the total number of steps T. However, for SSP problems, the horizon of each episode is unknown and T can be far greater than K. Thus, Theorem 6. is not satisfactory due to its dependence on T. To deal with this problem, further prove Thcorem 5.2, which translates the dependence on T into the dependence on K but has a worse dependence on the dimension d and other logarithmic factors.
Theorem 6.1 applies the general cost function with set to O. Note that the regret upper bound depends on the total number of time steps T, which is random. To replace the T T-dependence by the
K de-eeendencee it suffices to show that T = Ō(K) As mentioned in Section 5.1, this can be easily derived under Assumption 5.1. We are now ready to prove Theorem 5.2.
Proof of Theurem 5.2. The total cost in K episodes is upper bound by RK + K B, and is lower bounded by T Cmin- Together with Thcorem 6.1, with probability at least - ō, we have
T Cmin S 6Br aT log (1 11+ TB² + 7d., log T+
T Bed
K KB,
X
A
Solving the above inequality for the total number of steps T, we obtain that
T= o log" (
KB.
B2d²)
Cmin
Suin
Plugging this into Theorem 6.1 yields the desired result. Note that for the general cost functions, by simply picking K-1/3 the result immediately follows from the case of positive costs, which is summarized in Theorem 5.4.
8

---

Under review as a conference paper at ICLR 2022
6.2 PROOF SKETCH OF THEOREM 6.1
The main steps in proving Theorem 6. include an analysis of EVI and a regret decomposition. The complete proof can be found in Appendix D.
Analysis of EVI. By the algorithmic design we elaborated in Section EVI guarantees optimism and finite-time time convergence, which is summarized in Lemma 6.3 below.
Lemma 6.3. Let p and 3 B B dog (4(t² 1 /²2//) vtd for all 2 1, where B 2 B, Then with probability at least 5/2, for all j 2 EVI converges in finite time and the following holds
0r C
0 (5())) (*)))) and 0 (3)()s
Note that in Lemma 6.3 the optimism only holds for the EVI output, i.e., V, for any j 2 1. The initialization Vo Line 2 of the main Algorithm does not necessarily satisfy the optimism since it possible that (s) < for some s. Still, such an initialization guarantees ||Vol| = B., which crucial for establishing the optimism for j 2 The proof of Lemma 6.3 is given in Appendix F.I.
Regret Decomposition. In our analysis, instead of dealing with (3.3) directly, we first implicitly decompose the times steps into intervals, which are indexed by m 1,..., M in Lemma 6.4 below. The basic idea here is to decompose all the time sleps inlo disjoint intervals of which the end points are either the end of an episode or the time steps when the EVI subroutine triggered 3, The purpose of such regret decomposition is to guarantee that within each interval the optimistic action-value function remains the same, so the induced policy. This is a necessary and common requirement and can be found in the case of discounted infinite horizon MDPs (Zhou et al., 2021b). Similar decomposition trick has also been used in existing works on SSP (Rosenberg et al., 2020; Rosenberg & Mansour, 2020; Tarbouriech et al., 2021b).
Lemma 6.4. Assume the event in Lemma 6.3 holds, then have the following upper bound for the regret defined in (3.3)** 4:
R(M)= < E mm
Hm
Cm.h h + PV ((m))(sn (Sm, km.)) ((() (8m,
M m=1
Hm Di ((mm)((mmmtt)) (5m, PV)(()) (V) (sm,h am,,h))
(6.1)
2dB, log 1 TBdd 2B, log(T) +
Bounding E and Eg We bound the terms E1 and Es separately. Note that Eg is the sum of a martingale difference sequence, and can be bounded by O O(vTlog(T/8)) using standard concentration. Bounding E, is more technical and it requires almost all the properties of our algorithmic design. In detail, we need to show that every time when EVI is triggered, it can output an optimistic action-value function estimator with high probability (by Lemma 6.3). Second, we need to bound the total difference between the estimated functions and the optimal action-value function. This follows from the elliptical potential lemma and the determinant-basee need to bound the length of the epochs (i.e., the number of time steps between two EVIs). which is achieved by the time-step doubling criterion as explained in Section 4.
doubling criterion. Third,
7 CONCLUSIONS
In this paper, we proposed novel algorithm for linear mixture SSP and proved its regret upper and lower bounds. For future work, there are several important directions. First, there is B gap between the current upper and lower bounds. We believe this gap can be closed by using a Bernstein-type of confidence set (Zhou et al., 2021a). Second, it remains open to prove (VKK regret bound for linear mixture SSPs for general cost functions when Gmin 0.
'The interval decomposition indexed by in Lemma 6.4. It is implicit and only for the purpose of analysis. This is different from the epoch decomposition, which explicit and indexed by j Algorithm 1. The difference is that an epoch ends when EVI is triggered, while an interval ends when either EVI is triggered or the goal state is reached (i.c., an episode ends).
RRM) is the same as Rg. We different notation emphasize the interval decomposition.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
We don't 't see any potential ethical issues in our work.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin. Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay, arXiv 2017.
preprint Xrviv
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume 1. Athena scientific, 2012.
Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595 1991.
Dimitri Bertsekas and Huizhen Yu. Stochastic shortest path problems under weak conditions. Lab. for Information and Decision Systems Report LIDS-P-2909, MIT, 2013.
Blai Bonet. On the speed of convergence of value iteration on stochastic thortest-path problems. Mathematics of Operations Research, 32(2):365-373, 2007.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- lion. In International Conference on Machine Learning. pp. 1283-12944 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.05284 2021.
Liyu Chen, Mehdi Jafarnia-lahromi, Rahul lain, and Haipeng Luo. Implicit finite-horizon approxima- tion and efficient optimal algorithms for stochastic shortest path. arXiv preprint arXiv:2106.08377, 2021a.
Liyu Chen, Haipeng Luo, and Chen Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference on Learning Theory, pp. 1180-1215. PMLR, 2021b.
Alon Cohen, Haim Kaplan, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret bounds for stochastic shortest path. arXiv preprint arXiv:2002. 09009, 2020.
Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path. arXiv preprint 2103: 2021.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2019.
Matthieu Guillot and Gautier Stauffer.
The stochastic shortest path problem: a polyhedral combina- torics perspective. European Journal of Operational Research, 285(1): 14881)):481188, 2020.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 4171-4180. PMLR, 2021.
Mehdi Jafarnia- Jahromi, Liyu Chen, Rahul Jain, and Haipeng Luo. Online learning for stochastic shortest path model via posterior sampling. anXiv preprint N10::2106.00335 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
10

---

Under review as a conference paper at ICLR 2022
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Andrey Kolobov, Mausam Mausam, Daniel Weld, and Hector Geffner. Heuristic search for generalized stochastic shortest path mdps. In Twenty-First International Conference on Automated Planning and Scheduling, 2011.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference on Algoritumic Learning Theory, pp. 320-334. Springer, 2012.
Shiau Hong Lim and Peter Auer. Autonomous exploration for navigating mdps. In Conference on Learning Theory, pp. 40-1. JMLR Workshop and Conference Proceedings, 2012.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Soroush Nasiriany, Vitchyr H Pong. Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. arXiv preprint arXiv: 19911.11455. 2019.
Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. arXiv preprint arXiv:2006. 11561, 2020.
Aviv Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pp. 1219. PMLR, 2020.
Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference Machine Learning, pp. 9428-9437. PMLR, 2020a.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Improved sample complexity for incremental autonomous exploration in mdps. In NeurIPS, 2020b.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Sample complexity bounds for stochastic shortest path with generative model. In Algorithmic Learning Theory, pp. 1157- 1178. PMLR, 2021a.
Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter- and towards horizon-free regret. arXiv preprint arXiv:2104.11 1166, 2021b.
Daniel Vial, Advait Parulekar, Sanjay Shakkottai, and Srikant. Regret bounds for stochastic shortest path problems with linear function approximation. arXiv preprini arXiv:2105.01593, 2021.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020a.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in rein- forcement learning with generalized linear function approximation. International Conference Learning Representations, 2020h.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
11

---

Under review as a conference paper at ICLR 2022
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020.
Zihan Zhang. Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantae decomposition. Advances in Neural Information Processing Systems, 33, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR, 202 la
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pp. 12793-12802. PMLR, 2021b.
12


Reviews:
[{"review_id": "szblWllF6Ei", "reviewer": "Reviewer_q9Tm", "summary": "", "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": "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.\n\nDetailed Comments:\n1. Algorithm: \n    1. The algorithm, LEVIS, is very simple, easy to follow and clean. \n    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.\n\n2. Proof Sketch\n    1. In my opinion, Proof of Theorem 5.2 is not insightful and probably should be moved to Appendix.\n    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).\n\n3. Minor Issues:\n    1. T is only explicitly defined in Section 5.1 but is used in Section 4.\n    2. Mapping j() is only defined in the appendix but is used in Equation 6.1.\n    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.\n\n4. Verified Proofs:\nI 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.\n\n    1. Lemma 6.3: Verified. \n    2. Lemma B.1: Verified.\n    3. Lemma B.2: Verified.\n    4. Lemma C.1: Verified. \n    5. Lemma C.2: Verified\n    6. Theorem 5.4: Skimmed at high level without verifying all steps. ", "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. \n\nAlgorithm: \nLEVIS 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.\n\nThis work has three contributions:\n1. New Setting and Algorithm: Introduces a new setting for SSP problem: linear mixture SSP problem and a novel algorithm LEVIS for this setting.\n2. 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})$.\n3. 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$.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "QwTA2TXa8J", "reviewer": "Reviewer_sn7Z", "summary": "", "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": "Strengths:\n\nThe paper is overall well written. The problem formulation and Assumptions are clearly presented. It is in general easy to follow the paper.\n\nThere is an extensive literature review and references to many related works on SSP and mixture models.\n\nThe formulation of the SSP problem under linear mixture models seems novel.\n\n\nWeaknesses:\n\nAlthough the paper is well written in general, there are places where the writing can improve:\n- 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\n-  The term action-value function is used for Q function, but later it is changed to Q function\n\nThe 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.\n\nI 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?\n\nIt seems that the bounds can still significantly improve.\n\n- 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.\n- As mentioned by the authors, standard Bernstein-type variation of confidence intervals can be used to further improve the regret bounds.  \n\n\n\n\n", "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\nmixture\" 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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Hzz4VfyyThL", "reviewer": "Reviewer_wXVK", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\n**Strengths.**\n\n  - 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. \n  - The overall presentation of this paper is great and the theoretical results appear to be sound and clear as far as I have checked.\n - The authors provide also a minimax lower bound which is very much appreciated. \n\n**Weaknesses.**\n\n  -  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.\n - 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?\n  - 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?\n  - 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_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})$.", "summary_of_the_review": "My recommendation of the paper is based on the following (more details in the main review):\n- (+) 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).\n- (-) 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. \n- (-) 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). \n- (-) 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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

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