Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
Year: 2021

Abstract:
We introduce a generic template for developing regret minimization algorithms in the Stochastic Shortest Path (SSP) model, which achieves minimax optimal regret as long as certain properties are ensured. The key of our analysis is a new technique called implicit finite-horizon approximation, which approximates the SSP model by a finite-horizon counterpart only in the analysis without explicit implementation. Using this template, we develop two new algorithms: the first one is model-free (the first in the literature to our knowledge) and minimax optimal under strictly positive costs; the second one is model-based and minimax optimal even with zero-cost state-action pairs, matching the best existing result from [Tarbouriech et al., 2021b]. Importantly, both algorithms admit highly sparse updates, making them computationally more efficient than all existing algorithms. Moreover, both can be made completely parameter-free.

text: We introduce a generic template for developing regret minimization algorithms in the Stochastic Shortest Path (SSP) model, which achieves minimax optimal regret as long as certain properties are ensured. The key of our analysis is a new technique called implicit finite-horizon approximation, which approximates the SSP model by a finite-horizon counterpart only in the analysis without explicit implementation. Using this template, we develop two new algorithms: the first one is model-free (the first in the literature to our knowledge) and minimax optimal under strictly positive costs; the second one is model-based and minimax optimal even with zero-cost state-action pairs, matching the best existing result from [Tarbouriech et al., 2021b]. Importantly, both algorithms admit highly sparse updates, making them computationally more efficient than all existing algorithms. Moreover, both can be made completely parameter-free.

heading: 1 Introduction
text: We study the Stochastic Shortest Path (SSP) model, where an agent aims to reach a goal state with minimum cost in a stochastic environment. SSP is well-suited for modeling many real-world applications, such as robotic manipulation, car navigation, and others. Although it is widely studied empirically (e.g., [Andrychowicz et al., 2017, Nasiriany et al., 2019]) and in optimal control theory (e.g., [Bertsekas and Tsitsiklis, 1991, Bertsekas and Yu, 2013]), it has received less attention under the regret minimization setting where a learner needs to learn the environment and improve her policy on-the-fly through repeated interaction. Specifically, the problem proceeds in K episodes. In each episode, the learner starts at a fixed initial state, sequentially takes action, suffers some cost, and transits to the next state, until reaching a predefined goal state. The performance of the learner is measured by her regret, which is the difference between her total costs and that of the best policy.
Tarbouriech et al. [2020a] develop the first regret minimization algorithm for SSP with a regret bound of Õ(D3/2S √ AK/cmin), where D is the diameter, S is the number of states, A is the number of actions, and cmin is the minimum cost among all state-action pairs. Cohen et al. [2020] improve over their results and give a near optimal regret bound of Õ(B?S √ AK), where B? ≤ D is the largest expected cost of the optimal policy starting from any state. Even more recently, Cohen et al. [2021] achieve minimax regret of Õ(B? √ SAK) through a finite-horizon reduction technique, and concurrently Tarbouriech et al. [2021b] also propose minimax optimal and parameter-free algorithms. Notably, all existing algorithms are model-based with space complexity Ω(S2A). Moreover, they all
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
update the learner’s policy through full-planning (a term taken from [Efroni et al., 2019]), incurring a relatively high time complexity.
In this work, we further advance the state-of-the-art by proposing a generic template for regret minimization algorithms in SSP (Algorithm 1), which achieves minimax optimal regret as long as some properties are ensured. By instantiating our template differently, we make the following two key algorithmic contributions:
• In Section 4, we develop the first model-free SSP algorithm called LCB-ADVANTAGE-SSP (Algorithm 2). Similar to most model-free reinforcement learning algorithms, LCB-ADVANTAGESSP does not estimate the transition directly, enjoys a space complexity of Õ(SA), and also takes only O (1) time to update certain statistics in each step, making it a highly efficient algorithm. It achieves a regret bound of Õ(B? √ SAK + B5?S
2A/c4min), which is minimax optimal when cmin > 0. Moreover, it can be made parameter-free without worsening the regret bound.
• In Section 5, we develop another simple model-based algorithm called SVI-SSP (Algorithm 3), which achieves minimax regret Õ(B? √ SAK +B?S
2A) even when cmin = 0, matching the best existing result by Tarbouriech et al. [2021b].1 Notably, compared to their algorithm (as well as other model-based algorithms), SVI-SSP is computationally much more efficient since it updates each state-action pair only logarithmically many times, and each update only performs one-step planning (again, a term taken from [Efroni et al., 2019]) as opposed to full-planning (such as value iteration or extended value iteration); see more concrete time complexity comparisons in Section 5. SVI-SSP can also be made parameter-free following the idea of [Tarbouriech et al., 2021b].
We include a summary of regret bounds of all existing SSP algorithms as well as more complexity comparisons in Appendix A.
Techniques Our main technical contribution is a new analysis framework called implicit finitehorizon approximation (Section 3), which is the key to analyze algorithms developed from our template. The high level idea is to approximate an SSP instance by a finite-horizon counterpart. However, the approximation only happens in the analysis, a key difference compared to [Chen et al., 2021, Chen and Luo, 2021, Cohen et al., 2021] that explicitly implement such an approximation in their algorithms. As a result, our method not only avoids blowing up the space complexity by a factor of the horizon, but also allows one to derive a horizon-free regret bound (more explanation to follow).
In order to achieve the minimax optimal regret, our model-free algorithm LCB-ADVANTAGE-SSP uses a key variance reduction idea via a reference-advantage decomposition by [Zhang et al., 2020b]. However, crucial distinctions exist. For example, we update the reference value function more frequently instead of only one time, which helps reduce the sample complexity and improve the lower-order term in the regret bound. We also maintain an empirical upper bound on the value function in a doubling manner, which is the key to eventually make the algorithm parameter-free. On the other hand, for our model-based algorithm SVI-SSP, we adopt a special Bernstein-style bonus term and bound the learner’s total variance via recursion, taking inspiration from [Tarbouriech et al., 2021b, Zhang et al., 2020a].
Empirical Evaluation We support our theoretical findings with experiments in Appendix H. Our model-free algorithm demonstrates a better convergence rate compared to vanilla Q learning with naive -greedy exploration. Our model-based algorithm has competitive performance compared to other model-based algorithms, while spending the least amount of time in updates.
Related Work For a detailed comparison of existing results for the same problem, we refer the readers to [Tarbouriech et al., 2021b, Table 1] as well as our Table 1. There are also several works [Rosenberg and Mansour, 2020, Chen et al., 2021, Chen and Luo, 2021] that consider the even more challenging SSP setting where the cost function is decided by an adversary and can change over time. Apart from regret minimization, Tarbouriech et al. [2021a] study the sample complexity of SSP with a generative model; Lim and Auer [2012] and Tarbouriech et al. [2020b] investigate exploration problems involving multiple goal states (multi-goal SSP).
1Depending on the available prior knowledge, the final bounds achieved by SVI-SSP are slightly different, but they all match that of EB-SSP. See [Tarbouriech et al., 2021b, Table 1] for more details.
The special case of SSP with a fixed horizon has been studied extensively, for both stochastic costs (e.g., [Azar et al., 2017, Jin et al., 2018, Efroni et al., 2019, Zanette and Brunskill, 2019, Zhang et al., 2020a]) and adversarial costs (e.g., [Neu et al., 2012, Zimin and Neu, 2013, Rosenberg and Mansour, 2019, Jin et al., 2020]). Importantly, recent works [Wang et al., 2020, Zhang et al., 2020a] find that when the cost for each episode is at most a constant, it is in fact possible to obtain a regret bound with only logarithmic dependency on the horizon. Tarbouriech et al. [2021b] generalize this concept to SSP and define horizon-free regret as a bound with only logarithmic dependence on the expected hitting time of the optimal policy starting from any state (which is bounded by B?/cmin). They also propose the first algorithm with horizon-free regret for SSP, which is important for arguing minimax optimality even when cmin = 0. Notably, our model-based algorithm SVI-SSP also achieves horizon-free regret (but the model-free one does not).

heading: 2 Preliminaries
text: An SSP instance is defined by a Markov Decision Process (MDP) M = (S,A, sinit, g, c, P ), where S is the state space, A is the action space, sinit ∈ S is the initial state, and g /∈ S is the goal state. When taking action a in state s, the learner suffers a cost drawn in an i.i.d manner from an unknown distribution with mean c(s, a) ∈ [0, 1] and support [cmin, 1] (cmin ≥ 0), and then transits to the next state s′ ∈ S+ = S ∪ {g} with probability Ps,a(s′). We assume that the transition P and the cost mean c are unknown to the learner, while all other parameters are known.
The learning process goes as follows: the learner interacts with the environment for K episodes. In the k-th episode, the learner starts in initial state sinit, sequentially takes an action, suffers a cost, and transits to the next state until reaching the goal state g. More formally, at the i-th step of the k-th episode, the learner observes the current state ski (with s k 1 = sinit), takes action a k i , suffers a cost c k i , and transits to the next state ski+1 ∼ Pski ,aki . An episode ends when the current state is g, and we define the length of episode k as Ik, such that skIk+1 = g.
Learning Objective At a high level, the learner’s goal is to reach the goal with a small total cost. To this end, we focus on proper policies — a (stationary and deterministic) policy π : S → A is a mapping that assigns an action π(s) to each state s ∈ S, and it is proper if the goal is reached with probability 1 when following π (that is, taking action π(s) whenever in state s). Given a proper policy π, one can define the cost-to-go function V π : S → [0,∞) as V π(s) = E [∑I i=1 ci
∣∣∣P, π, s1 = s] , where the expectation is with respect to the randomness of the cost ci incurred at state-action pair (si, π(si)), next state si+1 ∼ Psi,π(si), and the number of steps I before reaching g. The optimal proper policy π? is then defined as a policy such that V π ? (s) = minπ∈Π V π(s) for all s ∈ S , where Π is the set of all proper policies assumed to be nonempty. The formal objective of the learner is then to minimize her regret against π?, the difference between her total cost and that of the optimal proper policy, defined as
RK = K∑ k=1 Ik∑ i=1 cki −K · V ?(sinit),
where we use V ? as a shorthand for V π ? . The minimax optimal regret is known to be Õ(B? √ SAK), where B? = maxs∈S V ?(s), and S = |S+| and A = |A| are the numbers of states (including the goal state) and actions respectively [Cohen et al., 2020].
Bellman Optimality Equation For a proper policy π, the corresponding action-value function Qπ : S × A → [0,∞) is defined as Qπ(s, a) = c(s, a) + Es′∼Ps,a [V π(s′)]. Similarly, we use Q? as a shorthand for Qπ ?
. it is known that π? satisfies the Bellman optimality equation: V ?(s) = mina∈AQ ?(s, a) for all s ∈ S [Bertsekas and Tsitsiklis, 1991].
Assumption on cmin Similar to many previous works, our analysis requires cmin being known and strictly positive. When cmin is unknown or known to be 0, a simple workaround is to solve a modified SSP instance with all observed costs clipped to if they are below some > 0, so that cmin = > 0. Then the regret in this modified SSP is similar to that in the original SSP up to an additive term of order O ( K) [Tarbouriech et al., 2020a]. Therefore, throughout the paper we assume that cmin is known and strictly positive unless explicitly stated otherwise.
Algorithm 1 A General Algorithmic Template for SSP Initialize: t← 0, s1 ← sinit, Q(s, a)← 0 for all (s, a) ∈ S ×A. for k = 1, . . . ,K do
repeat 1 Increment time step t +← 1. 2 Take action at = argminaQ(st, a), suffer cost ct, transit to and observe s ′ t. 3 Update Q (so that it satisfies Property 1 and Property 2). 4 if s′t 6= g then st+1 ← s′t; else st+1 ← sinit, break.
Record T ← t (that is, the total number of steps).
Other Notations For simplicity, we use CK = ∑K k=1 ∑Ik i=1 c k i in the analysis to denote the total costs suffered by the learner over K episodes. For a function X : S+ → R and a distribution P over S+, denote by PX = ES∼P [X(S)], PX2 = ES∼P [X(S)2], and V(P,X) = VARS∼P [X(S)] the expectation, second moment, and variance of X(S) respectively where S is drawn from P . For a scalar x, define (x)+ = max{x, 0}, and denote by dxe2 = 2dlog2 xe and bxc2 = 2blog2 xc the closest power of two upper and lower bounding x respectively. For an integer m, [m] denotes the set {1, . . . ,m}. In pseudocode, x +← y is a shorthand for the increment operation x← x+ y.

heading: 3 Implicit Finite-Horizon Approximation
text: In this section, we introduce our main analytical technique, that is, implicitly approximating the SSP problem with a finite-horizon counterpart. We start with a general template of our algorithms shown in Algorithm 1. For notational convenience, we concatenate state-action-cost trajectories of all episodes as one single sequence (st, at, ct) for t = 1, 2, . . . , T , where st ∈ S is one of the non-goal state, at ∈ A is the action taken at st, and ct is the resulting cost incurred by the learner. Note that the goal state g is never included in this sequence (since no action is taken there), and we also use the notation s′t ∈ S+ to denote the next-state following (st, at), so that st+1 is simply s′t unless s′t = g (in which case st+1 is reset to the initial state sinit); see Line 4.
The template follows a rather standard idea for many reinforcement learning algorithms: maintain an (optimistic) estimate Q of the optimal action-value function Q?, and act greedily by taking the action with the smallest estimate: at = argminaQ(st, a); see Line 2. The key of the analysis is often to bound the estimation error Q?(st, at)−Q(st, at), which is relatively straightforward in a discounted setting (where the discount factor controls the growth of the error) or a finite-horizon setting (where the error vanishes after a fixed number of steps), but becomes highly non-trivial for SSP due to the lack of similar structures.
A natural idea is to explicitly solve a discounted problem or a finite-horizon problem that approximates the original SSP well enough. Unfortunately, both approaches are problematic: approximating an undiscounted MDP by a discounted one often leads to suboptimal regret [Wei et al., 2020]; on the other hand, while explicitly approximating SSP with a finite-horizon problem can lead to optimal regret [Chen et al., 2021, Cohen et al., 2021], it greatly increases the space complexity of the algorithm, and also produces non-stationary policies, which is unnatural and introduces unnecessary complexity since the optimal policy in SSP is stationary.
Therefore, we propose to approximate the original SSP instance M with a finite-horizon counterpart M̃ implicitly (that is, only in the analysis). We defer the formal definition of M̃ to Appendix C, which is similar to those in [Chen et al., 2021, Cohen et al., 2021] and corresponds to interacting with the original SSP for H steps (for some integer H) and then teleporting to the goal. All we need in the analysis are the optimal value function V ?h and optimal action-value function Q ? h of M̃ for each step h ∈ [H], which can be defined recursively without resorting to the definition of M̃ :
Q?h(s, a) = c(s, a) + Ps,aV ? h−1, V ? h (s) = min a Q?h(s, a), (1)
withQ?0(s, a) = 0 for all (s, a). 2 Intuitively,Q?H approximatesQ ? well whenH is large enough. This is formally summarized in the lemma below, whose proof is similar to prior works (see Appendix C). Lemma 1. For any value of H , Q?H(s, a) ≤ Q?(s, a) holds for all (s, a). For any β ∈ (0, 1), if H ≥ 4B?cmin ln(2/β) + 1, then Q ?(s, a) ≤ Q?H(s, a) +B?β holds for all (s, a).
In the remaining discussion, we fix a particular value of H . To carry out the regret analysis, we now specify two general requirements of the estimate Q. Let Qt be the value of Q at the beginning of time step t (that is, the value used in finding at). Then Qt needs to satisfy: Property 1 (Optimism). With high probability, Qt(s, a) ≤ Q?(s, a) holds for all (s, a) and t ≥ 1. Property 2 (Recursion). There exists a “bonus overhead” ξH > 0 and an absolute constant d > 0 such that the following holds with high probability:
T∑ t=1 (Q̊(st, at)−Qt(st, at))+ ≤ ξH + ( 1 + d H ) T∑ t=1 (V̊ (st)−Qt(st, at))+,
for Q̊ = Q?h and V̊ = V ? h−1 (h = 1, . . . ,H) as well as Q̊ = Q ? and V̊ = V ?.3
Property 1 is standard and can usually be ensured by using a certain “bonus” term derived from concentration equalities in the update. These bonus terms on (st, at) accumulate into some bonus overhead in the final regret bound, which is exactly the role of ξH in Property 2. In both of our algorithms, ξH has a leading-order term Õ( √ B?SACK) and a lower-order term that increases in H .
Property 2 is a key property that provides a recursive form of the estimation error and allows us to connect it to the finite-horizon approximation. This is illustrated through the following two lemmas.
Lemma 2. Property 2 implies ∑T t=1(Q ? H(st, at)−Qt(st, at))+ ≤ O (HξH).
Proof. With Q̊ = Q?H and V̊ = V ? H−1, Property 2 implies
T∑ t=1 (Q?H(st, at)−Qt(st, at))+ ≤ ξH + ( 1 + d H ) T∑ t=1 (V ?H−1(st)−Qt(st, at))+
≤ ξH + ( 1 + d
H ) T∑ t=1 (Q?H−1(st, at)−Qt(st, at))+,
where in the last step we use the optimality of V ?H−1 from Eq. (1). Repeatedly applying this argument, we eventually arrive at ∑T t=1(Q ? H(st, at) − Qt(st, at))+ ≤ H ( 1 + dH )H ξH +(
1 + dH )H∑T t=1(Q ? 0(st, at) − Qt(st, at))+ = O (HξH), where the last step uses the facts
Q?0(st, at) = 0 and ( 1 + dH )H ≤ ed (an absolute constant). Lemma 3. For any β ∈ (0, 1), if H ≥ 4B?cmin ln(2/β) + 1, then Property 1 and Property 2 together imply ∑T t=1Q ?(st, at)− V ?(st) = O (βCK + ξH). Proof. Applying Property 2 with Q̊ = Q? and V̊ = V ?, we have ∑T t=1(Q
?(st, at)−Qt(st, at))+ ≤ ξH + ( 1 + dH )∑T t=1(V
?(st)−Qt(st, at))+. Now note that by Property 1, the Bellman optimality equation V ?(st) = minaQ?(st, a), and the fact Qt(st, at) = minaQt(st, a) (by the definition of at), the arguments within the clipping operation (·)+ are all non-negative and thus the clipping can be removed. Rearranging terms then gives
T∑ t=1 Q?(st, at)− V ?(st) ≤ ξH + d H T∑ t=1 (V ?(st)−Qt(st, at))
≤ ξH + d
H T∑ t=1 (Q?(st, at)−Qt(st, at)). (optimality of V ?)
2Note that our notation is perhaps unconventional compared to most works on finite-horizon MDPs, where Q?h usually refers to our Q ? H−h. We make this switch since we want to highlight the dependence on H for Q ? H .
3Note that ξH might be a random variable. In fact, it often depends on CK .
It remains to bound the last term using the finite-horizon approximation Q?H as a proxy:
T∑ t=1 (Q?(st, at)−Qt(st, at)) = T∑ t=1 (Q?(st, at)−Q?H(st, at) +Q?H(st, at)−Qt(st, at))
= O (TB?β +HξH) ,
where the last step uses Lemma 1 and Lemma 2. Importantly, this term is finally scaled by d/H , which, together with the fact TB?H ≤ cminT ≤ CK , proves the claimed bound. Readers familiar with the literature might already recognize the term ∑T t=1Q
?(st, at) − V ?(st) considered in Lemma 3, which is closely related to the regret. Indeed, with this lemma, we can conclude a regret bound for our generic algorithm.
Theorem 1. For any β ∈ (0, 1), if H ≥ 4B?cmin ln(2/β) + 1, then Algorithm 1 ensures (with high probability) RK = Õ (√ B?CK +B? + βCK + ξH ) .
Proof. We first decompose the regret as follows, which holds generally for any algorithm:
RK = K∑ k=1 ( Ik∑ i=1 cki − V ?(sk1) )
≤ K∑ k=1 Ik∑ i=1 ( cki − V ?(ski ) + V ?(ski+1) ) = T∑ t=1 (ct − V ?(st) + V ?(s′t))
= T∑ t=1 (ct − c(st, at)) + T∑ t=1 (V ?(s′t)− Pst,atV ?) + T∑ t=1 (Q?(st, at)− V ?(st)). (2)
The first and the second term are the sum of a martingale difference sequence (since s′t is drawn from Pst,at) and can be bounded by Õ (√ CK ) and Õ (√ B?CK +B? ) respectively using concentration inequalities; see Lemma 4, Lemma 35, and Lemma 5. The third term can be bounded using Lemma 3 directly, which finishes the proof.
To get a sense of the regret bound in Theorem 1, first note that since 1/β only appears in a logarithmic term of the required lower bound of H , one can pick β to be small enough so that the term βCK is dominated by others. Moreover, if ξH is Õ( √ B?SACK) plus some lower-order term ρH (which as
mentioned is the case for our algorithms), then by solving a quadratic of √ CK , the regret bound of
Theorem 1 implies RK = Õ(B? √ SAK + ρH), which is minimax optimal (ignoring ρH )!
Based on this analytical technique, it remains to design algorithms satisfying the two required properties. In the following sections, we provide two such examples, leading to the first model-free SSP algorithm and an improved model-based SSP algorithm.

heading: 4 The First Model-free Algorithm: LCB-ADVANTAGE-SSP
text: In this section, we present a model-free algorithm (the first in the literature) called LCB-ADVANTAGESSP that falls into our generic template and satisfies the required properties. It is largely inspired by the state-of-the-art model-free algorithm UCB-ADVANTAGE [Zhang et al., 2020b] for the finitehorizon problem. The pseudocode is shown in Algorithm 2, with only the lines instantiating the update rule of the Q estimates numbered. Importantly, the space complexity of this algorithm is only O (SA) since we do not estimate the transition directly or conduct explicit finite-horizon reduction, and the time complexity is only O (1) in each step. Specifically, for each state-action pair (s, a), we divide the samples received when visiting (s, a) into consecutive stages of exponentially increasing length, and only update Q(s, a) at the end of a stage. The number of samples ej in stage j is defined through e1 = H and ej+1 = b(1 + 1/H)ejc for some parameter H . Further define L? = {Ej}j∈N+ with Ej = ∑j i=1 ei, which contains all the indices indicating the end of some stage. As mentioned, the algorithm only updates Q(s, a) when the
Algorithm 2 LCB-ADVANTAGE-SSP Parameters: horizon H , threshold θ?, and failure probability δ ∈ (0, 1). Define: L? = {Ej}j∈N+ where Ej = ∑j i=1 ei, e1 = H and ej+1 = b(1 + 1/H)ejc. Initialize: t← 0, s1 ← sinit, B ← 1, for all (s, a), N(s, a)← 0,M(s, a)← 0. Initialize: for all (s, a), Q(s, a)← 0, V (s)← 0, V ref(s)← V (s), Ĉ(s, a)← 0. Initialize: for all (s, a), µref(s, a)← 0, σref(s, a)← 0, µ(s, a)← 0, σ(s, a)← 0, v(s, a)← 0. for k = 1, . . . ,K do
repeat Increment time step t +← 1. Take action at = argminaQ(st, a), suffer cost ct, transit to and observe s ′ t.
1 Increment visitation counters: n = N(st, at) +← 1,m = M(st, at) +← 1. 2 Update global accumulators: µref(st, at) +← V ref(s′t), σref(st, at) +← V ref(s′t)2,
Ĉ(st, at) +← ct.
3 Update local accumulators: v(st, at) +← V (s′t), µ(st, at) +← V (s′t)− V ref(s′t), σ(st, at) +← (V (s′t)− V ref(s′t))2. 4 if n ∈ L? then 5 Compute ι ← 256 ln6(4SAB8?n5/δ), cost estimator ĉ = Ĉ(st,at) n , bonuses b ′ ←
2 √
B2ι m + √ ĉι n +
ι n and b←√
σref(st,at)/n− (µref(st,at)/n)2 n ι+
√ σ(st,at)/m− (µ(st,at)/m)2
m ι+
( 4B
n +
3B
m
) ι+ √ ĉι
n .
6 Q(st, at)← max { ĉ+ v(st,at)m − b ′, Q(st, at) } .
7 Q(st, at)← max { ĉ+ µ ref(st,at) n + µ(st,at) m − b,Q(st, at) } . 8 V (st)← minaQ(st, a). 9 if V (st) > B then B ← 2V (st).
10 Reset local accumulators: v(st, at)← 0, µ(st, at)← 0, σ(st, at)← 0,M(st, at)← 0. 11 if ∑ aN(st, a) is a power of two not larger than θ
? then V ref(st)← V (st). if s′t 6= g then st+1 ← s′t; else st+1 ← sinit, break.
total number of visits to (s, a) falls into the set L? (Line 4). The algorithm also maintains an estimate V for V ?, which always satisfies V (s) = minaQ(s, a) (Line 8), and importantly another reference value function V ref whose role and update rule are to be discussed later.
In addition, some local and global accumulators are maintained in the algorithm. Local accumulators only store information related to the current stage. These include: M(s, a), the number of visits to (s, a) within the current stage; v(s, a), the cumulative value of V (s′) within the current stage, where s′ represents the next state after each visit to (s, a); and finally µ(s, a) and σ(s, a), the cumulative values of V (s′)− V ref(s′) and its square respectively within the current stage (Line 3). These local accumulators are reset to zero at the end of each stage (Line 10).
On the other hand, global accumulators store information related to all stages and are never reset. These include: N(s, a), the number of visits to (s, a) from the beginning; Ĉ(s, a), total cost incurs at (s, a) from the beginning; and µref(s, a) and σref(s, a), the cumulative value of V ref(s′) and its square respectively from the beginning, where again s′ represents the next state after each visit to (s, a) (Line 2).
We are now ready to describe the update rule of Q. The first update, Line 6, is intuitively based on the equality Q?(s, a) = c(s, a) + Ps,aV ? and uses v(s, a)/M(s, a) as an estimate for Ps,aV ? together with a (negative) bonus b′ derived from Azuma’s inequality (Line 5). As mentioned, the bonus is necessary to ensure Property 1 (optimism) so that Q is always a lower confidence bound of Q? (hence the name “LCB”). Note that this update only uses data from the current stage (roughly 1/H fraction of the entire data collected so far), which leads to an extra √ H factor in the regret.
To address this issue, Zhang et al. [2020b] introduce a variance reduction technique via a referenceadvantage decomposition, which we borrow here leading to the second update rule in Line 7. This is intuitively based on the decomposition Ps,aV ? = Ps,aV ref + Ps,a(V ? − V ref), where Ps,aV ref is approximated by µref(s, a)/N(s, a) and Ps,a(V ? − V ref) is approximated by µ(s, a)/M(s, a). In addition, a “variance-aware” bonus term b is applied, which is derived from a tighter Freedman’s inequality (Line 5). The reference function V ref is some snapshot of the past value of V , and is guaranteed to be O(cmin) close to V ? on a particular state as long as the number of visits to this state exceeds some threshold θ? = Õ ( B2?H 3SA/c2min )
(Line 11). Overall, this second update rule not only removes the extra √ H factor as in [Zhang et al., 2020b], but also turns some terms of order Õ( √ T ) into Õ( √ CK) in our context, which is important for obtaining the optimal regret.
Despite the similarity, we emphasize several key differences between our algorithm and that of [Zhang et al., 2020b]. First, [Zhang et al., 2020b] maintains a different Q estimate for each step of an episode (which is natural for a finite-horizon problem), while we only maintain one Q estimate (which is natural for SSP). Second, we update the reference function V ref(s) whenever the number of visits to s doubles (while still below the threshold θ?; see Line 11), instead of only updating it once as in [Zhang et al., 2020b]. We show in Lemma 8 that this helps reduce the sample complexity and leads to a smaller lower-order term in the regret. Third, since there is no apriori known upper bound on V (unlike the finite-horizon setting), we maintain an empirical upper bound B (in a doubling manner) such that V (s) ≤ B ≤ 2B? (Line 9), which is further used in computing the bonus terms b and b′. This is important for eventually developing a parameter-free algorithm.
In Appendix D, we show that Algorithm 2 indeed satisfies the two required properties.
Theorem 2. Let H = d 4B?cmin ln( 2 β ) + 1e2 for β = cmin 2B2?SAK
and θ? = Õ ( B2?H 3SA
c2min
) be de-
fined in Lemma 8, then Algorithm 2 satisfies Property 1 and Property 2 with d = 3 and ξH = Õ (√ B?SACK + B2?H 3S2A
cmin
) .
Proof Sketch. The proof of Property 1 largely follows the analysis of [Zhang et al., 2020b, Proposition 4] for the designed bonuses. To prove Property 2, similarly to [Zhang et al., 2020b] we can show:
T∑ t=1 (Q̊(st, at)−Qt(st, at))+ . ξH + T∑ t=1 1 mt mt∑ i=1 Psľt,i ,aľt,i (V̊ − Vľt,i)+,
where mt is the value of m used in computing Qt(st, at), and ľt,i is the i-th time step the agent visits (st, at) among thosemt steps. Now it suffices to show that ∑T t=1 1 mt ∑mt i=1 Psľt,i ,aľt,i
(V̊ −Vľt,i)+ . (1 + 3H ) ∑T t=1(V̊ (st)− Vt(st))+, which is proven in Lemma 13.
As a direct corollary of Theorem 1, we arrive at the following regret guarantee.
Theorem 3. With the same parameters as in Theorem 2, with probability at least 1−60δ, Algorithm 2 ensures RK = Õ ( B? √ SAK + B5?S 2A
c4min
) .
We make several remarks on our results. First, while Algorithm 2 requires setting the two parameters H and θ? in terms of B? to obtain the claimed regret bound, one can in fact achieve the exact same bound without knowing B? by slightly changing the algorithm. The high level idea is to first apply the doubling trick from Tarbouriech et al. [2021b] to determine an upper bound on B?, then try logarithmically many different values of H and θ? simultaneously, each leading to a different update rule for Q and V ref. This only increases the time and space complexity by a logarithmic factor, without hurting the regret (up to log factors). Details are deferred to Section D.5.
Second, as mentioned in Section 2, when cmin is unknown or cmin = 0, one can clip all observed costs to if they are below > 0, which introduces an additive regret term of order O ( K). By picking to be of order K−1/5, our bound becomes Õ ( K4/5 ) ignoring other parameters. Although most existing works suffer the same issue, this is certainly undesirable, and our second algorithm to be introduced in the next section completely avoids this issue by having only logarithmic dependence on 1/cmin.
Algorithm 3 SVI-SSP Parameters: horizon H , value function upper bound B, and failure probability δ ∈ (0, 1). Define: L = {Ej}j∈N+ , where Ej = ∑j i=1 ei, ej = bẽjc, and ẽ1 = 1, ẽj+1 = ẽj + 1 H ej . Initialize: t← 0, s1 ← sinit. Initialize: for all (s, a, s′), n(s, a, s′)← 0, n(s, a)← 0, Q(s, a)← 0, V (s)← 0, Ĉ(s, a)← 0. for k = 1, . . . ,K do
repeat Increment time step t +← 1. Take action at = argminaQ(st, a), suffer cost ct, transit to and observe s ′ t.
1 Update accumulators: n = n(st, at) +← 1, n(st, at, s′t) +← 1, Ĉ(st, at) +← ct. 2 if n ∈ L then 3 Update empirical transition: P̄st,at(s ′)← n(st,at,s ′) n for all s ′. 4 Compute ι ← 20 ln 2SAnδ , cost estimator ĉ ← Ĉ(s,a) n , and bonus b ←
max { 7 √ V(P̄st,at ,V )ι
n , 49Bι n
} + √
ĉι n .
5 Q(st, at)← max{ĉ+ P̄st,atV − b,Q(st, at)}. 6 V (st)← argminaQ(st, a).
if s′t 6= g then st+1 ← s′t; else st+1 ← sinit, break.
Finally, we point out that, just as in the finite-horizon case, the variance reduction technique is crucial for obtaining the minimax optimal regret. For example, if one instead uses an update rule similar to the (suboptimal) Q-learning algorithm of [Jin et al., 2018], then this is essentially equivalent to removing the second update (Line 7) of our algorithm. While this still satisfies Property 2, the bonus overhead ξH would be √ H times larger, resulting in a suboptimal leading term in the regret.

heading: 5 An Optimal and Efficient Model-based Algorithm: SVI-SSP
text: In this section, we propose a simple model-based algorithm called SVI-SSP (Sparse Value Iteration for SSP) following our template, which not only achieves the minimax optimal regret even when cmin = 0, matching the state-of-the-art by a recent work [Tarbouriech et al., 2021b], but also admits highly sparse updates, making it more efficient than all existing model-based algorithms. The pseudocode is in Algorithm 3, again with only the lines instantiating the update rule for Q numbered.
Similar to Algorithm 2, SVI-SSP divides samples of each (s, a) into consecutive stages of (roughly) exponentially increasing length, and only update Q(s, a) at the end of a stage (Line 2). However, the number of samples ej in stage j is defined slightly differently through ej = bẽjc, ẽ1 = 1, and ẽj+1 = ẽj + 1 H ej for some parameter H . In the long run, this is almost the same as the scheme used in Algorithm 2, but importantly, it forces more frequent updates at the beginning — for example, one can verify that e1 = · · · = eH = 1, meaning that Q(s, a) is updated every time (s, a) is visited for the first H visits. This slight difference turns out to be important to ensure that the lower-order term in the regret has no poly(H) dependence, as shown in Lemma 16 and further discussed in Remark 3. More intuition on the design of this update scheme is provided in Section E.1.
The update rule for Q is very simple (Line 5). It is again based on the equality Q?(s, a) = c(s, a) + Ps,aV
?, but this time uses P̄s,aV − b as an approximation for Ps,aV ?, where P̄s,a is the empirical transition directly calculated from two counters n(s, a) and n(s, a, s′) (number of visits to (s, a) and (s, a, s′) respectively), V is such that V (s) = minaQ(s, a), and b is a special bonus term (Line 4) adopted from [Tarbouriech et al., 2021b, Zhang et al., 2020a] which ensures that Q is an optimistic estimate of Q? and also helps remove poly(H) dependence in the regret.
SVI-SSP exhibits a unique structure compared to existing algorithms. In each update, it modifies only one entry of Q (similarly to model-free algorithms), while other model-based algorithms such as [Tarbouriech et al., 2021b] perform value iteration for every entry ofQ repeatedly until convergence (concrete time complexity comparisons to follow). We emphasize that our implicit finite-horizon
analysis is indeed the key to enable us to derive a regret guarantee for such a sparse value iteration algorithm. Specifically, in Appendix E, we show that SVI-SSP satisfies the two required properties. Theorem 4. If B ≥ B? and H = d 4Bcmin ln( 2 β ) + 1e2 for β = cmin 2B2SAK , then Algorithm 3 satisfies Property 1 and Property 2 with d = 1 and ξH = Õ( √ B?SACK + BS
2A + βCK), where the dependence on H in ξH is hidden in logarithmic terms.
Proof Sketch. The proof of Property 1 largely follows the analysis of [Tarbouriech et al., 2021b, Lemma 15]. To prove Property 2, we first show ∑T t=1(Q̊(st, at)−Qt(st, at))+ . ξH+ ∑T t=1 Pt(V̊− Vlt)+, where lt is the last time step Q(st, at) is updated. Then, the remaining main steps are shown below with all details deferred to the corresponding key lemmas:
T∑ t=1 Pt(V̊ − Vlt)+ . ( 1 + 1 H ) T∑ t=1 Pt(V̊ − Vt)+ (Lemma 16)
. ( 1 + 1
H ) T∑ t=1 (V̊ (st)− Vt(st))+ + ( 1 + 1 H ) T∑ t=1 (Pt − Is′t)(V̊ − Vt)+
. ( 1 + 1
H ) T∑ t=1 (V̊ (st)− Vt(st))+ + ξH , (Lemma 22 and Lemma 21)
which completes the proof.
Again, as a direct corollary of Theorem 1, we arrive at the following regret guarantee. Theorem 5. With the same parameters as in Theorem 4, with probability at least 1−12δ, Algorithm 3 ensures RK = Õ(B? √ SAK +BS2A). Setting B = B?, our bound becomes Õ(B? √ SAK + B?S
2A), which is minimax optimal even when cmin is unknown or cmin = 0 (this is because the dependence on 1/cmin is only logarithmic, and one can clip all observed costs to if they are below = 1/K in this case without introducing poly(K) overhead to the regret). When B? is unknown, we can use the same doubling trick from Tarbouriech et al. [2021b] to obtain almost the same bound (with only the lower-order term increased to Õ ( B3?S 3A ) ); see Section E.5 for details.4
Comparison with EB-SSP [Tarbouriech et al., 2021b] Our regret bounds match exactly the stateof-the-art by Tarbouriech et al. [2021b]. Thanks to the sparse update, however, SVI-SSP has a much better time complexity. Specifically, for SVI-SSP, each (s, a) is updated at most Õ(H) = Õ(B?/cmin) times (Lemma 16), and each update takes O(S) time, leading to total complexity Õ(B?S2A/cmin). On the other hand, for EB-SSP, although each (s, a) only causes Õ(1) updates, each update runs value iteration on all entries of Q until convergence, which takes Õ(B2?S2/c2min) iterations (see their Appendix C) and leads to total complexity Õ(B2?S5A/c2min), much larger than ours.
Comparison with ULCVI [Cohen et al., 2021] Another recent work by Cohen et al. [2021] using explicit finite-horizon approximation also achieves minimax regret but requires the knowledge of some hitting time of the optimal policy. Without this knowledge, their bound has a large 1/c4min dependence in the lower-order term just as our model-free algorithm. Our results in this section show that implicit finite-horizon approximation has advantage over explicit approximation apart from reducing space complexity: the former does not necessarily introduce poly(H) dependence even for the lower-order term, while the latter does under the current analysis.
Acknowledgments and Disclosure of Funding
LC thanks Chen-Yu Wei for many helpful discussions. HL is supported by NSF Award IIS-1943607 and a Google Faculty Research Award. MJ and RJ’s research is supported by NSF CCF-1817212, NSF ECCS-1810447 and ONR N00014-20-1-2258 awards.
4We note that this doubling trick is in fact also applicable to Algorithm 2. However, the specific approach we propose for this algorithm in Section D.5 is better in the sense that it does not worsen the regret at all.

Review summaries:
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.

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

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.