Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path
Authors: Haoyuan Cai
Tengyu Ma
Simon Shaolei Du
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning theory
autonomous exploration

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 goal-conditioned policies to reach the $L$-controllable states: states that are incrementally reachable from an initial state $s_0$ 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.

Under review as a conference paper at ICLR 2022
NEAR-OPTIMAL ALGORITHMS FOR AUTONOMOUS EXPLORATION AND MUITI-GOAL STOCHASTIC SHORTEST PATH
Anonymous authors Paper under double-blind review
ABSTRACT
We revisit the incremental autonomous exploration problem proposed by Lim and Auer (2012). In this setting, the agent aims to learn a set near-optimal goal- conditioned policies reach the L-controllable states: states that are incrementally reachable from an initial state so 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 algo- rithms, 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 problem and its connection autonomous exploration can be independent interest.
INTRODUCTION
Reinforcement learning (RL) with known state space has been studied in wide range of settings (e.g., Schmidhuberr 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 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 (Bert: sekas et al. 2000) where the agent aims to reach predefined goal state while minimizing its total expected cost. However, the autonomous exploration setting, the agent aims to discover a set of reachable states in 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 (212) 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 8 (, A/=*). Here L denotes the distance within which we hope the learning agent discover, S(1+e) denotes the total number of states within distance (1 + L from the starting state, A denotes the size of the action space, and s denotes the error that we can tolerate. Recent work by TTrbborrech et al. (2020) designed the DisCo algorithm with sample complexity bound 5 (1+5)L A/e2) which improves the 1/e
We translate their absolute error to the relative emror sT. Their bound has refined form Ō 012 S04 (144) (044) LA/²²) where T T(445) the branching factor which in the worst case is S(14e)

---

Under review as a conference paper at ICLR 2022
Algorithm
Sample Complexity
AX, on Sz"
AX' on S
AX, on AC
AX" on A
UchExplore Lim and Auer 2012
O(L (1105441))
Yes
No
DisCo Tarbouriech et al. 2020
SL 4/2)
Yes
Yes
Yes
VOISD
Ö(13S
Yes
No
No
VOTSD Re-MG-SSP
0(128140)A/E))
Yes
Yes
Yes
Yes
VATAF
Ö(I.S2LA/6))
Yes
Yes
No
Yes
Lower Bound
A(LS,,A/E))
Yes
Yes
Yes
Yes
Table Comparisons between our results and prior results. Algorithms and results in this paper are in grey cells. We define L, A, SL, ((1+5) S2L in Sect. 2 and is the target accuracy. We study four criteria, AX2 on ST," AX" on Sy," AX2 on K. and A. on K. whose definitions in Sect. 2 For simplicity, for each result, we only display the leading term in terms the scaling in 1/E.
dependency at the cost of worse dependency on S(1te)z In this paper. we present new algorithms to further improve the sample complexity.
1.1 CONTRIBUTIONS
In this paper, we take important steps toward resolving the autonomous exploration problem. We compare our results with prior ones Table and we summarize our contributions below:
1. We propose a new state discovery algorithm, Value-Opt imistic Incremental State Di iisovvery (VOISD), which uses 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 S A/e2) sample complexity, which improves prior results in Lim and Auer (2012) and Tarbouriech et al. (2020).
2. We connect the autonomous exploration problem new problem, multi-goal SSP and propose
new algorithm Re-MG-SS3 SSF that I) satisfies a stronger criterior and 2) serves as a burn-in step for the next algorithm.
3. We further propose Value-Awaa Aware Autonomous Exploration (VALAE), which uses VOISD and Re-MG-SSP initial steps and then uses the estimated value functions guide our exploration. By doing so, for each state-action pair (8,a), we derive an (s, d)-deeendent sample complexity bound, which can exploit the variance information, and yield sharper sample complexity bound than the bounds for VOISD and Re Re-MG-SSP. In particular, VALAE improves the dependency on from cubic linear.
4.
We give the first lower bound of the autonomous exploration problem. This lower bound shows VALAE is nearly -optimal when the St, grows polynomially with respect to L.
1.2 MAIN DIFFICULTIES AND TECHNIQUE OVERVIEW
While work borrows ideas from prior work autonomous exploration (Lim and Auer 2012 Tarbouriech et al., 2020) and recent advances in SSP (Tarbouriech et al. (021). we develop new techniques overcome additional difficulties that unique in autonomous exploration.
Dependence between the Estimated Transition Matrix and Discovered States. Our algorithm incrementally adds new states the set of discovered states K. To obtain tight dependency S(1+)) similar to the standard RL setting, one needs to use concentration on (P... Ps,a Ps, instead of ||P... Ps.all 1 (used by Tarbouriech al. 20200) where P.,a is the estimated transition,
II (Lim and Auer 2012) and (Tabbouricch et al. 2020), the cost is uniformly for state-action pairs. In this paper, we allow non-uniform costs. In Table, we consider uniform cost in Table T for fair comparisons. See Sect. 2 for different criteria.
2

---

Under review as a conference paper at ICLR 2022
Pa.a is the true transition, and Vi.gg is the value function of the optimal policy going to the state g restricted on the discovered states X. The main challenge is that the set of discovered states K. is dependent on the samples collected, and thus VR.g is dependent on Pa.a- a. We can use the union bound on all the possible K., but the number of possible I is exponential in the number of states S.
Our main technique is to construct series of sets of states {5o} - Kuo C C C ...... C K ST. where Kz+1 is constructed by adding all the states that are reachable from so by some policy on K. with expected cost no more than L. This series is only polynomially large so after applying the union bound we only have logarithmic overhead. 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 Sy, is unknown.
To this end, we first consider simpler problem, multi-goal SSP, and extend the technique for single- goal SSP (Tarbouriech et al. 202[) 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.
PRELIMINARIES
In this section, we introduce basic definitions and our problem setup.
For any two vectors X, Y E R.S. we write their inner product as XY = Exes (s) We denote
Notations.
|| 0o = maxess (X))) and if X is a probability distribution on S, we define V(X,Y) E.es (s) -E .ES (s))
so), where S is the state space with size S, A is the action space with size A, and 80 E S is the initial state. In state 8, taking action has cost drawn i...d. from distribution on [Cmin, 1] (where Gmin 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 to denote P(-ss, a) and P(s'|s, a). respectively. A deterministic and stationary policy S - A mapping, and the agent following the policy æ will take action π (s) at state s.
Markov Decision Process. We consider an MDP M := :
For fixed state g S we define the random variable t. (s) the number of steps it takes to reach state g starting from state when executing policy n,, i.. fg (s) == inf 2 0: s1+1 = g $1 8, T). A policy is proper policy if for any state s E S, (s) < too with probability 1. Then define the value function of a proper policy æ with respect to the goal state g and its corresponding Q- e-function as follows:
(s)
T (3)
V7 -
Σ
(6, E
Σ
c. ((:)) | = 8,
where E [emin 1] is the instantancous cost at step t incurred by the state-action pair (st, ((:)). and the expectation is taken over the random sequence of states generated by executing π starting from state E S. Here we have V. (g) = O. We use nQ to denote the greedy policy over a vector Q E RSXA i.e. nQ(s)= arg min (()
a
For fixed state E S, we denote V* as the value function of the optimal policy with respect to goal state g. and here we list some important properties of V there exists stationary, deterministic and proper policy n², such that its value function V == V=* and its corresponding Q-function Q3 : Q satisfies the following Bellman optimality equations (ef. Lem.
(7(8,)) a) = c(s, a) + V :
(s) min Q7 (s. a
V(s.)) ( E A.
Autonomous Exploration. Now we introduce the Autonomous Exploration problem. To formally discuss the setting, need the following assumption on MDP M.
3

---

Under review as a conference paper at ICLR 2022
Assumption 1. The action space contains RESET action s.t. P(sols, RESET) = 1 for any E 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 2 1, the agent needs to learn the set of incrementally controllable states S.. To introduce the concept of Szz, we first give the definition of policies restricted on a subset: Definition 1 (Policy restricted on a subset). For any S' C S, policy is restricted on the set S' if (s)) = RESET for all s & S'.
Now discuss the optimal policy restricted on set of states K. C S with respect to goal state g- We denote V2.g E IRS as the value function of the optimal policy restricted on K. with goal and Qk as the Q-function corresponding to Vg.g. We consider the case that there exists at least one proper policy restricted on KC with the goal state g. Then, Vic.g and Qi., are finite, and they satisfy the following Bellman equations:
(s, c(8, a) + Pa.a VK..
V(s,a) E E x A. Vs E K 9.
Vi (8) min Qic a), aEA
Vi.g (s) Qx,g RESET) = CRESET + (s)) VV.gg = O.
ss 4 [u
We note that when 1 S K2, for any g S, if V2 is finite, then VR..g is also finite, and we have Vi S VR component wise. And we note that for any s * g. we have min Qk.. (s, a) S Vg (s).
aEA Now we introduce the definition of incrementally controllable states St" (see) Tarbouriech al. (2020) for more intuitions on this definition.):
Definition (Incrementally L-controllable states ST'). Let < be any partial order on S. We denote Sy as the set of states reachable from so with expected cost no more than L w.r.l x, which defined as follows:
80 E St.
if there is a policy g restricted on {5' E ST, s' - {3} such that (s0) S L, then s E ST.
The set of incrementally L-controllable states ST. is given by S U.
Learning Objective. In our settings, the learning agent knows the constants S, A and Cmins 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 2 1 and an error parameter E E (0, 1]. learning algorithm of the autonomous exploration problem should output a set of states K. C S that satisfies:
ST C K. i.e., the algorithm discovers all the states that we want to explore.
The algorithm also outputs set of policies (Tx) that satisfy one of the following criteria:
1. (AX, on S Vs E ST. v (su) S (1 (1++) L;
2. (AX" on S Vs E ST V. (su) < V +eL;
(AX; K.) Ys K. (so)
S Li
4. (AX" on K)) Vs E K, (so) I (90 tEL.
We note that AX* on K is stronger than both AX on ST" and AX* on S but it is not necessarily
stronger than AX,, on K,, because we do not necessarily have V (sp) S when s & ST². . In the literature, AX2, on S 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 1-th step. We denote by ea (vr, az) the instantaneous cost incurred at the 1-th step. The performance
T
of an algorithm is measured by the cumulative cost: CT = ca (s(,) at).
Multi-goal SSP. We also study new problem, multi-gon goal SSP, natural generalization of the classical SSP problem. In multi-goal SSP, we consider an MDP and fixed length L 2 1. The MDP M satisfies Asmp. 11 and all of its states are incrementally I-controllable, i.e. 8 S.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Value- Value-Optimiste Optimistic Incremental State Discovery (VCTSD)
Input: MDP M (S,A, P, c, 8o), confidence 6 E (0, 1), error parameter e E (0, 1), and I. 2 1. Initialize < (, K, t (}. and Snew f se. Specity constants c 6, e2 72, cs 2v2, cs 2/2.
3 Set + e/3, - 6/2, B +- 10L and To E (1((50)))
Set v + 12000 L )² In( (d), and á + 2 $1, Smint
For (a, s') E A S, set
ass,a) < 0: a( t 0; N(s, as a,, + 0; P Pa.a,r t 0; 0(s, c 0; ((5,a) c 0.
for round r = 1,2. do
W(a) Discover Possible States in ST Add Snew K. Set f- Siew for each a E A do
10
while .V (V, a) < Φ do
Execute policy n, MDP M until reaching state
12
Take action a, incur cost e and observe next state s' ~ P(: s,
Set (ss a) as) + 1, (s) If & K. add s' to ut.
( N(,,,,)) +1
14
15
Set ((s <- ((s.o)
N[s.a] and ((s <
For s' E S, set P a. + N(s, a, ('),((s,)), n(x,a) + (()
16
17
Stop the algorithm if U is empty.
18
Whb Compute Optimistic Policy
19
each y E Ud compute (Qg. Vg) := VISGO A, KC so. 9: 5
29
Choose state E arg min (50). Stop the algorithm if (z()o) L. gEll
21 Set the policy मे as the greedy policy over Q.. Remove from 24 set Snew + and set na <- 7.
Output: The discovered states IC and their corresponding policies [N.).EK-
In multi-goal SSP, a learning algorithm should output set of policies {T such that V S (8)) + EL for all 8 E S. We observe that an algorithm that solves the autonomous exploration problem with AX" on S criterion can also solve the multi-goal SSP problem.
ALGOITHTMM AND SAMPLE COMPLEXITY BOUNDS
Now we are ready to describe our algorithms. There are three key components. The first component aims to discover set of states IC which is a superset of ST" but it is also not too much larger than ST (cf. Alg. D. and compute a set of policies { 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 (ef. Alg. 2. Then it collects fresh samples for all state-action pairs and computes set of near-optimal policies {TT J.g the set K. In the third component, inspired by recent advances in stochastic shortest path Tarbouricch et al. (202I), we design a policy evaluation step to obtain near-optimal estimates of the costs of getting each E ST (cf. Alg. 3
3.1 STATE DISCOVERY VIA A VALUE-OPTIMIST METHOD
In Alg. compute of states IC that contains ST" The algorithm maintains set of "known" states A. and a set of "unknown" states 2/ that have the potential to be recognized as members of ST" and become "known" states in future. Initially, the set of known states empty, and so the first state that will be added to X. Our algorithm will discover all the states E S one by one, and when the algorithm finds a policy that can reach s from sp with expected cost less than 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 (Tarbouricch et al. 2020) and (Lim and Auer 2012). We add a new state to the set of known states Then for each action a, we sample @ times, compute the empirical probability P Ps.a,'' and use the empirical 2(s, a). The collection of these samples has two objectives. First, will discover new states because it adds to 24 all the states that have not been discovered. Second, the collection of these samples helps us estimate the transition model P Pa which is crucial in estimating the value function of optimal policies.
5

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Reduce Autonomous Exploration to Multi-Goal SSP (Re-MG-SSP)
Input: MDP M (S,A, P, c, so), confidence á (0, 1), error parameter 5 E (0, 1), and I. 1.
Input: The states in I and their corresponding policy x..
For (s, a, E S A 8, set
N(s, a) < 0: (=, a) < 0; N(s, 5') <- 0; P Pa. t- O; 0(s, <- 0; ((s,a) <-
Set e/3, 8 /2,
12000( 1- Iu( (A)), and 2
Set KU {a} where x defined and construct an MDP M (KC A, Pi,c!,so) where x, K0, pt,ct are defined in Sect. 3.2
for each a) E K x A do
while (s, a) < Φ do
Execute policy æ, on MDP M until reaching state s. and observe next state s' ~ pt s.
Take action a, incur Set N(s,a) + N(s, + ((s + ((s,a) + N(s, a, t N(s,a,8)) +1.
10
Set a(s,a) < A(a.a) and ((s,a) + O.
11
N(s.a]
12
For all E K", set Pa,a,' + N(s, a, a, (/N(s, n(s,a) + N(s,a).
13 For all a E A. Net N ((r, = n(a, a) + o, Öe, a) t CRESET. Ps.a,s0 + 1, Pa.a. + 0 for all E S. 14 For g E K, compute (Qa, V)) = VISGO A, K. $0,g, Suf²), ), and set my as the greedy policy over Qg-
15 Output: K., J NO. m(), P, P, 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 E U, and we denote the estimated value as V,, We can prove that V, satisfies the optimism property. Hence, if g E S 9 will be eventually added to the set of known states K., and we can obtain K. 2 Sy. when the algorithm terminates. To this purpose, we use a procedure called VISGO (Value Iteration with Slight Goal Optimism), which is modified version of the VISGO procedure in (Tarbouriech et al. 2021).
In our VISGO procedure, we use slightly different bonus function 6(U, s,a). The VISGO procedure in (Tarbouriech 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 have collected e Ö(L² /0022//mmmm))) (2)
samples for each state-action pair (s, a) E K x A, we can ensure that the estimated model P is close enough to P, and in VISGO procedure, the bonus function b(U, a) is bounded by (Cmin=), ) and this is essential for our proof of C S The full algorithm of VISGO is deferred to Appendix
Now we present our upper bound of the [
Theorem 1. Assume that I, 2 1, < S 1 and <ō<1 1. For any MDP M = (S, P. c, 80) satisfying Asmp. [ with probability at least 1 8, our Alg. terminate and output of states K. such that S C S STi+e)L and a set of policies {Tebeck such that Vs E K, (s0) - (1 L.
and the cumulative cost Cr satisfies Cr = = L'S S
Thm. T shows that our Alg. T meets the AX on K. criterion. When Gmin = 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/e (cf. Table l). 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. However,
phase and a compute- potppuut-oppiiittippllliiiii 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+e)L factor in the bonus term bu.a- Our algorithm VOISD is based
sample complexity saves S(1+))r.
on the value- optimisicii subroutine VISGO. It uses the concentration of (Pe... Ps.a) VR..)V on series of sets K; and saves an S(1+e)z term on the sample complexity.
3.2 CONNECTION BETWEEN AUTONOMOUS EXPLORATION AND MULTI-GOAL SSP
In Alg.2 after we compute a set of known states K. 2 ST,,, , we have discovered all the states that we want explore. Alg. 2 aims to compute set of policies { bee that meets the AX* on IC criterion. We will fix our set of known states K, and focus only on the policies restricted on K. Therefore, for all the states K. we can regard them one artificial state æ, and the only action at state is

---

Under review as a conference paper at ICLR 2022
Algorithm 3: Value-Aware Autonomous Exploration (VALAE)
Input: MDP M (S,A, P, 80), confidence 6 (0, 1), error parameter 5 E (0, 1), and I. 1.
Specify: Trigger set N + {2/-1 j = .. Constants e1 6, oz 72, c3 2/2, c4 2/2.
3 Set + O(5e/ SAL).
We run Alg. 7 with 11 and get set K. such that ST. C Spi.
Run Alg. 1 with imput 5/2, 1, T.) and we get set K and a set of policies {Te]e
Run Alg. with input (M. 6/2, L, K, {T.) )ex)) and we obtain the MDP M (KC, A, pt ct 80) and P0,
the variables
Set initial time step + and trigger index j < 5 log2 Camm
Set + 5. f- 10I, A 2 In 256 ( 2. and initialize +- K. and 6- 80.
for round r = 1, 2, do
10
W(a) Compute Optimistic Policy
Compute (Q,V)== VISGO(X .A, KC,, so.g, 2..,,-1// ((x)))) Set the policy क as greedy policy over Q.
12
13
W/b Policy Evaluation
14
Set f + 0.
15
for episode k 1, A do
16
Set St f so and reset the initial state so. P + while st & g do
17
Take action = arg A Q(st, MDP M incur cost and observe next state
S1+1 [-] st.01).
Set "s,,ass',, c) (st, de, 8141, ce) and t + +
29
Set (N. a) t- ((s.a) a) + 1. (s) - 0(s, a) + c, ()),,,)) N(s,,, + 1.
21
if ((s E . then
Set + +i+1111 Set (s, + 20(s.a)
Na.a) and ((s, +
For all s' E Ett, set P. P + 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 skipped round).
Set f- 7 A: Fu +
26
if > (5o) + cL then Return to line 9, start new round (the current round has been a failure round).
27
28
Set T. + न. Remove g from U. The current round has been a success round. Choose another state g E U. Stop the algorithm if & is empty.
29
30
Output: The states in IC and their corresponding policy mT..
RESET. To this purpose, will construct an MDP M == (IC) A. A, Ai,ctt ct. where first define the artificial state v, and we set Kt = KC U {x), and K" K'= Ktt. .. For any (s, a) E K. x A, we define pl
s,a.s' as follows:
p s.a.s' Paaas Vs' E K. and P $,
Σ Pa.ass S'ZK
We also define pt z,a,s' = T[8' = so] for any a E A, E [(]()). Finally, we define ct a) c(s, a) for all (s E S x A. and (z, a) CRESET for all A. In this way, the problem reduces to solving multi-goal SSP problem on M with the set states being Kt.
Next, we collect á fresh samples for each state-action pair (s, again, and we will use these samples to compute policies {T. sek: that satisfy the AX* on K. criterion. We remark that using fresh samples essential for Alg. 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 8 < 1. For any MDP M (S,A, so)
satisfying Asmp. 7 running Alg. 7 and Alg. 2 successively will output a set of states K. such that
with probability at least 5, S S
S(i+e) and set of policies {T, besk such that
and Cr satisfies CT Ō (2
ds KC, V.- (s0) S (I+e)I. v (5o)
7

---

Under review as a conference paper at ICLR 2022
3.3 VALUE-AWARE ALGOIIHTMM FOR AUTONOMOUS EXPLORATION AND MULTI-GOAL SSP
Finally we describe our final algorithm. Va Value Aware Autonomous Exploration (VALAE). First, VALAE uses A with & = 1 as a subroutine, and Alg. T computes a set K such that Sy"" S K. Then we discard all the samples collected in Alg. in order to ensure the independence of K and Ps.a. Second, we use aas a burn-in step collect S2(L2 min)) samples for each of the state-action pair (s, a) so that we can use Lem. 13 to bound the expected cost of the greedy policy म in the policy-evaluation phase, and use Lem. 16to to show that we can use the average cost in O(1/ 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 Mt and compute near-optimal policies ag for all the goal states g E K. We choose the goal state g E IC one by one, and we move to another goal state g if the average performance of the policy Tg is close to our estimation of the optimal policy. In each round, we have two phases. the first phase, we use VISGO to estimate the value function of the optimal policy with goal state g. and we set the policy I 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 À = Ō(1/E)) times and check whether the average performance is close enough 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 ((s, a) meets the trigger set (i.e. is 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 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 VIGGO using the samples collected this round. In the case of success round, as the average performance of the policy ă is close to optimal, can set the f as the policy Ti for the goal state g. and choose another goal state g.
Theorem 3. Assume that I. 2 1, 0 < E S 1 and < < 1. For any MDP M = (S, P. 8o) satisfying Asmp. [ we have that with probability at least 1 - 8, our Alg. 3 will terminate and output set of states IC such that ST. C K. S Sgi, and a set of policies { Jeek such that Vs E KC, V (80) S
VVE, (80) + tT,, and the cumulative cost Cr satisfies Cr = Ō LSaLA LS A
19S2
mmin
Thm Jshows that Alg 3 satisfies the AX* on K. criterion. Note that in Thm. 3 the dependency on is tight when E - O, because we leverage the variance information in the policy-evaluation phase, which is necessary in RI. problems generally. Alg. [ Alg. 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 fundamen- tally does not scale with Cmin (cf. Lem. 17 and Lem. 18). While we discover a larger set IC C Szi. compared with Thm. Thm. we note that if the number of the L-controllable states grows poly- nomially with respect to T. (which is often implicitly considered in the literature because otherwise one may need to consider the logarithmic dependency on S (), then we have |Sgi = 0( and our complexity strictly improves the existing ones and is nearly minimax optimal.
Lastly, we note that Alg. enjoys a near-optimal sample complexity for multi-goal SSP:
Theorem 4. (Cumulative Cost for Multi- Goal SSP) Assume that L 2 1, 0 < S and 0 < 5 < 1. For any MDP M = (S,A, P,C. c, su) satisfying Asmp. [ and S = S, with probability at least 1 - 8, our Alg. 3will terminate and output set of polictes { T such that Vss E S, S.V. (so) S
(s0) + æL, and the cumulative cost OT satisfies CT = Õ LSA L.S LASA)
4 A MINIMAX LOWER BOUND FOR AUTONOMOUS EXPLORATION
Here present our lower bound for the autonomous exploration problem. To give the lower bound formally, we introduce some basic concepts about the definition of learning algorithm. following the definitions in Domingues et al. (022). We define Ie (S x A) x S be the set of all possible
8

---

81
P1B) 5,43
91
82
Ploy is eilin (11- So0t Myggin
State
Action
Pie (0 bed- PN60-1
Action
92
Plr % 9y (1l Sea Ragir
Figure 1: A graphical illustration of our construction of hard MDPs.
histories up to 1 steps with the form (s 2,, "e?,,....,
s²) E I' We denote π - (- as
history-dependent policy, where n' I - A(A) describes the probability of taking action E A after observing some history i E I at step l. We consider a class of MDPs M = (S.
so) such that Asmp. D holds, and we only consider the AX2 on St," criterion (cf. Sect. 2 and
note that | = S and |A| = A. Then we define an algorithm for the AX problem as a tuple (T,, T, Kc {m,) sex), which means the algorithm executes history-dependee set IC and set of policies [sx after sampling T times.
policy æ, and returns
Definition 3. Given any 2 1, < S 1, O < 5 < and SL E N, an algorithm (T, T, K, (sK) is 8)A for the AX problem within cumulative cost C, for any MDP M = (S.A,P,c C,,,P,c,,) 80) with at most S states and A actions such that M satisfies Asmp. and |S S St, the algorithm always terminates after using T samples, the cumulative cost always not larger than C, and with probability at least 1 5, it returns a set K. 2 ST and a set of policies { such that Vs S Vso)(s)) I (1 + L. The cumulative cost CAx(L,
(,,,,,,, S,,, 8) for the AX problem is the least C' E I satisfying that there exists an algorithm ( T, (ss)) within cumulative cost which (e, P)C for for AX.
The following theorem states the lower bound for the autonomous exploration problem.
Theorem 5. Assume that L 4, A 4, 4 Then we have CAx
S2 < min 1 3. 0 < <<<<<<> }. and 8 16
ب log!))
We note that this lower bound is for the weakest criterion AX, on S7,", so implies lower bounds for the other three criteria (AX" on Sy.", AX on K, and AX" on IC). This lower bound further implies our upper bound (Theorem 3 nearly minimax-optinal when Sn and S2t are of the same order. We also have a lower bound for multi-goal SSP (cf. Appendix HD.
For the proof, we first observe that even for a problem two states (an initial state 8o and goal state g), to determine whether g in S7², one needs Ωt ((LA/s") samples. Next, we construct an MDP Mú with S, - states and A/2 actions, so that each state s of M can be reached from the initial state with less than 1./2 steps. Then for each state in M we add a new state fs. and each of the remaining A/2 actions of either transits to state 92 or returns to state 8. By setting the p(gals, a) to ((1+ L Vūgg- (so))=²
ensure that the expected cost to reach all the states ge from 80 equals to (1 + 3.) Then for each state s in My. we slightly increase the probability of some action to reach 9s. making the expected cost to reach the state 9s from so become L. Under this construction, can prove the f A/E²) lower bound. A graphical illustration is in Fig. and the full proof is deferred to Appendix
CONCLUSION
We introduced new algorithms for the autonomous exploration problems, which improve existing ones. Along the way, we also introduced new problem, multi-goal SSP problem, which can be of independent interest. The natural future directions include designing algorithm with Ō (S sample complexity that satisfies all the four criteria listed in Sect. improving the lower order terms in existing bounds.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning, In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017.
Adrien Baranes and Fierre-Yves Oudeyer. R-iac: Robust intrinsically motivated exploration and active learning. IEEE Transactions on Autonomous Mental Development, 1(3):155-169 2009.
Dimitri Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595 1991.
Dimitri P Bertsekas et al. Dynamic programming and optimal control: Vol. 1. Athena scientific Belmont, 2000.
Alon Cohen, Haim Kaplan, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret bounds for stochastic shortest path. arXiv preprint arXiv:2002. 09869, 2020.
Alessandro Devo, Gabriele Costante, and Paolo Valigi. Deep reinforcement learning for instruction following visual navigation in 3d maze-like environments. IEFE Robotics and Automation Letters, 5(5):1175-1182, 2020.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theoory pages 578-598. PMLR, 2021.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-39, 2019.
Thomas Jaksch, Ronald Ortnrr, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563-1660) 2010.
Shiau Hong Lim and Peter Auer. Autonomous exploration for navigating in mdps. In Conference Learning Theory, pages 40-1. JMLR Workshop and Conference Proceedings, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Gergely Neu and Ciara Pure-Burke. A unifying view of optimism in episodic reinforcement learning. arXiv preprint arXiv:2007.0189) 2020.
Pierre-Yve Oudeyer and Frederic Kaplan. What is intrinsic motivation? a typology of computational approaches. Frontiers in neurorobotics, 1:6, 2009.
Pive Oudeyer, Frdric Kaplan, and Verena Hafner. Intrinsic motivation systems for au- tonomous mental development. IEEE transactions on evolutionary computation, 11(2):265-286, 2007.
Jürgen Schmidhuber. possibility for implementing curiosity and boredom in model-building neural controllers. In Proc. of the international conference simulation of adaptive behavior: From animals to animats, pages 222-227, 1991.
Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric, Improved sample complexity for incremental autonomous exploration in mdps. arXiv preprint vrXiv:2012.14755. 2020.
Jean Tarbouriech, Runlong Zhou, Simon S Du. Matteo Pirotta, Michal Valko, and Alessandro Lazarie. Stochastic shortest path: Minimax, parameter-frre and towards horizon-free regret. arXiv preprint arXiv:2104.1 11466..8.... 2021.
Huizhen Yu and Dimitri Bertsekas. On boundedness of q-learning iterates for stochastic shortest. path problems. Mathematics of Operations Research, 38(2):209-25) 1219922272000 2013.
10

---

Under review as a conference paper at ICLR 2022
A BASIC PROPERTY OF THE OPTIMAL POLICY
Lemma 1 [Bertsekas and Tsitsiklis 1991 Yu and Bertsekas, 2013). Suppose that there exists proper policy with respect to the goal state and that for every improper policy a'' there exists least one state s S such that V (s) +00. Then the optimal policy x² is stationary. deterministic, and proper. Moreover, V = V is the unique solution of the optimality equations V VV3 and (s) +o0 for any S, where for any vector V I2 the optimal Bellman operator C is defined as
min { (c(ss)) a) + P. aEA (s)s) :-min
Furthermore, the optimal Q-value, denoted by Q2 = Q7 is related to the optimal value function as follows
Qg(s,)) = +
(i((s min 27 (s) acA
E(x.
(2)
B HIGH- PROBAPROBABIIITY EVENT
We focus on the samples collected in Alg. and we will define the high-pre bagh-probbbility event G to do con- centration on the variables P and in Alg. We construct a series of sets of states Ko, K1, ... Kzz in the following way.
Definition 4 (A series of sets Ka, Ki, ... KEz), The sets Ki, Kz are defined follows:
Sei Ko {50}, and Z +- 0.
(*) (*) Set Kz+1 Kz. For any & Kz+1, if there is policy a restricted Kzz such that Vi' (80) I L, then add to Kz+1-
Stop if K2++ = Kz. Otherwise set Z + Z + and return to step (*).
We note that under this definition, we have Kn C K1 C K2 S ... K = depends only on our MDP M, and is independent of the samples collected our algorithm.
== ST_ And each K.:
We define the set F. = {(C2,,) g)
E S, 0,1,2, ... Z, and (5)) S L}, and we note that IF] < 52. Also, we note that as we set B = 10T in our algorithm, we can obtain K.gET [|V S B. Then we introduce the high- ceab-robbbbiltyy event g.
B. = max
Definition (High-probability event G). We define the event = G1 n 7 n3, where
20(s, a)la, 281a,a
9 = ES A,Vss, 21 [((s,a) - c(s, a)l 2/ n(s,a) 3n(s,a) S
G2 (1s.,s')SAAxx Vn(s, 21: Pa.., -P Panno V
n(s,a)
n(s,a)
V( Vi
14B.caa
Ga = V(s,a) E ESx A. 1, FF: I(P.. - -Pa.) K. $2
n(s,a)
3 a)
where lg,a 4n 215AIn((,aa))
Lemma 2. It holds that P(G) 2 1 6/4.
The lemma above is direct consequence of the concentration inequalities.
Lemma (Cohen et (2020), Lem. B.5). Let be a proper policy such that for some d > the expected cost (s) S foror every non-goal state s + Then the probability that the cumulative
cost of reach the goal state from any state
than m, most 26 mm/((d)) for all m
11

---

Under review as a conference paper at ICLR 2022
Lemma 4. Let T be random variable +0)+ such that Pr(r > m) S 2c 2emm/4d for any
where d is a constant. We define the random variable i 1 Σ 8k, where each fr. has the same
k=
distribution with т. Then for any e >> O, we have Pr(E(T) > + ed) S exp( 128 (64/e)
Proof. We set the constant I' = [8d [n64/ee]] Then we define the random variables rT = min(T, 1)),
t = min r), and f Σ tk-
As each f a random variable on [0. r). by Hoeffding's inequality, we have
nc²d d2
nc² 128 (64/c)
Pr(E(n) ++ cd) s exp(
S exp(
21
Moreover, have
D0 E(7) E(T)
1.
F((r) +
Σ
Pr(r > m)
m=r
< E(T) +
> exp( mm/
m=r
1
s E(Tr) + cd.
2
Therefore, obtain
1 ++
nE 2
Pr(F(r) > f + ed) S [D
>
2 =dd)= s exp(
128 2 (64/e)
C ANALYSIS OF A VISGO PROCEDURE
In this section, fix the known states and the goal state g and we analysis an execution of the VISGO procedure in Alg.4 We use the value iteration the form (i+1) CV()) to estimate the value funtion of the optimal policy. Here, we define the operator in the following way. For any U E R such that U 2 0, (g) and |0| B, we first define
ČU(s a) == 20, a) + Pr.U - ((U,,aa)
for any () E K. x A. where define
V(Pa. U)i,a n(s,a)
Bus.a m((sa)
a(s, a)ssa
b(U,8 8, a) = max ci
C2
+ +Cy n(s.a)
for any a) K. x A, and we define the transition probability Pa.a,'== that slightly increases the probability to reach the goal at each state-action pair.
m(a,a)+1 Pa.ass
n(s.a)
=/s==
n(8,0)+
Then, we set (U)) == min.e (s, a) for s E K. and + g, and we set ŽU(s) = +RESET+U for S (KC {g}). Finally, set [U ;= 0.
We note that all Alg. Alg and Alg before we executed VISGO procedure, we have collected @ = =((LL/ (c2 samples for each state-action pair (s, a) E KC x A. Thus we have n(s,0 a) 2 6 for each (s, a) E K. A. Also, we have 6v1 I Cmin8/18 188. The lemmas of this section
12

---

Under review as a conference paper at ICLR 2022
Algorithm 4: Subroutine VISGO
Input: Set of states S, set actions A, set known states initial state so. goal state g and evr. Global variables: B, L, NO, n(), P, 80, Z)
For all (s,a, E K S,
n(s,a) n(s,a) +
Poadt + 1 = n(s, a) +1
Pe.
For (8,a) E K x A, 6.0 1ln
245A/n(e,a)
Set ((0) 0, v(11) t00.
while ||[ |( EvI do
For (s E I0 x A. set
((++1) + max fap V(P... V(lleaa
Bla
as. n(3,a)
m(s,a)
02 ((ss
+ +rs
(3)
Q (s,a) a( P.ov (1,
(4)
(() min Q (s.
(5)
For $ KCU (g). set (() + cuESTT + (so)
Set v(+1)) (g) + 0, itit1.
10 if vi (oo) > L then
return Q(9) V(
11
12 return (19) p()
are based on these conditions. We note that as n(x, 2 d. and by our construction of Φ, we have b(U, s, a.) I CminE/ 188 for any (s, a) E K. x A. Therefore, if (g) = 0 and U 2 0 component-wis wise, when n(s, a) 2 for any (s, a) K. A, have (U(s, a) 2 0 for any (s, a) A.
For convenience, we define b(U, 8, a) == for any 8 & K. and a E A. Lemma (Tarbouriech
2021 Lemma 12). For any non-negative vector U R such that ((g) = 0, for any (s, a) E K x A. it holds that
|0
Po.o s P..USSPPP
n(s, a) +1
The proof of the following Lem. Lem.66is similar with Lem. 16 in (Taboouricch et al. 2021). but here we have two distributions and We give the whole proof for completeness.
Lemma 6. Let Y = {u E R u 2 O, v(g) = 0, ||o|l0 I B). Let f A x x xxxXXXRR R with f(p p, v. n, B,t) pu max C1 V(p..).
with constants Ci 6 and C2 2 20 Then satisfies, for all Y, n, P. A s.t. p(s) fp(s) for all + g.
C2 Bc
1. f(p.p, n, B,t) is non-decreasing in v(s), i.e.
V(v.o') T2, v v = f J. n, B,) (6.p,0' B,t);
2. f(p,p, U. B,) S p - V(p.ole
2 B S S
2/ Y(p.o) 14 Br
3. lf > 0, then f p. v. B, is po-contractive in v(s), with Ps = -- 1-p() < 1, i.e.
V(v T U. f(p.p, n, B, 1) s pollu - of cooo
We the idea in Tarbouriech et al. 2021). Lemma 14 to finish the proof. The second claim holds by max(x, y 2 (a + v)/2, Ve, y. by the choices of Cı and because both V(p.e n
Proof.
and Bi negatvga To verify the first and third claims, fix all other variables but
13

---

Under review as a conference paper at ICLR 2022
(s))
and view function in e(s). Because the derivative of in v(s) does not exist only when Vip.ul
Of
C2 Be where the condition has at most two solutions, it suffices to prove de(s) 2
Ci
V(p # 02 n when 01
Be Direct computation gives that for any E S and # 9.
0f
Vi, v)e
Bi
(())( ppe
= [(s) -lll-aal 9
C2
dv(s)
n
n
VnV(p,e)e
&
Iv min (Ø(s), p(s)
BB
((s)( po)}
BB
wve min (p(s), p(s) p())
0
M 0.
Here (i) is by u(s) - p S u(s) & B. In addition, we have
Σ
0s
Σ
p(s) a
(p, v)c
Bi p())(((s) pu)e
(u(s)
(n 1)
#zg
*Øg
V(p,v)
Bi
-lg)(g)
ei
C1
C2
V VV v)
Ip - p(g)) pu)
72
$1-p(g)
Therefore, we obtain that pp-contractive.
- We note that by definition of Ps... we have Ps.as' - 2 s. 2 for all (8,0,8) E K. x A S.
The following two lemmas follow the same proof with Lem.18, Lem. in (Tarbouriech et al. 2021 respectively.
Lemma 7. The sequence (V is non-decreasing.
Lemma 8. É. is a p-contractive operator with modulus p p= - - 1, where v min (xxA)
P Pa.a.
Hence, the VISGO procedure will terminate after at most [log(1/cn)/ log(1/p)] iterations.
C.I THE BOUNDED ERROR PROPERTY OF VISGO
Now we focus on Alg. I We give the following lemma of the bounded error property (Lem. 9), which indicates that the value function of the policy π, is close our estimation. The proof Lem. Lem.. techniques of Lem. 2 in (Tarbouriech et al. 2020). Our eom.ffocuse on a more general operator C. In our Σ, we involve the bonus function b(U, a.,, which is not contained in (Tarbouriech et al. 2020
uses the
Lemma 9. Alg.7 under the event G. for any goal state g that added to K., let (Q.V) be the output (Qq. Vg) of VISGO in that round, and let n be the greedy policy with respect to Q. Then is proper on the model Pao,,' and all S, we have (s) < (1 (1++)) (s)
Proof. We define V (s) the value function of with goal state g the model P Ps,,,'- We will first prove that (*) (s) & (1 + {s)) and then prove that (s) < (1 + e/3) (s) using the simulation lemma on the two models Pe,a,s' and Pa.,,.. Combining them together yields Vi((s) (8) < + (s).
First we focus on model P....r. We recall that for any s K. and s #
Zu(s) = min ((, b(u, s, + Paau
min
14

---

Under review as a conference paper at ICLR 2022
where
W P ( ) is
b(u,8,a) max C1
.02 n(s, a)
Bls,a
v3/ n(s.0)
6,00
n(s,a) a)
and we define b(u, s,a) =0 when s & K.
As set
L )² In( SA ))
Φ= = O((
Cmin
and n(s. a) 2 Φ. we can obtain b(u, a) S Canin 188 when 1|//|0 S B.
In addition, under the event 91, when n(ss a) Φ. we have ((s, - c(s, a)l S cmme/18 for all (s, as E S x A.
We denote I as the final iteration index of VISGO, and V = v In VISGO, we have vii) (v(i-1 for all i 1,2, ... .I. As ((L-1) < p(t) component-wise, we have for any E S ((s) - (1- (sp) + +1sL+ Hence, | S + B.
We y Cmin=/6. As EvI Cmine/18, we have s,a) (a a) c(s,a)) + $ when
|| S B.
Given the policy restricted on IC, we introduce the following operators on R
L (² = ē(s (s)) - b(u, s, (s)) + (s)
(x)(s) = c(s. (s)) - -7+ P (o)
We can write component-wise
TVVLVV EvI (a)
(b) ΣV - tvi I V,
where (a) uses that æ is the greedy policy with respect to V. To prove (b), we recall that V = V(O) (V((1)), By contraction property of L, we have ||C - Vll I [|v()) y( By stopping condition of VISGO, we have ||V - V(-11)| S 6v,, thus (b) is proved. By monotonicity of the operator T,", we have for all m > 0, (T," V"V V.
As (T,") V not increases element-wiss when m increase, and is non-negative element wise, when oc, 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 S V component-wise We define the random variable
En (s) as the number of steps takes reach g starting from s on model P when executing policy Thus
E
W (s) = Ep
Σ
c(St, (s:)) -7 1 = (s)(s) 11
[1, (s)
1=1
Moreover, have Cmin E (5)] 5 V (s). Therefore, we get
(s)
V(s)
(s) <
{1+
7/Cmin I 7/Cmin
As n(s,a) 2 d. under the event G2, we have ((s,,, ESxAxxx
Paa.s' - P P <
CminE
6(L +
Thus by simulation lemma for SSP (Lemma in Tarbouriech al. (2020)), is proper true model P. st and we have for all S, V (s) & (1 e/3)V (s). The proof is completed.
n
15

---

Under review as a conference paper at ICLR 2022
C.2 OPTIMISM OF VISGO
Now we will give the optimism property. We still focus on Alg- We note that there are exponentially possible number of set K., thus we cannot include all the K. in our eigh-probability event G. As the event G3 includes the sets Ko, K,, ,Kz, we choose 2 E {0 v I Z : K2 C [C), and we will compare the output of VISGO (denoted by V). with the value function of the optimal policy restricted on K₂ with goal state g (denoted by VK_..).. We recall that we define B, = max II K., llo. By (K.g)EF
the definition of F, we have B. S L B.
Lemma 10. Let E {0= S S Z: K2 S K). Assume that there exists at least one proper policy restricted on K with the goal state g, and V ( S B for all s E S. A under the event G. for any output (Q, V) of the VISGO procedure, it holds that (s,,a) S (s,))
((s x
V(s) & (g (8).
Proof. We prove by induction that for any inner iteration of VISCO, (s. any (s, E A. and (s) I (s) for any E S. By definition we have Q 0 I Vk..g and v(0) = 0 S Vi Assume that the property holds for iteration i, then for any (8, E IC x A.
a) S og..g(s, (s,a) for
(s)
Q(++)( = =(s + Po.o v -b(+1) (s,
where
a( + (( (s(+t)ssaaaa
(+))
V P (Paa, V(0) Ua.
Bla. n(8,a)
as a)ssa n(8,a)
= =((sa) a) + Po v(1) - -mxx {
n(s,a)
S <((s,)) + PPaV(() max (a1
@
V(Ps.a s.a V(0))
Bls,a
28 3n(s,a) a)
n((sa)
((s,aa)
= a((s,a) + {(P Ps.ay v(1), a), B,l,,aa
286z
3n(s,a)
28
<((s, + -((P Psas VŘ. n(s, B,,,),,,..... B,o.,)
3n(s,a)
V(P..a. "K.gg)a.
14B
3 c((s,)) + PP.aVV.. 2V
n(B,a)
3n(s,a) a)
v(P Vi
14B
I (c(s a) + +Po. Vx kg.g - -2
a(s,a)
3n(s,a)
(B - B.) 146,,0
2 c(8,0) a) + Pa.aV Vin
3n(s,a)
< (s,
where (i) is by definition of 91 and choice of ca, (ii) uses the first property of Lem. o and the induction hypothesis that v(() < VV..gr (iii) uses the second property of Lem. and assumption B 2 ma 1}. (iv) uses Lem. 5 (s) by definition of G3. Ultimately, for any (s,a) E K. x A,
Q(++1((s a) S Qi..g
Then for any s E K. and s * g. we have v(i+)(ss) = min Q (s, S min Q VV
Qk (s, (s, a) S
aEA
aEA
In addition, ((+ (g) = 0 Vii.g (g), and for any s & 1C {g), as K, S K, we have
((+t)(s) CRESET (5)) I CRESET + V2 (s).
This completes the proof of this lemma.
16

---

Under review as a conference paper at ICLR 2022
D PROOF OF THM. 1
Proof idea. We provide the main intuition here. We denote K and { as the output of Alg We fix the round index r, and we consider a state 9 & K, g S7, and V Kggg (50) S L. To show that ST. S X, we need two steps. First, we show that g will be added to under the event G2. Then we will use the optimism property of VISGO (Lem. I0 to prove that estimation of the value funtion of the optimal policy (5())) is no larger than L.
To prove that K C S we need to prove that when g is added to K, we have V (so) I (1+s)L, where स is the greedy policy over Qg in that round. This is a direct consequence of Lem.
Now bound the total cumulative cost. For each state-action pair (s, a) E K x A, we collected Ö(L (CLL)(Cmiia (cminn²)) samples. And to reach each s E K,, we executed the policy Te. and the cost to reach 8 is no larger than (()) with high probability. Thus the total cost can be bounded by Ö K A/(min))))) ))), and K = |K] S S(1t))
Proof. We first use Lem. 10 to show that St' C K. Then we use Lem. 9 to show that KC C S L1+))
and each policy n, output by Alg I satisfies V.Ta (so) I (1 + =) K (30). Then we will bound the
total sample complexity Alg
To show that ST. C K. we will prove that K,2 K. for all 0, 2....... Z by induction. We observe that { = Ko S K. because the initial Snew is sg. Then we assume that K,2 S K, and we will prove 2 C K.
For any state E KCz+1 and g & K.,, we have V2 V S L by definition of KC++1- To show that g will be added to IC eventually, output of VISCO procedure (so) S L when K.2 S K. We observe that as VR. I L, there must
need to prove the following two statements: (1) g is added to 2t; (2) the
exist (s, a) E K,, x A such that Pa.a,g 2 I/L. As we have collected & ( samples for each of the state-action pair (s, a) E K. x A, under event G2, we can obtain that P..... 2 - > O, which yields that has been discovered. Thus g has been added to some round, and statement (1) verified. The statement (2) is a direct consequence of the optimism property Lem. T0 Thus we have proved that K 1 S K., which yields that S C K.
Then we will prove K. C te)) By Lem. each time when we add to K. we have (.T) S (L+ i.c. the AX, on IC criterion is met. We recall that the definition of S (i+tjz is a recursive
construction, adding new state s whenever there exists some policy π such that (/*) ) $ (1 + L) Therefore, each state added to IC is subset of S ((+te) and we obtain that K. C S(
Now will bound the total cumulative cost. We note that have collected Φ o= samples for each state-action pair (s, a) E K. x A. To collect each sample (s, a, c). we executed a policy we to reach the state s, and the expected cost V.** (5o) S (1++) < 2L. By Lem 3 we obtain that with probability at least 1 - 6/4, for any state s, each time when the policy
is executed, the total cost reach s from Su is larger than O(L log (og(S)))). Therefore, the total cumulative cost OL
in Part of Alg. can be bounded by ((L3S(1+e)L.A) =²n=))) Thus we obtain the bound
CT = Ō - L'S (1+eLL
min c2
Now we bound the total failure probability. The event G fails with probability no more than 5/4. And in the previous para the failure probability is bounded by 6/4, thus the total failure probability is no more than 5/2. The proof of Thm. is completed.
17

---

Under review as a conference paper at ICLR 2022
E PROOF OF THM. 2
First we define the high high-probability event & to do concentration on all the samples collected in We note that the definition of also applies for Alg. after it finishes the subroutine Alg. and clears all the samples in A We note that after A the set of known states K. is fixed, and our algorithm focuses the new MDP MM (Kt A. Pt su). Here for any g E K, denote the vector V RK' as the value function of the optimal policy on MDP M with respect to goal g, and when K C ((+E)) in 3 we have B V lmo S B. For convenience, here we denote Vi (s) as the expected cost of the optimal policy to reach from s on MDP M and we have (s) S 2T + I B for all g) E Kct x K. Then we define the high-probability event GT. Definition (High-probabilityy event G!). We define the event g = 9 ngg n n where
Alg 2
22(s, a)lsa n(x,a)
28 3n(8, a)
Gf v(s,a) e A,(nss, 1: ((s d (s, s 2
2p 2P n(ssa)
G v(s,a,s') E x AAx,, vn(s,a) 21 11: |Pt Paa Pe.a,o $$
60.0
n(s,a)
V(Pa,ay Vi)la, 14Blesa n(s,a)
03 V(s,a,g) EKt AX vn(s,a) 21: I(P.. pf Po = S2
3n(s,
where la.a = 4ln 245AAl((aaa)
Finally, we define the high-probabillty event = g!. And we have the following lemma. Lemma 11. It holds that (E) 2 8/2.
We introduce the lemma of optimism and the lemma of bounded error in Alg We note that the proof of them is the same with Lem. an) Lem. respectively.
the VISGO procedure, holds Lemma 12. In 2 under the event &, for any outpui (Qg, Vg) the that
Qs(8,a) S Q7(s,a), (s(s) S Vs)
a( EKt A,
Kt.
Lemma 13. In Alg. under the event E, let (Qy, Vg) be the output of VISGO, where g is the goal state, and let i be the greedy policy with respect Qg- Then proper on the model Ps and for all KT, we have V7 (s) < + Vs))
Now we give the proof of Thm.
2 First we prove the correctness. By Thm. | VOISD outputs a set IC
such that S7 K. S(+z))z Now focus the set of policies (=x) SEx that Alg. outputs, and we will prove that for each K., we have
g (so) S (1 - Le) and V (sp) S C. (50) + 3eL. As we set E + =/3 in the beginning of Alg. [. the correctness of Alg Alg can be proved.
By Lem. 13 and Lem. 12 obtain that (s()s I (1+ =s) S (1+ VV+ (so). We note that (so) + e) because Alg. satisfies AX, on K. Hence, we can get V (5o) (11+))=L
(L+ and V (5o) (s))s) +e(1 +1) V (sn) 3.T. Thus Alg. ootputs set of policies {T₂) that satisfies both AX2
and AX* on K.
Similarly with Thm. as we collect & samples for each state-action pair (s, a) E K. x A. we can
obtain that with probability at least - 5, the total sample complexity is bounded by Ō 0( 5
F PROOF OF THM.
Here we give a proof of Thm and we focus on the fixed set Ktt and our constructed MDP M
(CT, A, Pt, so). We denote K [K], and K' |Kt K
18

---

Under review as a conference paper at ICLR 2022
Proof idea. First we prove the accuracy of Alg It uses Alg. with = 1 as subroutine, thus can get a set K. such that St - C Szi. For each goal state g. when g is removed from 24 and the policy " is set, the cost to reach from so under policy T has been tested for À = ((1/c²) times. Therefore, by the concentration inequality, we can prove that the average cost is close to the expected cost of Tg. Moreover, the average cost is less than our estimation of the cost of the optimal policy (Su) plus eL. Hence we can prove that the expected cost of Kg is close to the optimal cost using the optimism property.
3
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 Ö(L/E²). Then we will bound the total number of rounds. We denote 7 as the total number of samples collected in Alg. The number of success rounds is most K. And the trigger condition holds for at most logg (2Z") times for each state-action pair (s, a), thus we obtain that the number of skipped rounds can be bounded by K' A 2 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 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 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 eLd, thus can give 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 Ō(KA + s k* Thus the total number of rounds is bounded by Ö(K A + =K A), and multiplying it with the cost each round, we can get the bound in Thm. 3 and complete the proof.
Now we give the full proof. Here we denote (s) as the expected cost of the optimal policy to reach 9 from s on MDP Mi, and we have (s) < 2L + 1 S B for all (s, g) E KC1 x K.
We recall the definition of the high-probability event in Appendix E Also, we introduce the lemma of optimism and the lemma of bounded error in Alg. and the proof of them is the same with Lem. 12 and Lem. [3 respectively.
Lemma 14. In A 3 under the event for any output (Q, V) of the VISGO procedure, it holds that
a) S (s(s,)),
x A, VsEK'
V(s) (s).
where g is the goal state in that round.
Lemma 15. In Alg.3 3 under the event E, for any output (Q, V) of the VISGO procedure, let n be the greedy policy with respect to Q. Then is proper on the model Pa Ps and all K!,, we have Vi < 2V (s), where g is the goal state in that round.
Now we prove the correctness of Alg 3 i.c. Alg. satisfies AX" on K. The main intuition is that each policy n, has been tested for times in a success round, and the average cost it takes to reach 8 from so is less than our estimate for optimal cost (ss) plus eL. Thus by concentration inequalities, the expected cost of Ta is close to optimal.
Lemma 16. Let {as) be the set of policies output by Alg With probability at least 5, (50) < Vi* (so) + EL for all s E K.
Proof. We fix any state s E S. In any given round where the chosen target 8, let ÿn be the total cost in the k-th episode of that round. Recall that for the algorithm to output policy n,, its empirical performance after À episodes must satisfy that f < V (su) + eL, where = Ei_
We define the random variable 7 as the total cost takes reach the goal state s from the start state so when executing policy n., and we have E[T) = V (so) by definition. We note that we have collected & ((L2/Cam samples for each of the actton pair (s, a). By Lem. 15 under event E, the policy n, is proper, and we have E(T) < 2L. Hence, we obtain d' := V| llac 2L + S 4L. By Lem33 obtain Pr(r m) 5 2exp(-mp m/ m/d)) for any m 0.
19

---

Under review as a conference paper at ICLR 2022
As set
À 1 In² (n)(-)) In( ( )1,
2048
256
25
2
by Lem. we obtain that with probability least 1 0/(2S), we have
V (80) F(T) S el.
We note that & < (ssu) + cL S (sp) + cL by the optimism property (Lem 14 Hence, set c e/3 in initial, we obtain that with probability at least 625),,
V (50) & (50) + +EL.
Finally, as there are most states total, and the event & holds with probability at least 8/2. by the union bound, the total success probability is at least 1 - 6.
Now we focus 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 H the number of steps it takes in the k-th episode of the j-th round. The regret in an episode is defined as
( ('():)
where *f is the empirical cost in the h-th step the k-th episode the j-th round, and (* is the value of V(so) in the j-th round. Let ny be the total number of episodes executed in the j-th round, we define the regret in the j-th round as follows:
Hick
Σ
ch (so)).
Then we will define the total regret of Alg Let be the total number of rounds, ny be the total number of episodes executed in the j-th round, and 0 < n, I X. Then we know that the total number of episodes in the whole process Alg
Σ Mi. For notation convenience, we define m j=1
as the number of steps it takes the m-th episode the whole process of Alg and denote c as the empirical cost in the h-step of episode m. Finally define the total regret of all the rounds
Ha.k
M
H
R: ΣΣ
V)
V (so)).
Am1
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
== == Ō(LKKAAM + LK²A).
This upper bound comes from the regret bound the EB-SSP algorithm (Tarbouriech et al., (021). which solves the classical SSP problem, and the proof of Lem. 17 is similar with Thm.3 in (Tar. bouriech al. 202T).
observe that there are at most Ö(K A) skipped rounds and K success rounds. We denote by ry the number of failure rounds, and we have the total number of episodes M = Ö((KA +ry))) = Ö((K O((K+rr))e r))/ee) Thus the total regret in rounds be bounded by ry sublinearly:
LKA
R -= VKAr
LK*
Then gives the lower bound of the total regret in terms of the number of failure rounds ry-
20

---

Under review as a conference paper at ICLR 2022
Lemma 18. With probability 1 1-6 8, when r= Ō((A))))). the total regret in the rounds is at least
R R= Lrg
LKA
where fy in the number of failure rounds in the rounds.
Proof. By the criterion of our performance check, in any failure round, we have 7 > V(so) cL,
Ry
H&*
and in round j. we have == Σ
Σ
J.k) ch > by definition. Hence, in any failure round j, the regret
km hm
AF - ny (so) 2 X(F - V2 (50)) 2 deL = 52 (25)
Then we focus on skipped rounds and success rounds. We denote g as the goal state in the j-th round, and xy 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
Ry-1
mpa.
Ry H
Σ + V
L+
(so)) 2 L+
(5o)),
k=1 1=1
A=1
h=1
H
where we used the optimism property in Lem. 14 We note that Σ ch is the empirical cost of
policy n, in episode k, and we will use the concentration inequality give 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 - to lower bound the regret of the last episode round j. Then we denote n = n2 - 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  from 8o, and By Lem 4 with d 4L, with probability at least
Hj.k
recall that fz
j.k c
(8A)2 have
6
Σ (+x E(7)) 2 2r V
SA In(
5 2 2D
A In
SA 5
2
-,
4
where r = (64/c))4/))) Thus the regret in any round j is no less than - -7 ). As there are at most Ö(KA) skipped rounds and K success rounds, we obtain that the total regret R has the lower bound
R R= Try
LKA
Now we bound the total failure probability. The number of rounds = ((SS))), in each round the failure probability is at most (SAy= and the events & fails with probability 5/2. By resetting (SLL) in initial, the total failure probability is at most 8.
8
5 - (6/((5A))
As the lower bound is linear in ry. and the upper bound is sublinear in ry. we can solve it and obtain that ry = Ō(KA + ck² A), thus the total number of rounds can be bounded by Ö(KA A + +K2 A).
To get the cumulative cost bound in Thm. B need only to bound the cost in round. In any round, we observe that except for the last episode, the average cost f for all the other episodes is no larger than ((0o) + eT. < 2T., thus the total cost in these episodes is no larger than 27.A ( Also, we know that in the any episode, the expected cost of the policy स to reach the goal from so is no larger than 2L. Thus by Lem. 3 in any round, with probability at least 1 TSA the cost
in the last episode is larger than O(L). Hence, the total cost in each round is larger than Ö(L/e²). By multiplying it with Ö(KA+ AA) the cumulative cost in Alg can be bounded by OLKA//2 + LK2 A/ where the term I L3KA/ A/2 comes from the subroutine of Alg. As we have K < S21,, obtain the bound in Thm
Now we count the total failure probability. First, Alg. fails with probability 8/2, the event & fails with probability 8/2, and the lower bound of the total regret R fails with probability 8. And in the
21

---

Under review as a conference paper at ICLR 2022
previous para, to bound the cost in the last episode of each round using Lem. the failure probability in each episode is at most (SA)². 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 Ō(K A + ek² A),
where we omit the logarithmic factors. Thus by setting 5 - ( in initial, we can bound the total failure probability by the initial 6, and the proof of Thm. 3 completed.
G ANALYSIS OF THE LOWER BOUND
Here we discuss the lower bound of the autonomous exploration problem. We recall that we relax the problem and consider only all the MDPs M with states and A actions, and M satisfies Asmp. Our algorithm needs output set K ST," and a set of policies {TT and when policy т. satisfies (so) I (1 (1++)L: L. Moreover, we note that here we allow the algorithm to output non-deterministic policies, i.e. the policy n, - (AA) is function from the set of states to probability distribution over the actions.
ST, the
We recall the some basic concepts about the definition of learning algorithm, and we the notations in (Domingues et al. 2021). Let = (S x A) x S be the set of all possible histories up to t steps, that is, be the set of tuples of the form (s' a' ,,?,a² aa........$ st) E I'. We denoted (m') 121 as a history-dependent policy, where n' I (AA) describes the probability of taking action a A after observing some history i It.
Given an MDP M = (S.AA,: so), policy π interacting with the MDP M defines a stochastic process denoted by (S* )²) where (S", A+) is the state-action pair at time The Conescu-Tulcea theorem ensures the existence of the probability space F., PM) such that
[M s] = [[s so), PM SM[St-1 = A 1 p(s 1 A²), and [P, 1 n' r'(a 19)
where π (z'),²1 and for any 1s a (S A ) is the random vector in I' containing all state-action pairs observed up to step t. We denote the o olalgebra generated by I' as Ft. And we denote by PMM the measure of Is under PM as follows:
T-1
PM 1 = [ = llss = so) II 7' 12))p((stt (s", t=1
Then denote EM as the expectation under PMM Note that the dependence of P. and EM on the policy π is denoted implicitly in the definition of IPM. We will denote them explicitly as PT.M and Ex,M respectively when we need to stress
Moreover, given the MDP M = (S,A, p. so), we denote VM.g (8) 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 mallback-Leibler divergence between two distributions P1 and IP on a measurable space (S2 G) is defined as
dP1 (w)
KL(FI.P2)
A log sn
dP (w),
dI,,
PI < P2 and too otherwise. For Bernoulli distributions, we define ((p.g) E 10.
k)(p.g) A (TT(B(p), = pooo (2)
P + p) log
1 1-P)
i-
Lemma 19 (Lemma 5. Domingues et al. 2021), modified). Let M and M' be two MDPs that are identical except for their transition probabilities, denoted by p and p', respectively. Assume that have V8, a). p(- 8,a) a) < 1/(- 88 8,)). Then, for any stopping time T with respect to (F²) that
satisfies PM < 20] 1,
KL (PL PPM.PP Pk..)
ΣΣ
E EM NT [ 8, s.)))p(( s,,)),
#ES aEA
22

---

Under review as a conference paper at ICLR 2022
where N5,a - Ci=11((8) ,4) = (s,a)} and I" is the random vector representing the history of samples.
Lemma 20 (Lemma 1. Garivier et al. (011)). Consider a measurable space FD, equipped with two distributions P1 and 12 For any F F-measurable function Z : - [0, 1), we have
(L(PI,PP)) 2 1E,
where R2 and B2 are the expectations under IP and P2 respectively. Lemma 21. For any p. q E (0, 21. kl(p, 9) S 2(p-a)²
Now construct family of adversarial MDPs 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 transits to g with success probability (1++) -)- and transits s to with failure probability 1 ((1++))+)))))))) L) -1_ In this MDP, the expected cost to reach g from is (1 + L. Then we construct MDPs, each MDP increasing the success probability of an action a to L and the the expected cost to reach 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 7.-1 and p ((1 + =) Using the KI.-divergence, we can obtain that the minimum number of samples is O(L/s²). As there are A actions, we can obtain the O(LA/=²) lower bound.
The construction of hard MDPs with general ST. Now we fix L, A, St., 8 such that L > 4, A > 4, 4 < S₁ < min (1) Si
2 0 < < 3. It's straightforward to verify that we can construct an (8' A', pby C, sp) with |8 = =, I states and |A' = [A/2] actions, such that c(s, a) = Cmin for each (s,a) E S' x A', and each state E is incrementally (L/2) controllollll,,
MDP Mr
Le. its S L/2 = S'. Thus for each s E 8", we have Ving, S 2.
Then will construct the MDP Mo A, po: C, so) based on .Mo in the following way. First we construct S, - 1 states and [A/2] actions, and denote them as St and A", respectively, and we set S' U U A A' U A" For each S and any actions every action at E St is the reset action to so. And we set c(s, a) = Cmin for each (s, a) E S x A. Moreover, for all (s, a) E S' x A', our transition model po(-|s, a) constructed based on ph((|s, a). i.e. we set Po as follows:
A. have Po (8g 8, a) 1, i.e.
Pols' s a. pb(s'(s,a).
V(s, E S' x A' E ( x'x St. V(s,a,s') E 8' x S
Po a) O.
(s(s' a) O,
and then we need only define the transition function Po(gss a) for each (s, g) E S' x Att x St. We note that as ST| = Sy. 1, for each g E St, we can pair with state 8 E S", and all pairs (g, 8) are mutually disjoint. Thus we use the notation 9s E St to denote state in St that is paired with the state s E S¹. Then for all as,a) E S x A', we define
pu(gals,a) a) (1 + 3z) - Vig (50) Pu(s|s, = -1 -PPu(oals, a),
Cmin
i.c. each new action either transits E S to its pair go S remains at itself.
We observe that (50) ( for all S', and (s0) = (1 + 3 for all s E St,
Then define the adversarial examples of MDPs. Now we fix any state-action pair (s, a) E S' x A The adversarial MDP M(s.a) (S, Pe.a; c, so) is constructed from Ma. and the only difference of M(sa)) and Mo lies on the transition probability at the fixed sate-action pair (s, a), and we define Pa.a (-|s, a) as follows:
Pa.a Ps.a (g)ls,a) L Mr (so)
Cmin
Ps.a (8]s, = 1 Pa.a (gals,a).
ie. at state s, we slightly increase the probability of the action a to reach the pair state g.. And for all the state-action pairs (8',a') other than (s, a), the transition probability (- ( a²) is the
23

---

Under review as a conference paper at ICLR 2022
same po(-)s'; ,a). Therefore, we have V Min.a, (su) L, and V Mana (50) Mo (8u) for all s' E VEES E {go).
Finally, we define the family of our adversarial MDPs as {Mo} U ( (s.a)ss*x x.At- We note that for each MDP ((saa). its |S = St. and it satisfies Asmp. Also, for the MDP Mo. its | = S5 - 1, and it also satisfies Asmp. Thus the family is valid for the relaxed autonomous exploration problem.
Now we give our proof of Thm. through the adversarial family of MDPs. Here we use the techniques of Thm. in (Tarbouriech et 2020).
Proof. We denote by (a) P any) and (ss- ,a*) E _ the probability measure and expectation in the MDP M(r",a)) by following π and by Po and Ep the corresponding operators in the MDP Mo- We fix any algorithm (π, T, Kc {T. bae)) that solves the AX problem. We will prove that when working on the MDP Mo. the algorithm will cost at least 9 LS log ()) samples in expectation, i.e.
Guie
LSLA A
1
Ba[T] = 22
log
7)
Cmin
which yields that the lower bound of the total cost is 92 LS log 2.)
Now we fix the state-action pair (s", a") 8' x At, and we denote gs- E St as the state paired with s* E S Also, we denote the random variable (s.a) as the number of samples that the algorithm takes at the state-action pair (s,a) E S A. For any -emmauurable random variable Z taking values in [0, 1], we have
72Cmin
Eg
N aa))
(a-)
L
Bo (or KL
Gmin
Cmin
(1+38)1
o (50) L- V
My (80)
i KL (P6 P/-- ((or(ar))
IvS
(L(Bol E,. .a.) 121).
where (a) uses Lemma 21 and Ving. (so) S :.= (b) uses Lemma 19 (c) uses Lemma 20
For any policy π S A(A), define (als)) the probability that the policy takes action at state s. Then for any (s,a) E S' x A', we define the event Za 1 (The algorithm's 's output satisfies E K. and Tq. (als) 2 }. And we set the event Z = Za- We observe that as the algorithm T, K., (T.) solves the AX problem, when working on the MDP Mis (a*), with probability at least 1 - 5, its output should satisfy 9.- IC and the expected cost
of the policy Tg.- satisfies Vi""" (su) I (1 + L. which yields that ng.- (a (a*(s*) 2 2. Therefore,
for any (s" a²) E S' Ai, we have
P(sraa)) ZZ a 1 2 8,
as the algorithm succeeds with probability at least --5. 5.
Moreover, for any policy observe that for any two state-action pairs (s, a) and a'), # a'. we cannot have both π (a|s) 2 and (aa'ls
[s) 2 2 Therefore, we obtain that given any state 8 E S',
have
Σ PolZz.d $
REAt
as any events Za,a and Zs (a f a') are mutually exclusive.
We recall that we set 7 = 75 and we can obtain
kl (looo/ Ee,,,,-) (2)) kl (75- 77755aat ar P( a.) 7 a-
24

---

Under review as a conference paper at ICLR 2022
IV8 (1 - PolZs.,a- log
- log(2)
1
a.)) (e),a))00r
2 (1 - PolZs',a- :a..s..a))) log
8 - -log(2),
where (a) uses the fact that kl(p, 9) (1 p) log ( log(2) for any p.q [0, 1); (b) uses that
P(sra aa,,aa) 1Zs 2 1 - 8. Therefore, we have
L
1
Eu NT. Na-) 720min 22 Po/ss log 8
log(2)).
We recall that EeEAt Pul PalZs,al S 1.
Thus we can obtain that for any s* E ES',
Σ EAAA
Eo No so0 2 720mine2 (1,41 - 1) log 5 - log(2))(at))
Summing up all the state-action pairs (s", E S' x At, we can obtain the lower bound of the sample complexity.
L|S
Eo[T|-
Σ (x.a)ESx
No. (s,a)
Σ
Eo
N (or
(1A1)) 1) log (og(2))(At))
720min
(E""
As |At| = LA/2] and |S = Sy - 1, provided that L > 4, A > 4, 4 S St S min ( 5).
0 <<< E < 1. and ā < 1
To we can eventually prove that
LS A log
1
Eo[r] = 52(
g)))
Cmin 2
which yields the lower bound of the cumulative cost in Thm.
H LOWER BOUNDS FOR MULTI-GOAL SSP
Here we formulize the lower bound CMssP S, e, 6) for the multi-goal SSP problem. First we define an algorithm for the multi-go goal SSP problem as triple (x, T, [T, h.s), which means the algorithm executes a history-dependent policy π,, and returns a set of policies {T*]xeS after sampling times. Also, we allow n, to be non non-deterministic policies.
Definition 8. Given any I. 2 1, 0 < < 1, < < and S E N, an algorithm (πT, T, (ma ( (e, PPC for the multi-goal SSP problem within cumulative cost C. if for any MDP M (S,A, so) with at most S states and A actions such that M satisfies Asmp. and S = S, the algorithm always terminates after using T samples, and the cumulative cost always not larger than C, and with probability at least 1 - 8, it returns a set of policies { such that ds E S, &S. S V2(ss) + EL.
The cumulative cost CAssp(LL, ST, S,e, for the multi-goul SSP problem is the least C E R satisfying that there exists an algorithm (TI, T, { (ss) within cumulative cost C which (c, 8)-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 [] i.e. SMssP(2L. 25, s/2, 8) > CAx( (L, S. E. 8). Thus we obtain the following lower bound for multi-goal SSP, which implies that our Alg. 3 is also minimax for multi- multi-goal SSP problem.
Theorem 6. Assume that L > 8, A >>
4, 8 < S (
0 O<E<<<> 1.2 and 8 < 1 Then we have 16.
L.A
CMssp SL, = Ω
log
25


Reviews:
[{"review_id": "vZvcF4Yi5l9", "reviewer": "Reviewer_CNUB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Pros and Cons\n\n## Pros\n\n- Proposed algorithms achieved better sample complexities on different criteria, as summarized in Table 1.  As I understand correctly, the four criteria are based on the existing literature but more clearly discussed and summarized in the four columns. Further, a restriction on the cost $c$ is relaxed by $c_\\mathrm{min}$; that is, the authors generalize the problem settings.\n- The proposed algorithm is well described (it is as complete and interpretable as those in two existing works UcbExplore and DisCo).\n\n## Cons\n\n- Some knowledge about autonomous exploration is used before the definition or references (i.e., Sec 1 is a bit complex without Sec 2 and reference papers).\n- Readers are hard to follow all the details of theoretical proofs (much longer than the main content).\n- No experimental results (cf., [Tarbouriech et al. 2020] contains some experimental evaluations)\n\n# Comments\n\n(I) A part of the statement in this paper is unclear for me.\n\nIn [Tarbouriech et al. 2020], the authors seem to say that the sample complexity is $\\tilde{O}\\left(L^5 S_{L+\\epsilon}\\Gamma_{L+\\epsilon}A/\\epsilon^2\\right)$ under the definition of $\\mathrm{AX}^\\star$ of $\\forall s\\in\\mathcal{K}, v_{\\pi\\_s}(s\\_0\\to s) \\leq V^\\star\\_{\\mathcal{S}^{\\to}\\_L}(s\\_0\\to s) + \\epsilon$ (I copied this equation from Def.5 of [Tarbouriech et al. 2020]).\n\nThis definition is a slight different from the submitted paper (i.e., $(1+\\epsilon)L$ vs $L + \\epsilon$ or $\\epsilon$ vs $\\epsilon L$ or ?). Then, I cannot follow the part of Table 1 (it says $\\tilde{O}(L^3+S^2_{(1+\\epsilon)L}A/\\epsilon^2)$). I feel that such correspondence could be explained a bit more clearly because the complexity statements are core contributions of the paper for possible readers.\n\n(II) Please clarify the assumption of algorithms.\n\nIn Alg.1, the input is an MDP $M=\\langle\\mathcal{S, A}, P, c, s_0\\rangle$. However, from the _Learning Objective_ part, an agent has no prior knowledge of $P$ and $c$, then I wonder how we can input such an $M$ to Alg.1. I guess I misunderstand some parts of the algorithms.\n\n[Just a comment] The mathematical notations (Sec 1.2) are used prior to the definition (Sec 2). This makes readers hard follow the 'overview' of the paper. One approach to mitigate this issue is the paper stats with Sec.2 (i.e., a similar way of Tarbouriech et al. 2020), but I can also understand the current form of the structure.\n\nSome minor comments and questions.\n- p2. $P_{s,a}$ and $\\hat{P}_{s,a}$ are the true and estimated transitions. Are these evaluated for all $s, a$? or partially discovered states on $\\mathcal{K}$?\n- p3. $z\\in \\{0,1,\\dots,Z-1\\}$ to incrementally define $\\mathcal{K}_z$?\n- p3. notation $\\max_{s\\in\\mathcal{S}} |X(S)| \\to \\max_{s\\in\\mathcal{S}} |X(s)|$ as |S| means the number of states\n- p3. Please describe the semantics of $\\mathbb{V}(X, Y)$. I wonder, is it $X(s)^2 Y(s)^2$? (why the square is only for $Y(s)$?).\n- p18. Notation $A[n(s,a)]$ is not defined?", "summary_of_the_paper": "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.", "summary_of_the_review": "The statement of the problem is clearly stated, and good theoretical results are reported with substantial proof. As I read and check, algorithms seem to work. Then, I feel that the proposed result is valuable for the field.\n\nA disadvantage of this paper is that most proofs are included in the appendix, and therefore it is hard to follow and validate the correctness of the paper. To be honest, I cannot validate the correctness of all proof. I feel that the paper should be published as a journal article (e.g., Theoretical Computer Science).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gouOTYkTP3b", "reviewer": "Reviewer_J6YN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is globally well written (see specific comments). I suggest defining at the beginning the learning framework, the (\\epsilon,\\delta) conditions for the different criteria and the sample complexity. I am not convinced by the proofs (see specific comments): some proofs are missing and some points are not clear (see specific comments about the proof of Lemma 9 and Theorem 1). I did not check the proofs of the lower bound. I think that the characterization of the rate for the incremental autonomous exploration problem is a valuable contribution. On the other hand, I find the proposed algorithm a bit involved (see specific comment).\n\nI could increase my score if my concerns about proofs are cleared up.\n\nMain comments: \n-The algorithm is somewhat involved and not very natural. I think that the authors could have put more effort in the description of the algorithm and in providing intuition.\n\n-Can you provide preliminary experiments to illustrate how the proposed algorithms behave on very simple MDP?\n\n-Can you provide the time complexity and space complexity of VALAE algorithm? \n\nSpecific comments:\n-Introduction: the sentence \"This procedure also resembles some biological learning processes\" is a bit cryptic.\n\n-P1, note 1: It seems that there is an extra L in the big O.\n\n-P4, end of the page: the learning framework is not completely clear: how does the agent interact with the MDP? when does the agent stop and output the policies (is T chosen by the agent)? \n\n-P5, end of the page: the sentence \"Then for each action [..] \\hat{c}(s,a)\" is not clear at all.\n\n-P6, Alg2, L5: typo \"where x is defined\".\n\n-P8, top of the page: The first paragraph is hard to follow since we do not know at this point what are Lemma 15 and 16.\n\n-P9, above Definition 3: maybe you could have defined an algorithm for AX/* before in the introduction.\n\n-P11, Lemma 2: Which concentration inequalities? This lemma should be proved even if it is a classical proof.\n\n-P12, Lemma 4: You need an extra assumption on the \\tau_k such that independence to be able to apply Hoeffding inequality.\n\n-P15, end of the proof of Lemma 9: Can you detail why | P_{s,a,s'}  - \\tilde{P}_{s,a,s'} | \\leq \\frac{c_min \\epsilon} {6(L+1)}, it is not \ncompletely obvious for me. And to apply Lemma 3 you need a control in norm 1 and not in infinite norm so there is a S factor missing here?\n\n-P17, proof of Theorem 1: can you detail why on \\cG_2 you get \\hat{P}_{s,a,g} \\geq 3/4 L if \\P_{s,a,g} \\geq1/ L? Typo \"previous paragraph\". \n\n-P17, end of the proof of Theorem 1: can you write explicitly what is the event that happens with probability 1-\\delta/4 to collect the sample? Because a priori for a given state s the policy used to reach s is random. Furthermore to use that V^\\pi \\leq L you used Lemma 9 that is you conditioned by the event \\cG. Thus it is not clear that conditioned don this event the samples remain independent/ have the same distribution in order to apply Lemm 3.  Thus you cannot do a simple union bound over the state as it seems to be done also over policies. Maybe you should rather concentrate a well-chosen martingale.\n\n-P18, proof of Theorem 2: same remark as above.\n\n-P19, Lemma 14,15: can you provide proof for Lemma 14 and 15? In particular, in Algorithm 3 the Visgo procedure is called with \\epsilon_VI = 2^-j... and to prove these two lemma you need according to the proof of Lemma 9 and 10 a lower bound on the number of visits of all state-action pairs that scales with \\epsilon_VI .", "summary_of_the_paper": "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.", "summary_of_the_review": "See the main review", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "U2h-Kn4I1V", "reviewer": "Reviewer_hPxX", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies an interesting topic and makes a significant contribution by presenting the first lower bound and improved upper bounds.\nHowever, I have many problems with its presentation and technical novelty:\n1. The authors did not provide the appendix in the supplementary material. Instead it is attached to the main paper in the same pdf file.\n2. The multi-goal SSP problem is not presented clearly. In fact, I am not sure if I understood it correctly. Is this problem simply the autonomous exploration problem where all of the states of the MDP are $L$-controllable? If so, then this is not really an interesting problem since the authors (and previous work) already solve a more general problem. Moreover, I don't  understand why the name multi-goal SSP suits this problem since it does not seem like a generalization of SSP. Isn't this problem simply reward-free RL?\n3. The authors refer to SSP quite a lot, but they never introduced it properly. The introduction of the multi-goal SSP problem is not clear, but maybe it could be clearer if the authors presented the standard SSP problem first. Furthermore, the authors use many techniques from SSP (e.g., Tarbouriech et al. 2021) so they should really dedicate at least one paragraph to discussing the algorithmic ideas behind SSP algorithms and give the relevant references (all of these references can be found in Tarbouriech et al. 2021).\n4. The technical novelty in the algorithms is not clear to me. Algorithms 1 and 2 look exactly like the algorithms of Tarbouriech et al. 2020, and the only difference is that they use a tighter optimistic planning algorithms (the VISGO algorithm of Tarbouriech et al. 2021). Are there any other new features or difficulties in the analysis? It makes sense that the upper bound is better than Tarbouriech et al. 2020 by a factor of $S$ (actually I think it should also save a factor of $L$) but it does not seem like there is anything new here. If there are technical difficulties then the authors must highlight them and present the ways that they deal with them. In addition, I think that algorithm 3 does not have any real benefits. It trades a factor of $L^2 S_{(1+\\epsilon)L}$ for a factor of $S_{2L}$, but is it really better? To me it looks like (in most actual applications) $S_{2L}$ would be at least of order $(S_L)^2$ and definitely larger than $L$.\n5. The lower bound sketch is not clear at all. In my opinion it should have a lot more focus since this is the first lower bound for the problem. After reading the proof in the appendix, the construction looks almost the same as the lower bound for SSP in \"Near-optimal regret bounds for stochastic shortest path\" (Rosenberg et al. 2020). Are there real differences here? Is the required analysis different? I am having a hard time understanding why this lower bound does not simply arise from the SSP lower bound.\n6. The authors claim that Tarbouriech et al. 2020 study uniform cost of 1, but it looks like section 4.3 in their paper they extend the results to non-uniform cost. Can the authors please comment on that? I would also be interested in the authors opinions regarding costs that may be zero (i.e., $c_{min}=0$). In SSP, strictly positive costs are a much easier case (almost similar to uniform cost of 1), so I wonder how can zero costs be handled in autonomous exploration.", "summary_of_the_paper": "This paper studies the incremental autonomous exploration problem and introduces algorithms with improved sample complexity.\nIt also provides the first lower bound for the problem.", "summary_of_the_review": "The paper studies an interesting topic and give improved sample complexity guarantees. However, the authors fail to present their contributions, novelties, difficulties and techniques clearly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "9gnRujGqxWr", "reviewer": "Reviewer_nNZN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "For the positive side, the expression and organization of the paper is good. It is comfortable to read the paper and understand the critical points made by authors. The series construction argument and the connection between AX and multi-goal SSP is also very interesting. The proposed lower bound complements the AX theory largely. \n\nFor the negative side, I have a few concerns:\n1.\tIt appears to me that the VALAE algorithm is a simple extension of EB-SSP from single point SSP to multi-goal SSP on the MDP induced by the first two algorithms. This somehow reduces the novelty of the paper. \n2.\tThe data collection procedure of the algorithms rely heavily on the RESET action, as if there are a generative model. I wonder if we can design some algorithms to direct the agent from any state back to $s_0$, rather than relying on a RESET action. As far as I’m concerned, such reliance drops a lot of data\n3.\tThere are many examples and detailed explanations, reducing the readability of the paper. This makes readers miss the important conclusions, but stick to those descriptive sentences.\n4.\tI am not sure about the technical novelty of the hard instance constrcution. It appears that the construction is much similar to the one proposed by Rosenberg et al. (2020). You both follow the novel construction proposed in the paper of UCRL2. The constrcution also looks similar. Please make it clear if there is any new idea.", "summary_of_the_paper": "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.\n\n", "summary_of_the_review": "The paper is generally well written, though some paragraphs need shorten. The technical contributions are a little confusing to me, so I recommend the boardline reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an interesting problem, but as pointed out by reviewers, the presentation of the problem statement and contributions need to be improved.
Decision: Reject