Year: 2021

Abstract:
We revisit the incremental autonomous exploration problem proposed by Lim and Auer (2012). In this setting, the agent aims to learn a set of near-optimal goalconditioned policies to reach the L-controllable states: states that are incrementally reachable from an initial state s0 within L steps in expectation. We introduce three new algorithms with stronger sample complexity bounds than existing ones. Furthermore, we also prove the first lower bound for the autonomous exploration problem. In particular, the lower bound implies that one of our proposed algorithms, Value-Aware Autonomous Exploration, is nearly minimax-optimal when the number of L-controllable states grows polynomially with respect to L. Key in our algorithm design is a connection between autonomous exploration and multi-goal stochastic shortest path, a new problem that naturally generalizes the classical stochastic shortest path problem. This new problem and its connection to autonomous exploration can be of independent interest.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) with a known state space has been studied in a wide range of settings (e.g., Schmidhuber, 1991; Oudeyer et al., 2007; Oudeyer and Kaplan, 2009; Baranes and Oudeyer, 2009). When the state space is large, it is difficult for a learning agent to discover the whole environment. Instead, the agent can only explore a small portion of the environment. At a high level, we hope that the agent can discover states near the initial state, expand the range of known states by exploration, and learn near-optimal goal-conditioned policies for the known states. Because the agent discovers its known states of the environment incrementally, this learning problem was named Autonomous Exploration (AX) (Lim and Auer, 2012; Tarbouriech et al., 2020).
The autonomous exploration problem generalizes the Stochastic Shortest Path (SSP) problem (Bertsekas et al., 2000) where the agent aims to reach a predefined goal state while minimizing its total expected cost. However, in the autonomous exploration setting, the agent aims to discover a set of reachable states in a large environment and find the optimal policies to reach them. The autonomous exploration formulation is applicable to an increasing number of real-world RL problems, ranging from navigation in mazes (Devo et al., 2020) to game playing (Mnih et al., 2013). For example, in the maze navigation problem, a robot aims to follow a predefined path in an unknown environment, and the robot has to discover and expand the size of regions known to itself autonomously without prior knowledge of the environment. This procedure also resembles some biological learning processes. See Lim and Auer (2012) for more discussions.
Related Work. The setting of autonomous exploration was introduced by Lim and Auer (2012), who gave the first algorithm, UcbExplore, with a sample complexity Õ(L3S(1+ε)LA/ε3). Here L denotes the distance within which we hope the learning agent to discover, S(1+ε)L denotes the total number of states within distance (1 + ε)L from the starting state, A denotes the size of the action space, and ε denotes the error that we can tolerate. Recent work by Tarbouriech et al. (2020) designed the DisCo algorithm with a sample complexity bound Õ(L3S2(1+ε)LA/ε 2)1, which improves the 1/ε
1We translate their absolute error ε to the relative error εL. Their bound has a refined form Õ(L3S(1+ε)LΓ(1+ε)LA/ε 2) where Γ(1+ε)L is the branching factor which in the worst case is S(1+ε)L.
dependency at the cost of a worse dependency on S(1+ε)L. In this paper, we present new algorithms to further improve the sample complexity.

heading: 1.1 CONTRIBUTIONS
text: In this paper, we take important steps toward resolving the autonomous exploration problem. We compare our results with prior ones in Table 1.2 and we summarize our contributions below:
1. We propose a new state discovery algorithm, Value-Optimistic Incremental State Discovery (VOISD), which uses a value-optimistic method (Neu and Pike-Burke, 2020) to estimate the expected cost of the optimal policy to reach these states. We prove this algorithm enjoys an Õ ( L3S(1+ε)LA/ε 2 )
sample complexity, which improves prior results in Lim and Auer (2012) and Tarbouriech et al. (2020). 2. We connect the autonomous exploration problem to a new problem, multi-goal SSP and propose a new algorithm Re-MG-SSP that 1) satisfies a stronger criterion3 and 2) serves as a burn-in step for the next algorithm. 3. We further propose Value-Aware Autonomous Exploration (VALAE), which uses VOISD and Re-MG-SSP as initial steps and then uses the estimated value functions to guide our exploration. By doing so, for each state-action pair (s, a), we derive an (s, a)-dependent sample complexity bound, which can exploit the variance information, and yield a sharper sample complexity bound than the bounds for VOISD and Re-MG-SSP. In particular, VALAE improves the dependency on L from cubic to linear. 4. We give the first lower bound of the autonomous exploration problem. This lower bound shows VALAE is nearly minimax-optimal when the SL grows polynomially with respect to L.

heading: 1.2 MAIN DIFFICULTIES AND TECHNIQUE OVERVIEW
text: While our work borrows ideas from prior work on autonomous exploration (Lim and Auer, 2012; Tarbouriech et al., 2020) and recent advances in SSP (Tarbouriech et al., 2021), we develop new techniques to overcome additional difficulties that are unique in autonomous exploration.
Dependence between the Estimated Transition Matrix and Discovered States. Our algorithm incrementally adds new states to the set of discovered states K. To obtain a tight dependency on S(1+ε)L, similar to the standard RL setting, one needs to use concentration on (P̂s,a − Ps,a)V ∗K,g instead of ‖P̂s,a − Ps,a‖1 (used by Tarbouriech et al. (2020)) where P̂s,a is the estimated transition,
2In (Lim and Auer, 2012) and (Tarbouriech et al., 2020), the cost is 1 uniformly for all state-action pairs. In this paper, we allow non-uniform costs. In Table, we consider uniform cost in Table 1 for fair comparisons.
3See Sect. 2 for different criteria.
Ps,a is the true transition, and V ∗K,g is the value function of the optimal policy going to the state g restricted on the discovered states K. The main challenge is that the set of discovered states K is dependent on the samples collected, and thus V ∗K,g is dependent on P̂s,a. We can use the union bound on all the possible K, but the number of possible K is exponential in the number of states S. Our main technique is to construct a series of sets of states {s0} = K0 ⊆ K1 ⊆ · · · ⊆ KZ = S→L , where Kz+1 is constructed by adding all the states that are reachable from s0 by some policy on Kz with expected cost no more than L. This series is only polynomially large so after applying the union bound we only have a logarithmic overhead. In order to use concentrations only on this sequence of sets, we also need to develop a modified definition of optimism. See Appendix B and Appendix C.2 for details.
Connection between Autonomous Exploration and Multi-Goal SSP. In standard RL setting, it is known that in order to obtain a tight dependency on L, one needs to exploit the variance information in the value function (Azar et al., 2017). However, in autonomous exploration, it is unclear how to exploit the variance information because even which state is in S→L is unknown. To this end, we first consider a simpler problem, multi-goal SSP, and extend the technique for singlegoal SSP (Tarbouriech et al., 2021) to this new problem (cf. Alg. 3). We also present a reduction from autonomous exploration to multi-goal SSP (cf. Alg. 2). These two techniques together yield the first tight dependency on L for autonomous exploration.

heading: 2 PRELIMINARIES
text: In this section, we introduce basic definitions and our problem setup. Notations. For any two vectorsX,Y ∈ RS , we write their inner product asXY := ∑ s∈S X(s)Y (s). We denote ‖X‖∞ := maxs∈S |X(S)|, and if X is a probability distribution on S, we define V(X,Y ) := ∑ s∈S X(s)Y (s) 2 − ( ∑ s∈S X(s)Y (s)) 2.
Markov Decision Process. We consider an MDP M := 〈S,A, P, c, s0〉, where S is the state space with size S, A is the action space with size A, and s0 ∈ S is the initial state. In state s, taking action a has a cost drawn i.i.d. from a distribution on [cmin, 1] (where cmin > 0) with expectation c(s, a), and transits to the next state s′ with probability P (s′|s, a). For convenience, we use Ps,a and Ps,a,s′ to denote P (·|s, a) and P (s′|s, a), respectively. A deterministic and stationary policy π : S → A is a mapping, and the agent following the policy π will take action π(s) at state s.
For a fixed state g ∈ S we define the random variable tπg (s) as the number of steps it takes to reach state g starting from state swhen executing policy π, i.e. tπg (s) := inf{t ≥ 0 : st+1 = g | s1 = s, π}. A policy π is a proper policy if for any state s ∈ S, tπg (s) < +∞ with probability 1. Then we define the value function of a proper policy π with respect to the goal state g and its corresponding Q-function as follows:
V πg (s) = E tπg (s)∑ t=1 ct(st, π(st)) | s1 = s , Qπg (s, a) = E tπg (s)∑ t=1 ct(st, π(st)) | s1 = s, π(s1) = a , where ct ∈ [cmin, 1] is the instantaneous cost at step t incurred by the state-action pair (st, π(st)), and the expectation is taken over the random sequence of states generated by executing π starting from state s ∈ S. Here we have V πg (g) = 0. We use πQ to denote the greedy policy over a vector Q ∈ RS×A, i.e. πQ(s) := arg min
a∈A Q(s, a).
For a fixed state g ∈ S, we denote V ∗g as the value function of the optimal policy with respect to goal state g, and here we list some important properties of V ∗g : there exists a stationary, deterministic and proper policy π∗, such that its value function V ∗g := V π∗
g and its corresponding Q-function Q∗g := Q π∗ g satisfies the following Bellman optimality equations (cf. Lem. 1):
Q∗g(s, a) = c(s, a) + Ps,aV ∗ g , V ∗ g (s) = min a∈A Q∗g(s, a), ∀(s, a) ∈ S ×A.
Autonomous Exploration. Now we introduce the Autonomous Exploration problem. To formally discuss the setting, we need the following assumption on our MDP M .
Assumption 1. The action space contains a RESET action s.t. P (s0|s,RESET) = 1 for any s ∈ S . Moreover, taking RESET in any state s will incur a cost cRESET with probability 1, where cRESET is a constant in [cmin, 1].
Given any fixed length L ≥ 1, the agent needs to learn the set of incrementally controllable states S→L . To introduce the concept of S→L , we first give the definition of policies restricted on a subset: Definition 1 (Policy restricted on a subset). For any S ′ ⊆ S, a policy π is restricted on the set S ′ if π(s) = RESET for all s /∈ S ′.
Now we discuss the optimal policy restricted on a set of states K ⊆ S with respect to goal state g. We denote V ∗K,g ∈ RS as the value function of the optimal policy restricted on K with goal g, and Q∗K,g as the Q-function corresponding to V ∗ K,g. We consider the case that there exists at least one proper policy restricted on K with the goal state g. Then, V ∗K,g and Q∗K,g are finite, and they satisfy the following Bellman equations:
Q∗K,g(s, a) = c(s, a) + Ps,aV ∗ K,g, ∀(s, a) ∈ S ×A,
V ∗K,g(s) = min a∈A Q∗K,g(s, a), ∀s ∈ K, s 6= g, V ∗K,g(s) = Q ∗ K,g(s,RESET) = cRESET + V ∗ K,g(s0), ∀s /∈ K ∪ {g}, V ∗K,g(g) = 0.
We note that when K1 ⊆ K2, for any g ∈ S, if V ∗K1,g is finite, then V ∗ K2,g is also finite, and we have V ∗K2,g ≤ V ∗ K1,g component-wise. And we note that for any s 6= g, we have mina∈AQ ∗ K,g(s, a) ≤ V ∗K,g(s). Now we introduce the definition of incrementally controllable states S→L (see Tarbouriech et al. (2020) for more intuitions on this definition.): Definition 2 (Incrementally L-controllable states S→L ). Let ≺ be any partial order on S . We denote S≺L as the set of states reachable from s0 with expected cost no more than L w.r.t. ≺, which is defined as follows:
• s0 ∈ S≺L , • if there is a policy π restricted on {s′ ∈ S≺L : s′ ≺ s} such that V πs (s0) ≤ L, then s ∈ S ≺ L .
The set of incrementally L-controllable states S→L is given by S→L = ⋃ ≺ S≺L . Learning Objective. In our settings, the learning agent knows the constants S, A and cmin, but the learning agent has no prior knowledge of the transition probability P or the cost function c(·, ·) of the MDP M . We fix the length L ≥ 1 and an error parameter ε ∈ (0, 1]. A learning algorithm of the autonomous exploration problem should output a set of states K ⊆ S that satisfies: • S→L ⊆ K, i.e., the algorithm discovers all the states that we want to explore. The algorithm also outputs a set of policies {πs}s∈K that satisfy one of the following criteria: 1. (AXL on S→L ) ∀s ∈ S→L , V πss (s0) ≤ (1 + ε)L; 2. (AX∗ on S→L ) ∀s ∈ S→L , V πss (s0) ≤ V ∗S→L ,s(s0) + εL; 3. (AXL on K) ∀s ∈ K, V πss (s0) ≤ (1 + ε)L; 4. (AX∗ on K) ∀s ∈ K, V πss (s0) ≤ V ∗K,s(s0) + εL.
We note that AX∗ on K is stronger than both AXL on S→L and AX ∗ on S→L , but it is not necessarily stronger than AXL on K, because we do not necessarily have V ∗K,s(s0) ≤ L when s /∈ S→L . In the literature, AXL on S→L was studied in the original paper that proposed the autonomous exploration problem (Lim and Auer, 2012) and AX∗ on K condition was studied in (Tarbouriech et al., 2020). We denote T as the total number of steps the agent uses, and denote (st, at) as the state-action pair at the t-th step. We denote by ct(st, at) the instantaneous cost incurred at the t-th step. The performance
of an algorithm is measured by the cumulative cost: CT := T∑ t=1 ct(st, at).
Multi-goal SSP. We also study a new problem, multi-goal SSP, a natural generalization of the classical SSP problem. In multi-goal SSP, we consider an MDP and a fixed length L ≥ 1. The MDP M satisfies Asmp. 1, and all of its states are incrementally L-controllable, i.e. S→L = S.
Algorithm 1: Value-Optimistic Incremental State Discovery (VOISD) 1 Input: MDP M = 〈S,A, P, c, s0〉, confidence δ ∈ (0, 1), error parameter ε ∈ (0, 1], and L ≥ 1. 2 Initialize U ← {},K ← {}, and snew ← s0. Specify constants c1 = 6, c2 = 72, c3 = 2 √ 2, c4 = 2 √ 2. 3 Set ε← ε/3, δ ← δ/2, B ← 10L and πs0 ∈ Π({s0}). 4 Set ψ ← 12000( L
cminε )2 ln(SA δ ), and φ← 2dlog2 ψe.
5 For (s, a, s′) ∈ S ×A× S, set N(s, a)← 0; n(s, a)← 0; N(s, a, s′)← 0; P̂s,a,s′ ← 0; θ(s, a)← 0; ĉ(s, a)← 0. 6 for round r = 1, 2, · · · do 7 \\(a) Discover Possible States in S→L 8 Add snew to K. Set s← snew. 9 for each a ∈ A do
10 while N(s, a) < φ do 11 Execute policy πs on MDP M until reaching state s. 12 Take action a, incur cost c and observe next state s′ ∼ P (· | s, a). 13 Set N(s, a)← N(s, a) + 1, θ(s, a)← θ(s, a) + c, N(s, a, s′)← N(s, a, s′) + 1. 14 If s′ /∈ K, add s′ to U .
15 Set ĉ(s, a)← θ(s,a) N(s,a) and θ(s, a)← 0. 16 For all s′ ∈ S, set P̂s,a,s′ ← N(s, a, s′)/N(s, a), n(s, a)← N(s, a). 17 Stop the algorithm if U is empty. 18 \\(b) Compute Optimistic Policy 19 For each g ∈ U , compute (Qg, Vg) := VISGO(S,A,K, s0, g, cminε18 ). 20 Choose a state s ∈ arg min
g∈U Vg(s0). Stop the algorithm if Vs(s0) > L.
21 Set the policy π̃ as the greedy policy over Qs. Remove s from U , set snew ← s and set πs ← π̃. 22 Output: The discovered states K and their corresponding policies {πs}s∈K.
In multi-goal SSP, a learning algorithm should output a set of policies {πs}s∈S , such that V πss (s0) ≤ V ∗s (s0) + εL for all s ∈ S. We observe that an algorithm that solves the autonomous exploration problem with AX∗ on S→L criterion can also solve the multi-goal SSP problem.

heading: 3 ALGORITHMS AND SAMPLE COMPLEXITY BOUNDS
text: Now we are ready to describe our algorithms. There are three key components. The first component aims to discover a set of states K which is a superset of S→L but it is also not too much larger than S→L (cf. Alg. 1), and compute a set of policies {πs}s∈K to reach each state with a small cost. The second component reduces the autonomous exploration problem to multi-goal SSP using the set K computed from the first component (cf. Alg. 2). Then it collects fresh samples for all state-action pairs and computes a set of near-optimal policies {πs}s∈K on the set K. In the third component, inspired by recent advances in stochastic shortest path Tarbouriech et al. (2021), we design a policy evaluation step to obtain near-optimal estimates of the costs of getting to each s ∈ S→L (cf. Alg. 3).

heading: 3.1 STATE DISCOVERY VIA A VALUE-OPTIMISTIC METHOD
text: In Alg. 1, we compute a set of states K that contains S→L . The algorithm maintains a set of "known" states K and a set of "unknown" states U that have the potential to be recognized as members of S→L and become "known" states in future. Initially, the set of known states is empty, and s0 is the first state that will be added to K. Our algorithm will discover all the states s ∈ S→L one by one, and when the algorithm finds a policy that can reach s from s0 with expected cost less than L, the algorithm adds s to the set of known states K. Now we discuss this process in detail. In each round, we have two phases. The first phase is called state discovery phase, and it borrows the idea from (Tarbouriech et al., 2020) and (Lim and Auer, 2012). We add a new state s to the set of known states K. Then for each action a, we sample φ times, compute the empirical probability P̂s,a,s′ , and use the empirical ĉ(s, a). The collection of these samples has two objectives. First, it will discover new states because it adds to U all the states that have not been discovered. Second, the collection of these samples helps us estimate the transition model Ps,a,s′ , which is crucial in estimating the value function of optimal policies.
Algorithm 2: Reduce Autonomous Exploration to Multi-Goal SSP (Re-MG-SSP) 1 Input: MDP M = 〈S,A, P, c, s0〉, confidence δ ∈ (0, 1), error parameter ε ∈ (0, 1], and L ≥ 1. 2 Input: The states s in K and their corresponding policy πs. 3 For (s, a, s′) ∈ S ×A× S, set
N(s, a)← 0; n(s, a)← 0; N(s, a, s′)← 0; P̂s,a,s′ ← 0; θ(s, a)← 0; ĉ(s, a)← 0. 4 Set ε← ε/3, δ ← δ/2, ψ ← 12000( L
cminε )2 ln(SA δ ), and φ← 2dlog2 ψe.
5 Set K† = K ∪ {x} where x is defined in and construct an MDP M† = 〈K†,A, P †, c†, s0〉 where x, K†, P †, c† are defined in Sect. 3.2. 6 for each (s, a) ∈ K ×A do 7 while N(s, a) < φ do 8 Execute policy πs on MDP M† until reaching state s. 9 Take action a, incur cost c and observe next state s′ ∼ P †(· | s, a).
10 Set N(s, a)← N(s, a) + 1, θ(s, a)← θ(s, a) + c, N(s, a, s′)← N(s, a, s′) + 1.
11 Set ĉ(s, a)← θ(s,a) N(s,a) and θ(s, a)← 0. 12 For all s′ ∈ K†, set P̂s,a,s′ ← N(s, a, s′)/N(s, a), n(s, a)← N(s, a).
13 For all a ∈ A, set N(x, a) = n(x, a)← φ, ĉ(x, a)← cRESET, P̂x,a,s0 ← 1, P̂x,a,s′ ← 0 for all s′ ∈ S. 14 For g ∈ K, compute (Qg, Vg) := VISGO(K†,A,K†, s0, g, cminε18 ), and set πg as the greedy policy over Qg . 15 Output: K, {πs}s∈K, N(), n(), P̂ , θ(), ĉ, M†.
In the second phase, we use the estimated model P̂ to estimate the value function of the optimal policy with respect to all the goal states g ∈ U , and we denote the estimated value as Vg. We can prove that Vg satisfies the optimism property. Hence, if g ∈ S→L , g will be eventually added to the set of known states K, and we can obtain K ⊇ S→L when the algorithm terminates. To this purpose, we use a procedure called VISGO (Value Iteration with Slight Goal Optimism), which is a modified version of the VISGO procedure in (Tarbouriech et al., 2021).
In our VISGO procedure, we use slightly different bonus function b(U, s, a). The VISGO procedure in (Tarbouriech et al., 2021) computes the optimistic policy on the whole set S , and here we make VISGO estimate the optimistic policy restricted on the set K. As we have collected φ = Õ(L2/(cminε)2) samples for each state-action pair (s, a) ∈ K ×A, we can ensure that the estimated model P̂ is close enough to P , and in VISGO procedure, the bonus function b(U, s, a) is bounded by O(cminε), and this is essential for our proof of K ⊆ S→(1+ε)L. The full algorithm of VISGO is deferred to Appendix C. Now we present our upper bound of the Alg.1. Theorem 1. Assume that L ≥ 1, 0 < ε ≤ 1 and 0 < δ < 1. For any MDP M = 〈S,A, P, c, s0〉 satisfying Asmp. 1, with probability at least 1−δ, our Alg. 1 will terminate and output a set of statesK such that S→L ⊆ K ⊆ S→(1+ε)L, and a set of policies {πs}s∈K such that ∀s ∈ K, V πs s (s0) ≤ (1 +ε)L, and the cumulative cost CT satisfies CT = Õ( L3S(1+ε)LA
c2minε 2 ).
Thm. 1 shows that our Alg. 1 meets the AXL on K criterion. When cmin = 1, which is the setting considered in prior works (Lim and Auer, 2012; Tarbouriech et al., 2020), our bound is stronger than previous ones either in L or 1/ε (cf. Table 1). We remark that our algorithm VOISD follows the same template as the DisCo algorithm in (Tarbouriech et al., 2020), which also consists of a state-discovery phase and a compute-optimistic-policy phase. However, our sample complexity saves an S(1+ε)L factor compared with (Tarbouriech et al., 2020), and the main reasons lie in the difference of the methods of computing optimistic policies. The DisCo algorithm applies a model-optimistic method, which will incur an additional S(1+ε)L factor in the bonus term bs,a. Our algorithm VOISD is based on the value-optimistic subroutine VISGO. It uses the concentration of (P̂s,a − Ps,a)V ∗Kz,g on a series of sets Kz and saves an S(1+ε)L term on the sample complexity.

heading: 3.2 CONNECTION BETWEEN AUTONOMOUS EXPLORATION AND MULTI-GOAL SSP
text: In Alg. 2, after we compute a set of known states K ⊇ S→L , we have discovered all the states that we want to explore. Alg. 2 aims to compute a set of policies {πs}s∈K that meets the AX∗ on K criterion. We will fix our set of known states K, and focus only on the policies restricted on K. Therefore, for all the states s /∈ K, we can regard them as one artificial state x, and the only action at state x is
Algorithm 3: Value-Aware Autonomous Exploration (VALAE) 1 Input: MDP M = 〈S,A, P, c, s0〉, confidence δ ∈ (0, 1), error parameter ε ∈ (0, 1], and L ≥ 1. 2 Specify: Trigger setN ← {2j−1 : j = 1, 2, . . .}. Constants c1 = 6, c2 = 72, c3 = 2 √ 2, c4 = 2 √ 2. 3 Set δ ← O(δε/SAL). 4 \\We run Alg. 1 with ε = 1 and get a set K such that S→L ⊆ K ⊆ S→2L. 5 Run Alg. 1 with input (M, δ/2, 1, L) and we get a set K and a set of policies {πs}s∈K. 6 Run Alg. 2 with input (M, δ/2, 1, L,K, {πs}s∈K), and we obtain the MDP M† = 〈K†,A, P †, c†, s0〉 and
the variables N(), n(), P̂ , θ(), ĉ. 7 Set initial time step t← 1 and trigger index j ← 5 + log2 1cmin . 8 Set ← ε
3 , B ← 10L, λ = d 2048 2 ln2( 256 ) ln( 2S δ )e, and initialize U ← K, and g ← s0.
9 for round r = 1, 2, · · · do 10 \\(a) Compute Optimistic Policy 11 Compute (Q,V ) := VISGO(K†,A,K†, s0, g, 2−j/(|K†|A)). 12 Set the policy π̃ as the greedy policy over Q. 13 \\(b) Policy Evaluation 14 Set τ̂ ← 0. 15 for episode k = 1, 2, · · · , λ do 16 Set st ← s0 and reset to the initial state s0. Set τ̂k → 0. 17 while st 6= g do 18 Take action at = arg mina∈AQ(st, a) on MDP M†, incur cost ct and observe next state st+1 ∼ P †(· | st, at). 19 Set (s, a, s′, c)← (st, at, st+1, ct) and t← t+ 1. 20 SetN(s, a)← N(s, a) + 1, θ(s, a)← θ(s, a) + c, N(s, a, s′)← N(s, a, s′) + 1. 21 if N(s, a) ∈ N then 22 Set j ← j + 1. Set ĉ(s, a)← 2θ(s,a)
N(s,a) and θ(s, a)← 0.
23 For all s′ ∈ K†, set P̂s,a,s′ ← N(s, a, s′)/N(s, a), n(s, a)← N(s, a). 24 Return to line 9, start a new round (the current round has been a skipped round).
25 Set τ̂ ← τ̂ + c λ , τ̂k ← τ̂k + c. 26 if τ̂ > V (s0) + L then 27 Return to line 9, start a new round (the current round has been a failure round).
28 Set πg ← π̃. Remove g from U . The current round has been a success round. 29 Choose another state g ∈ U . Stop the algorithm if U is empty. 30 Output: The states s in K and their corresponding policy πs.
RESET. To this purpose, we will construct an MDP M† := 〈K†,A, P †, c†, s0〉 where we first define the artificial state x, and we set K† = K ∪ {x}, and K ′ = |K†|. For any (s, a) ∈ K ×A, we define P †s,a,s′ as follows:
P †s,a,s′ = Ps,a,s′ , ∀s ′ ∈ K, and P †s,a,x = ∑ s′ /∈K Ps,a,s′ .
We also define P †x,a,s′ = I[s ′ = s0] for any a ∈ A, s′ ∈ K∪{x}. Finally, we define c†(s, a) = c(s, a) for all (s, a) ∈ S × A, and c†(x, a) = cRESET for all a ∈ A. In this way, the problem reduces to solving a multi-goal SSP problem on M† with the set of states being K†. Next, we collect φ fresh samples for each state-action pair (s, a) again, and we will use these samples to compute policies {πs}s∈K that satisfy the AX∗ on K criterion. We remark that using fresh samples is essential for Alg. 2 to ensure these samples are independent of K. The following theorem states the sample complexity for Alg. 2.
Theorem 2. Assume that L ≥ 1, 0 < ε ≤ 1 and 0 < δ < 1. For any MDP M = 〈S,A, P, c, s0〉 satisfying Asmp. 1, running Alg. 1 and Alg. 2 successively will output a set of states K such that with probability at least 1 − δ, S→L ⊆ K ⊆ S→(1+ε)L, and a set of policies {πs}s∈K such that ∀s ∈ K, V πss (s0) ≤ (1+ε)L and V πss (s0) ≤ V ∗K,s(s0)+εL, andCT satisfiesCT = Õ( L3S(1+ε)LA
c2minε 2 ).

heading: 3.3 VALUE-AWARE ALGORITHMS FOR AUTONOMOUS EXPLORATION AND MULTI-GOAL SSP
text: Finally we describe our final algorithm, Value-Aware Autonomous Exploration (VALAE). First, VALAE uses Alg. 1 with ε = 1 as a subroutine, and Alg. 1 computes a set K such that S→L ⊆ K. Then we discard all the samples collected in Alg. 1, in order to ensure the independence of K and P̂s,a. Second, we use Alg. 2 as a burn-in step to collect Ω̃(L2/c2min) samples for each of the state-action pair (s, a) so that we can use Lem. 15 to bound the expected cost of the greedy policy π̃ in the policy-evaluation phase, and use Lem. 16 to show that we can use the average cost in Õ(1/ 2) episodes to estimate the expected cost of the policy π̃.
From now on we work on the MDP M†, and we will solve the multi-goal SSP problem on M† and compute near-optimal policies πg for all the goal states g ∈ K. We choose the goal state g ∈ K one by one, and we move to another goal state g if the average performance of the policy πg is close to our estimation of the optimal policy. In each round, we have two phases. In the first phase, we use VISGO to estimate the value function of the optimal policy with goal state g, and we set the policy π̃ as the greedy policy over Q. Since we do not know whether the policy π̃ is close enough to the optimal policy, in the second phase, we will execute π̃ for λ = Õ(1/ 2) times and check whether the average performance is close enough to our estimation of the optimal policy. In this process, we also collect samples, and use them to help us estimate the value function of the optimal policy.
In the second phase, the current round will be classified into three cases: failure round, skipped round, and success round. This borrows the idea from (Lim and Auer, 2012). If the average performance of the policy π̃ is too bad, we will consider the current round as a failure round. If the number of samples N(s, a) meets the trigger set (i.e. is a power of 2), we will consider the current round as a skipped round, following the idea in (Jaksch et al., 2010). Otherwise, the current round is a success round. In the case of a failure round or a skipped round, we will not change the goal state g, and in the next round, we compute a new policy by VISGO using the samples collected in this round. In the case of a success round, as the average performance of the policy π̃ is close to optimal, we can set the π̃ as the policy πg for the goal state g, and choose another goal state g.
Theorem 3. Assume that L ≥ 1, 0 < ε ≤ 1 and 0 < δ < 1. For any MDP M = 〈S,A, P, c, s0〉 satisfying Asmp. 1, we have that with probability at least 1− δ, our Alg. 3 will terminate and output a set of statesK such that S→L ⊆ K ⊆ S→2L, and a set of policies {πs}s∈K such that ∀s ∈ K, V πss (s0) ≤ V ∗K,s(s0) + εL, and the cumulative cost CT satisfies CT = Õ( LS2LA ε2 + LS22LA ε + L3S2LA c2min ).
Thm.3 shows that Alg.3 satisfies the AX∗ on K criterion. Note that in Thm. 3, the dependency on L is tight when ε→ 0, because we leverage the variance information in the policy-evaluation phase, which is necessary in RL problems generally. Alg. 1, Alg. 2 and algorithms in prior work cannot use the variance information because they collect equal number of samples on each state-action pair (s, a), thus the sample collection does not use the estimated value function as the guidance.
We highlight that the leading term of CT does not have cmin. This is because the variance fundamentally does not scale with cmin (cf. Lem. 17 and Lem. 18). While we discover a larger set K ⊆ S→2L compared with Thm. 1 and Thm. 2, we note that if the number of the L-controllable states grows polynomially with respect to L (which is often implicitly considered in the literature because otherwise one may need to consider the logarithmic dependency on |S→L |), then we have |S→2L| = O(|S→L |), and our complexity strictly improves the existing ones and is nearly minimax optimal.
Lastly, we note that Alg. 3 enjoys a near-optimal sample complexity for multi-goal SSP:
Theorem 4. (Cumulative Cost for Multi-Goal SSP) Assume that L ≥ 1, 0 < ε ≤ 1 and 0 < δ < 1. For any MDP M = 〈S,A, P, c, s0〉 satisfying Asmp. 1 and S→L = S, with probability at least 1− δ, our Alg. 3 will terminate and output a set of policies {πs}s∈S such that ∀s ∈ S, V πss (s0) ≤ V ∗s (s0) + εL, and the cumulative cost CT satisfies CT = Õ( LSA ε2 + LS2A ε + L3SA c2min ).

heading: 4 A MINIMAX LOWER BOUND FOR AUTONOMOUS EXPLORATION
text: Here we present our lower bound for the autonomous exploration problem. To give the lower bound formally, we introduce some basic concepts about the definition of a learning algorithm, following the definitions in Domingues et al. (2021). We define It = (S ×A)t−1 ×S be the set of all possible
histories up to t steps with the form
(
s1, a1, s2, a2, . . . , st
)
∈ It. We denote π , (πt)t≥1 as a history-dependent policy, where πt : It → ∆(A) describes the probability of taking action a ∈ A after observing some history it ∈ It at step t. We consider a class of MDPsM = 〈S,A, P, c, s0〉 such that Asmp. 1 holds, and we only consider the AXL on S→L criterion (cf. Sect. 2). and we note that |S| = S and |A| = A. Then we define an algorithm for the AX problem as a tuple (π, τ,K, {πs}s∈K), which means the algorithm executes a history-dependent policy π, and returns a set K and a set of policies {πs}s∈K after sampling τ times. Definition 3. Given any L ≥ 1, 0 < ε ≤ 1, 0 < δ < 1, and SL ∈ N, an algorithm (π, τ,K, {πs}s∈K) is (ε, δ)-PAC for the AX problem within cumulative cost C, if for any MDP M = 〈S,A, P, c, s0〉 with at most S states and A actions such that M satisfies Asmp. 1 and |S→L | ≤ SL, the algorithm always terminates after using τ samples, the cumulative cost is always not larger than C, and with probability at least 1− δ, it returns a set K ⊇ S→L and a set of policies {πs}s∈K, such that ∀s ∈ S→L , V πss (s0) ≤ (1 + ε)L. The cumulative cost CAX(L, S, ε, δ) for the AX problem is the least C ∈ R satisfying that there exists an algorithm (π, τ,K, {πs}s∈K) within cumulative cost C which is (ε, δ)-PAC for AX.
The following theorem states the lower bound for the autonomous exploration problem.
Theorem 5. Assume that L > 4, A > 4, 4 ≤ SL ≤ min{(A2 ) bL2 c, S2 }, 0 < ε < 1 4 , and δ < 1 16 . Then we have CAX(L, S, ε, δ) = Ω(LSLAε2 log 1 δ ).
We note that this lower bound is for the weakest criterion AXL on S→L , so it implies lower bounds for the other three criteria (AX∗ on S→L , AXL on K, and AX
∗ on K). This lower bound further implies our upper bound (Theorem 3) is nearly minimax-optimal when SL and S2L are of the same order. We also have a lower bound for multi-goal SSP (cf. Appendix H).
For the proof, we first observe that even for a problem two states (an initial state s0 and a goal state g), to determine whether g is in S→L , one needs Ω̃ ( LA/ε2 ) samples. Next, we construct an MDP M′0 with SL − 1 states and A/2 actions, so that each state s ofM′0 can be reached from the initial state s0 with less than L/2 steps. Then for each state s inM′0, we add a new state gs, and each of the remaining A/2 actions of s either transits to state gs or returns to state s. By setting the p(gs|s, a) to ((1 + 3ε)L− V ∗M′0,s(s0))
−1, we can ensure that the expected cost to reach all the states gs from s0 equals to (1 + 3ε)L. Then for each state s inM′0, we slightly increase the probability of some action a to reach gs, making the expected cost to reach the state gs from s0 become L. Under this construction, we can prove the Ω̃(LSLA/ε2) lower bound. A graphical illustration is in Fig. 1 and the full proof is deferred to Appendix G.

heading: 5 CONCLUSION
text: We introduced new algorithms for the autonomous exploration problems, which improve existing ones. Along the way, we also introduced a new problem, multi-goal SSP problem, which can be of independent interest. The natural future directions include designing an algorithm with Õ ( LSLA ε2 ) sample complexity that satisfies all the four criteria listed in Sect. 2 and improving the lower order terms in existing bounds.

heading: A BASIC PROPERTY OF THE OPTIMAL POLICY
text: Lemma 1 (Bertsekas and Tsitsiklis, 1991;Yu and Bertsekas, 2013). Suppose that there exists a proper policy with respect to the goal state g and that for every improper policy π′ there exists at least one state s ∈ S such that V π′g (s) = +∞. Then the optimal policy π∗ is stationary, deterministic, and proper. Moreover, V ∗g = V π∗ g is the unique solution of the optimality equations V ∗ g = LV ∗g and V ∗g (s) < +∞ for any s ∈ S, where for any vector V ∈ RS the optimal Bellman operator L is defined as
LV (s) := min a∈A
{ c(s, a) + Ps,aV } . (1)
Furthermore, the optimal Q-value, denoted by Q∗g = Q π∗
g , is related to the optimal value function as follows
Q∗g(s, a) = c(s, a) + Ps,aV ∗ g , V ∗ g (s) = min a∈A Q∗g(s, a), ∀(s, a) ∈ S ×A. (2)

heading: B HIGH-PROBABILITY EVENT
text: We focus on the samples collected in Alg. 1, and we will define the high-probability event G to do concentration on the variables P̂ and ĉ in Alg. 1. We construct a series of sets of states K0,K1, · · · ,KZ in the following way.
Definition 4 (A series of sets K0,K1, · · · ,KZ). The sets K0,K1, · · · ,KZ are defined as follows:
• Set K0 ← {s0}, and Z ← 0.
• (*) Set KZ+1 ← KZ . For any s /∈ KZ+1, if there is a policy π restricted on KZ such that V πs (s0) ≤ L, then add s to KZ+1.
• Stop if KZ+1 = KZ . Otherwise set Z ← Z + 1 and return to step (*).
We note that under this definition, we have K0 ⊆ K1 ⊆ K2 ⊆ · · · ⊆ KZ = S→L . And each Kz depends only on our MDPM, and is independent of the samples collected in our algorithm. We define the set F := {(Kz, g) : g ∈ S, z = 0, 1, 2, · · · , Z, and V ∗Kz,g(s0) ≤ L}, and we note that |F| ≤ S2. Also, we note that as we set B = 10L in our algorithm, we can obtain

heading: B∗ := max
text: K,g∈F ‖V ∗K,g‖∞ ≤ B. Then we introduce the high-probability event G.
Definition 5 (High-probability event G). We define the event G := G1 ∩ G2 ∩ G3, where
G1 := { ∀(s, a) ∈ S ×A,∀n(s, a) ≥ 1 : |ĉ(s, a)− c(s, a)| ≤ 2 √ 2ĉ(s, a)ιs,a n(s, a) + 28ιs,a 3n(s, a) } ,
G2 := { ∀(s, a, s′) ∈ S ×A× S, ∀n(s, a) ≥ 1 : |Ps,a,s′ − P̂s,a,s′ | ≤ √ 2Ps,a,s′ιs,a n(s, a) + ιs,a n(s, a) } ,
G3 := ∀(s, a) ∈ S ×A,∀n(s, a) ≥ 1,∀(K, g) ∈ F : |(P̂s,a − Ps,a)V ∗K,g| ≤ 2 √ V(P̂s,a, V ∗K,g)ιs,a n(s, a) + 14B∗ιs,a 3n(s, a) , where ιs,a := 4 ln ( 24SA[n(s,a)]
δ
) .
Lemma 2. It holds that P(G) ≥ 1− δ/4.
The lemma above is a direct consequence of the concentration inequalities.
Lemma 3 (Cohen et al. (2020), Lem. B.5). Let π be a proper policy such that for some d > 0, the expected cost V πg (s) ≤ d for every non-goal state s 6= g. 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.
Lemma 4. Let τ be a random variable on [0,+∞) such that Pr(τ > m) ≤ 2e−m/4d for any m ≥ 0, where d > 0 is a constant. We define the random variable τ̂ = 1n n∑ k=1 τ̂k, where each τ̂k has the same distribution with τ . Then for any > 0, we have Pr(E(τ) > τ̂ + d) ≤ exp(− n 2
128 ln2(64/ ) ).
Proof. We set the constant Γ = b8d ln(64/ )c. Then we define the random variables τΓ = min(τ,Γ), τ̌k = min(τ̂k,Γ), and τ̌ = 1n n∑ k=1 τ̌k.
As each τ̌k is a random variable on [0,Γ], by Hoeffding’s inequality, we have
Pr(E(τΓ) > τ̌ + 1 2 d) ≤ exp(−n
2d2
2Γ2 ) ≤ exp(− n
2
128 ln2(64/ ) ).
Moreover, we have
E(τ) ≤ E(τΓ) + ∞∑ i=1 i · Pr(Γ + i− 1 < τ ≤ Γ + i)
= E(τΓ) + ∞∑ m=Γ Pr(τ > m)
≤ E(τΓ) + 2 ∞∑ m=Γ exp(−m/4d)
≤ E(τΓ) + 1
2 d.
Therefore, we obtain
Pr(E(τ) > τ̂ + d) ≤ Pr(E(τ) > τ̌ + d) ≤ Pr(E(τΓ) > τ̌ + 1 2 d) ≤ exp(− n
2
128 ln2(64/ ) ).
C ANALYSIS OF A VISGO PROCEDURE
In this section, we fix the known states K and the goal state g and we analysis an execution of the VISGO procedure in Alg. 4. We use the value iteration of the form V (i+1) = L̃V (i) to estimate the value funtion of the optimal policy. Here, we define the operator L̃ in the following way. For any U ∈ RS such that U ≥ 0, U(g) = 0, and ‖U‖∞ ≤ B, we first define
L̃U(s, a) := ĉ(s, a) + P̃s,aU − b(U, s, a),
for any (s, a) ∈ K ×A, where we define
b(U, s, a) := max c1 √ V(P̂s,a, U)ιs,a n(s, a) , c2 Bιs,a n(s, a) + c3 √ ĉ(s, a)ιs,a n(s, a) ,
for any (s, a) ∈ K×A, and we define the transition probability P̃s,a,s′ = n(s,a)n(s,a)+1 P̂s,a,s′ + I[s′=g] n(s,a)+1 that slightly increases the probability to reach the goal g at each state-action pair.
Then, we set L̃U(s) := mina∈A L̃U(s, a) for s ∈ K and s 6= g, and we set L̃U(s) := cRESET+U(s0) for s ∈ S \ (K ∪ {g}). Finally, we set L̃U(g) := 0. We note that in all of Alg. 1, Alg. 2, and Alg. 3, before we executed VISGO procedure, we have collected φ = Õ(L2/(c2minε
2)) samples for each state-action pair (s, a) ∈ K × A. Thus we have n(s, a) ≥ φ for each (s, a) ∈ K × A. Also, we have VI ≤ cminε/18. The lemmas of this section
Algorithm 4: Subroutine VISGO 1 Input: Set of states S, set of actions A, set of known states K, initial state s0, goal state g and VI. 2 Global variables: B, L, N(), n(), P̂ , θ(), ĉ(). 3 For all (s, a, s′) ∈ K ×A× S, set
P̃s,a,s′ ← n(s, a)
n(s, a) + 1 P̂s,a,s′ +
I[s′ = g]
n(s, a) + 1 .
4 For all (s, a) ∈ K ×A, set ιs,a ← 4 ln ( 24SA[n(s,a)] δ ) . 5 Set i← 0, V (0) ← 0, V (−1) ← +∞. 6 while ‖V (i) − V (i−1)‖∞ > VI do 7 For all (s, a) ∈ K ×A, set
b(i+1)(s, a) ← max { c1
√ V(P̂s,a, V (i))ιs,a
n(s, a) , c2 Bιs,a n(s, a)
} + c3 √ ĉ(s, a)ιs,a n(s, a) , (3)
Q(i+1)(s, a) ← ĉ(s, a) + P̃s,aV (i) − b(i+1)(s, a), (4)
V (i+1)(s) ← min a Q(i+1)(s, a). (5)
8 For all s /∈ K ∪ {g}, set V (i+1)(s)← cRESET + V (i)(s0). 9 Set V (i+1)(g)← 0, i← i+ 1.
10 if V (i)(s0) > L then 11 return Q(i), V (i).
12 return Q(i), V (i).
are based on these conditions. We note that as n(s, a) ≥ φ, and by our construction of φ, we have b(U, s, a) ≤ cminε/18 for any (s, a) ∈ K ×A. Therefore, if U(g) = 0 and U ≥ 0 component-wise, when n(s, a) ≥ φ for any (s, a) ∈ K ×A, we have L̃U(s, a) ≥ 0 for any (s, a) ∈ K ×A. For convenience, we define b(U, s, a) := 0 for any s /∈ K and a ∈ A. Lemma 5 (Tarbouriech et al. (2021), Lemma 12). For any non-negative vector U ∈ RS such that U(g) = 0, for any (s, a) ∈ K ×A, it holds that
P̃s,aU ≤ P̂s,aU ≤ P̃s,aU + ‖U‖∞
n(s, a) + 1 .
The proof of the following Lem. 6 is similar with Lem. 16 in (Tarbouriech et al., 2021), but here we have two distributions p̃ and p. We give the whole proof for completeness. Lemma 6. Let Υ := {v ∈ RS : v ≥ 0, v(g) = 0, ‖v‖∞ ≤ B}. Let f : ∆S×∆S×Υ×R×R×R→ R with f(p̃, p, v, n,B, ι) := p̃v −max { c1 √ V(p,v)ι n , c2 Bι n } , with constants c1 = 6 and c2 ≥ 2c21. Then f satisfies, for all v ∈ Υ, n, ι > 0, p̃, p ∈ ∆S s.t. p̃(s)− 12p(s) ≥ 0 for all s 6= g,
1. f(p̃, p, v, n,B, ι) is non-decreasing in v(s), i.e.
∀(v, v′) ∈ Υ2, v ≤ v′ =⇒ f(p̃, p, v, n,B, ι) ≤ f(p̃, p, v′, n,B, ι);
2. f(p̃, p, v, n,B, ι) ≤ p̃v − c12 √ V(p,v)ι n − c2 2 Bι n ≤ p̃v − 2 √ V(p,v)ι n − 14 Bι n ;
3. If p̃(g) > 0, then f(p̃, p, v, n,B, ι) is ρp̃-contractive in v(s), with ρp̃ := 1− p(g) < 1, i.e.
∀(v, v′) ∈ Υ2, |f(p̃, p, v, n,B, ι)− f(p̃, p, v′, n,B, ι)| ≤ ρp̃‖v − v′‖∞.
Proof. We use the idea in Tarbouriech et al. (2021), Lemma 14 to finish the proof. The second claim holds by max{x, y} ≥ (x+ y)/2,∀x, y, by the choices of c1, c2 and because both√ V(p,v)ι n and Bι n are non-negative. To verify the first and third claims, we fix all other variables but
v(s) and view f as a function in v(s). Because the derivative of f in v(s) does not exist only when
c1 √ V(p,v)ι n = c2 Bι n , where the condition has at most two solutions, it suffices to prove ∂f
∂v(s) ≥ 0 when c1 √ V(p,v)ι n 6= c2 Bι n . Direct computation gives that for any s ∈ S and s 6= g,
∂f
∂v(s) = p̃(s)− c1I
[ c1 √ V(p, v)ι
n ≥ c2
Bι
n
] p(s)(v(s)− pv)ι√
nV(p, v)ι
≥ min { p̃(s), p̃(s)− c 2 1
c2B p(s)
( v(s)− pv )} (i) ≥ min { p̃(s), p̃(s)− c 2 1
c2 p(s) } ≥ 0.
Here (i) is by v(s)− pv ≤ v(s) ≤ B. In addition, we have
∑ s6=g ∣∣∣∣ ∂f∂v(s) ∣∣∣∣ = ∑ s 6=g [ p̃(s)− c1I [ c1 √ V(p, v)ι n ≥ c2 Bι n ] p(s)(v(s)− pv)ι√ nV(p, v)ι ]
= 1− p̃(g)− c1I [ c1 √ V(p, v)ι
n ≥ c2
Bι
n
]√ ι
nV(p, v) [pv − (1− p(g)) · pv]
≤ 1− p̃(g).
Therefore, we obtain that f is ρp̃-contractive.
We note that by definition of P̃s,a, we have P̃s,a,s′ − 12 P̂s,a,s′ ≥ 0 for all (s, a, s ′) ∈ K ×A× S.
The following two lemmas follow the same proof with Lem.18, Lem.19 in (Tarbouriech et al., 2021), respectively.
Lemma 7. The sequence (V (i))i≥0 is non-decreasing.
Lemma 8. L̃ is a ρ-contractive operator with modulus ρ := 1− ν < 1, where ν = min (s,a)∈K×A P̃s,a,g . Hence, the VISGO procedure will terminate after at most dlog(1/ VI)/ log(1/ρ)e iterations.
C.1 THE BOUNDED ERROR PROPERTY OF VISGO
Now we focus on Alg. 1. We give the following lemma of the bounded error property (Lem. 9), which indicates that the value function of the policy πs is close to our estimation. The proof Lem. 9 uses the techniques of Lem. 2 in (Tarbouriech et al., 2020). Our Lem. 9 focuses on a more general operator L̃. In our L̃, we involve the bonus function b(U, s, a), which is not contained in (Tarbouriech et al., 2020).
Lemma 9. In Alg.1, under the event G, for any goal state g that is added to K, let (Q,V ) be the output (Qg, Vg) of VISGO in that round, and let π be the greedy policy with respect to Q. Then π is proper on the model Ps,a,s′ , and for all s ∈ S, we have V πg (s) ≤ (1 + ε)V (s).
Proof. We define Ṽ πg (s) as the value function of π with goal state g on the model P̃s,a,s′ . We will first prove that Ṽ πg (s) ≤ (1 + ε/3)V (s), and then prove that V πg (s) ≤ (1 + ε/3)Ṽ πg (s) using the simulation lemma on the two models P̃s,a,s′ and Ps,a,s′ . Combining them together yields V πg (s) ≤ (1 + ε)V (s).
First we focus on model P̃s,a,s′ . We recall that for any s ∈ K and s 6= g,
L̃u(s) := min a∈A
{ ĉ(s, a)− b(u, s, a) + P̃s,au }
where
b(u, s, a) = max c1 √√√√V(P̂s,a, u)ιs,a n(s, a) , c2 Bιs,a n(s, a) + c3 √ ιs,a n(s, a) ,
and we define b(u, s, a) = 0 when s /∈ K. As we set
φ = O(( L
cminε )2 ln(
SA
δ )),
and n(s, a) ≥ φ, we can obtain b(u, s, a) ≤ cminε/18 when ‖u‖∞ ≤ B. In addition, under the event G1, when n(s, a) ≥ φ, we have |ĉ(s, a) − c(s, a)| ≤ cminε/18 for all (s, a) ∈ S ×A.
We denote l as the final iteration index of VISGO, and V = V (l). In VISGO, we have V (i) = L̃V (i−1) for all i = 1, 2, · · · , l. As V (l−1) ≤ V (l) component-wise, we have for any s ∈ S, V (s) ≤ V (l−1)(s0) + 1 ≤ L+ 1. Hence, ‖V ‖∞ ≤ L+ 1 ≤ B. We set γ = cminε/6. As VI ≤ cminε/18, we have b(u, s, a) + |ĉ(s, a) − c(s, a)| + VI ≤ γ when ‖u‖∞ ≤ B. Given the policy π restricted on K, we introduce the following operators on RS :
Lπu(s) = ĉ(s, π(s))− b(u, s, π(s)) + P̃s,π(s)u,
T πγ u(s) := c(s, π(s))− γ + P̃s,π(s)u.
We can write component-wise
T πγ V ≤ LπV − VI (a) = L̃V − VI
(b) ≤ V,
where (a) uses that π is the greedy policy with respect to V . To prove (b), we recall that V = V (l) = L̃V (l−1). By contraction property of L̃, we have ‖L̃V − V ‖∞ ≤ ‖V (l) − V (l−1)‖∞. By stopping condition of VISGO, we have ‖V (l) − V (l−1)‖∞ ≤ VI, thus (b) is proved. By monotonicity of the operator T πγ , we have for all m > 0, (T πγ )mV ≤ V .
As (T πγ )mV not increases element-wise when m increase, and is non-negative element wise, when m→∞, it will converge to Wπγ , where Wπγ is the value function of policy π in the model P̃ with γ subtracted to all the costs, and we have Wπγ ≤ V component-wise. We define the random variable t̃πg (s) as the number of steps it takes to reach g starting from s on model P̃ when executing policy π. Thus
Wπγ (s) := EP̃ t̃πg (s)∑ t=1 c(st, π(st))− γ | s1 = s  = Ṽ πg (s)− γEP̃ [t̃πg (s)]. Moreover, we have cminE [ t̃πg (s) ] ≤ Ṽ πg (s). Therefore, we get
Ṽ πg (s) ≤ Wπγ (s) 1− γ/cmin ≤ V (s) 1− γ/cmin ≤ (1 + ε/3)V (s).
As n(s, a) ≥ φ, under the event G2, we have ∀(s, a, s′) ∈ S ×A× S ,∣∣∣Ps,a,s′ − P̃s,a,s′ ∣∣∣ ≤ cminε 6(L+ 1) .
Thus by simulation lemma for SSP (Lemma 3 in Tarbouriech et al. (2020)), π is proper on true model Ps,a,s′ , and we have for all s ∈ S, V πg (s) ≤ (1 + ε/3)Ṽ πg (s). The proof is completed.
C.2 OPTIMISM OF VISGO
Now we will give the optimism property. We still focus on Alg. 1. We note that there are exponentially possible number of set K, thus we cannot include all the K in our high-probability event G. As the event G3 includes the sets K0,K1, · · · ,KZ , we choose z ∈ {0 ≤ z ≤ Z : Kz ⊆ K}, and we will compare the output of VISGO (denoted by V ), with the value function of the optimal policy restricted on Kz with goal state g (denoted by V ∗Kz,g). We recall that we define B∗ = max(K,g)∈F ‖V ∗K,g‖∞. By the definition of F , we have B∗ ≤ L+ 1 ≤ B. Lemma 10. Let z ∈ {0 ≤ z ≤ Z : Kz ⊆ K}. Assume that there exists at least one proper policy restricted on Kz with the goal state g, and V ∗Kz,g(s) ≤ B for all s ∈ S. In Alg.1, under the event G, for any output (Q,V ) of the VISGO procedure, it holds that
Q(s, a) ≤ Q∗Kz,g(s, a), ∀(s, a) ∈ K ×A, V (s) ≤ V ∗Kz,g(s), ∀s ∈ S.
Proof. We prove by induction that for any inner iteration i of VISGO, Q(i)(s, a) ≤ Q∗Kz,g(s, a) for any (s, a) ∈ K×A, and V (i)(s) ≤ V ∗Kz,g(s) for any s ∈ S . By definition we haveQ
(0) = 0 ≤ Q∗Kz,g , and V (0) = 0 ≤ V ∗Kz,g . Assume that the property holds for iteration i, then for any (s, a) ∈ K ×A,
Q(i+1)(s, a) = ĉ(s, a) + P̃s,aV (i) − b(i+1)(s, a),
where ĉ(s, a) + P̃s,aV (i) − b(i+1)(s, a)
= ĉ(s, a) + P̃s,aV (i) −max { c1
√ V(P̂s,a, V (i))ιs,a
n(s, a) , c2 Bιs,a n(s, a)
} − c3 √ ĉ(s, a)ιs,a n(s, a)
(i) ≤ c(s, a) + P̃s,aV (i) −max { c1
√ V(P̂s,a, V (i))ιs,a
n(s, a) , c2 Bιs,a n(s, a)
} +
28ιs,a 3n(s, a)
= c(s, a) + f(P̃s,a, P̂s,a, V (i), n(s, a), B, ιs,a) + 28ιs,a 3n(s, a)
(ii) ≤ c(s, a) + f(P̃s,a, P̂s,a, V ∗Kz,g, n(s, a), B, ιs,a) + 28ιs,a 3n(s, a)
(iii) ≤ c(s, a) + P̃s,aV ∗Kz,g − 2
√ V(P̂s,a, V ∗Kz,g)ιs,a
n(s, a) − 14Bιs,a 3n(s, a)
(iv) ≤ c(s, a) + P̂s,aV ∗Kz,g − 2
√ V(P̂s,a, V ∗Kz,g)ιs,a
n(s, a) − 14Bιs,a
3n(s, a) (v) ≤ c(s, a) + Ps,aV ∗Kz,g︸ ︷︷ ︸
=Q∗Kz,g(s,a)
−(B −B∗) 14ιs,a
3n(s, a)
≤ Q∗Kz,g(s, a), where (i) is by definition of G1 and choice of c3, (ii) uses the first property of Lem. 6 and the induction hypothesis that V (i) ≤ V ∗Kz,g, (iii) uses the second property of Lem. 6 and assumption B ≥ max{B∗, 1}, (iv) uses Lem. 5, (v) is by definition of G3. Ultimately, for any (s, a) ∈ K ×A,
Q(i+1)(s, a) ≤ Q∗Kz,g(s, a).
Then for any s ∈ K and s 6= g, we have V (i+1)(s) = min a∈A Q(i+1)(s, a) ≤ min a∈A Q∗Kz,g(s, a) ≤ V ∗Kz,g(s).
In addition, V (i+1)(g) = 0 = V ∗Kz,g(g), and for any s /∈ K ∪ {g}, as Kz ⊆ K, we have
V (i+1)(s) = cRESET + V (i)(s0) ≤ cRESET + V ∗Kz,g(s0) = V ∗ Kz,g(s).
This completes the proof of this lemma.

heading: D PROOF OF THM. 1
text: Proof idea. We provide the main intuition here. We denote K and {πs}s∈K as the output of Alg.1. We fix the round index r, and we consider a state g /∈ K, g ∈ S→L and V ∗K,g(s0) ≤ L. To show that S→L ⊆ K, we need two steps. First, we show that g will be added to U under the event G2. Then we will use the optimism property of VISGO (Lem. 10) to prove that our estimation of the value funtion of the optimal policy Vg(s0) is no larger than L.
To prove thatK ⊆ S→(1+ε)L, we need to prove that when g is added toK, we have V π̃ g (s0) ≤ (1+ε)L, where π̃ is the greedy policy over Qg in that round. This is a direct consequence of Lem. 9.
Now we bound the total cumulative cost. For each state-action pair (s, a) ∈ K × A, we collected Õ(L2/(c2minε
2)) samples. And to reach each s ∈ K, we executed the policy πs, and the cost to reach s is no larger than Õ(L) with high probability. Thus the total cost can be bounded by Õ(L3KA/(c2minε 2)), and K = |K| ≤ S(1+ε)L.
Proof. We first use Lem. 10 to show that S→L ⊆ K. Then we use Lem. 9 to show that K ⊆ S→(1+ε)L, and each policy πs output by Alg.1 satisfies V πss (s0) ≤ (1 + ε)V ∗K,s(s0). Then we will bound the total sample complexity of Alg.1.
To show that S→L ⊆ K, we will prove that Kz ⊆ K for all z = 0, 1, 2, · · · , Z by induction. We observe that {s0} = K0 ⊆ K because the initial snew is s0. Then we assume that Kz ⊆ K, and we will prove Kz+1 ⊆ K. For any state g ∈ Kz+1 and g /∈ Kz , we have V ∗Kz,g ≤ L by definition of Kz+1. To show that g will be added to K eventually, we need to prove the following two statements: (1) g is added to U ; (2) the output of VISGO procedure Vg(s0) ≤ L when Kz ⊆ K. We observe that as V ∗Kz,g ≤ L, there must exist (s, a) ∈ Kz ×A such that Ps,a,g ≥ 1/L. As we have collected φ = Õ(L2) samples for each of the state-action pair (s, a) ∈ K × A, under event G2, we can obtain that P̂s,a,g ≥ 34L > 0, which yields that g has been discovered. Thus g has been added to U in some round, and statement (1) is verified. The statement (2) is a direct consequence of the optimism property Lem. 10. Thus we have proved that Kz+1 ⊆ K, which yields that S→L ⊆ K. Then we will prove K ⊆ S→(1+ε)L. By Lem. 9, each time when we add s to K, we have V πs s (s0) ≤ (1 + ε)L, i.e. the AXL on K criterion is met. We recall that the definition of S→(1+ε)L is a recursive construction, adding new state s whenever there exists some policy π such that V πs (s0) ≤ (1 + ε)L. Therefore, each state added to K is a subset of S→(1+ε)L, and we obtain that K ⊆ S → (1+ε)L.
Now we will bound the total cumulative cost. We note that we have collected φ = Õ(L2/(c2minε 2)) samples for each state-action pair (s, a) ∈ K ×A. To collect each sample (s, a, s′, c), we executed a policy πs to reach the state s, and the expected cost V πss (s0) ≤ (1 + ε)L ≤ 2L. By Lem. 3, we obtain that with probability at least 1− δ/4, for any state s, each time when the policy πs is executed, the total cost to reach s from s0 is no larger than O(L log(S/δ)). Therefore, the total cumulative cost in Part 1 of Alg. 1 can be bounded by Õ(L3S(1+ε)LA/(c2minε 2)). Thus we obtain the bound
CT = Õ( L3S(1+ε)LA
c2minε 2
).
Now we bound the total failure probability. The event G fails with probability no more than δ/4. And in the previous para the failure probability is bounded by δ/4, thus the total failure probability is no more than δ/2. The proof of Thm. 1 is completed.

heading: E PROOF OF THM. 2
text: First we define the high-probability event E to do concentration on all the samples collected in Alg.2. We note that the definition of E also applies for Alg. 3 after it finishes the subroutine Alg. 1 and clears all the samples in Alg. 1. We note that after Alg.1, the set of known states K is fixed, and our algorithm focuses on the new MDPM† = 〈K†,A, P †, c†, s0〉. Here for any g ∈ K, we denote the vector V ∗g ∈ RK ′ as the value function of the optimal policy on MDPM† with respect to goal g, and when K ⊆ S→(1+ε)L in Alg. 2, we have B † ∗ := ‖V ∗g ‖∞ ≤ B. For convenience, here we denote V ∗g (s) as the expected cost of the optimal policy to reach g from s on MDP M †, and we have V ∗g (s) ≤ 2L+ 1 ≤ B for all (s, g) ∈ K† ×K. Then we define the high-probability event G†. Definition 6 (High-probability event G†). We define the event G† := G†1 ∩ G † 2 ∩ G † 3 , where
G†1 :=
{ ∀(s, a) ∈ K† ×A,∀n(s, a) ≥ 1 : |ĉ(s, a)− c†(s, a)| ≤ 2 √ 2ĉ(s, a)ιs,a n(s, a) + 28ιs,a 3n(s, a) } ,
G†2 := ∀(s, a, s′) ∈ K† ×A×K†, ∀n(s, a) ≥ 1 : |P †s,a,s′ − P̂s,a,s′ | ≤ √ 2P †s,a,s′ιs,a n(s, a) + ιs,a n(s, a) , G†3 := ∀(s, a, g) ∈ K† ×A×K,∀n(s, a) ≥ 1 : |(P̂s,a − P †s,a)V ∗g | ≤ 2 √ V(P̂s,a, V ∗g )ιs,a n(s, a) + 14B†∗ιs,a 3n(s, a)
, where ιs,a := 4 ln ( 24SA[n(s,a)]
δ
) .
Finally, we define the high-probability event E := G ∩ G†. And we have the following lemma. Lemma 11. It holds that P(E) ≥ 1− δ/2.
We introduce the lemma of optimism and the lemma of bounded error in Alg. 2. We note that the proof of them is the same with Lem. 10 and Lem. 9, respectively. Lemma 12. In Alg.2, under the event E , for any output (Qg, Vg) of the VISGO procedure, it holds that
Qg(s, a) ≤ Q∗g(s, a), ∀(s, a) ∈ K† ×A, Vg(s) ≤ V ∗g (s), ∀s ∈ K†.
Lemma 13. In Alg. 2, under the event E , let (Qg, Vg) be the output of VISGO, where g is the goal state, and let π be the greedy policy with respect to Qg. Then π is proper on the model Ps,a,s′ , and for all s ∈ K†, we have V πg (s) ≤ (1 + ε)Vg(s).
Now we give the proof of Thm. 2. First we prove the correctness. By Thm. 1, VOISD outputs a set K such that S→L ⊆ K ⊆ S→(1+ε)L. Now we focus on the set of policies {πs}s∈K that Alg. 2 outputs, and we will prove that for each g ∈ K, we have V πg (s0) ≤ (1 + 3ε)L and V πg (s0) ≤ V ∗K,g(s0) + 3εL. As we set ε← ε/3 in the beginning of Alg. 1, the correctness of Alg. 1+Alg. 2 can be proved. By Lem. 13 and Lem. 12, we obtain that V πg (s0) ≤ (1 + ε)Vg(s0) ≤ (1 + ε)V ∗g (s0). We note that V ∗g (s0) ≤ (1 + ε)L, because Alg. 1 satisfies AXL on K. Hence, we can get V πg (s0) ≤ (1 + ε)2L ≤ (1+3ε)L, and V πg (s0) ≤ V ∗g (s0)+ε(1+ε)L ≤ V ∗g (s0)+3εL. Thus Alg. 2 outputs a set of policies {πs} that satisfies both AXL on K and AX∗ on K. Similarly with Thm. 1, as we collect φ samples for each state-action pair (s, a) ∈ K × A, we can obtain that with probability at least 1− δ, the total sample complexity is bounded by Õ(L 3S(1+ε)LA
c2minε 2 ).

heading: F PROOF OF THM. 3
text: Here we give a proof of Thm. 3 and we focus on the fixed set K† and our constructed MDP M† = 〈K†,A, P †, c†, s0〉. We denote K = |K|, and K ′ = |K†| = K + 1.
Proof idea. First we prove the accuracy of Alg.3. It uses Alg. 1 with ε = 1 as a subroutine, thus we can get a set K such that S→L ⊆ K ⊆ S→2L. For each goal state g, when g is removed from U and the policy πg is set, the cost to reach g from s0 under policy πg has been tested for λ = Õ(1/ 2) times. Therefore, by the concentration inequality, we can prove that the average cost is close to the expected cost of πg. Moreover, the average cost is less than our estimation of the cost of the optimal policy Vg(s0) plus L. Hence we can prove that the expected cost of πg is close to the optimal cost using the optimism property.
To bound the cumulative cost of Alg.3, we will focus on the number of "rounds" and the cost it takes in each round. By multiplying them together, we can get the upper bound of the cumulative cost.
It’s straightforward to show that the total cost in each round is no larger than Õ(L/ε2). Then we will bound the total number of rounds. We denote T as the total number of samples collected in Alg. 3. The number of success rounds is at most K. And the trigger condition holds for at most log2(2T ) times for each state-action pair (s, a), thus we obtain that the number of skipped rounds can be bounded by K ′A log2(2T ). Now we need only to bound the total number of failure rounds. We borrow the idea from (Lim and Auer, 2012). We first define the regret of an episode as the total cost in this episode minus our estimation of the optimal cost, and define the total regret as the sum of the regret in each episode. Then we prove a regret bound of our Alg. 3, and the upper bound grows sublinearly with the total number of episodes M . As the regret in each failure round is at least Lλ, thus we can give a lower bound of the total regret that grows linearly with the number of episodes M . By solving the inequality, we will obtain that the total number of failure rounds is bounded by Õ(KA+ εK2A). Thus the total number of rounds is bounded by Õ(KA+ εK2A), and multiplying it with the cost in each round, we can get the bound in Thm. 3 and complete the proof.
Now we give the full proof. Here we denote V ∗g (s) as the expected cost of the optimal policy to reach g from s on MDP M†, and we have V ∗g (s) ≤ 2L+ 1 ≤ B for all (s, g) ∈ K† ×K. We recall the definition of the high-probability event E in Appendix E. Also, we introduce the lemma of optimism and the lemma of bounded error in Alg. 3, and the proof of them is the same with Lem. 12 and Lem. 13, respectively. Lemma 14. In Alg.3, under the event E , for any output (Q,V ) of the VISGO procedure, it holds that
Q(s, a) ≤ Q∗g(s, a), ∀(s, a) ∈ K† ×A, V (s) ≤ V ∗g (s), ∀s ∈ K†,
where g is the goal state in that round. Lemma 15. In Alg. 3, under the event E , for any output (Q,V ) of the VISGO procedure, let π be the greedy policy with respect to Q. Then π is proper on the model Ps,a,s′ , and for all s ∈ K†, we have V πg (s) ≤ 2V (s), where g is the goal state in that round.
Now we prove the correctness of Alg. 3, i.e. Alg. 3 satisfies AX∗ on K. The main intuition is that each policy πs has been tested for λ times in a success round, and the average cost it takes to reach s from s0 is less than our estimate for optimal cost V (s0) plus L. Thus by concentration inequalities, the expected cost of πs is close to optimal. Lemma 16. Let {πs}s∈K be the set of policies output by Alg.3. With probability at least 1 − δ, V πss (s0) ≤ V ∗s (s0) + εL for all s ∈ K.
Proof. We fix any state s ∈ S. In any given round where the chosen target is s, let τ̂k be the total cost in the k-th episode of that round. Recall that for the algorithm to output a policy πs, its empirical performance after λ episodes must satisfy that τ̂ ≤ V (s0) + L, where τ̂ = ∑λ k=1 τ̂k λ .
We define the random variable τ as the total cost it takes to reach the goal state s from the start state s0 when executing policy πs, and we have E(τ) = V πss (s0) by definition. We note that we have collected φ = Õ(L2/c2min) samples for each of the state-action pair (s, a). By Lem. 15, under event E , the policy πs is proper, and we have E(τ) ≤ 2L. Hence, we obtain d := ‖V πss ‖∞ ≤ 2L+ 1 ≤ 4L. By Lem 3, we obtain Pr(τ > m) ≤ 2 exp(−m/4d) for any m > 0.
As we set
λ = d2048 2 ln2( 256 ) ln( 2S
δ )e,
by Lem. 4, we obtain that with probability at least 1− δ/(2S), we have
V πss (s0) = E(τ) ≤ τ̂ + L.
We note that τ̂ ≤ V (s0) + L ≤ V ∗s (s0) + L by the optimism property (Lem. 14). Hence, as we set = ε/3 in initial, we obtain that with probability at least 1− δ/(2S),
V πss (s0) ≤ V ∗s (s0) + εL.
Finally, as there are at most S states in total, and the event E holds with probability at least 1− δ/2, by the union bound, the total success probability is at least 1− δ.
Now we focus on bounding the cumulative cost of Alg.3. The key idea lies in bounding the "regret". We will use the regret to bound the total number of rounds. We first define the regret in the k-th episode of the j-th round. We denote Hj,k as the number of steps it takes in the k-th episode of the j-th round. The regret in an episode k is defined as
( Hj,k∑ h=1 cj,kh )− V j(s0),
where cj,kh is the empirical cost in the h-th step in the k-th episode in the j-th round, and V j(s0) is the value of V (s0) in the j-th round. Let nj be the total number of episodes executed in the j-th round, we define the regret in the j-th round as follows:
nj∑ k=1 (( Hj,k∑ h=1 cj,kh )− V j(s0)).
Then we will define the total regret of Alg.3. Let r be the total number of rounds, nj be the total number of episodes executed in the j-th round, and 0 ≤ nj ≤ λ. Then we know that the total number
of episodes in the whole process of Alg.3 is M = r∑ j=1 nj . For notation convenience, we define Hm as the number of steps it takes in the m-th episode of the whole process of Alg.3, and denote cmh as the empirical cost in the h-step of episode m. Finally we define the total regret of all the rounds as
R := r∑ j=1 nj∑ k=1 (( Hj,k∑ h=1 cj,kh )− V j(s0)) = M∑ m=1 (( Hm∑ h=1 cmh )− V m(s0)).
We will give both the upper bound and the lower bound of the regret. Here we gives the upper bound.
Lemma 17. Under event E , the total regret in M episodes is at most
R = Õ(L √ KAM + LK2A).
This upper bound comes from the regret bound of the EB-SSP algorithm (Tarbouriech et al., 2021), which solves the classical SSP problem, and the proof of Lem. 17 is similar with Thm.3 in (Tarbouriech et al., 2021).
We observe that there are at most Õ(KA) skipped rounds and K success rounds. We denote by rf the number of failure rounds, and we have the total number of episodes M = Õ((KA+ rf )λ) = Õ((KA+ rf )/ 2). Thus the total regret in r rounds can be bounded by rf sublinearly:
R = Õ( L √ KArf + LKA + LK2A).
Then we gives the lower bound of the total regret in terms of the number of failure rounds rf .
Lemma 18. With probability 1− δ, when r = Õ((SA)2), the total regret in the r rounds is at least
R = Ω̃( Lrf − LKA ),
where rf in the number of failure rounds in the r rounds.
Proof. By the criterion of our performance check, in any failure round, we have τ̂ > V (s0) + L, and in round j, we have τ̂ = 1λ nj∑ k=1 ( Hj,k∑ h=1 cj,kh ) by definition. Hence, in any failure round j, the regret is λτ̂ − njV j(s0) ≥ λ(τ̂ − V j(s0)) ≥ λ L = Ω̃(Lrf ).
Then we focus on skipped rounds and success rounds. We denote gj as the goal state in the j-th round, and πj as the policy π̃ in the j-th round, which is the greedy policy over the Q-function in the j-th round. We observe that the regret in any round j satisfies nj∑ k=1 (( Hj,k∑ h=1 cj,kh )−V j(s0)) ≥ −L+ nj−1∑ k=1 (( Hj,k∑ h=1 cj,kh )−V ∗ gj (s0)) ≥ −L+ nj−1∑ k=1 (( Hj,k∑ h=1 cj,kh )−V πj gj (s0)), where we used the optimism property in Lem. 14. We note that Hj,k∑ h=1 cj,kh is the empirical cost of policy πj in episode k, and we will use the concentration inequality to give a lower bound of the regret in round j. As the last episode in a skipped round can terminate before reaching the goal, we should take special considerations the last episode of each round. We directly use −L to lower bound the regret of the last episode in round j. Then we denote n = nj − 1, and focus on the previous n episodes in round j.
Now we fix the round index j. We denote the random variable τ as the cost to reach gj from s0, and we recall that τ̂k = Hj,k∑ h=1 cj,kh . By Lem. 4 with d = 4L, with probability at least 1− δ (SA)2 , we have
n∑ k=1 (τ̂k − E(τ)) ≥ −2Γ √ n ln( SA δ ) ≥ −2Γ √ λ ln( SA δ ) ≥ −Ω̃(L ),
where Γ = b8d ln(64/ )c. Thus the regret in any round j is no less than−Ω̃(L ). As there are at most Õ(KA) skipped rounds and K success rounds, we obtain that the total regret R has the lower bound
R = Ω̃( Lrf − LKA ).
Now we bound the total failure probability. The number of rounds r = Õ((SA)2), in each round the failure probability is at most δ(SA)2 , and the events E fails with probability δ/2. By resetting δ → O(δ/(SALε )) in initial, the total failure probability is at most δ.
As the lower bound is linear in rf , and the upper bound is sublinear in rf , we can solve it and obtain that rf = Õ(KA+ K2A), thus the total number of rounds can be bounded by Õ(KA+ K2A).
To get the cumulative cost bound in Thm. 3, we need only to bound the cost in a round. In any round, we observe that except for the last episode, the average cost τ̂ for all the other episodes is no larger than V (s0) + L ≤ 2L, thus the total cost in these episodes is no larger than 2Lλ = Õ(L/ 2). Also, we know that in the any episode, the expected cost of the policy π̃ to reach the goal from s0 is no larger than 2L. Thus by Lem. 3, in any round, with probability at least 1 − δ(SA)2 , the cost in the last episode is no larger than Õ(L). Hence, the total cost in each round is no larger than Õ(L/ 2). By multiplying it with Õ(KA+ K2A), the cumulative cost in Alg.3 can be bounded by Õ(LKA/ε2 + LK2A/ε+ L3KA/c2min), where the term L
3KA/c2min comes from the subroutine of Alg. 1. As we have K ≤ S2L, we obtain the bound in Thm. 3. Now we count the total failure probability. First, Alg. 1 fails with probability δ/2, the event E fails with probability δ/2, and the lower bound of the total regret R fails with probability δ. And in the
previous para, to bound the cost in the last episode of each round using Lem. 3, the failure probability in each episode is at most δ(SA)2 . We observe that the total number of these failures is no larger than the total number of rounds, and the total number of rounds can be bounded by Õ(KA + K2A), where we omit the logarithmic factors. Thus by setting δ → O(δ/(SALε )) in initial, we can bound the total failure probability by the initial δ, and the proof of Thm. 3 is completed.

heading: G ANALYSIS OF THE LOWER BOUND
text: Here we discuss the lower bound of the autonomous exploration problem. We recall that we relax the problem and consider only all the MDPsM with S states and A actions, andM satisfies Asmp. 1. Our algorithm needs output a set K ⊇ S→L and a set of policies {πs}s∈K, and when s ∈ S→L , the policy πs satisfies V πss (s0) ≤ (1 + ε)L. Moreover, we note that here we allow the algorithm to output non-deterministic policies, i.e. the policy πs : S → ∆(A) is a function from the set of states to a probability distribution over the actions.
We recall the some basic concepts about the definition of a learning algorithm, and we use the notations in (Domingues et al., 2021). Let It = (S ×A)t−1 × S be the set of all possible histories up to t steps, that is, be the set of tuples of the form ( s1, a1, s2, a2, . . . , st ) ∈ It. We denoted
π , (πt)t≥1 as a history-dependent policy, where π t : It → ∆(A) describes the probability of taking action a ∈ A after observing some history it ∈ It. Given an MDPM = 〈S,A, p, c, s0〉, a policy π interacting with the MDPM defines a stochastic process denoted by (St, At)t≥1, where (S
t, At) is the state-action pair at time t. The Ionescu-Tulcea theorem ensures the existence of the probability space (Ω,F ,PM) such that
PM [ S1 = s ] = I[s = s0],PM [ St+1 = s | At, It ] = p ( s | St, At ) , and PM [ At = a | It ] = πt ( a | It ) ,
where π = (πt)t≥1 and for any t, I t ,
( S1, A1, S2, A2, . . . St ) is the random vector in It containing
all state-action pairs observed up to step t. We denote the σ-algebra generated by It as F t. And we denote by PITM the measure of IT under PM as follows:
PI T M [ iT ] , PM [ IT = iT ] = I(s1 = s0) T−1∏ t=1 πt ( at | it ) p ( st+1 | st, at ) .
Then we denote EM as the expectation under PM. Note that the dependence of PM and EM on the policy π is denoted implicitly in the definition of PM. We will denote them explicitly as Pπ,M and Eπ,M respectively when we need to stress π.
Moreover, given the MDPM = 〈S,A, p, c, s0〉, we denote V ∗M,g(s) as the optimal policy to reach the goal state g from the state s.
Here we introduce the basic definitions and the technical lemmas used in our proof. Definition 7. The Kullback-Leibler divergence between two distributions P1 and P2 on a measurable space (Ω,G) is defined as
KL(P1,P2) , ∫
Ω
log ( dP1 dP2 (ω) ) dP1(ω),
if P1 P2 and +∞ otherwise. For Bernoulli distributions, we define ∀(p, q) ∈ [0, 1]2, kl(p, q) , KL(B(p),B(q)) = p log ( p
q
) + (1− p) log ( 1− p 1− q ) .
Lemma 19 (Lemma 5, Domingues et al. (2021), modified). LetM andM′ be two MDPs that are identical except for their transition probabilities, denoted by p and p′, respectively. Assume that we have ∀(s, a), p(· | s, a) p′(· | s, a). Then, for any stopping time τ with respect to (F t)t≥1 that satisfies PM[τ <∞] = 1,
KL ( PI τ
M,PI τ M′ ) = ∑ s∈S ∑ a∈A EM [ Nτs,a ] KL(p(· | s, a), p′(· | s, a)),
where Nτs,a , ∑τ t=1 1{(St, At) = (s, a)} and Iτ is the random vector representing the history of τ samples.
Lemma 20 (Lemma 1, Garivier et al. (2019)). Consider a measurable space (Ω,F) equipped with two distributions P1 and P2. For any F-measurable function Z : Ω→ [0, 1], we have
KL(P1,P2) ≥ kl(E1[Z],E2[Z]),
where E1 and E2 are the expectations under P1 and P2 respectively.
Lemma 21. For any p, q ∈ (0, 12 ], kl(p, q) ≤ 2(p−q)2 q .
Now we construct a family of adversarial MDPs to obtain the lower bound of sample complexity.
An example of hard MDP with two states. For clarity, we first consider an MDP with two states s and g. There are A actions in the state s, and each action a transits s to g with success probability ((1 + ε)L)−1, and transits s to s with failure probability 1− ((1 + ε)L)−1. In this MDP, the expected cost to reach g from s is (1 + ε)L. Then we construct A MDPs, each MDP increasing the success probability of an action a to L−1, and the the expected cost to reach g from s is L in all of these MDPs. Thus to discriminate these MDPs, we need to discriminate between the two Bernoulli distributions with p = L−1 and p = ((1 + ε)L)−1. Using the KL-divergence, we can obtain that the minimum number of samples is Õ(L/ε2). As there are A actions, we can obtain the Õ(LA/ε2) lower bound.
The construction of hard MDPs with general SL. Now we fix L,A, SL, ε such that L > 4, A > 4, 4 ≤ SL ≤ min{(A2 ) bL2 c, S2 }, 0 < ε < 1 4 . It’s straightforward to verify that we can construct an MDP M′0 = 〈S ′,A′, p′0, c, s0〉 with |S ′| = SL − 1 states and |A′| = dA/2e actions, such that c(s, a) = cmin for each (s, a) ∈ S ′ ×A′, and each state s ∈ S ′ is incrementally (L/2)-controllable, i.e. its S→L/2 = S ′. Thus for each s ∈ S ′, we have V ∗M′0,s(s0) ≤ L 2 .
Then we will construct the MDPM0 = 〈S,A, p0, c, s0〉 based onM′0 in the following way. First we construct SL − 1 states and bA/2c actions, and denote them as S† and A†, respectively, and we set S = S ′ ∪ S†, A = A′ ∪ A†. For each s ∈ S† and any actions a ∈ A, we have p0(s0|s, a) = 1, i.e. every action at s ∈ S† is the reset action to s0. And we set c(s, a) = cmin for each (s, a) ∈ S × A. Moreover, for all (s, a) ∈ S ′ ×A′, our transition model p0(·|s, a) is constructed based on p′0(·|s, a), i.e. we set p0 as follows:
p0(s ′|s, a) = p′0(s′|s, a), ∀(s, a, s′) ∈ S ′ ×A′ × S ′, p0(s ′|s, a) = 0, ∀(s, a, s′) ∈ S ′ ×A′ × S†,
p0(s ′|s, a) = 0, ∀(s, a, s′) ∈ S ′ ×A† × S ′,
and then we need only define the transition function p0(g|s, a) for each (s, a, g) ∈ S ′ × A† × S†. We note that as |S†| = SL − 1, for each g ∈ S†, we can pair it with a state s ∈ S ′, and all pairs (g, s) are mutually disjoint. Thus we use the notation gs ∈ S† to denote a state in S† that is paired with the state s ∈ S ′. Then for all (s, a) ∈ S ′ ×A†, we define
p0(gs|s, a) = cmin
(1 + 3ε)L− V ∗M′0,s(s0) , p0(s|s, a) = 1− p0(gs|s, a),
i.e. each new action a either transits s ∈ S ′ to its pair gs ∈ S† or remains at s itself. We observe that V ∗M0,s(s0) = V ∗ M′0,s (s0) for all s ∈ S ′, and V ∗M0,s(s0) = (1 + 3ε)L for all s ∈ S †.
Then we define the adversarial examples of MDPs. Now we fix any state-action pair (s, a) ∈ S ′×A†. The adversarial MDPM(s,a) = 〈S,A, ps,a, c, s0〉 is constructed fromM0, and the only difference ofM(s,a) andM0 lies on the transition probability at the fixed state-action pair (s, a), and we define ps,a(·|s, a) as follows:
ps,a(gs|s, a) = cmin
L− V ∗M′0,s(s0) , ps,a(s|s, a) = 1− ps,a(gs|s, a),
i.e. at state s, we slightly increase the probability of the action a to reach the pair state gs. And for all the state-action pairs (s′, a′) other than (s, a), the transition probability ps,a(·|s′, a′) is the
same as p0(·|s′, a′). Therefore, we have V ∗M(s,a),gs(s0) = L, and V ∗ M(s,a),s′(s0) = V ∗ M0,s′(s0) for all s′ ∈ S \ {gs}. Finally, we define the family of our adversarial MDPs as {M0} ∪ {M(s,a)}(s,a)∈S′×A† . We note that for each MDPM(s,a), its |S→L | = SL, and it satisfies Asmp. 1. Also, for the MDPM0, its |S→L | = SL − 1, and it also satisfies Asmp. 1. Thus the family is valid for the relaxed autonomous exploration problem.
Now we give our proof of Thm. 5 through the adversarial family of MDPs. Here we use the techniques of Thm. 7 in (Tarbouriech et al., 2020).
Proof. We denote by P(s∗,a∗) , Pπ,M(s∗,a∗) and E(s∗,a∗) , Eπ,M(s∗,a∗) the probability measure and expectation in the MDPM(s∗,a∗) by following π and by P0 and E0 the corresponding operators in the MDPM0. We fix any algorithm (π, τ,K, {πs}s∈K) that solves the AX problem. We will prove that when working on the MDPM0, the algorithm will cost at least Ω(LSLAcminε2 log 1 δ ) samples in expectation, i.e.
E0[τ ] = Ω( LSLA
cminε2 log
1 δ ),
which yields that the lower bound of the total cost is Ω(LSLAε2 log 1 δ ).
Now we fix the state-action pair (s∗, a∗) ∈ S ′ ×A†, and we denote gs∗ ∈ S† as the state paired with s∗ ∈ S ′. Also, we denote the random variable Nτ(s,a) as the number of samples that the algorithm takes at the state-action pair (s, a) ∈ S × A. For any Fτ -measurable random variable Z taking values in [0, 1], we have
E0 [ Nτ(s∗,a∗) ]72cminε2 L
(a) ≥ E0 [ Nτ(s∗,a∗) ] KL ( cmin
(1 + 3ε)L− V ∗M′0,s∗(s0) , cmin L− V ∗M′0,s∗(s0) ) (b) = KL ( PI τ
0 ,PI τ (s∗,a∗) ) (c) ≥ KL ( E0[Z],E(s∗,a∗)[Z] ) ,
where (a) uses Lemma 21 and V ∗M′0,s∗(s0) ≤ L 2 ; (b) uses Lemma 19; (c) uses Lemma 20.
For any policy π : S → ∆(A), we define π(a|s) as the probability that the policy π takes action a at state s. Then for any (s, a) ∈ S ′ × A†, we define the event Zs,a = 1{The algorithm’s output satisfies gs ∈ K and πgs(a|s) ≥ 23}. And we set the event Z = Zs∗,a∗ . We observe that as the algorithm (π, τ,K, {πs}s∈K) solves the AX problem, when working on the MDPM(s∗,a∗), with probability at least 1−δ, its output should satisfy gs∗ ∈ K and the expected cost of the policy πgs∗ satisfies V πgs∗ s∗ (s0) ≤ (1 + ε)L, which yields that πgs∗ (a∗|s∗) ≥ 23 . Therefore, for any (s∗, a∗) ∈ S ′ ×A†, we have
P(s∗,a∗)[Zs∗,a∗ ] ≥ 1− δ,
as the algorithm succeeds with probability at least 1− δ. Moreover, for any policy π we observe that for any two state-action pairs (s, a) and (s, a′), a 6= a′, we cannot have both π(a|s) ≥ 23 and π(a ′|s) ≥ 23 . Therefore, we obtain that given any state s ∈ S ′,
we have ∑ a∈A† P0[Zs,a] ≤ 1,
as any two events Zs,a and Zs,a′ (a 6= a′) are mutually exclusive. We recall that we set Z = Zs∗,a∗ , and we can obtain
kl ( E0[Z],E(s∗,a∗)[Z] ) = kl ( P0[Zs∗,a∗ ],P(s∗,a∗)[Zs∗,a∗ ] )
(a) ≥ (1− P0[Zs∗,a∗ ]) log
( 1
1− P(s∗,a∗)[Zs∗,a∗ ]
) − log(2)
(b) ≥ (1− P0[Zs∗,a∗ ]) log
( 1
δ
) − log(2),
where (a) uses the fact that kl(p, q) ≥ (1− p) log (
1 1−q
) − log(2) for any p, q ∈ [0, 1]; (b) uses that
P(s∗,a∗)[Zs∗,a∗ ] ≥ 1− δ. Therefore, we have
E0 [ Nτ(s∗,a∗) ] ≥ L
72cminε2 ((1− P0[Zs∗,a∗ ]) log
( 1
δ
) − log(2)).
We recall that ∑ a∈A† P0[Zs,a] ≤ 1. Thus we can obtain that for any s∗ ∈ S ′,∑
a∗∈A† E0 [ Nτ(s∗,a∗) ] ≥ L 72cminε2 ( ( |A†| − 1 ) log ( 1 δ ) − log(2)|A†|).
Summing up all the state-action pairs (s∗, a∗) ∈ S ′ × A†, we can obtain the lower bound of the sample complexity. E0[τ ] = ∑
(s,a)∈S×A
Nτ(s,a) ≥ ∑ (s∗,a∗)∈S′×A† E0 [ Nτ(s∗,a∗) ] ≥ L|S ′| 72cminε2 ( ( |A†| − 1 ) log ( 1 δ ) −log(2)|A†|)
As |A†| = bA/2c and |S ′| = SL − 1, provided that L > 4, A > 4, 4 ≤ SL ≤ min{(A2 ) bL2 c, S2 }, 0 < ε < 14 , and δ < 1 16 , we can eventually prove that
E0[τ ] = Ω( LSLA
cminε2 log
1 δ ),
which yields the lower bound of the cumulative cost in Thm. 5.

heading: H LOWER BOUNDS FOR MULTI-GOAL SSP
text: Here we formulize the lower bound CMSSP(L, S, ε, δ) for the multi-goal SSP problem. First we define an algorithm for the multi-goal SSP problem as a triple (π, τ, {πs}s∈S), which means the algorithm executes a history-dependent policy π, and returns a set of policies {πs}s∈S after sampling τ times. Also, we allow πs to be non-deterministic policies. Definition 8. Given any L ≥ 1, 0 < ε ≤ 1, 0 < δ < 1, and S ∈ N, an algorithm (π, τ, {πs}s∈S) is (ε, δ)-PAC for the multi-goal SSP problem within cumulative cost C, if for any MDP M = 〈S,A, P, c, s0〉 with at most S states and A actions such thatM satisfies Asmp. 1 and S→L = S, the algorithm always terminates after using τ samples, and the cumulative cost is always not larger than C, and with probability at least 1 − δ, it returns a set of policies {πs}s∈S , such that ∀s ∈ S, V πss (s0) ≤ V ∗s (s0) + εL. The cumulative cost CMSSP(L, S, ε, δ) for the multi-goal SSP problem is the least C ∈ R satisfying that there exists an algorithm (π, τ, {πs}s∈S) within cumulative cost C which is (ε, δ)-PAC for multi-goal SSP.
We remark that our constructed adversarial examples for the autonomous exploration problem can also be applied to multi-goal SSP using the similar proof with Thm. 5, i.e. CMSSP(2L, 2S, ε/2, δ) ≥ CAX(L, S, ε, δ). Thus we obtain the following lower bound for multi-goal SSP, which implies that our Alg. 3 is also minimax for multi-goal SSP problem.
Theorem 6. Assume that L > 8, A > 4, 8 ≤ S ≤ (A2 ) bL2 c, 0 < ε < 18 , and δ < 1 16 . Then we have
CMSSP(L, S, ε, δ) = Ω( LSA
ε2 log
1 δ ).

Review summaries:
This paper studies the autonomous exploration problem and multi-goal SSP problem, and proposes three algorithms with improved cumulative costs on 4 learning objectives. The authors also construct a hard instance and show the lower bound of the cumulative cost. Their bounds are optimal in terms of $L, A, \epsilon$. The main technical contributions are a new series construction of $\mathcal{K}$, the connection between autonomous exploration and multi-goal SSP, and the construction of the hard instance.  

The authors consider the incremental autonomous exploration problem. That is, the agent faces an MDP and wants to learn near-optimal goal-conditioned policies to reach the states that are L-controllable, i.e. incrementally reachable from an initial state s_0 within L steps in expectation. The learning procedure is the following: the agent collects transition by interacting with the MDP, decides to stop, and outputs a set of states (that should be the L-controllable states) and a policy for each state ( that should be the associated near-optimal goal-conditioned policy). The authors propose the Value-Aware Autonomous Exploration (VALAE) algorithms. It works in 3 phases: in the first one a sub-algorithm Value-Optimistic Incremental State Discovery (VOISD) aims at identifying the set of  L-controllable states then sub-algorithm Reduce Autonomous Exploration to Multi-Goal SSP (Re-MG-SSP) as burn-in sample collector, finally a procedure close to the one of UCBExplore by Lime and Auer (2012). They prove a bound on the sample complexity ( the number of steps before the algorithm stops) of order O(L S_{2L} A / \epsilon^2 ) where S_L is the number of  L-controllable states, A the number of actions, \epsilon the error tolerated for the goal-conditioned policy. This bound improves prior results by Lim and Auer (2012) and Tarbouriech et al. (2020) with respect to the dependence on \epsilon or L. The authors also proved a lower bound of order  \Omega(L S_{L} A / \epsilon^2 )  implying that  VALAE is nearly minimax optimal if S_L grows polynomially with L.

This paper studies the sample complexity of learning algorithms for autonomous explorations (AX). Theoretical results showed that the proposed algorithm (VOISD, VOISD+Re-MG-SSP, VALAE) achieved better sample complexities than the existing two studies. The authors compared the methods by setting the uniform cost. Further, the proposed algorithm seems to have more general performance.