Minimax Regret for Stochastic Shortest Path

Abstract:
We study the Stochastic Shortest Path (SSP) problem in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent has no prior knowledge about the costs and dynamics of the model. She repeatedly interacts with the model for K episodes, and has to minimize her regret. In this work we show that the minimax regret for this setting is Õ( √ (B? + B?)|S||A|K) where B? is a bound on the expected cost of the optimal policy from any state, S is the state space, and A is the action space. This matches the Ω( √ B?|S||A|K) lower bound of Rosenberg et al. [2020] for B? ≥ 1, and improves their regret bound by a factor of √ |S|. For B? < 1 we prove a matching lower bound of Ω( √ B?|S||A|K). Our algorithm is based on a novel reduction from SSP to finite-horizon MDPs. To that end, we provide an algorithm for the finitehorizon setting whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.

text: √ (B2? + B?)|S||A|K) where B? is a bound on the expected cost of the
optimal policy from any state, S is the state space, and A is the action space. This matches the Ω( √ B2?|S||A|K) lower bound of Rosenberg et al. [2020] for B? ≥ 1, and
improves their regret bound by a factor of √
|S|. For B? < 1 we prove a matching lower bound of Ω( √ B?|S||A|K). Our algorithm is based on a novel reduction from SSP to finite-horizon MDPs. To that end, we provide an algorithm for the finitehorizon setting whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.

heading: 1 Introduction
text: We study the stochastic shortest path (SSP) problem in which an agent aims to reach a predefined goal state while minimizing her total expected cost. This is one of the most basic models of reinforcement learning (RL) that includes both finite-horizon and discounted Markov Decision Processes (MDPs) as special cases. In addition, SSP captures a wide variety of realistic scenarios such as car navigation, game playing and drone flying.
We study an online version of SSP in which both the immediate costs and transition distributions of the model are initially unknown to the agent. The agent interacts with the model for K episodes, in each of which she attempts to reach the goal state with minimal cumulative cost. A main challenge in the online model is found when instantaneous costs are small. For example, any learning algorithm that attempts to myopically minimize the accumulated costs might get caught in a cycle with zero cost and never reach the goal state. Nonetheless, even if the costs are not zero, only very small, the agent must be able to trade off the need to minimize costs with that of reaching the goal quickly.
The online setting was originally suggested by Tarbouriech et al. [2020] who gave an algorithm with Õ(K2/3) regret guarantee. In a follow-up work, Rosenberg et al. [2020] improved the previous bound to Õ(B?|S| √ |A|K), where S is the state space, A is the action space, and B? is an upper bound on the total expected cost of the optimal policy when initialized at any state. Rosenberg et al. [2020] also provide a lower bound of Ω(B? √ |S||A|K) – leaving a gap of √ |S| between the upper and lower bounds. In this work, unlike the previously mentioned works that assume the cost function is deterministic
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
and known, we consider the case where the costs are i.i.d. and initially unknown. We prove upper and lower bounds for this case, proving that the optimal regret is of order Θ̃( √ (B2? + B?)|S||A|K).
The algorithms of both Tarbouriech et al. [2020], Rosenberg et al. [2020] were based on a direct application of the “Optimism in the Face of Uncertainty” principle to the SSP model, following the ideas behind the UCRL2 algorithm [Jaksch et al., 2010] for average-reward MDPs. In this work we take a different approach. We propose a novel black-box reduction to finite-horizon MDPs, showing that the SSP problem is not harder than the finite-horizon setting assuming prior knowledge on the expected time it takes for the optimal policy to reach the goal state. While the reduction itself is simple, the analysis is highly nontrivial as one has to show that the goal state is indeed reached in every episode without incurring excessive costs in the process.
The idea of reducing SSP to finite-horizon was previously used by Chen et al. [2020], Chen and Luo [2021] for SSP with adversarially changing costs. However, they run one finite-horizon episode in every SSP episode and then simply try to reach the goal as fast as possible, while we restart a new finite-horizon episode every H steps. This modification is what enables us to obtain the optimal and improved dependence in the number of states.
In addition, we provide a new algorithm for regret minimization in finite-horizon MDPs called ULCVI. We show that (for large enough number of episodes) its regret depends polynomially on the expected cost of the optimal policy B?, and only logarithmically on the horizon length H. This implies that the correct measure for the regret is the expected cost of the optimal policy and not the length of the horizon. We note that regret with logarithmic dependence in the horizon H was also obtained by Zhang et al. [2020], yet they make a much stronger assumption: that the cumulative cost of every trajectory is bounded by 1. In contrast, we only assume that the expected cost of the optimal policy is bounded by some constant B?, while other policies may suffer a cost of H. Our reduction, when combined with our finite-horizon algorithm ULCVI, guarantees SSP regret of Õ( √
(B2? + B?)|S||A|K). This matches the lower bound of Rosenberg et al. [2020] for B? ≥ 1 up to logarithmic factors. However, their lower bound does not hold for B? < 1 suggesting that this is not the correct rate in this case. Indeed, we prove a tighter lower bound of Ω( √ B?|S||A|K) for B? < 1, showing that our regret guarantees are minimax optimal in all cases.
As a final remark we note that, following our work, Tarbouriech et al. [2021] were able to obtain a comparable regret bound for SSP without prior knowledge of the optimal policy’s expected time to reach the goal state.

heading: 1.1 Additional related work
text: Planning for stochastic shortest path. Early work by Bertsekas and Tsitsiklis [1991] studied planning in SSPs, i.e., computing the optimal strategy efficiently when parameters are known. Under certain assumptions, they established that the optimal strategy is a deterministic stationary policy and can be computed efficiently using standard planning algorithms, e.g., Value Iteration and LP.
Adversarial stochastic shortest path. Rosenberg and Mansour [2020] presented stochastic shortest path with adversarially changing costs. Their regret bounds were improved by Chen et al. [2020], Chen and Luo [2021] using a reduction to online loop-free SSP (see next paragraph). As mentioned before, our reduction is different and therefore able to remove the extra √ |S| factor in the regret.
Regret minimization in MDPs. There is a vast literature on regret minimization in RL that mostly builds on the optimism principle. Most literature focuses on the tabular setting [Jaksch et al., 2010, Azar et al., 2017, Jin et al., 2018, Fruit et al., 2018, Zanette and Brunskill, 2019, Efroni et al., 2019, Simchowitz and Jamieson, 2019], but recently it was extended to function approximation under various assumptions [Yang and Wang, 2019, Jin et al., 2020b, Zanette et al., 2020a,b].
Online loop-free SSP. A different line of work considers finite-horizon MDPs with adversarially changing costs [Neu et al., 2010, 2012, Zimin and Neu, 2013, Rosenberg and Mansour, 2019b,a, Jin et al., 2020a, Cai et al., 2020, Shani et al., 2020, Lancewicki et al., 2020, Lee et al., 2020, Jin and Luo, 2020]. They refer to finite-horizon adversarial MDPs as online loop-free SSP. This is not to be confused with our setting in which the interaction between the agent and the environment ends only when (and if) the goal state is reached, and not after a fixed number of steps H. See Rosenberg and Mansour [2020], Chen et al. [2020] for a discussion on the differences between the models.

heading: 2 Preliminaries and main results
text: An instance of the SSP problem is defined by an MDPM = (S, A, P, c, sinit, g) where S is a finite state space and A is a finite action space. The agent begins at an initial state sinit ∈ S, and ends her interaction withM by arriving at the goal state g (where g 6∈ S). Whenever she plays action a in state s, she pays a cost C ∈ [0, 1] drawn i.i.d. from a distribution with expectation c(s, a) ∈ [0, 1] and the next state s′ ∈ S ∪ {g} is chosen with probability P(s′ | s, a). Note that the transition function P satisfies ∑ s′∈S∪{g} P(s ′ | s, a) = 1 for every (s, a) ∈ S× A.
Proper policies. A stationary and deterministic policy π : S 7→ A is a mapping that selects action π(s) whenever the agent is at state s. A policy π is called proper if playing according to π ensures that the goal state is reached with probability 1 when starting from any state (otherwise it is improper). In SSP, the agent has two goals: (a) reach the goal state; (b) minimize the total expected cost. To facilitate the first goal, we make the basic assumption that there exists at least one proper policy. In particular, the goal state is reachable from every state, which is clearly a necessary assumption.
Any policy π induces a cost-to-go function Jπ : S 7→ [0,∞]. The cost-to-go at state s is defined by Jπ(s) = limT→∞ Eπ [∑T t=1 c(st, at) | sinit = s ] , where the expectation is taken w.r.t the random sequence of states generated by playing according to π when the initial state is s. For a proper policy π, it follows that Jπ(s) is finite for all s ∈ S. However, note that Jπ(s) may be finite even if π is improper. We additionally denote by Tπ(s) the expected time it takes for π to reach g starting at state s; in particular, if π is proper then Tπ(s) is finite for all s ∈ S, and if π is improper there must exist some state s such that Tπ(s) =∞. Learning formulation. Here, the agent does not have any prior knowledge of the cost function c or transition function P. She interacts with the model in episodes: each episode starts at the fixed initial state sinit,1 and ends when the agent reaches the goal state g (note that she might never reach the goal state). Success is measured by the agent’s regret over K such episodes, that is the difference between her total cost over the K episodes and the total expected cost of the optimal proper policy:
RK = K∑
k=1 Ik∑ i=1 Cki – K · min π∈Πproper Jπ(sinit),
where Ik is the time it takes the agent to complete episode k (which may be infinite), Cki is the cost suffered in the i-th step of episode k when the agent visited state-action pair (ski , a k i ), and Πproper is the set of all stationary, deterministic and proper policies (that is not empty by assumption). In the case that Ik is infinite for some k, we define RK =∞. We denote the optimal proper policy by π?, Jπ ?
(sinit) = arg minπ∈Πproper J π(sinit). Moreover, let B? > 0
be an upper bound on the values of Jπ ? and let T? > 0 be an upper bound on the times Tπ ?
, i.e., B? ≥ maxs∈S Jπ ? (s) and T? ≥ maxs∈S Tπ ? (s). Finally, let D = maxs∈S minπ∈Πproper T π(s) be the SSP-diameter, and note that B? ≤ D ≤ T?.

heading: 2.1 Summary of our results
text: In Section 3 we present a novel black-box reduction from SSP to finite-horizon MDPs (Algorithm 1), that yields √ K regret bounds when combined with a certain class of optimistic algorithms for regret minimization in finite-horizon MDPs that we call admissible (Definition 1). The regret analysis for the reduction is described in Section 4, and in Section 5 we present an admissible algorithm for regret minimization in finite-horizon MDPs called ULCVI. We show that it guarantees the following optimal regret in the finite-horizon setting (stated formally in Theorem 5.1). Note that (for large enough number of episodes) this bound depends only on the expected cost of the optimal policy and not on the horizon H. Theorem 2.1. Running ULCVI (Algorithm 2 in Section 5) in a finite-horizon MDP guarantees, with probability at least 1 – δ, a regret bound of
O (√ (B2? + B?)|S||A|M log MH|S||A|
δ + H4B–1? |S|
2|A| log3/2 MH|S||A|
δ
) ,
1The initial state is fixed for simplicity of presentation, but it can be chosen adversarially at the beginning of every episode. Without any change to the algorithm or analysis, the same guarantees hold.
for any number of episodes M ≥ 1 simultaneously.
Combining ULCVI with our reduction yields the following minimax optimal regret bound for SSP.
Theorem 2.2. Running the reduction in Algorithm 1 with the finite-horizon regret minimization algorithm ULCVI ensures, with probability at least 1 – δ,
RK = O (√ (B2? + B?)|S||A|K log KT?|S||A|
δ + T5?B –2 ? |S|
2|A| log6 KT?|S||A|
δ
) .
Remark 1. An important observation is that this regret bound is meaningful even for small K. Unlike finite-horizon MDPs, where linear regret is trivial, in SSP ensuring finite regret is not easy. Our regret bound also implies that if we play for only one episode, i.e., we are only interested in the time it takes to reach the goal state, then it will take us at most Õ(T5?B –2 ? |S| 2|A|) time steps to do so.
Remark 2. Note that our algorithm needs to know an upper bound on T? in advance. However, if all costs are strictly positive (i.e., at least cmin > 0), then there is a trivial upper bound of B?/cmin. In this case, our algorithm keeps an optimal regret bound for large enough K, since the bound on T? only appears in the additive factor. Some previous work used a perturbation argument to generalize their results from the cmin case to general costs [Tarbouriech et al., 2020, Rosenberg et al., 2020, Rosenberg and Mansour, 2020]. In our case, it will not work since the dependence on 1/cmin in the additive term is too large. This may be an inherent shortcoming of using finite-horizon reduction to solve SSPs, as it also appears in the works of Chen et al. [2020], Chen and Luo [2021] for the adversarial setting.
Remark 3. In practice, one can think of T? as a parameter of the algorithm that controls computational complexity and the number of steps to complete K episodes. By choosing the parameter T? = x for example, we can guarantee that the regret bound of Theorem 2.2 holds against the best proper policy with expected time to the goal of at most x (assuming there exists one), and we can also guarantee that the total computational complexity of the algorithm is Õ(x log K) (see Remark 5). Furthermore, the algorithm will take at most Õ(xK + poly(x, |S|, |A|)) steps to complete K episodes.
Remark 4. While the additive term in our regret bound is standard for most cases, it becomes large when B? is extremely small because of the dependence in B–1? . This was not an issue in previous work [Tarbouriech et al., 2020, Rosenberg et al., 2020] since they assumed that the costs are deterministic and known. We believe that this dependence is an artifact of our analysis that may be avoided with a more careful definition of ωA (see Definition 1) that depends on the actual cost in each state-action pair and not just B?. Nevertheless, the main focus of this paper is on establishing that the minimax optimal regret for SSP is Θ̃( √ (B2? + B?)|S||A|K), and not on optimizing lower order terms. By that we also show that this is the minimax optimal regret for finite-horizon which is independent of the horizon H (up to logarithmic factors). Tightening the additive term and eliminating its dependence in B–1? is left as an interesting future direction.
In Appendix D we prove that our regret bound is indeed minimax optimal. To complement the Ω(B? √ |S||A|K) lower bound of Rosenberg et al. [2020] that assumes B? ≥ 1, we provide the following tighter lower bound for the case that B? < 1.
Theorem 2.3. Let B? ≤ 12 . There exists an SSP problem instanceM = (S, A, P, c, sinit, g) in which Jπ ?
(s) ≤ B? for all s ∈ S, |S| ≥ 2, |A| ≥ 2, K ≥ B?|S||A|, such the expected regret of any learner after K episodes satisfies
E[RK] ≥ 1
32
√ B?|S||A|K.

heading: 3 A black-box reduction from SSP to finite-horizon
text: Our algorithm takes as input an algorithm A for regret minimization in finite-horizon MDPs, and uses it to perform a black-box reduction. The algorithm is depicted below as Algorithm 1.
The algorithm breaks the individual time steps that comprise each of the K episodes into intervals of H time steps. If the agent reaches the goal state before H time steps, we simply assume that she stays in g until H time steps are elapsed. We see each interval as one episode of a finite-horizon model M̂ = (Ŝ, A, P̂, H, ĉ, ĉf ), where Ŝ = S ∪ {g} and ĉf : Ŝ→ R is a set of terminal costs defined by
ĉf (s) = 8B?I{s 6= g}, where I{s 6= g} is the indicator function that equals 1 if s 6= g and 0 otherwise. Moreover, P̂, ĉ are the natural extensions of P, c to the goal state. That is, ĉ(s, a) = c(s, a)I{s 6= g} and
P̂(s′ | s, a) =  P(s′ | s, a), s 6= g; 1, s = g, s′ = g; 0, s = g, s′ 6= g.
The horizon H (which we will set to be roughly T?) is chosen such that the optimal SSP policy will reach the goal state in H time steps with high probability (recall that the expected hitting time of the optimal policy is bounded by T?). The additional terminal cost is there to encourage the agent to reach the goal state within H steps, which otherwise is not necessarily optimal with respect to the planning horizon.
Algorithm 1 REDUCTION FROM SSP TO FINITE-HORIZON MDP 1: input: state sapce S, action space A, initial state sinit, goal state g, confidence parameter δ, number
of episodes K, bound on the expected cost of the optimal policy B?, bound on the expected time of the optimal policy T? and algorithm A for regret minimization in finite-horizon MDPs. 2: initialize A with state space Ŝ = S ∪ {g}, action space A, horizon H = 8T? log(8K), confidence parameter δ/4, terminal costs ĉf (s) = 8B?I{s 6= g} and bound on the expected cost of the optimal policy 9B?. 3: initialize intervals counter m← 0 and time steps counter t← 1. 4: for k = 1, . . . , K do 5: set st ← sinit. 6: while st 6= g do 7: set m← m + 1, feed initial state st to A and obtain policy πm = {πmh : Ŝ→ A}Hh=1. 8: for h = 1, . . . , H do 9: play action at = πmh (st), suffer cost Ct ∼ c(st, at), and set smh = st, amh = at, Cmh = Ct.
10: observe next state st+1 ∼ P(· | st, at) and set t← t + 1. 11: if st = g then 12: pad trajectory to be of length H and BREAK. 13: end if 14: end for 15: set smH+1 = st. 16: feed trajectory Um = (sm1 , a m 1 , . . . , s m H , a m H , s m H+1) and costs {C m h } H h=1 to A. 17: end while 18: end for
The algorithm A is initialized with the state and action spaces as in the original SSP instance, the horizon length H, a confidence parameter δ/4, a set of terminal costs ĉf and a bound on the expected cost of the optimal policy in the finite-horizon model 9B?. At the beginning of each interval, it takes as input an initial state and outputs a policy to be used throughout the interval. In the end of the interval it receives the trajectory and costs observed through the interval.
Note that while Algorithm 1 may run any finite-horizon regret minimization algorithm, in the analysis we require thatA possesses some properties (that most optimistic algorithms already have) in order to establish our regret bound. We specifically require A to be an admissible algorithm—a model-based optimistic algorithm for regret minimization in finite-horizon MDPs, e.g., UCBVI [Azar et al., 2017] and EULER [Zanette and Brunskill, 2019]. Admissible algorithms are defined formally as follows. Definition 1. A model-based algorithm A for regret minimization in finite-horizon MDPs is called admissible if, when running A with confidence parameter δ, there is a good event that holds with probability at least 1 – δ, under which the following hold:
(i) A provides anytime regret guarantees without prior knowledge of the number of episodes, and when the initial state of each episode is arbitrary. The regret bound that A guarantees for M episodes is denoted by R̂A(M), for some non-decreasing function R̂A.
(ii) The policy πm that A picks in episode m is greedy with respect to an estimate of the optimal policy’s Q-function.
(iii) The algorithm’s estimate Jm of Ĵ? (the cost-to-go function associated with the optimal finite-horizon policy) is optimistic, i.e., Jmh (s) ≤ Ĵ?h (s) for every s ∈ S and h = 1, . . . , H + 1.
(iv) A computes Jm using estimates c̃m, P̃m of the cost function ĉ and the transition function P̂, respectively. There exists ωA which is a function of H, |S|, |A| such that: if state-action pair (s, a) was visited at least ωA log MH|S||A|δ times, then |c̃ m h (s, a) – ĉ(s, a)| ≤ B?/H and
‖P̃m(· | s, a) – P̂(· | s, a)‖1 ≤ 1/(9H).
Using an admissible algorithm in Algorithm 1 enables us to bound the total number of intervals, thus ensuring that the agent reaches the goal state in almost every interval. This is because, as A is optimistic, it will try to avoid the terminal cost (which is suffered in all states except for g) by reaching the goal state. In addition, A will succeed in doing so once it has a good enough estimation of the transition function. Armed with the notion of admissibility, in the sequel we prove the following regret bound for any admissible algorithm A. The proof of Theorem 2.2 is now given by combining Theorem 3.1 with the regret bound of ULCVI in Theorem 2.1.
Theorem 3.1. Let A be an admissible algorithm for regret minimization in finite-horizon MDPs and denote its regret in M episodes by R̂A(M). Then, running Algorithm 1 with A ensures that, with probability at least 1 – δ,
RK ≤ R̂A ( 4K + 4 · 104|S||A|ωA log KT?|S||A|ωA
δ ) + O (√ (B2? + B?)K log
KT?|S||A|ωA δ + T?ωA|S||A| log2 KT?|S||A|ωA δ
) ,
where ωA is a quantity that depends on the algorithm A and on |S|, |A|, H. Remark 5 (Computational complexity). Our reduction directly inherits the computational complexity of the finite-horizon algorithm A in M episodes, where M ≈ K + poly(|S|, |A|, T?) by Lemma 4.3. The computational complexity of ULCVI is O(H|S|3|A|2 log(MH)), and therefore our optimal regret for SSP is achieved in total computational complexity of O ( T?|S|3|A|2 log2 KT? |S||A|δ ) which is only logarithmic in the number of episodes.

heading: 3.1 Unknown expected optimal cost B?
text: Inspired by techniques for estimation of the SSP-diameter in the adversarial SSP literature [Rosenberg and Mansour, 2020, Chen and Luo, 2021], in Appendix C we show that our reduction does not need to know B? in advance, but can instead estimate it on the fly.
We can obtain a reasonable estimate (up to a constant multiplicative factor) of the cost-to-go from state s by running the Bernstein-SSP algorithm of Rosenberg et al. [2020] for regret minimization in SSPs (that does not need to know B?) with initial state s for roughly T2? |S|
2|A| episodes. Thus, we can apply our reduction while utilizing our first visits to each state in order to estimate its cost-to-go.
We operate in phases where each phase ends when some state is visited at least T2? |S| 2|A| times, and all states that were not visited enough are treated as the goal state. Once we reach a poorly visited state, we simply run an episode of the corresponding Bernstein-SSP algorithm. Notice that this comes at a computational cost that is independent of the number of episodes K (since we use Bernstein-SSP for a small number of episodes), and in Appendix C we show that it achieves similar regret bounds with only an additional additive factor of Õ(T3? |S| 3|A|).

heading: 4 Regret analysis
text: In this section we prove Theorem 3.1. Below we give a high-level overview of the proofs and defer the details to Appendix A. We start the analysis with a regret decomposition that states that the SSP regret can be bounded by the sum of two terms: the expected regret of the finite-horizon algorithm, and the deviation of the actual cost in each interval from its expected value. To that end, we use the notations: M for the total number of intervals, Um = (sm1 , a m 1 , . . . , s m h , a m h , s m H+1) for the trajectory visited in interval m, Cmh for the cost suffered in step h of interval m, π m for the policy chosen by A for interval m, and Ĵπh (s) for the expected finite-horizon cost when playing policy π starting from state s in time step h.
Lemma 4.1. For H = 8T? log(8K), we have the following bound on the regret of Algorithm 1:
RK ≤ R̂A(M) + M∑
m=1
( H∑
h=1
Cmh + ĉf (s m H+1) – Ĵ
πm
1 (s m 1 ) ) + B?. (1)
The bound in Eq. (1) is comprised of two summands and an additional constant. The first summand is an upper bound on the expected finite-horizon regret which we acquire by the admissibility of A (Definition 1). Note that this bound is in terms of the number of intervals M (i.e., the number of finite-horizon episodes) which is a random variable and not necessarily bounded. In what follows we show that, using the admissibility of A, we can actually bound M by the number of SSP episodes K plus a constant that depends on ωA, |S|, |A|, T? (but not on K). The second summand in Eq. (1) relates to the deviation of the total finite-horizon cost from its expected value.
The proof of Lemma 4.1 builds on two key ideas. The first is that, by setting H to be O(T? log K), we ensure that the expected cost of the optimal policy in the SSP modelM is close to that in the finite-horizon model M̂. The second idea is that if the agent does not reach the goal state in a certain interval, then she must suffer the terminal cost in the finite-horizon model. Therefore, although in a single episode there may be many intervals in which the agent does not reach the goal state, we can upper bound the cost in these extra intervals inM by the corresponding terminal costs in M̂. Next, we bound the deviation of the actual cost in each interval from its expected value which appears as the second summand in Eq. (1). The bound is due to the following lemma. Lemma 4.2. Assume that the reduction is performed using an admissible algorithm A. Then, the following holds with probability at least 1 – 3δ/8,
M∑ m=1
( H∑
h=1
Cmh + ĉf (s m H+1) – Ĵ
πm
1 (s m 1 )
) = O (√ (B2? + B?)M log
M δ + HωA|S||A| log MKT?|S||A| δ
) .
The key observation here relies on the notion of unknown state-action pairs – pairs that were not visited at least ωA times. After ωA visits to some state-action pair s, a, we have a reasonable estimate of the next-state distribution P(· | s, a) therefore we can show that the expected accumulated cost in an interval until reaching an unknown state-action pair or the goal state is of order B?. Moreover, the second moment of this cost is of order B2? + B?. Thus, using Freedman inequality, we bound the deviation by Õ( √ (B2? + B?)M), plus a cost of O(H) for each “bad” interval in which we do not reach an unknown state-action pair or the goal state (there are roughly ωA|S||A| such intervals).
Lastly, we need to bound the number of intervals M to obtain a regret bound in terms of K and not M (notice that M is a random variable that is not bounded a-priori). Lemma 4.3. Assume that the reduction is performed using an admissible algorithm A. Then, with probability at least 1 – 3δ/8, M ≤ 4K + 4 · 104|S||A|ωA log(KT?|S||A|ωA/δ).
The proof shows that in every interval there is a constant probability to reach either the goal state or an unknown state-action pair. Leveraging this observation with a concentration inequality, we can bound the number of intervals by Õ(K + ωA|S||A|H).
We can now prove a bound on the regret of Algorithm 1 using any admissible algorithm A.
Proof of Theorem 3.1. The regret bound of A, Lemmas 4.2 and 4.3 all hold with probability at least 1 – δ, via a union bound. Using Lemmas 4.1 and 4.2 we can write
RK ≤ R̂A(M) + O (√
(B2? + B?)M log M δ + HωA|S||A| log MKT?|S||A| δ
) + B?.
Finally, we use Lemma 4.3 to bound M by 4K + 4 · 104|S||A|ωA log(KT?|S||A|ωA/δ).

heading: 5 ULCVI: an admissible algorithm for finite-horizon MDPs
text: In this section we present the Upper Lower Confidence Value Iteration algorithm (ULCVI; Algorithm 2) for regret minimization in finite-horizon MDPs. This result holds independently of our SSP
Algorithm 2 UPPER LOWER CONFIDENCE VALUE ITERATION (ULCVI) 1: input: state space S, action space A, horizon H, confidence parameter δ, terminal costs ĉf and
upper bound on the expected cost of the optimal policy B?. 2: initialize: n0(s, a) = 0, n0(s, a, s′) = 0, N0(s, a) = 0, N0(s, a, s′) = 0 ∀(s, a, s′) ∈ S× A× S. 3: initialize: C0(s, a) = 0, c̄0(s, a) = 0, P̄0(s′|s, a) = I{s′ = s} ∀(s, a, s′) ∈ S× A× S. 4: initialize: PlanningTrigger = true. 5: for m = 1, 2, . . . do 6: observe initial state sm1 . 7: if PlanningTrigger = true then 8: set nm–1(s, a)← Nm–1(s, a), nm–1(s, a, s′)← Nm–1(s, a, s′) ∀(s, a, s′). 9: set P̄m–1(s′|s, a)← n
m–1(s,a,s′) max{1,nm–1(s,a)} , c̄ m–1(s, a)← C m–1(s,a) max{1,nm–1(s,a)} ∀(s, a, s ′).
10: compute {πmh (s)}s,h via OPTIMISTIC-PESSIMISTIC VALUE ITERATION (Algorithm 3). 11: set PlanningTrigger← false. 12: else 13: set nm–1(s, a)← nm–2(s, a), nm–1(s, a, s′)← nm–2(s, a, s′) ∀(s, a, s′) 14: set P̄m–1(s′|s, a)← P̄m–2(s′|s, a), c̄m–1(s, a)← c̄m–2(s, a) ∀(s, a, s′). 15: set πmh (s)← πm–1h (s) for all s ∈ S and h = 1, . . . , H. 16: end if 17: set Nm(s, a)← Nm–1(s, a), Nm(s, a, s′)← Nm–1(s, a, s′), Cm(s, a)← Cm–1(s, a) ∀(s, a, s′). 18: for h = 1, . . . , H do 19: pick action amh = π m h (s m h ). 20: suffer cost Cmh ∼ ĉ(smh , amh ) and observe next state smh+1 ∼ P̂(· | smh , amh ). 21: update visits counters nm(smh , a m h )← nm(smh , amh ) + 1, nm(smh , amh , smh+1)← nm(smh , amh , smh+1) + 1. 22: update accumulated cost Cm(smh , a m h )← Cm(smh , amh ) + Cmh . 23: if Nm(smh , amh ) ≥ 2nm–1(smh , amh ) then 24: set PlanningTrigger← true. 25: end if 26: end for 27: Suffer terminal cost ĉf (smH+1). 28: end for
algorithm. Since the algorithm is similar to previous optimistic algorithms for the finite-horizon setting, e.g., UCBVI [Azar et al., 2017] and ORLC [Dann et al., 2019], we defer the analysis to Appendix B and focus on our technical novelty – bounding the regret in terms of the optimal value function and not the horizon.
In each episode m, the ULCVI algorithm maintains an optimistic lower bound Jmh (s) and a pessimistic upper bound J̄mh (s) on the cost-to-go function of the optimal policy J ? h (s), and acts greedily with respect to the optimistic estimates. These optimistic and pessimistic estimates are computed based on the empirical transition function P̄m–1(s′ | s, a) and the empirical cost function c̄m–1(s, a) to which we add an exploration bonus bmc (s, a) + b m p (s, a), where b m p handles the approximation error in the transitions and bmc handles the approximation error in the costs. The bonuses are defined as follows,
bmc (s, a) =
√ 2Var m–1 s,a (C)Lm
max{1, nm–1(s, a)} + 5Lm max{1, nm–1(s, a)}
(2)
bmp (s, a) =
√ 2VarP̄m–1(·|s,a)(J m h+1)Lm
max{1, nm–1(s, a)} + 62H3B–1? |S|Lm max{1, nm–1(s, a)} + B? 16H2 EP̄m–1(·|s,a)[J̄mh+1(s′) – Jmh+1(s ′)],
where Lm = 3 log(3|S||A|Hm/δ) is a logarithmic factor and nm–1(s, a) is the number of visits to (s, a) in the first m – 1 episodes. Furthermore, Var m–1 s,a (C) is the empirical variance of the observed costs in (s, a) in the first m – 1 episodes.2 Lastly, the term VarP̄m–1(·|s,a)(J m h+1) is the variance of the next state value Jmh+1 from state-action pair (s, a), calculated via the empirical transition model, i.e., VarP̄m–1(·|s,a)(J m h+1) = EP̄m–1(·|s,a)[Jmh+1(s′)2] – EP̄m–1(·|s,a)[Jmh+1(s′)]2.
2The empirical variance of n numbers a1, . . . , an is defined by 1n ∑n i=1 ( ai – 1n ∑n j=1 aj )2.
Algorithm 3 OPTIMISTIC-PESSIMISTIC VALUE ITERATION 1: input: nm–1, P̄m–1, c̄m–1, ĉf , B?. 2: initialize JmH+1(s) = J̄mH+1(s) = ĉf (s) for all s ∈ S. 3: for h = H, H – 1, . . . , 1 do 4: for s ∈ S do 5: for a ∈ A do 6: set the bonus bmh (s, a) = b m c (s, a) + b m p (s, a) defined in Eq. (2).
7: compute optimistic and pessimistic Q-functions:
Qm h (s, a) = c̄m–1(s, a) – bmh (s, a) + EP̄m–1(·|s,a)[Jmh+1(s ′)] Q̄mh (s, a) = c̄ m–1(s, a) + bmh (s, a) + EP̄m–1(·|s,a)[J̄mh+1(s′)].
8: end for 9: πmh (s) ∈ arg mina∈A Q m h (s, a).
10: Jmh (s) = max { Qm h (s,πmh (s)), 0 } , J̄mh (s) = min { Q̄mh (s,π m h (s)), H } . 11: end for 12: end for
For improved computational complexity, we compute the optimistic policy only in episodes in which the number of visits to some state-action pair was doubled. This ensures that the number of optimistic policy computations grows only logarithmically with the number of episodes, i.e., it is bounded by 3|S||A| log(MH). Since each optimal policy computation costs O(H|S|2|A|) in the finite-horizon MDP model, our algorithm enjoys a total computational complexity of O(H|S|3|A|2 log(MH)).
For clarity, we keep the notation of the finite-horizon MDP as M̂ = (S, A, P̂, H, ĉ, ĉf ), and let B? = maxs,h Ĵ?h (s) where Ĵ
π is the value function of policy π (in the case of our SSP reduction this parameter is simply 9B? by Lemma A.1). This implies that ĉf (s) ≤ B? for every s, and for simplicity, we assume that B? ≤ H. Thus, the maximal total cost in an episode is bounded by H + B? ≤ 2H. In Appendix B we prove the following high probability regret bound. Theorem 5.1. ULCVI (Algorithm 2) is admissible with the following guarantees:
(i) With probability at least 1 – δ, the regret bound of ULCVI is R̂ULCVI(M) = O (√ (B2? + B?)|S||A|M log MH|S||A|
δ + H4B–1? |S|
2|A| log3/2 MH|S||A|
δ ) for any number of episodes M ≥ 1.
(ii) ωULCVI = O(H 4B–2? |S|).
Our analysis resembles the one in Efroni et al. [2021], and is adapted to the stationary MDP setting (i.e., the transition function does not depend on the time step h), and to the setting where we have costs instead of rewards, and terminal costs (which do not appear in previous work). By the definition of the algorithm and the regret bound in Theorem 5.1, it is clear that properties (i)-(iii) in Definition 1 of admissible algorithms hold. For property (iv), we use standard concentration inequalities and the definition of the bonuses in Eq. (2) in order to show it holds for ωULCVI = O(H 4B–2? |S|).
To obtain a regret bound whose leading term depends on B? and not H, we start with a standard regret analysis for optimistic algorithms that establishes the regret scales with the square-root of the variance of the value functions of the agent’s policies, i.e.,
R̂ULCVI(M) . √ |S||A| √√√√ M∑ m=1 H∑ h=1 VarP(·|smh ,amh )(J πm h+1) + H 4B–1? |S| 2|A|,
up to logarithmic factors and lower order terms. This can be further bounded by the second moment of the cumulative cost in each episode as follows,
R̂ULCVI(M) . √ |S||A| √√√√√ M∑ m=1 E ( H∑ h=1 Cmh + ĉf (s m H+1) )2 ∣∣∣∣ Ūm  + H4B–1? |S|2|A|,
where Ūm is the sequence of state-action pairs observed up to episode m. Leveraging our techniques for the SSP reduction (but independently), we show that the second moment of the cumulative cost until an unknown state-action pair is reached can be bounded by O(B2? + B?). Therefore, we have at most Õ(H4B–2? |S|
2|A|) episodes in which we bound the second moment trivially by O(H2), and in the rest of the episodes we can bound it by O(B2? + B?). Together this yields the theorem as follows,
R̂ULCVI(M) . √ |S||A| √ (B2? + B?)M + H2 · H4B–2? |S|2|A| . √ (B2? + B?)|S||A|M + H 4B–1? |S| 2|A|.

heading: Acknowledgements
text: This project has received funding from the European Research Council (ERC) under the European Union’sHorizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation(grant number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University

Review summaries:
As the title suggests, this paper established the minimax regret for the stochastic shortest path (SSP) problem. Specifically, given a state space S, action space A, an upper bound B_\star on the total cost of the shortest path, the rate-optimal regret (up to logarithmic factors) with K episodes is of the order \Theta(sqrt((B_\star^2 + B_\star)SAK)). This result improves over the prior result by a factor of sqrt(S) in the upper bound, as well as a factor of sqrt(B_\star) in the lower bound if B_\star < 1. The main contributions of this paper are:   1. The authors proposed a novel black-box reduction from SSP to finite-horizon MDPs, which holds for a general class of finite-horizon MDP regret minimization algorithms.   2. Similar to the celebrated optimistic algorithms, in finite-horizon MDP the authors proposed the ULCVI algorithm for regret minimization, where the key technical novelty is to upper bound the regret in terms of the optimal value function instead of the horizon.   3. For B_\star < 1 the authors also proved a matching minimax lower bound. 

The paper focuses on the problem of stochastic shortest path. The authors provide a regret bound of $\tilde{O}(\sqrt{({B_*}^2+B_*)SAK })$ , which matches the lower bound up to log terms. Besides, the authors show a lower bound of $\Omega(\sqrt{B_* SAK})$ when $B_*< 1$. Their results hold even in the case $B_*$ is unknown.

The paper proposed a novel reduction from stochastic shortest path (SSP) to finite-horizon Markov decision process (MDP). Based on this approach, the paper proposes a model-based algorithm, showing that the minimax regret is $\tilde{O}(\sqrt{(B_{\star}^2+B_{\star})|S||A|K})$, where where $B_{\star}$ is a bound on the expected cost of the optimal policy from any state, $S$ is the state space, and $A$ is the action space. This upper bound attains the lower bound $\Omega(\sqrt{B_{\star}^2|S||A|K})$ for $B_{\star} \ge 1$. The paper also prove a matching lower bound $\Omega(\sqrt{B_{\star}|S||A|K})$ for $B_{\star} < 1$. In addition, the paper provides a new algorithm for regret minimization in finite-horizon MDPs and the regret depends only logarithmically on the horizon length.