Proceedings of Machine Learning Research vol 132:1–22, 2021
32nd International Conference on Algorithmic Learning Theory
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model Jean Tarbouriech
JEAN . TARBOURIECH @ GMAIL . COM
Facebook AI Research Paris & Inria Lille
Matteo Pirotta
PIROTTA @ FB . COM
Facebook AI Research Paris
Michal Valko
VALKOM @ DEEPMIND . COM
arXiv:2604.16111v1 [cs.LG] 17 Apr 2026
DeepMind Paris
Alessandro Lazaric
LAZARIC @ FB . COM
Facebook AI Research Paris Editors: Vitaly Feldman, Katrina Ligett and Sivan Sabato
Abstract We consider the objective of computing an ε-optimal policy in a stochastic shortest path (SSP) setting, provided that we can access a generative sampling oracle. We propose two algorithms for this setting and derive PAC bounds on their sample complexity: one for the case of positive costs and the other for the case of non-negative costs under a restricted optimality criterion. While tight sample complexity bounds have been derived for the finite-horizon and discounted MDPs, the SSP problem is a strict generalization of these settings and it poses additional technical challenges due to the fact that no specific time horizon is prescribed and policies may never terminate, i.e., we are possibly facing non-proper policies. As a consequence, we can neither directly apply existing techniques minimizing sample complexity nor rely on a regret-to-PAC conversion leveraging recent regret bounds for SSP. Our analysis instead combines SSP-specific tools and variance reduction techniques to obtain the first sample complexity bounds for this setting. Keywords: sample complexity, stochastic shortest path, Markov decision process
1. Introduction A common assumption in approximate dynamic programming and reinforcement learning (RL) is to have access to a generative model of the Markov decision process (MDP), that is, a sampling device which can generate samples of the transition and reward functions at any state-action pair. A large body of prior work (Azar et al., 2013; Wang, 2017; Sidford et al., 2018a,b; Zanette et al., 2019; Agarwal et al., 2020; Li et al., 2020) studied how to compute an ε-optimal policy in the infinitehorizon discounted MDP (DMDP) setting with as few calls to the generative model as possible. While the infinite-horizon discounted setting is common in practical RL, many problems are better formalized within the strictly more general1 stochastic shortest-path (SSP) setting (Bertsekas, 1995), where the objective is to compute a policy that minimizes the cost accumulated before reaching a specific goal state. Recently, Tarbouriech et al. (2020a) and Rosenberg et al. (2020) studied the SSP problem in the online case and derived the first regret bounds for this setting. In this paper we focus on the generative model setting and study the problem of computing a near-optimal policy in an SSP problem with a given goal state and cost function. We derive two 1 Any DMDP with discount factor γ can indeed be converted into an SSP problem with the same state space augmented by an artificial termination state that is reached with probability 1 − γ at any time step and state-action pair.
© 2021 J. Tarbouriech, M. Pirotta, M. Valko & A. Lazaric.
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
closely related algorithms for this setting and we prove PAC bounds for their sample complexity. The first algorithm is designed to return an ε-optimal policy for any SSP problem with strictly positive cost function and it has a sample complexity that is adaptive to the (unknown) range of the optimal value function. The second can be used for any cost function, including the case when the cost is zero in some states, for which the optimal policy may not even be proper (i.e., it may never reach the goal yet still minimize the cumulative cost). In this case, we re-frame the objective as computing an ε-optimal solution in the set of (proper) policies that in expectation reach the goal in at most a number of steps that is proportional to the minimum number of expected steps to the goal (i.e., the SSP-diameter of the problem). The main technical challenge in deriving these results is due to the fact that in SSP we have no knowledge of the effective horizon of the problem, unlike in DMDP (with 1/(1 − γ)). As a result, model estimation errors may accumulate indefinitely, thus preventing from achieving any desired level of accuracy. In order to deal with this problem, a first approach is to build on an SSP-specific simulation lemma, which reveals the level of accuracy needed in estimating the MDP to be able to recover proper policies and the role played by the minimum cost. Although this approach yields a bound on the sample complexity, we show that it can in fact be tightened by leveraging and combining SSP-specific tools for regret minimization (Rosenberg et al., 2020) and variance-aware techniques for DMDP sample complexity (Azar et al., 2013).
2. Preliminaries Stochastic shortest path (SSP) We start by introducing the notion of MDP with an SSP objective as done by Bertsekas (1995, Sect. 3). Definition 1 (SSP-MDP) An SSP-MDP is an MDP M := ⟨S, A, g, p, c⟩, where S is the state space with S := |S| states and A is the action space with A := |A| actions. We denote by g ∈ / S the goal state, and we set S ′ := S ∪ {g}. Taking action a in state s incurs a cost of c(s, a) ∈ [0, 1] and the next state s′ ∈ S ′ is selected with probability p(s′ |s, a). The goal state g is absorbing and zero-cost, i.e., p(g|g, a) = 1 and c(g, a) = 0 for any action a ∈ A, which effectively implies that the agent ends its interaction with M when reaching the goal g. We denote by Π := {π : S → A} the set of stationary deterministic policies. For any π ∈ Π and s ∈ S, the random (possibly unbounded) goal-reaching time starting from s is denoted by τπ (s) := inf{t ≥ 0 : st+1 = g | s1 = s, π}. Definition 2 (Proper policy) A policy π is proper if its execution reaches the goal with probability 1 when starting from any state in S. A policy is improper if it is not proper. The set of proper policies is denoted by Πproper . Assumption 1 There exists at least one proper policy, i.e., Πproper ̸= ∅. The value function (also called expected cost-to-go) of a policy π ∈ Π is defined as π
V (s) := E
X +∞
τX π (s) c(st , π(st )) s1 = s = E c(st , π(st )) s1 = s ,
t=1
t=1
2
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
where the expectation is w.r.t. the random sequence of states generated by executing π starting from state s ∈ S. Note that for improper policies π ̸∈ Πproper , V π has at least one unbounded component. Our objective is to find an optimal policy π ⋆ that minimizes the value function. For any vector V ∈ RS , the optimal Bellman operator is defined as n o X LV (s) := min c(s, a) + p(y | s, a)V (y) . (1) a∈A
y∈S
Lemma 1 (Bertsekas and Tsitsiklis, 1991, Prop. 2) Suppose that Asm. 1 holds and that for every ′ improper policy π ′ there exists at least one state s ∈ S such that V π (s) = +∞. Then the optimal ⋆ policy π ⋆ is stationary, deterministic, and proper. Moreover, V ⋆ = V π is the unique solution of the optimality equations V ⋆ = LV ⋆ and V ⋆ (s) < +∞ for any s ∈ S. We define the following quantities: • The SSP-diameter D (Tarbouriech et al., 2020a) is defined as D := max Ds , s∈S
with Ds := min E[τπ (s)]. π∈Π
(2)
• B⋆ := maxs∈S minπ∈Πproper V π (s) is the maximal optimal value function over states. • Γ := maxs,a ∥p(·|s, a)∥0 ≤ S + 1 is the maximal support of p(·|s, a). • Finally, cmin := min(s,a)∈S×A c(s, a) ∈ [0, 1] is the minimum non-goal cost. Note that since the number of states S is finite, Asm. 1 implies that B⋆ ≤ D < +∞. Problem formulation We consider that the costs c are deterministic and known to the learner, while the transition dynamics p is unknown. We assume access to a generative model, which for any state-action pair (s, a) returns a sample drawn from p(·|s, a). We ask the following: How many calls to the generative model are sufficient to compute a near-optimal policy with high probability? On the online-to-batch conversion in the SSP setting Since the problem of learning in SSP has already been studied in the regret-minimization setting (Tarbouriech et al., 2020a; Rosenberg et al., 2020), it may be tempting to leverage a regret-to-PAC conversion to obtain a sample complexity bound and provide a first answer to the question above. For instance, in finite-horizon MDPs, a regret bound can be converted to a PAC guarantee by selecting as a candidate optimal solution any policy chosen at random out of all episodes (Jin et al., 2018). Unfortunately this procedure cannot be applied here. In fact, the SSP-regret differs from the finite-horizon regret, since at each episode it compares the empirical costs accumulated along one trajectory with the optimal value function. Indeed, following K episodes with initial state s0 where for each k ∈ [K] the (possibly non-stationary) policy executed is denoted by πk , we recall that the SSP-regret is defined as (s ) K τπX k 0 hX k=1
i c(sk,h , πk (sk,h )) − K · min V π (s0 ), π∈Πproper
h=1
where sk,h denotes the h-th state visited during episode k and τπk (s0 ) is the (possibly infinite) time it takes the agent to complete episode k. As a result, no guarantee is provided for the value function 3
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
(i.e., the expected cumulative costs) of one episode. Indeed, it has been shown in the existing regret analyses for SSP that explicitly guaranteeing the properness of the deployed policies is not an intermediate step that is required to derive the regret bounds. SSP-regret algorithms may change multiple policies within each episode and none of them may actually be proper (i.e., they may have an unbounded value function, so that there exists a state s such that V π (s) = +∞). As such, it is unclear which policy should be retained as a solution candidate. Finally, the near-optimal guarantees we intend to achieve are for any arbitrary initial state in S, while regret-style guarantees are only in expectation with respect to a starting state distribution. Distinction of cases depending on cmin Our analysis considers two distinct cases, cmin > 0 and cmin = 0, for which it targets different notions of sample complexity. First case: sample complexity objective for cmin > 0 When the cost function is strictly positive, the conditions of Lem. 1 hold, so the optimal policy is guaranteed to be proper. We seek to achieve the following standard PAC guarantees. Definition 3 We say that an algorithm is (ε, δ)-optimal with sample complexity n, if after n calls to the generative model it returns a policy π that verifies ∥V π − V ⋆ ∥∞ ≤ ε with probability at least 1 − δ. We denote by S AMP C OMP(ε) the corresponding sample complexity n. Second case: sample complexity objective for cmin = 0 The case of zero minimum cost is a complex SSP problem where the optimal policy may not even be guaranteed to be proper (Bertsekas, 1995). In this case, it is unclear whether the sample complexity of Def. 3 may even be bounded, since estimation errors may propagate indefinitely. On the other hand, we seek ε-optimality guarantees w.r.t. a set of proper policies. Definition 4 (Restricted set Πθ ) For any θ ∈ [1, +∞], we define the set Πθ := {π ∈ Π : ∀s ∈ S, E[τπ (s)] ≤ θDs }. Notice that Π+∞ = Π. Moreover, for any θ ∈ [1, +∞), Πθ only contains proper policies, i.e., Πθ ⊆ Πproper . Similar to Def. 3, we then reformulate the desired notion of optimality. Definition 5 We say that an algorithm is (ε, δ, θ)-optimal with sample complexity n, if after n calls to the generative model it returns a policy π that verifies ∥V π − Vθ⋆ ∥∞ ≤ ε with probability at least 1 − δ, where Vθ⋆ = minπ∈Πθ V π is the optimal value function restricted to policies in Πθ . We denote by S AMP C OMP(ε, θ) the corresponding sample complexity n. While alternative definitions of restricted set may be introduced, we believe that Def. 4 is well-suited for our problem, as it defines the restriction w.r.t. Ds , a cost-independent quantity describing the difficulty of navigating in the SSP-MDP (Eq. 2). Nonetheless, this poses an additional layer of complexity, since Ds is unknown to the agent, which only receives θ as additional parameter.
3. A first approach: Simulation Lemma for SSP We begin by stating a general simulation lemma tailored to SSP which is a useful component to derive sample complexity bounds. For any model p and any η > 0, we introduce the set of models close to p as follows n o ′ ′ Pη(p) := p′ ∈ RS ×A×S : ∀(s, a) ∈ S ′ × A, p′ (·|s, a) ∈ ∆(S ′ ), ∥p(·|s, a) − p′ (·|s, a)∥1 ≤ η . 4
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
(p)
Up to a slight difference in the way the set Pη is defined, leveraging the result of Tarbouriech et al. (2020b, App. C) yields the following guarantee (see App. C). (p)
Lemma 2 (Simulation Lemma for SSP) Consider any η > 0 and any two models p and p′ ∈ Pη such that, for each model, there exists at least one proper policy w.r.t. the goal state g. Consider a cost function such that cmin > 0. Consider any policy π that is proper in p′ , with value function denoted by Vπ′ , such that the following condition is verified η∥Vπ′ ∥∞ ≤ 2cmin .
(3)
Then π is proper in p (i.e., its value function verifies Vπ < +∞ component-wise), and we have 2η∥Vπ′ ∥∞ ∀s ∈ S, Vπ (s) ≤ 1 + Vπ′ (s), cmin and conversely, ∀s ∈ S, Vπ′ (s) ≤
η∥Vπ′ ∥∞ 1+ Vπ (s). cmin
Combining the two inequalities above yields ∥Vπ − Vπ′ ∥∞ ≤
7η∥Vπ′ ∥2∞ · cmin
For comparison let us now recall the classical simulation lemma for discounted MDPs. Lemma 3 (Simulation Lemma for DMDP, see e.g., Kearns and Singh, 2002) Consider any two (p) models p and p′ ∈ Pη for any η > 0. Consider as value function expected discounted Pin p the t r(s , π(s )) | s = s ; cumulative reward, i.e., for any policy π and state s ∈ S, Vπ (s) := E +∞ γ t t 1 t=1 and Vπ′ is the value function in p′ . Suppose that the instantaneous rewards are known and bounded in [0, 1]. Then for any policy π, we have η ′ ∥Vπ − Vπ ∥∞ ≤ O · (1 − γ)2 We spell out the key differences between the simulation lemma in the discounted setting (Lem. 3) and in SSP (Lem. 2), bringing to light the criticalities in the latter setting. First, a guarantee can only be obtained if the condition (3) is verified, which involves both the accuracy η and the value function of (p) π in p′ ∈ Pη . We observe that the smaller the minimum cost cmin , the smaller the accuracy η needs to be. Importantly, cmin must be positive and the error scales inversely with it. Indeed, the “trajectory length” is captured not by a known hyperparameter 1/(1 − γ) as in DMDPs, but by the ratio between the (a priori unknown) infinity norm of the value function of the policy and the minimum cost cmin (note that this ratio indeed has a time dimension and it upper bounds the expected goal-reaching time of the policy since ∥E[τπ ]∥∞ ≤ ∥Vπ ∥∞ /cmin ). Similar to existing approaches in DMDP, we could leverage the simulation lemma to directly derive sample complexity guarantees. More precisely, building on the result of Lem. 2 and plugging
5
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
it in the algorithms proposed in Sect. 4 would eventually lead to sample complexities scaling as ! 4 ΓSA 2S2A B B ⋆ ⋆ e , (4) S AMP C OMP(ε) = O + cmin ε c2min ε2 ! 2 D 2 B 4 ΓSA 2S2A θ θDB ⋆ ⋆ e S AMP C OMP(ε, θ) = O + . (5) ε4 ε2 In the following section, we will show that these two bounds can in fact be improved by refining the guarantee of Lem. 2 thanks to variance-aware arguments (as also leveraged by e.g., Azar et al., 2013; e −2 ) Rosenberg et al., 2020). Notably, it will enable to shave off a B ⋆ /cmin dependency in the O(ε main-order term of Eq. 4 for the first case of cmin > 0 (see Thm. 1). Furthermore, in the case of e −4 ) to O(ε e −3 ) (see Thm. 2). cmin = 0, the dependency on ε in Eq. 5 will be reduced from O(ε
4. Main Result We first illustrate the common structure of our algorithms. As an input, we receive a desired accuracy ε ∈ (0, 1), the confidence level δ ∈ (0, 1], and the cost function c ∈ [0, 1]. Since the model p is unknown, akin to Azar et al. (2013) for DMDPs, we collect transition samples from the generative model and we use them to compute an estimate pb by simply evaluating the frequency of transitions from each state-action pair s, a to any state s′ . In particular, we rely on a carefully tuned function to determine the number of transition samples that should be collected for every state-action pair. For some positive values of X and y, we introduce the allocation function2 ! b b X 3Γ XSA X 2S XSA X 2Γ XSA , ϕ(X, y) := α · log + log + 2 log2 (6) yε2 yεδ yε yεδ y yδ b := maxs,a ∥b where α > 0 is a numerical constant and Γ p(·|s, a)∥0 ≤ Γ is the largest support of pb. Let us now consider that the conditions of Lem. 1 hold. A standard approach would then be c = ⟨S, A, g, pb, c⟩ and return the to execute SSP-value iteration (VI) on the estimated SSP-MDP M corresponding optimal policy π b. While this approach is effective in DMDPs and finite-horizon problems, it may fail in the SSP setting. In fact, the estimated SSP-MDP may not even admit a proper optimal policy and deriving guarantees on the actual value of π b (i.e., V πb ) may not be possible. As c, we rather execute an extended value iteration such, instead of solving the estimated SSP-MDP M (EVI) scheme tailored to SSP problems, which can be run efficiently as shown by Tarbouriech et al. (2020a). As detailed in App. B, EVI for SSP constructs confidence intervals for pb and builds a f = ⟨S, A, g, pe, c⟩, where pe belongs to the confidence intervals and is chosen suitable SSP-MDP M so that the corresponding optimal policy π e is optimistic w.r.t. to the optimal policy π ⋆ of M . More formally, let us now consider that our SSP-MDP at hand has a strictly positive cost function c (which entails that the conditions of Lem. 1 hold), and consider a set N of samples collected so far as well as a VI precision level µVI > 0. Then EVI(N , c, µVI ) outputs an optimistic value vector ve and an optimistic policy π e that is greedy w.r.t. ve. Note that here (as opposed to Tarbouriech et al., 2020a), we consider Bernstein-based concentration inequalities for EVI, as it is done by Rosenberg et al. (2020) as well as in average-reward EVI by Fruit et al. (2020). The crucial advantage of EVI w.r.t. VI 2
The actual choice of X and y is algorithm-specific and it is illustrated later.
6
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Algorithm 1: Algorithm for cmin > 0 Input: cost function c with minimum cost cmin > 0, accuracy ε > 0, confidence level δ ∈ (0, 1), allocation function ϕ(·, ·). π e := SEARCH(c). Output: the policy π e. Algorithm 2: SEARCH Input: A positive cost function c′ . Set ι := mins,a c′ (s, a) the minimum cost of c′ . Set ∆ := 12 and continue = True, sample set N = ∅. while continue do Set ∆ ← 2∆. Add samples obtained from the generative model to N until ϕ(∆, ι) samples are available at each state-action pair. ιε Compute (e v, π e) := EVI N , c′ , µVI := 6∆ with N the samples collected so far. if ∥e v ∥∞ ≤ ∆ then continue = False. end end Output: the policy π e. f. Indeed its value function in the optimistic run on the estimated SSP-MDP is that π e is proper in M model pe, denoted by Ve πe , is bounded with high-probability. This is shown by the following lemma (which stems from Tarbouriech et al., 2020a, Lem. 4 & App. E), where we denote by V ⋆ (resp. Ve ⋆ ) the optimal value function in the true model p (resp. optimistic model pe). Lemma 4 For any cost function c ≥ cmin > 0, let (e v, π e) = EVI(N , c, µVI ). Then with high ⋆, v probability, we have the component-wise inequalities v e ≤ V e ≤ Ve ⋆ ≤ Ve πe , and if the VI precision 2µVI e πe level verifies µVI ≤ cmin e. 2 , then V ≤ 1 + cmin v We are now ready to detail our algorithms. 4.1. Strictly Positive Cost Function When cmin > 0, we seek to achieve the standard PAC guarantees of Def. 3. The algorithm is reported in Alg. 1. Since no prior knowledge about the optimal policy is available, the algorithm’s subroutine SEARCH (Alg. 2) relies on a doubling scheme to guess the range of the optimal value function B⋆ . Starting with ∆ = 1, we use the allocation function ϕ to determine a sufficient number of samples to compute an ε-optimal policy if the range of the optimal policy was smaller than ∆. We then test whether ∆ is indeed a valid upper bound on the range of the optimistic value returned by EVI and, relying on Lem. 4, we stop whenever the test is successful and return π e. Otherwise, we double the guess ∆ and reiterate. Since ϕ is increasing in its first argument, the total number of samples required at iteration is also increasing.
7
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Theorem 1 For any accuracy ε ∈ (0, 1], confidence δ ∈ (0, 1), and cost function c in [cmin , 1], with cmin > 0, Algorithm 1 (with the allocation function of Eq. 6) is (ε, δ)-optimal with a sample complexity bounded as follows ! 3 ΓSA 2S2A 2 ΓSA B B B ⋆ e S AMP C OMP(ε) = O + ⋆ + ⋆2 . cmin ε2 cmin ε cmin Proof sketch Throughout we assume that the standard high-probability event of satisfied concentration inequalities holds (Lem. 5). The analysis starts by showing that enough samples per state-action pair are available to guarantee that the candidate optimistic policy π e is proper not only in the optimistic model pe but also in the true model p. This is proved by applying the simulation lemma for SSP of Lem. 2. Hence, the value functions in the true and optimistic models, denoted by V πe and Ve πe respectively, are each bounded component-wise and close enough up to a multiplicative constant. Moreover, by optimism and choice of VI accuracy µVI , we obtain that Ve πe ≤ V ⋆ + O(ε) componentwise. In addition we can prove that the doubling scheme of Alg. 1 guarantees that ∆ ≤ 2B⋆ . Putting everything together implies two important properties: (i) it holds that ∥V πe ∥∞ = O(B⋆ ), and (ii) it is sufficient to bound V πe − Ve πe in order to obtain the sought-after guarantee of Def. 3. To do so, subtracting the two respective Bellman equations yields X V πe (s) − Ve πe (s) = p(y|s, π e(s))(V πe (y) − Ve πe (y)) + W (s), y∈S
where we introduce W (s) :=
X
(p(y|s, π e(s)) − pe(y|s, π e(s)))Ve πe (y).
y∈S
Let us denote by Qπe ∈ RS×S the transition matrix between the non-goal states under policy π e in ′ π e ′ ′ the true model p (i.e., for any (s, s ) ∈ S, Q (s, s ) := p(s |s, π e(s))). Since π e is proper in p, Qπe is π e strictly substochastic which implies that the matrix (I − Q ) is invertible, and therefore we have +∞ h i h i X π e π e −1 e V (s) − V (s) = (I − Q ) W = Eπe,p 1st ̸=g W (st ) |s0 = s . π e
s
(7)
t=0
We now apply variance-aware arguments, similar to e.g., Azar et al. (2013, 2017); Rosenberg et al. (2020); Fruit et al. (2020), in order to decompose W (st ) and thus obtain V πe (s) − Ve πe (s) ≤ ➊ + ➋ + ➌, with s
+∞ h i X b p e Γ ➊=O Eπe,p 1st ̸=g V(st ) , n t=0 s +∞ X b p e Γ cmin ∆ ➋=O Pπe,p (st ̸= g), n t=0 ! +∞ X ∆S e ➌=O Pπe,p (st ̸= g) , n t=0
8
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
where n denotes the minimum number of samples collected at each state-action pair and where we b := maxs,a ∥b define the empirical branching factor Γ p(·|s, a)∥0 ≤ Γ as well as the following variance quantity !2 X X V(st ) := p(s′ |st , π e(st )) Ve πe (s′ ) − p(s′′ |st , , π e(st ))Ve πe (s′′ ) . s′ ∈S ′
s′′ ∈S
The series that appears in the terms ➋ and ➌ is bounded by leveraging the exponential decay of the probability of not reaching the goal w.r.t. the time step t, i.e., cmin t Pπe,p (st ̸= g) = O exp − πe . (8) ∥V ∥∞ Furthermore, the series appearing in term ➊ is split by the Cauchy-Schwarz inequality and by the time step decomposition of Rosenberg et al. (2020) into intervals that are carefully constructed so that the expected variance V accumulated over a whole interval is adequately bounded. Ultimately, there remains to invert the equation ➊ + ➋ + ➌ ≤ ε w.r.t. n in order to obtain a lower bound on n. High-level connection to DMDP analysis Here we point out a high-level parallel with the DMDP analysis of Azar et al. (2013). Recall h informally thati the latter analysis handles sums of the sort P+∞ t π b −1 (I − γP ) W s = t=0 γ Eπb,p W (st ) |s0 = s , for different yet related quantities W . In contrast, the SSP setting does not display a natural discount factor in the Bellman equations (γ = 1 in Eq. 1). Instead, the “shrinking” of summands in Eq. 7 is captured by the indicator 1st ̸=g , which is an unknown, time-dependent, state-dependent and policy-dependent quantity. Crucially, we obtain that its expectation displays an exponential decay similar to the γ t -phenomenom observed in DMDPs, specifically Eq. 8. As such, we can argue that any proper policy π in SSP displays a pseudo-discounting property with rate γπ ∼ exp (−cmin /∥V π ∥∞ ) < 1. Despite this interesting connection with the DMDP analysis, note that one cannot simply plug in the DMDP analysis for the SSP setting considered here (recall that DMDPs are a subclass of SSP-MDPs, not the other way around). In fact, we need to consider SSP-specific analytical tools to handle the upper bounding of Eq. 7 (e.g., interval decomposition) as alluded to above and detailed in App. D. 4.2. Any Cost Function and Restricted Optimality Whenever cmin = 0, Alg. 1 has a possibly unbounded sample complexity. To handle this, we add a small perturbation to all the costs (denoted by ν) during the computation of the optimistic policies. Note that this perturbation technique is also employed by e.g., Bertsekas and Yu (2013); Tarbouriech et al. (2020a); Rosenberg et al. (2020). Executing Alg. 1 with the modified cost function would directly return a policy that is ε-optimal w.r.t. the optimal policy of the SSP-MDP with perturbed cost. Nonetheless, this is not a significant guarantee, since it does not say anything about the performance of the policy in the original SSP-MDP. For this reason, we rather derive ε-optimality guarantees w.r.t. a set of restricted policies, as discussed in Sect. 2. Note that Def. 5 involves the unknown quantities {Ds }s∈S . In fact, in order to properly tune the cost perturbation ν and return an ε-optimal policy, b the SSP-diameter. This requires an additional initial phase we need to compute an upper bound D to perform such estimation step. We explain the procedure in App. C.1 (Alg. 4) and show that the amount of samples used in this initial phase is subsumed in the final sample complexity bound by the second phase where we compute the final candidate policy. 9
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Algorithm 3: Algorithm for θ < +∞ Input: slack parameter θ ≥ 1, accuracy ε > 0, confidence level δ ∈ (0, 1), cost function c, allocation function ϕ(·, ·). b an upper bound estimate of the SSP-diameter (see Alg. 4 of App. C.1). First compute D Set cost perturbation ν = ε b . 2θD π e = SEARCH(c ∨ ν). Output: the policy π e. The second phase is basically the same as in Alg. 1 except for the perturbation on the original cost function by ν and a slightly different precision level µVI . The analysis simply applies Thm. 1 in the perturbed model and leverages the optimality restriction of Def. 4 to control the bias induced by the cost perturbation (see App. E). We obtain the following sample complexity guarantees. Theorem 2 For any accuracy ε ∈ (0, 1], confidence δ ∈ (0, 1), cost function c in [0, 1], and slack parameter θ ≥ 1, Algorithm 3 (with the allocation function of Eq. 6) is (ε, δ, θ)-optimal with a sample complexity bounded as follows ! 3 ΓSA 2A 2 D 2 B 2 ΓSA θDB θDB S θ ⋆ ⋆ ⋆ e S AMP C OMP(ε, θ) = O + + . ε3 ε2 ε2 In Thm. 2 the slack parameter θ ≥ 1 is implicitly considered as a bounded constant which implies that Πθ ⊊ Π. It is possible to link θ to the accuracy ε, by for example instantiating θ = ε−1 . In this e −4 )), we obtain an special case, at the cost of a worse dependency on ε for Thm. 2 (namely, in O(ε ε-accurate guarantee w.r.t. the optimal proper policy as ε tends to 0, since limε→0 Πε−1 = Π.
5. Discussion In this section we discuss the bounds obtained in Thm. 1 and 2 and compare them with existing bounds in related settings. First, let us consider the unit-cost case (cmin = 1). In this case, it is easy to show that the sample complexity is lower-bounded as Ω(SA(B⋆ )3 /ε2 ). In fact, the inclusion DMDP ⊂ SSP-MDP, and the mapping 1/(1 − γ) = B⋆ in the unit-cost case (see footnote1 ), allows us to directly inherit the lower bound of Azar et al. (2013) in DMDPs, which scales as Ω(SA/(1 − γ)3 ε2 ). This shows that in this case, the sample complexity in Thm. 1 matches the lower bound in the ε, A and B⋆ terms. As for the dependency on the state space, our bound scales as ΓS with Γ ∈ [1, S + 1] the maximal branching factor. While in many environments Γ = O(1) as long as the dynamics are not too chaotic, ΓS may scale with S 2 in the worst case. This possibly quadratic dependency in S is worse than the linear dependency for sample complexity in DMDPs with a generative model (Azar et al., 2013). This bound mismatch is also present between SSP-MDP and finite-horizon in the regret minimization framework, where no-regret algorithms for SSP (Tarbouriech √ et al., 2020a; Rosenberg et al., 2020) e scale as O(S), which contrasts with the lower bound in S derived by Rosenberg √ et al. (2020) and with regret bounds in finite-horizon (e.g., Azar et al., 2017) which match the S lower bound. How to improve the state dependency for the SSP setting remains an open question, whether it be in the regret minimization or sample complexity setting. Note that the ΓS dependency stems from 10
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
the analysis estimating the transition kernel accurately well across the state-action space. As an immediate byproduct, this implies that after its sample collection phase, each algorithm Alg. 1 or 3 can actually guarantee ε-optimal planning for any cost function in [cmin , 1], respectively where cmin > 0 (Thm. 1) and where cmin = 0 with θ < +∞ (Thm. 2). The role of the effective horizon H in finite-horizon or 1/(1−γ) in DMDPs is captured in the SSP setting by the ratio B⋆ /cmin (when cmin > 0). Compared to the application of the simulation lemma for SSP (Lem. 2), the use of variance-aware techniques succeeds in shaving off a term B⋆ /cmin in the main order term of the sample complexity. Our analysis combines techniques on regret minimization for the SSP problem (Rosenberg et al., 2020) and on sample complexity of DMDPs with a generative model (Azar et al., 2013). The latter work removes a factor 1/(1 − γ), with γ < 1 the discount factor. As we fleshed out in our analysis, the role of the discount factor γ in DMDPs is implicitly captured in SSP by the policy-dependent indicator 1{st ̸=g} , whose expectation decays exponentially w.r.t. the time t with rate scaling as exp (−cmin /B⋆ ) < 1. Recall that this high-level parallel between the SSP-MDP and DMDP settings is not surprising insofar as, more generally, DMDPs are a subclass of SSP-MDPs (Bertsekas, 1995). We can wonder whether the cmin dependency is unavoidable or not in the sample complexity result of Thm. 1 for the case cmin > 0. While we do not have a definite answer, we can investigate the question by drawing a high-level analogy with √setting. Taking the regret of UCBVI P the finite-horizon (Azar et al., 2017) in the stationary case k (V πk − V ⋆ ) ≤ H 2 SAK, and performing a regretto-PAC conversion, we notice that to obtain V π − V ⋆ ≤ ε, we require K ′ ≈ H 2 SA/ε2 episodes and hence HK ′ time steps of sample complexity, since each episode accounts for H interactions with the environment. We thus see that the dependency in H 3 = H 2 H can be decomposed as H 2 capturing the range of the value function, and another H capturing the length of an episode. Now by analogy, pretending such a regret-to-PAC conversion works in SSP (which we recall from Sect. 2 is not the case), we would obtain the dependency B⋆2 (B⋆ /cmin ), because the range of the optimal value function is B⋆ while the characteristic length of an optimal episode scales as B⋆ /cmin in the worst case. This reasoning provides an intuitive support to our conjecture that the lower bound must contain a dependency on the characteristic length of an optimal episode which in the worst case scales as B⋆ /cmin . It remains an open question whether it is possible or not to construct a lower bound problem explicitly displaying the critical role of cmin . Finally, the bound of Thm. 1 inherits e −2 ) dependency, when cmin is considered as a positive constant. On the other hand, Thm. 2 a O(ε e −3 ), and the can cope with very small (or even zero-valued) cmin , yet the bound worsens to O(ε performance becomes restricted to policies with not too large expected goal-reaching time (via the slack parameter θ). This interesting behavior does not appear in the finite-horizon or discounted case (where the range of rewards has no influence on the rate in ε), and it captures the key role of the minimum cost played in the behavior of the optimal goal-reaching policy: the more the minimum cost is allowed to be small, the longer the duration of the trajectory to reach the goal may be, thus the harder it is analysis-wise to control the trajectory variations of a policy between two models.
11
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
R EFERENCES Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67–83. PMLR, 2020. Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3): 325–349, 2013. Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 263–272. JMLR. org, 2017. Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995. Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathematics of Operations Research, 16(3):580–595, 1991. Dimitri P Bertsekas and Huizhen Yu. Stochastic shortest path problems under weak conditions. Lab. for Information and Decision Systems Report LIDS-P-2909, MIT, 2013. Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved analysis of UCRL2 with empirical bernstein inequality. arXiv preprint arXiv:2007.05456, 2020. Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient? In NeurIPS, pages 4868–4878, 2018. Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning Adversarial MDPs with Bandit Feedback and Unknown Transition. In International Conference on Machine Learning, pages 4860–4869. PMLR, 2020. Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi, and Benjamin Van Roy. Conservative contextual linear bandits. In Advances in Neural Information Processing Systems, pages 3910– 3919, 2017. Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2-3):209–232, 2002. Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. In Advances in Neural Information Processing Systems, volume 33, pages 12861–12872, 2020. Aviv Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pages 8210–8219. PMLR, 2020. Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pages 5186–5196, 2018a. 12
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770–787. SIAM, 2018b. Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference on Machine Learning, pages 9428–9437. PMLR, 2020a. Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Improved sample complexity for incremental autonomous exploration in mdps. In Advances in Neural Information Processing Systems, volume 33, pages 11273–11284, 2020b. Mengdi Wang. Randomized linear programming solves the discounted markov decision problem in nearly-linear running time. arXiv preprint arXiv:1704.01869, 2017. Andrea Zanette, Mykel J Kochenderfer, and Emma Brunskill. Almost horizon-free structure-aware best policy identification with a generative model. In Advances in Neural Information Processing Systems, pages 5626–5635, 2019.
13
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Appendix A. High-probability Event Here we characterize the high-probability event, denoted by E. Throughout the remainder of the analysis, we will assume that E holds. Lemma 5 Denote by E the event under which for any time step t ≥ 1 and for any state-action pair (s, a) and next state s′ , it holds that s 28 log SANt+ (s,a) + ′ δ SANt (s, a) pbt (s |s, a) + |b pt (s′ |s, a) − p(s′ |s, a)| ≤ 4 log , (9) + + δ Nt (s, a) Nt (s, a) where Nt+ (s, a) := max{1, Nt (s, a)} with Nt the state-action counts accumulated up to (and including) time t. Then we have P(E) ≥ 1 − δ. Proof The confidence intervals in Eq. 9 are constructed using the empirical Bernstein inequality, which guarantees that P(E) ≥ 1 − δ, see e.g., Rosenberg et al. (2020); Fruit et al. (2020).
Appendix B. Extended Value Iteration for SSP Here we briefly recall how to perform an extended value iteration (EVI) scheme tailored to SSP, as explained by Tarbouriech et al. (2020a). Note that we leverage a Bernstein-based construction of confidence intervals, as done by e.g., Fruit et al. (2020); Rosenberg et al. (2020). Formally, we consider as input any SSP-MDP instance M (cf. Def. 1) with cost function c lower bounded by cmin > 0, a set N of samples collected so far (with corresponding state-action counters denoted by N ) and a VI precision level µVI > 0. We now detail what the scheme EVI(N , c, µVI ) does and outputs. First it computes a set of plausible SSP-MDPs defined as X M := {⟨S, A, g, pe, c⟩ | pe(g|g, a) = 1, pe(s′ |s, a) ∈ B(s, a, s′ ), pe(s′ |s, a) = 1}, s′ ∈S ′
where for any (s, a) ∈ S × A, B(s, a, s′ ) is a high-probability confidence set on the dynamics of the true SSP-MDP M . Specifically, we define the compact sets B(s, a, s′ ) := [b p(s′ |s, a) − β(s, a, s′ ), pb(s′ |s, a) + β(s, a, s′ )] ∩ [0, 1], where β(s, a, s′ ) denotes the right hand side of Eq. 9. From Lem. 5 the choice of β(s, a, s′ ) guarantees that M ∈ M with probability at least 1 − δ. Once M has been computed, the scheme applies extended value iteration (EVI) to compute a policy with lowest optimistic value. Formally, it defines the extended optimal Bellman operator Le such that for any vector ve ∈ RS and non-goal state s ∈ S, n o X ev (s) := min c(s, a) + min Le pe(s′ |s, a)e v (s′ ) . a∈A
pe∈B(s,a)
s′ ∈S
evi . For the predefined VI precision We consider an initial vector ve0 := 0 and set iteratively vei+1 := Le µVI > 0, the stopping condition is reached for the first iteration j such that ∥e vj+1 − vej ∥∞ ≤ µVI . The policy π e is then selected to be the optimistic greedy policy w.r.t. the vector vej . While vej is not the value function of π e in the optimistic model pe, which we denote by Ve πe , both quantities can be related according to Lem. 4. 14
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Appendix C. Useful Results (p)
Proof of Lem. 2 Although we consider here a slightly different Pη set, the result is almost identical to Tarbouriech et al. (2020b, App. C). For completeness, we report the full derivation here. The analysis follows the proof of Rosenberg et al. (2020, Lem. B.4) whose result can be seen as a special case of Lem. 2. First, let us assume that π is proper in the model p′ . This implies that its value function, denoted by V ′ , is bounded component-wise. Moreover, for any state s ∈ S, the Bellman equation holds as follows X V ′ (s) = c(s, π(s)) + p′ (y|s, π(s))V ′ (y) y∈S
= c(s, π(s)) +
X
p(y|s, π(s))V ′ (y) +
y∈S
X
p′ (y|s, π(s)) − p(y|s, π(s)) V ′ (y).
(10)
y∈S (p)
By successively using Hölder’s inequality and that p′ ∈ Pη and c(s, π(s)) ≥ cmin , we get η∥V ′ ∥∞ V ′ (s) ≥ c(s, π(s)) − η∥V ′ ∥∞ + p(·|s, π(s))⊤ V ′ ≥ c(s, π(s)) 1 − + p(·|s, π(s))⊤ V ′ . cmin −1 ′∥ ∞ V ′ . Then for all s ∈ S, Let us now introduce the vector V ′′ := 1 − η∥V cmin V ′′ (s) ≥ c(s, π(s)) + p(·|s, π(s))⊤ V ′′ . Hence, from Lem. 6, π is proper in p (i.e., V < +∞), and we have η∥V ′ ∥∞ ′′ V ≤V ≤ 1+2 V ′, cmin
(11)
1 where the last inequality stems from condition (3) and the fact that 1−x ≤ 1 + 2x holds for any 1 0 ≤ x ≤ 2 . Conversely, analyzing Eq. 10 from the other side, we get η∥V ′ ∥∞ ′ V (s) ≤ c(s, π(s)) 1 + + p(·|s, π(s))⊤ V ′ . cmin −1 ′∥ ∞ Let us now introduce the vector V ′′ := 1 + η∥V V ′ . Then cmin
V ′′ (s) ≤ c(s, π(s)) + p(·|s, π(s))⊤ V ′′ . We then obtain in the same vein as Lem. 6 (by leveraging the monotonicity of the Bellman operator Lπ U (s) := c(s, π(s)) + p(·|s, π(s))⊤ U ) that V ′′ ≤ V , and therefore η∥V ′ ∥∞ V′ ≤ 1+ V. (12) cmin Combining Eq. 11 and 12 yields component-wise ∥V − V ′ ∥∞ ≤ 2
η∥V ′ ∥∞ ′ η∥V ′ ∥∞ η∥V ′ ∥2∞ ∥V ∥∞ + ∥V ∥∞ ≤ 7 , cmin cmin cmin 15
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
where the last inequality stems from plugging condition (3) into Eq. 11. Note that here p and p′ play symmetric roles; we can perform the same reasoning in the case where π is proper in the model p and it would yield an equivalent result by switching the dependencies on V and V ′ .
Lemma 6 (Bertsekas and Tsitsiklis, 1991, Lem. 1) Consider an SSP instance under the conditions of Lem. 1. Let π be any policy, then P • If there exists a vector U : S → R such that U (s) ≥ c(s, π(s)) + s′ ∈S p(s′ |s, π(s))U (s′ ) for all s ∈ S, then π is proper, and V π the value function of π is upper bounded by U component-wise, i.e., V π (s) ≤ U (s) for all s ∈ S. • If π is proper, then itsP value function V π is the unique solution to the Bellman equations π V (s) = c(s, π(s)) + s′ ∈S p(s′ |s, π(s))V π (s′ ) for all s ∈ S. We now state a useful result which showcases the exponential decay of the goal-reaching probability of a proper policy with component-wise bounded value function. Lemma 7 (Rosenberg et al., 2020, Lem. B.5) Let π be a proper policy such that for some d > 0, V π (s) ≤ d for every non-goal state s. Then the probability that the cumulative cost of π to reach the goal state from any state s is more than m, is at most 2e−m/(4d) for all m ≥ 0. Note that a cost of at most m implies that the number of steps is at most m/cmin . We finally spell out an important property stemming from optimism. Lemma 8 Under the event E, we have Ve ≤ V ⋆ + 3ε component-wise. Proof Denote by ve the VI vector output by the computation of the candidate policy π e via EVI. min FromLem. 4 and by the choice of the VI precision µVI := εc6∆ , we have component-wise that 2µ Ve ≤ 1 + VI ve ≤ V ⋆ + ε ve ≤ V ⋆ + ε since ve ≤ ∆ by construction of Alg. 2. cmin
3∆
3
C.1. Procedure to Estimate an Upper Bound of the SSP-Diamater Lemma 9 (D- SUBROUTINE) With probability at least 1 − δ, the D SUBROUTINE (Alg. 4): e D2 ΓSA/ε2 + DS 2 A/ε , • has a sample complexity bounded by O • requires at most log2 (D(1 + ε)) + 1 inner iterations, b that verifies D ≤ D b ≤ (1 + 2ε(1 + ε))(1 + ε)D. • outputs a quantity D b SUBROUTINE. Throughout the remainder of the proof, we We now delve into the analysis of the Dwill assume that the event E holds. We now give a useful statement stemming from optimism. b SUBROUTINE, denote by ve the vector computed using EVI for Lemma 10 At any stage of the DSSP (App. B). Then under the event E, we have component-wise (i.e., starting from any non-goal state) that ve ≤ minπ Vpπ ≤ D. 16
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Algorithm 4: D-S UBROUTINE Input: accuracy ε > 0, confidence level δ ∈ (0, 1). Set W := 12 and ∥e v ∥∞ := 1. while ∥e v ∥∞ > W do Set W ← 2W . Set the accuracy η := Wε . Collect additional samples until pb ∈ Pη/2 with confidence level δ (we verify this using the Bernstein upper bound of Eq. 9) Compute (e v , ) := EVI N , c = 1, µVI := 2ε . end b := (1 + 2η∥e Output: the optimistic quantity D v ∥∞ )∥e v ∥∞ .
Proof The first inequality stems from Lem. 4 while the second inequality uses the definition of the SSP-diameter D and the fact that the considered costs are equal to 1. We now prove Lem. 9. Denote by i the iteration index of the subroutine (starting at i = 1), so that Wi = 2i . Introduce j := min{i ≥ 1 : ∥e vi ∥∞ ≤ Wi }. By choice of each optimistic model, we have ∥e vi ∥∞ ≤ D at any iteration i ≥ 1 from Lem. 10. Since (Wi )i≥1 is a strictly increasing sequence, the subroutine is bound to end in a finite number of iterations (i.e., j < +∞), and given that Wj−1 ≤ ∥e vj−1 ∥∞ ≤ D, we get j ≤ log2 (D) + 1. Moreover, we have ∥e vj ∥∞ ≤ Wj and W ε ε ηj = Wj , which implies that ηj ≤ ∥evj ∥∞ . Moreover, combining Wj−1 ≤ D and Wj−1 = 2j = 2ηε j ε ≤ ηj . The Bernstein upper bound of Eq. 9 entails that the total sample complexity yields that 2D e D2 ΓSA/ε2 + DS 2 A/ε . Now, denote by ve the optimistic matrix output by the is bounded by O b SUBROUTINE. Let us consider s1 ∈ arg maxs minπ E[τπ (s)]. Denote by π De the greedy policy w.r.t. the vector ve in the optimistic model. Then we have (a)
D = min E[τπ (s1 )] ≤ E[τπe (s1 )] ≤ (1 + 2η∥E[e τπe ]∥∞ )E[e τπe (s1 )] π
(b)
≤ (1 + 2η(1 + ε)∥e v ∥∞ )(1 + ε)e v (s1 ) b ≤ (1 + 2η(1 + ε)∥e v ∥∞ )(1 + ε)∥e v ∥∞ := D (c)
≤ (1 + 2η(1 + ε)∥e v ∥∞ )(1 + ε)D (d)
≤ (1 + 2ε(1 + ε))(1 + ε)D, where (a) corresponds to the simulation lemma for SSP (Lem. 2), (b) comes from the value iteration precision µVI := 2ε which implies that E[e τπe ] ≤ (1 + 2µVI )e v ≤ (1 + ε)e v component-wise according to Lem. 4, (c) is implied by Lem. 10, and finally (d) uses that η∥e v ∥∞ ≤ ε as proved above.
17
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Appendix D. Proof of Thm. 1 Here we provide the proof of Thm. 1. Denoting by the subscript i the quantities considered at any iteration i of Alg. 2, recall that the algorithm terminates at the first iteration i such that ∥e vi ∥∞ ≤ ∆i . This implies that at the previous iteration i − 1, ∆i−1 < ∥e vi−1 ∥∞ . Also, ∆i = 2∆i−1 and ∥e vi−1 ∥∞ ≤ B⋆ from optimism. Combining everything gives ∆i ≤ 2B⋆ . Therefore when Alg. 3 terminates it is aware of a quantity ∆ := ∆i such that ∥e v ∥∞ ≤ ∆ ≤ 2B⋆ . We denote by n the minimum number of samples collected at each state-action pair. We denote by π e the candidate policy output by Alg. 1. Let us denote by V and Ve the value functions of policy π e in the true model p and the optimistic model pe, respectively (note that we may have V = +∞ for some components if π e is not proper in p). Note that p := p(·|·, π e(·)), pb := pb(·|·, π e(·)) and pe := pe(·|·, π e(·)) can be seen as matrices. Our analysis draws inspiration from variance-aware techniques, see e.g., Azar et al. (2013, 2017); Fruit et al. (2020); Rosenberg et al. (2020). We will make multiple use of the Cauchy-Schwartz (C-S)
inequality, for which we will use the symbol ≤. We assume throughout that the event E holds. Finally, we introduce the (unknown) quantity Γ := maxs,a ∥p(·|s, a)∥0 , and its empirical counterpart b := maxs,a ∥b b ≤ Γ). Γ p(·|s, a)∥0 (note that we always have Γ (p) min We first require to have pe ∈ Pη with accuracy η = c6∆ . To do so, we use the triangle inequality to write |e p − p| ≤ |e p − pb| + |b p − p|. The second term is bounded by the empirical Bernstein inequality (Eq. 9), and the first term is bounded the same way by construction of EVI. Hence, by inverting Eq. 9 to extract n and after some algebraic manipulations (i.e., by applying the technical lemma of Kazerouni et al., 2017, Lem. 8), is it sufficient to require ! b ∆2 Γ ∆SA ∆ ∆SA n = Ω 2 log2 + log . δcmin cmin δcmin cmin
(α)
The simulation lemma (Lem. 2) then ensures that π e is proper in p, and moreover that its value function verifies V ≤ 2∆ component-wise by virtue of Lem. 8. Since π e is proper in both p and pe, the associated Bellman equations hold, thus entailing the following for any non-goal state s X X V (s) − Ve (s) = p(y|s)V (y) − pe(y|s)Ve (y) y∈S
=
X
y∈S
p(y|s)(V (y) − Ve (y)) +
y∈S
X
(p(y|s) − pe(y|s))Ve (y).
y∈S
Let us define W (s) :=
X
(p(y|s) − pe(y|s))Ve (y).
y∈S
Note that W (g) = 0. Denote by Q ∈ RS×S the transition matrix restricted between the non-goal states of policy π e in the true model p, i.e., for any (s, s′ ) ∈ S 2 , Q(s, s′ ) := p(s′ |s, π e(s)). Since π e is proper in p, the matrix Q is strictly substochastic which implies that the matrix (I − Q) is invertible,
18
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
and therefore we have V (s) − Ve (s) = (I − Q)−1 W s +∞ h X = Eπe,p 1st ̸=g W (st )
i |s0 = s .
t=0
First, let us consider that V (s) ≤ Ve (s). Then from Lem. 8 we immediately have that V (s) ≤ V ⋆ (s) + 3ε . From now on, we thus consider that V (s) ≥ Ve (s). Hence we have V (s) − Ve (s) ≤
+∞ X
h Eπe,p 1st ̸=g |W (st )|
i |s0 = s .
(13)
t=0
From now on, for notational simplicity, we will omit the (implicit) dependency s0 = s for the expectations. We bound each term |W (st )|. Given that Ve (g) = 0 and both p(·|s) and pe(·|s) are probability distributions over S ′ , the “shifting” trick (also performed by e.g., Fruit et al., 2020; Jin et al., 2020; Rosenberg et al., 2020) yields ! X X W (st ) = (p(y|st ) − pe(y|st )) Ve (y) − p(z|st )Ve (z) . y∈S ′
z∈S
In addition the empirical Bernstein inequalityq entails that there exist two absolute positive constants ′
′
′
−1
−1
Aδ n) n) c1 and c2 such that |p(s′ |st ) − pe(s′ |st )| ≤ c1 pb(s |st ) log(S + c2 log(S Aδ (see e.g., Fruit n n ′ et al., 2020, Thm. 10). Recall that S = S + 1 amounts P to the total number of states (i.e., the S non-goal states plus the goal state g). Setting Z(st ) := z∈S p(z|st )Ve (z), we have X |Ve (s′ ) − Z(st )| · |p(s′ |st ) − pe(s′ |st )| |W (st )| ≤ s′ ∈S ′
≤ c1
v 2 u u X t pb(s′ |st ) |Ve (s′ ) − Z(st )| log(S ′ Aδ −1 n) n
s′ ∈S ′
+ 2c2
X ∆ log(S ′ Aδ −1 n) s′ ∈S ′
s
n
s 2 X ∆ log(S ′ Aδ −1 n) b log(S ′ Aδ −1 n) X Γ ≤ c1 pb(s′ |st ) |Ve (s′ ) − Z(st )| + 2c2 n n s′ ∈S ′ s′ ∈S ′ v r u X log(S ′ Aδ −1 n) u t (b p(s′ |st ) − p(s′ |st ))4∆2 ≤ c1 n s′ ∈S ′ s b log(S ′ Aδ −1 n)V(st ) Γ ∆S ′ log(S ′ Aδ −1 n) + c1 + 2c2 , (14) n n
(C-S)
where we use the subadditivity of the square root and define the following variance !2 X X ′ ′ ′′ ′′ V(st ) := p(s |st ) Ve (s ) − p(s |st )Ve (s ) . s′ ∈S ′
s′′ ∈S
19
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
(p)
min Leveraging (α) which guarantees that pb ∈ Pη with accuracy η = c6∆ , the first term in Eq. 14 can q p ′ −1 b min be bounded as c1 Γ log(SnAδ n) ∆ c6∆ . Consequently, plugging the bound of Eq. 14 into Eq. 13 yields
V (s) − Ve (s) ≤ ➊ + ➋ + ➌, where s ➊ := c1
+∞ h i b log(S ′ Aδ −1 n) X p Γ Eπe,p 1st ̸=g V(st ) , n t=0
s ➋ := c1
r +∞ b log(S ′ Aδ −1 n) cmin X Γ Pπe,p (st ̸= g), ∆ n 6∆ t=0
➌ := c2
+∞ ∆S ′ log(S ′ Aδ −1 n) X
n
Pπe,p (st ̸= g).
t=0
t Leveraging that V ≤ 2∆ component-wise, we obtain that Pπe,p (st ̸= g) ≤ 2 exp − cmin by apply8∆ ing Lem. 7 with m = cmin t. To make an analogy to the infinite-horizon discounted setting studied by Azar et al. (2013), we can observe that we have Pπe,p (st ̸= g) ∼ γ t where γ ∼ exp − cmin < 1. ∆ +∞ X
min 2 exp c8∆ 2 19∆ Pπe,p (st ̸= g) ≤ ≤ , cmin = cmin cmin 1 − exp − 8∆ exp 8∆ − 1 t=0
where the last inequality uses that ex ≥ 1 + x holds for any real x. Consequently, we get ➌≤
19c2 ∆2 S ′ log(S ′ Aδ −1 n) . cmin n
We seek to ensure that ➌ ≤ 2ε 9 . There simply remains to invert the inequality above to extract n and do some algebraic manipulations (see e.g., Kazerouni et al., 2017, Lem. 9). We thus require that: 2 ∆SA ∆ S n=Ω log cmin ε cmin εδ
(β)
Furthermore, we have s ➋ ≤ 19c1
∆ cmin
b log(S ′ Aδ −1 n) Γ ∆ n
r
cmin . 6∆
We seek to ensure that ➋ ≤ 2ε 9 . There simply remains to invert the inequality above to extract n and do some algebraic manipulations (see e.g., Kazerouni et al., 2017, Lem. 9). We thus require that: ! b ∆3 Γ ∆SA n=Ω log . cmin ε2 cmin εδ 20
(γ)
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
We now proceed in bounding ➊. To do so, we split the time into intervals, similar to Rosenberg et al. (2020). The first interval begins at the first time step, and each interval ends when its total cost accumulates to at least ∆ (or when the goal state g is reached). Denote by tm the time step at the beginning of the m-th interval, and by Hm the length of the m-th interval. An important property is that Hm ≤ 2∆/cmin . Denote by Im the boolean equal to 1 if the goal g is not reached by the end of the m-th interval, and denote by s(m) the state at the end of the m-th interval. Note that Im = 1 ⇐⇒ s(m) ̸= g, implying that Eπe,p [Im ] = Pπe,p (s(m) ̸= g). We introduce a change of variable in the sums, from the time index t to the interval index m. Formally, for any time indexPt, there exists an interval m + 1 (during which it occurs) and an integer h ∈ [Hm+1 ] such that t= m i=0 Hi + h. The change of variable yields the following tm+1 +Hm+1 +∞ +∞ h i X X X p p Eπe,p 1st ̸=g V(st ) ≤ V(sh ) Eπe,p Im t=0
m=0
(C-S)
≤
+∞ X
h=tm+1
v 2 u tm+1 +Hm+1 u X p u V(sh ) Pπe,p (s(m) ̸= g)tEπe,p
m=0
h=tm+1
v u tm+1 +Hm+1 +∞ u X (C-S) X u ≤ Pπe,p (s(m) ̸= g)tEπe,p Hm+1 V(sh ) m=0
h=tm+1
v u r tm+1 +Hm+1 +∞ u X 2∆ X u Pπe,p (s(m) ̸= g)tEπe,p V(sh ). ≤ cmin m=0
(15)
h=tm+1
To bound the expression above, we first use the property shown by Rosenberg et al. (2020, Lem. 4.7) that whenever every state-action pair has been sampled sufficiently many times (specifically, at least −1 −1 αB⋆ Sc−1 min log(B⋆ SAcmin δ ) times for some constant α > 0, which is the case here), then the expected variance V accumulated over a whole interval m can be bounded as O(B⋆2 ), i.e., there exists an absolute constant c3 > 0 such that tm+1 +Hm+1 X Eπe,p V(sh ) ≤ c3 ∆2 . (16) h=tm+1
Second, we bound the series of the probabilities. The construction of the intervals entails that if the m-th interval does not end in the goal state, then the cumulative cost to reach the goal state is more than ∆m. Furthermore, the probability of the latter event can be bounded by Lem. 7 leveraging the component-wise inequality V ≤ 2∆. As a result, we get m ∆m 1 Pπe,p (s(m) ̸= g) ≤ 2 exp − = 2 exp − , 8∆ 8 which implies that +∞ X
Pπe,p (s(m) ̸= g) ≤
m=0
21
2 . 1 − exp(− 81 )
(17)
S AMPLE C OMPLEXITY B OUNDS FOR S TOCHASTIC S HORTEST PATH WITH A G ENERATIVE M ODEL
Plugging Eq. 16 and 17 into Eq. 15 gives √
➊ ≤ 25c1 c3
s
b log(S ′ Aδ −1 n) ∆3/2 Γ . cmin n
We seek to ensure that ➊ ≤ 2ε 9 . There simply remains to invert the inequality above to extract n and do some algebraic manipulations (see e.g., Kazerouni et al., 2017, Lem. 9). We thus require (once again) that: ! b ∆3 Γ ∆SA n=Ω log . (γ) cmin ε2 cmin εδ Overall, combining the requirements of Eq. (α), (β) and (γ) means that we get the component-wise ⋆ guarantee that V ≤ Ve + 2ε 3 , and therefore from Lem. 8 that V ≤ V + ε, as soon as: ! b b ∆3 Γ ∆SA ∆2 S ∆SA ∆2 Γ 2 ∆SA n=Ω log + log + 2 log . cmin ε2 cmin εδ cmin ε cmin εδ cmin δ cmin
Appendix E. Proof of Thm. 2 Here we provide the proof of Thm. 2 by establishing that the output policy π e of Alg. 3 is ε-optimal w.r.t. the restricted set Πθ . We assume that the event E holds. Here we offset all the costs with the additive perturbation ν = ε b . We use the subscript ν to denote quantities considered in the 2θD perturbed model. In the perturbed model, the costs are set to c′ν (s, a) := max{c(s, a), ν}, which in particular implies that the minimum cost verifies mins,a c′ν (s, a) ≥ ν. The application of Thm. 1 in the perturbed model immediately yields the component-wise § inequality Vν ≤ Vν⋆ + 2ε . Moreover, let π § ∈ minπ∈Πθ V π , V § := V π and T § := E[τπ§ ]. In b Furthermore, given the choice of ν and particular, we have Vν⋆ ≤ Vν§ and T § (s) ≤ θDs ≤ θD. § ′ § the fact that cν (s, a) ≤ c(s, a) + ν, we have Vν ≤ V + νT § ≤ V § + 2ε . Lastly, we have V ≤ Vν . Putting everything together yields the sought-after inequality V ≤ V § + ε.
22