A Provably Efficient Sample Collection Strategy for Reinforcement Learning
Authors: Jean Tarbouriech
Matteo Pirotta
Michal Valko
Alessandro Lazaric
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: exploration
sample complexity
Markov decision process
reinforcement learning

Abstract: One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. Whether we optimize for regret, sample complexity, state-space coverage or model estimation, we need to strike a different exploration-exploitation trade-off. In this paper, we propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that (adaptively) prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., a simulator of the environment); 2) An "objective-agnostic" sample collection exploration strategy responsible for generating the prescribed samples as fast as possible. Building on recent methods for exploration in the stochastic shortest path problem, we first provide an algorithm that, given as input the number of samples $b(s,a)$ needed in each state-action pair, requires $\widetilde{O}(B D + D^{3/2} S^2 A)$ time steps to collect the $B=\sum_{s,a} b(s,a)$ desired samples, in any unknown communicating MDP with $S$ states, $A$ actions and diameter $D$. Then we show how this general-purpose exploration algorithm can be paired with "objective-specific" strategies that prescribe the sample requirements to tackle a variety of settings — e.g., model estimation, sparse reward discovery, goal-free cost-free exploration in communicating MDPs — for which we obtain improved or novel sample complexity guarantees.

A Provably Efficient Sample Collection Strategy for Reinforcement Learning
Jean Tarbouriech
Matteo Pirotta Facebook Al Research Paris pirottaffb. com
Facebook Al Research Paris & Inria Lille jean. tarbouriech@@mail. com
Michal Valko
Alessandro Lazaric Facebook Al Research Paris lazaric@fb.. com
DeepMind Paris
valkom@deepmind.comm com
Abstract
One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. Whether we optimize for regret, sample complexity, state-space coverage or model estimation, we need strike dif- ferent exploration-exxlliiation trade-off. In this paper, we propose to tackle the exploration-exploittionn problem following decoupled approach composed of: 1) An "objective-speciff" algorithm that (adaptively) prescribes how many samples collect at which states, as it has access to generative model (i.e.. simulator of the environment); 2) An cobeetiive-gnostii egy responsible for generating the prescribed samples as fast as possible. Building recent methods for exploration in the stochastic shortest path problem, we first provide an algorithm that, given as input the number of samples b(s, a) needed in each state-action pair, requires Ö(BD + 5² time steps to collect the = E.. b(s, a) desired samples, in any unknown communicating MDP with S states, A actions and diameter D. Then we show how this general-purpor ex- ploration algorithm can be paired with "objective-specific" strategies that prescribe the sample requirements to tackle variety of settings - e.g., model estimation, sparse reward discovery, goal-free cost-free exploration in communicating MDPs for which we obtain improved or novel sample complexity guarantees.
sample collection exploration strat-
Introduction
One the challenges in online reinforcement learning (RL) that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. Whenever the agent needs to gather information about a specific region the Markov decision process (MDP), it must plan for policy to reach the desired states, despite not having exact knowledge of the environment dynamics. This makes solving the in RL highly non-trive trivial and it requires designing specific strategy depending the learning objective, such as PAC-MDP learning [e.g.. 13, 47, 59], regret minimization [e.g.. 28, 6, 29, 66) or pure exploration [e.g.. 30, 31, 39, 63, 64].
problem
simpler scenario considered in the literature is to assume access to a generative model or sampling oracle (SO) [33]. Given any state-action pair (s, a). the SO returns next state s' drawn from the transition probability p[-|s, a) and reward r(s, a). In this case, is possible focus exclusively on where and how many samples to collect, while disregarding the problem of finding suitable policy
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to obtain them. For instance, an SO can be used to obtain samples from the environment, which are combined with dynamic programming techniques to compute an e-optimal policy. SO-based algorithms can be as simple as prescribing the same amount of samples from each state-action pair le.g. 35, 33, 5, 16, 46, 38] or they may adaptively change the sample requirements on different state- action pairs [e.g. 15, 58, 62]. An SO is also used in Monte-Carke planning [49, 25, 7] which focuses on computing the optimal action at the current state by optimizing over rollout trajectories sampled from the SO. Finally, in multi-armed bandit [37]. there are cases where each arm corresponds to a state (or state-action), and "pulling" an arm translates into a call to an SO (see e.g., the pure exploration setting of [51]). Unfortunately, while an SO may be available in domains such as simulated robotics and computer games, this is not the case in the more general online RL setting.
In this paper we tackle the asplorationeeploottane
problem in online RL by drawing inspiration from the SO assumption. Specifically, we define an approach that decoupled in two parts: 1) an "objective-specifee
algorithm that assumes access to an SO that (adaptively) prescribes the samples needed to achieve the learning objective of interest, and 2) an "objective-agnostic algorithm that takes on the exploration challenge of collecting the samples requested by the SO-based algorithm as quickly as possible.' Our main contributions can be summarized as follows:
We define the sample complexity of the objective-agnostic algorithm as the number of (online) steps needed to satisty the prescribed sampling requirements. Leveraging recent techniques on exploration in the stochastic shortest path (SSP) problem [45, 50], we propose GOSPRL (Goal- based Optimistic Sampling Procedure for RL), a conceptually simple and flexible exploration algorithm that learns how to "generate" the samples requested by any 5O-based algorithm and we derive bounds on its sample complexity.
Leveraging the generality of our approach, we combine GOSPRI. with problem-specific SO-based algorithms and readily obtain online RI. algorithms in difficult exploration problems. While in general our decoupled approach may be suboptimal compared to exploration strategies designed to solve one specific problem, we obtain sample complexity guarantees that are on par better than state-of-the-art algorithms in a range of problems. 1) GOSPRL solves the problem of sparse reward discovery in (( D3/252 A) time steps, which improves the dependency on the diameter D w.r.t. a reward-free variant of UCRL2B [28, 22], as well as on S and A w.r.t. MAXENT-type approach [26, 17]. 2) GOSPRL improves over the method of [54] for model estimation, by removing their ergodicity assumption as well as achieving better sample complexity. 3) GOSPRL provably tackles the problem of goal-free cost-free exploration, for which no specific strategy is available.
We report numerical simulations supporting our theoretical findings and showing that pairing GOSPRL with SO-based algorithms outperforms both heuristic and theoretically grounded base- lines in various problems.
Related work. While to the best of our knowledge no other work directly addresses the problem of simulating an SO, number of approaches are related to it. The problem solved by GOSPRL can be seen as a reward-free exploration problem, since it is not driven by any external reward but by the objective of covering the state space to quickly meet the sampling requirements. Standard algorithms, such as UCRL2 [28] in the undiscounted setting or RMAX [13] in the discounted one, implicitly encourage exploration specific areas of the state-action space that are not estimated accurately enough. The objective of covering the state space is also studied in [26, 17] with Frank-Wolfe approach that optimizes smooth aggregate function of the state visitations.
Recent works on reward-free exploration (RFE) in the finite-horizon setting [c.g.. 30, 31, 39, 64] provide sufficient exploration so that an e-optimal policy for any reward function can be computed. Our proposed solution shares high-level algorithmic principles with RFE approaches which incen- tivize the agent to visit insufficiently visited states via intrinsic reward. Nonetheless, our contribution significantly differs from existing RFE literature in two dimensions: 1) While we study the perfor- mance of GOSPRL in one goal-conditioned RFE problem (Sect. 4.3), our framework is much broader and it allows us to tackle a wider and diverse set of problems (Sect. 4 and App. I); 2) Our setting is horizon-agnosic and reset-free, which prevents from directly using any method or technical analysis in RFE designed for problems with an imposed planning horizon (e.g., finite-horizon or discounted).
Finally, GOSPRL draws inspiration from the SSP formalism and solutions of [50, 45], but our approach critically differs from these works in three main ways: 1) we are interested in sample
Alternatively, we can view it as general approach to take any Sa-ba algorithm and convert it into an online RL algorithm.

---

complexity guarantees rather than a regret analysis; 2) we consider requirements (i.e., goals to sample) that vary throughout the learning process, instead of an SSP problem with fixed goal state and cost function; 3) we show how GOSPRI. can serve as sample collection component to tackle various learning problems other than regret minimization.
2 Problem Definition
We consider a finite and reset-free MDP [43] M AS,,. with = states, A : | actions and an arbitrary starting state &o S. Calling an SO any state-action pair (s, a) leads to two outcomes: next state sampled from the transition probability distribution p(-1s, a) E ASS), and a reward r(s, E IR. A stationary deterministic policy is a mapping æ : actions and we denote by ITSD the set of all such policies. For any policy π and pair of states (s, s'), let Ta (s + 8') be the (possibly infinite) hitting time from & to s' when executing T, i.e., Ta (s ++) ==
from states to
it 2 0: 8r41 = = 81 5, TT. where 8, is the state visited at time step L. We introduce
Das' min E|T s'),,
Dør ==
max Das's sES([=)
D == max Dx'
s'ES
where Das is the shortest-path distance between and s', Dy is the SSP-diameter of s' [50] and D is the MDP diameter [28].
We now formalize the problem of simulating an SO (i.e., to generate the samples prescribed by an SO-based algorithm). At each time step / 2 1 the agent receives a function b, S x A + N, where be(s, a) defines the total number of samples that need be collected (s, a) by time step L. We consider that (be) is an arbitrary sequence with each b, measurable w.r.t. the filtration up to time t (i.e., it may depend on the samples observed so far).² We focus on the objective of designing an online algorithun that minimizes the time required collect the prescribed samples. Since the environment is initially unknown, we need to trade off between exploring states and actions to improve estimates of the dynamics and exploiting current estimates to collect the required samples as quickly as possible. We formally define the performance metric as follows.
Definition 1. For any catteacction pair, we denote by a)(s,a) := E 1l ((s,a)))= the number of visits to state s and action a up to (and including) time step Given a sampling requirement sequence b := (bx)r21 with by SS x A + M and confidence level 5 E (0, 1), we define the sumple complexity of a learning algorithm 21 as
C(21.b, == min {t > 0 P(V(s, E SSS Ny a) 2 b,(s,a)) 2 1- 1-67.
With no additional condition, it is trivial to define problems such that C(21, b, too for any algorithm. To avoid this case, we introduce the following assumptions.
Assumption 1. The MDP M is communicating with a finite and unknown diameter D) < +00. Assumption 2. There exist an unknown and bounded function b S x A + N such that the sequence (be)e21 verifies: Vt 2 1, V(s, E x A, hi(s,a) S b(s, a).
Asm. 1 guarantees that whatever state needs to be sampled. there exists at least one policy that can reach it in finite time almost-surely (notice that is considerably weaker than the ergodicity assumption (App.J) often used in online RL, see e.g., [60, 40, 24]). Asm. 2 ensures that the sequence of sampling requirements does not diverge and can thus be fulfilled in finite time. These assumptions guarantee that the problem in Def. I is well-posed and the sample complexity is bounded.
variety of problems can be cast under our decoupled approach, the sense that they can be tackled by solving the problem of Def. I under specific instantiation of the sampling requirement sequence (bx)221 For instance, consider the problem of covering the state-action space (e.g., to discover a hidden sparse reward), then the requirement is immediately defined as (e a) = In Sect. 4 and App. I, we review problems where defining by can be as simple as computing the sufficient number of samples needed to reach certain level of accuracy in estimating a quantity of interest (c.g., model estimation) or can be directly extracted from existing literature (e.g., --optimll policy learning).
We now provide a simple worst-case lower bound on the sample complexity (details in App. D).
2 Allowing adaptive sampling requirements enables to pair GOSPRL with SCO-baedd algorithms that adjust their requirements online samples are being generated (see e.g.. 4.2t.
3

---

Algorithm GOSPRL Algorithm
sampling requirement sequence (bc (21 with b 8 A - N revealed time (or anytime before). Initialize: Set 91 {s E S 3a E A, (s, > 0}. time step counters (s, a) == attempt index == and attempt counters (i a) = 0, v1 (s, := 0.
Input:
while G. is not empty do
Define the SSP problem Mr with goal states Gs, and compute its optimistic shortest-path policy T Set =afffla-rrai True and counter (x, a) == 0. while flag do
Execute action a, == (s.) and observe next state 8141 p(.).e...).. Increment counters (x (st, az) and (s(s., at).
if 8 E Gi or (st, 0x) (Ua(st, V V1 then
Sct f False. end
Set t +- 1. end while
if E GR then
Execute action a s.t. Ni be(st, observe next state 8141 ~ p(-1se, a) and set t += 1.
end
Set U441 (s, a) == Un(s, a) ( kt +- Update the set of goal states GR == E Fa A. < b end while
Lemma 1. For any S 2 1, there exists an MDP with S states satisfying Asm. such that for any sampling requirement b: + satisfying Asm. 2,
min (2, 11) = S2 ED.((s))
A
BES
Lem. shows that the (possibly non-stationary) policy minimizing the time to collect all samples requires (2( Σ. Dyb(s)) time steps in a worst-case MDP. We also notice that when the total sampling requirement B is concentrated on the state for which D3 D (i.e., b(s') 0, Vs * 3), the previous bound reduces to ((BD).
Online Learning for SO Simulation
We now introduce our algorithm for the problem in Def. 1, bound its sample complexity and discuss several extensions.
3.1 The GOSPRL Algorithm
In Alg. we outline GOSPRL (Goal-based Optimistic Sampling Procedure for Reinforcement Learn- ing). At each time step f, GOSPRL receives sampling requirement S A N. The algorithm relies on the principle of optimism in the face of uncertainty and proceeds through attempts to collect relevant samples. We index the attempts by k 1, 1, ... and denote by le the time step at the start of attempt k and by Ua == Nr,-1 the number of samples available at the start of attempt k. At each attempt, GOSPRI goes through the following steps: 1) Cast the under-sampled states goal states and define an associated unit-cost multi-goal SSP instance (with unknown transitions); 2) Compute an optimistic shortest-path policy: 3) Execute the policy until either a goal state is reached stopping condition is satisfied; 4) If a sought- goal state denoted by has been reached, execute an under-sampled action (i.e., an action such that (2 a) be(g. a)). The algorithm ends when the sampling requirements are met, i.e., at the first time 2 1 where N₂ a) 2 be(s, a) for all (s, a).
Step At any attempt we begin by defining the set of all under-sampled states
G3 = {s S 3a E A. Ns, a) < (s. a)). We then cast the sample collection problem goal-reaching objective, by constructing multi goal SSP problem [9] denoted by Mf : (Sk. A, pks ck. Gk), with:?
'If' the current state St, is uunder-samlle (i.e., Stg E Gu). we duplicate the state and consider it to be both goal state in Gi and a non- state from which the attempt & starts (and whose outgoing dynamics are the same those of st,) ). which ensures that the state the start of each attempt cannot be a goal state.

---

G. denotes the set of goal states, S₁ := S' \ Gk the set of non-goal states and A the set of actions. The transition model Pk is the same as the original p except for the transitions exiting the goal states which are redirected as a self-loop, i... pk (s'|s, a) == p(s' s, and (x a) := 1 for any
(s, g) E Sx x S x A x Gj.
The cost function C₁ is defined as follows: for any a E ... any goal state g E Gk is zero-cost (cx(g, a) 0), while the non-goal costs are unitary (c& (s, a) := for E Sk).
From [10], Asm. and the positive non-goal costs C₁ entail that solving M₁ is a well-posed SSP problem and that there exists optimal policy that is proper (i.e., that eventually reaches one of the goal states with probability 1 when starting from any E Sk)). Crucially, the objective of collecting sample from the under-sampled states GE coincides with the SSP objective of minimizing the expected cumulative cost to reach goal state in Mg.
Step 2. Since ps is unknown, cannot directly compute the shortest-path policy for Mg. Instead, leveraging the samples collected so far, we apply an extended value iteration scheme for SSP which implicitly skews the empirical transitions Pk: towards reaching the goal states. This procedure can be done efficiently as shown in [50] (see App. A), and it outputs an optimistic shortest-path policy Ty.
Step 3. 3y is then executed with the aim of quickly reaching an under-sampled state. Along its trajectory, the counter N₂ is updated for each visited state-action. Because of the error in estimating the model, 7t may never reach one of the goal states (i.e., it may not be proper in p&). Thus TR executed until either one of the goals in GE is reached, or the number of visits is doubled in a state-action pair in S₁ x A, a standard termination condition first introduced in [28]. If sought-after goal state is reached, the agent exccutes an snder--ampled action according to the current sampling requirements at that state. At the end of each attempt, the statisties (e.g., model estimate) are updated.
The algorithmic design of GOSPRL is conceptually simple and can flexibly incorporate various modifi- cations driven by slightly different objectives or prior knowledge, without altering Thm. I (cf. App. B).
3.2 Sample Complexity Guarantee of GOSPRL
Thm. establishes the sample complexity guarantee of GOSPRL (Alg. 1).
Theorem 1. Under Asm. 1 and 2, for any sampling requirement sequence b (be)121 and any confidence level 8 E (0, 1), the sample complexity of GOSPRI. is bounded as
C(GOSPRL, 6,0) = =Ō(BD= =O(BD+D8/2 22/2 AA)
(1)
C(GOSPRL, D. = Ō (D),(())))))))) + S2/2
(2)
SES
where the Ô notation hides logarithmic dependencies S, A, D, 1/8 and b(s) == EnEA b(s,a) a)
and B == Exes b(s). Recall that D2 S. D is the SSP-diameter of state and captures the difficulty of collecting a sample at state starting at any other state in the MDP
We notice that in practice GOSPRL stops at the first random step T at which the sampling requirement b, 0-(s, a) is achieved for all (s, a). Thm. I provides a worst-case upper bound on the stopping time of GOSPRL using the possibly loose bound b, (x, a) < a), On the other hand, in the special case b: S - N when the requirements are both ine-iindependent (i.e., given as initial input to the algorithm) and action- action-independent, the actual sampling requirement b(s) (resp. B E.es b(s)) replaces B(s) (resp. B) in the bound. In the following, we consider this case for the ease of exposition.
Proof idea. The key step (see App. C for the full derivation) is to link the sample complexity of GOSPRI. the regret accumulated over the sequence of multi-goal SSP problems Ms generated across multiple attempts. Indeed we can define the regret at attempt k: as the gap between the performance of the SSP-optimal policy z solving Ms (i.e., the minimum expected number of steps to reach any of the states in G. starting from Sty) and the actual number of steps executed by GOSPRL before terminating the attempt. While the SSP regret minimization analysis of [45] assumes that the goal is fixed, we show that it is possible to bound the regret accumulated across different attempts for any arbitrary sequence of goals. The proof is concluded by bounding the cumulative performance of the SSP-optimal policies and leads to the bound Ö(BD + D3/2 52 A) where B == Eses b(s). On the other hand, the refined bound in Eq. 2 requires a more careful analysis, where we no longer directly
5

---

translate regret bounds into sample complexity and we rather focus on relating the performance to state-dependent quantities Dj and b(s). Finally, we show that the extension to the general case of time-dependent action-dependent sampling requirements is straightforward and obtain Thm. 1.
Interpretation of Thm. 1. We can decompose Eq. as a linear term in B and a constant term. In the regime of large sample requirements (i.e., large B), the sample complexity thus reduces to O(BD), which adds at most an extra "cost" factor of D w.r.t. an SO. As this may be loose in many cases, the more refined analysis of Eq. 2 stipulates cost of D. to collect a sample at state which better captures the connectivity of the MDP. In fact the lower bound in Lem. shows that this cost of De is unavoidable in the worst case, and that GOSPRL is only constant and logarithmic terms off w.I.t. to the best sample complexity that can be achieved in the worst case. While an extra attempt of refinement would be to avoid being worst-case w.r.t. the starting state in the definition of D.. this seems particularly challenging as the randomness of the environment makes it hard to control and analyze the sequence of states traversed by the agent. Also note that existing bounds in SSP [50, 45] are only worst-case and it remains an open question to derive finer (e.g., in SSP and how they could be leveraged in our case.
bounds
Optimal solution. GOSPRL targets a greedy-optimal strategy, which seeks to sequentially minimize each time to reach an under-sampled state. Alterntively, one may wonder if it is possible to design a learning algorithm that approaches the performance of the exact-optimal solution, i.e., a (non- stationary) policy explicitly minimizing the number of steps required to fulfill the sampling require- ments. Such strategy can be characterized as the optimal policy of an SSP problem for an MDP with state space augmented by the current sampling requirements and goal state corresponding to the case when all desired samples are collected. Even under known dynamics, the computational complexity of computing the optimal policy in this MDP (e.g.. via value iteration) is exponential (scaling in BS). When the dynamics is unknown, it appears highly challenging to obtain any learning algorithm whose performance is comparable to the exact-optimal strategy for any finite sample requirement B.
Beyond Communicating MDPs. In App. E we design an extension of GOSPRL to poorly or weakly communicating environments. In this setting, it is expected to assess online the "feasibility" of certain sampling requirements and discard them whenever associated to states that are too difficult to reach or unreachable. Given as input a "reachability" threshold L, we derive sample complexity guarantees for our variant of GOSPRI. where the (possibly large or infinite) diameter D is fittingly replaced by T..
4 Applications of GOSPRL
An appealing feature of GOSPRL is that it can be integrated with techniques that compute the (fixed or adaptive) sampling requirements to readily obtain an online RL algorithm with theoretical guarantees. In this section we focus on three specific problems where in our decoupled approach the SO-based algorithm is either trivial or can be directly extracted from existing literature, and its combination with the sample collection strategy of GOSPRL yields improved or novel guarantees. Other applications (e.g., PAC-policy learning, diameter estimation, bridging bandits and MDPs) are illustrated in App. I.
4.1 Sparse Reward Discovery (TREASURE)
A number of recent methods focus the state-space coverage problem, where each state in the MDP needs to be reached as quickly as possible. This problem is often motivated by environments where a one-hot reward signal, called the treasure, is hidden and can only be discovered by reaching specific state and taking a specific action. Not only the environment but also the treasure state-action pair is unknown, and the agent does not receive any side information to guide its search (e.g., measure of closeness to the treasure). Thus the agent must perform exhaustive exploration to find the treasure.
Definition 2. Given confidence 8 (0, 1), the TREASURE sample complexity of learning algo- rithm 2 is defined as CTREASURE (RI, 8) = min {t > 0 : P(Y(s,)) E S x A, (((s.)) 2 1) 2 1-.
'For instance, consider simple deterministic chain with requirement of sample per state. If the agent starts on the leftmost state, then policy that keeps moving right has sample complexity S without extra factor D. 'Notice that as illustrated in the lower bound of Lem. 1, the exact-optimal and greedy-optimal have the same performance in the worst case.

---

In this case, SO-based algorithm would immediately solve the problem by collecting one sample from each state-action pair. As a result, we can directly apply GOSPRL for TREASURE by simply setting b(8, a) 1 for each (s, a) and from Thm. with B = SA we obtain the following guarantee.
Lemma 2. GOSPRL with b(s, a) = verifies CTREASURE CRREAscRe(GOSPEE (GOSPRL, 6) O
We now compare this result alternative approaches to the problem, showing that GOSPRL has state-of-the-art guarantee for TREASURE (see App. G for details).
First, reward-free methods such as [30, 64, 31, 39] are designed for finite-horizon problems so their guarantees cannot be directly translated to sample complexity for the TREASURE problem. Nonetheless, we draw inspiration from their algorithmic principles and analyze a reward-free variant of UCRL2 [28, 22]. Specifically we consider 0/I-UCRL, which runs UCRL by setting reward of to under sampled states and 0 otherwise. However, we obtain a TREASURE sample complexity for 0/I-UCRI, of O(ErEs 5 A), which is always worse than the bound in Lem. 2. Second, we can adapt the MAXENT approach [26] to state-action coverage so that targets a policy whose stationary state-action distribution À maximizes (A)
E.,a a A(s, a) log X(s, a). While optimizing this entropy does not provably solve TREASURE, it encourages us to take a "worst-case" approach w.r.t. the state-action visitations, and rather maximize F(A) = (ia A(s, a). We show that the learning algorithm of [17] instantiated to maximize F yields TREASURE sample complexity of at least (min| D² A/(((")?? D'/(////// /(==)())))))))>>))))()) with w == min, F(A) I (SA)
which is significantly poorer than Lem. 2. In fact, in contrast to MaxENT-inspired methods that optimize for a single stationary policy, GOSPRL realizes a non non- stationtt strategy that gradually collects the required samples by tackling successive learning problems.
4.2 Model Estimation (MODEST)
We now study the problem of accurately estimating the unknown transition dynamics in reward- free communicating environment. The objective was recently introduced in [54] and we refer to it as the model-estimation problem, or MODEST for short.
Definition 3. Given an accuracy level 0 and confidence level 8 E (0, 1). the MODEST sample complexity of an online learning algorithm 2 is defined as
CMODEST (onDEsT(2L,,00 5. == min {t 0: P: E x A, ( - ls) S 2n) 2 1
where px,t is the estimate (i.e., empirical average) of the transition dynamics p after time steps.
Unlike in TREASURE, here the sampling requirements are not immediately prescribed by the problem. To define the Sa-b algorithm we first upper-bound the estimation error using an empirical Bernstein inequality and then invert it to derive the amount of samples (, a) needed to achieve the desired level of accuracy 7) (see App. F). Specifically, letting @f ss a) Pe (ss,a)(1- (1''ss"''ss,.. be the estimated variance of the transition from (s, a) to s' after t steps, we set
(s'[s,
be(s, a) = 57 6e(5'1s,a)) n
log? Se(E, Ge 8, a)) 2SA
24S log
24. A
)
(3)
Von
ön
Since the estimated variance changes depending on the samples observed so far, the sampling requirements adapted over time. Given that (ss'ss), a) 1/4, be(s, a) is always bounded so Thm. provides the following guarantee.
Lemma 3. Ler I := max,, a IIp(- (s, a)llu S S be the maximal support of p(-1s, a) over the state- action pairs (s, a). Running GOSPRL with the sampling requirements in Eq. yields
0) = - ( +
DDSS
DS A + 1332252A) A).
AMooEET((GOSPRL. CMODEST (GOSPRI, 11
Lem. improves over the result of [54] two important aspects. First, the latter suffers from an inverse dependency on the stationary state-action distribution that optimizes proxy objective function used in the derivation of their algorithm. Second, while [54] requires an ergodicity assumption, Lem. 3 is the first sample complexity result for MODEST in the more general communicating setting.
7

---

4.3 Goal-Free & Cost-Free Exploration in Communicating MDPs
We finally delve into the paradigm of reward-free exploration introduced by [30]: the objective of the agent is to collect enough information during the reward-free exploration phase, so that it can readily compute a near-optimal policy once any reward function provided. The problem has been analyzed in the fiiie-horizon setting [e.g., 30, 39, 64]. Here we study the more general and challenging setting of
RL. 6 We define the goal-free cost-free objective as follows: after the exploration phase, the agent is expected to compute a near-optimal coal-conditioned policy for any goal state and any cost function (w.lo.gg we consider a maximum possible cost Cmax = 1). Recall that given a goal state y and costs the (possibly unbounded) value function of policy is
(8-+))
(* - g) = E
c(s (8t))
Given slack parameter 0 E [1, +o0,, we say that a policy ît is (E, (c,0))optimal)) if
min vn + g) (l
(" + +) +
In this setting, constructing an efficient SO-based algorithm is considerably more complex than TREASURE and MODEST. Relying on sample complexity analysis for the fixed-goal SSP problem with generative model [53], we define the (adaptive) number of samples needed in each state-action pair for our online objective. Although the number depends on the unknown diameter, we estimate D using GOSPRL. The resulting sequence of sampling requirements is then fed online to GOSPRL. Combining the result of [53] and the properties of GOSPRL yields the following bound (see App. H).
Lemma 4. Consider any MDP satisfying Asm. I and the goal-free cost-free exploration problem with accuracy level 0 < < < 1, confidence level ō E (0, 1), minimum cost Cmin E [0, 1], slack parameter 0 e [oo]. We can instantiate GOSPRL that its exploration phase (i.e., number of time steps) bounded with probability at least 8 by
DTSA wg2
DA
D'TSA w2
WC
where w == ==axx Cmin, (OD) (thus, either Cmin = 0 or 0 +oc, but not both simultane- ously). Following the exploration phase, the algorithm can compute in the planning phase, for any goal state E and any cost function c in [Cmin, 1], policy ag. that is (s. (E.0) -)ottmmlll
Lem. 4 establishes the first sample complexity guarantee for general goal-free, cost-free exploration. While the objective is demanding and the upper bound on the length of the exploration phase can be large, the main purpose of this result is showcase how GOSPRL can be readily instantiated to tackle a challenging exploration problem for which no existing solution can be easily leveraged. Comparing our analysis the finite-horizon objective of [30] reveals two interesting properties:
The goal-free aspect: moving from finite-horizon to goal-conditioned renders unavoidable both the communicating requirement (Asm. 1) and the bound's dependency the unknown diameter D (which partly captures the role of the known horizon H in the bound of [30]).
The cost-free aspect: in contrast to mnite-horizon. the value Cmin has an important impact on the type of performance guarantees
can obtain; in particular analysis distinguishes between
positive and non-negative costs (as also done in existing SSP analysis [11, 50, 45]).
5 Experiments
In this section we report preliminary numerical validation of our theoretical findings, While GOSPRL can be integrated in many different contexts, here we focus the problems where our theory suggests that GOSPRL performs better than state-of-the-aa online learning methods.
'While an approach proposed in [52]. it is restricted to considering only the incrementally attainable goal states from resettable reference state So.
"This reduces to standard e-optimllity for = +oo. We only consider 0 < +oo in the case of minimum possible cost Cain 0 and it ensures that the algorithm targets proper policies (see App.
8

---

Proportann P.
GOSPRI.
0.5
64-
0/1-UCRL
B-UCRL
0.1-
MANNEN
Uniform
6.
0.
1,000
3,000
Grae
tiee
Figure 1: TREASURE-10 problem (i.e. with b(s, a) = 10): Proportion Pr of states meeting the requirements at time f, averaged over 30 runs. By definition of the sample complexity, the metric of interest is not the rate of increase of Pe over time but only the time needed to reach the line of success P; 1. Left: 6-state RiverSwim, Center: 24-state corridor gridworld, Right: 43-state 4-room gridworld (sec App. K. for details the domains).
random instannes of 0,10,5,5)
candora instances of (,0,,5,
10a
10
Sumple complectyy
2.4
V
2.2
50
82
Figure 2: Sample complexity boxplots GOSPRI. (in red) and 0/1-UCRI. (in blue). Each column represents 30 runs on a randomly generated Garnet G(S, A = 5, 5) with randomly generated state-action sampling require- ments b: S A u(0, 100). Left: S = 10, Right: S 50.
Sample comple (GDSSpt)
10
comp.
10a
Wheel
Gamad (66
10a-
Taffrr Melghted Mucdee
cod Elabers
15
10'
10'
10
OEGPSE
Diametter D (ss 1/0)
Figure 4: Simple threc-state reward-free domain [23]
and TREASURE- 10 sample complexity of GOSPRL. 10
(averaged over 30 runs) as
Figure 3: MODEST problem: Eserrror & == (S Σs.o ( (-)s,a)
function of the diameter D Rz 1/v.
o(-[s,a)]l averaged over 30 runs. Left: NoisyRiverSwim(35) Center:
W3eel(30), Right: Randomly generated Garnet G(50, 5, 25).
TREASURE-type problem. We consider TREASURE-lype problem (Sect. 4.1), where for all (s, a) we set b(s, a) instead (we call the TREASURE- 10 problem). 8 We begin by showing in Fig. 4 that it is easy to construct worst-case problem where the sample complexity scales linearly with the diameter, which is consistent with the thcoretical discussion in Sect. and 3.
We compare to two heuristics based on UCRL2B [28, 22]: O-UCRL, where the reward used in computing the optimistic policy is set proportional to (s, b(s, )))=)//22/// and 0/1-UCRL with reward for undersampled state-action pairs and otherwise. We also compare with the MAXENT algorithm [17] that maximizes entropy over the state-action space, and with a uniformly random baseline policy. We test on the RiverSwim domain [48] and various gridworlds (see App. for details and more results). Fig. reports the proportion P, of states that satisfy the sampling requirements at time Our metric of interest the time needed collect all required samples, and we see that GOSPRL reaches the P, = 1 line of success consistently, and faster than 0/1- 0/I-UCRL, while the other heuristics struggle. The steady increase of P: illustrates GOSPRI.' 's design to progressively meet the sampling requirements, and not exhaust them state after state.
*Since GOSPRL and baselines all based upper confidence bounds, they tend display similar behaviors the initial phases learning, since the estimates when ((s, a) 0 are similar. As the number of samples required in each state-action increases, the difference between the algorithms' design starts making a real difference in the behavior and eventually their performance. This is why we study here TREASURE- 10 instead of the TREASURE-1 I problem for which empirical performance is comparable between learning algorithms.

---

Random MDPs and sampling requirements. To study the generality of GOSPRL to collect arbitrary sought-after samples, we further compare GOSPRL with 0/1-UCRL which is the best heuristic from the previous experiment. We test on variety of randomly generated configurations, that we define as follows: each configuration corresponds to i) randomly generated Garnet environment (SS, A, (3) (with S states, A actions and branching factor /3, see [12]), and ii) randomly generated requirements b(s, a) ( U), where the maximum budget is set to U = 100 to have wide range of possible requirements across each environment. The boxplots in Fig. 2 provide aggregated statistics on the sample complexity for different configurations. We observe that GOSPRL consistently meets the sampling requirements faster than 0/1-UCRI,, as well as suffers from lower variance across runs.
MODEST problem. Finally, we empirically evaluate GOSPRL for the MODEST problem (Sect. 4.2). We compare to the fully online "EIGHTEDMAXENT heuristic, which weighs the state-action entropy components with an optimistic estimate of the next-state transition variance and was shown in [54] to perform empirically better than algorithms with theoretical guarantees. We test on the two environments Roiisy and Wheel) proposed in [54] for their high level of stochasticity, as well as on a randomly generated Garnet. To facilitate the comparison, we consider a GOSPRI-ffr- MODEST algorithm where the sampling requirements are computed using decreasing error (see App. K for details). We observe in Fig. 3 that GOSPRL. outperforms the WEIGHTEDMMXENT heuristic.
6 Conclusion
In this paper, we introduced the online learning problem of simulating sampling oracle (Sect. 2) and derived the algorithm GOSPRL with its sample complexity guarantee (Sect. We then illustrated how it can be used to tackle in a unifying fashion a variety of applications without having to design specific online algorithm for each, while at the same time obtaining improved or novel sample complexity guarantees (Sect. 4). Going forward, we believe that GOSPRL can be used as a competitive off- thelshelf baseline when a new application is introduced.
An exciting direction of future investigation is to extend the general sample collection problem and its various applications beyond the tabular setting. Handling a continuous state space or linear function approximation requires redefining the notion of reaching specific state (e.g., via adequate discretiza- tion or by considering requirements based on the covariance matrix). Studying the SSP problem beyond tabular may provide insights, as recently initiated in [56] in linear function approximation under the assumption that all policies are proper. On the more algorithmic side, GOSPRL hinges on knowing the sampling requirement function by and deriving a shortest-path policy म. Interestingly, we can identify algorithmic counterparts to both modules in deep RL. The computation of मे can be entrusted to a to goal-samplin selection mechanisms that elect hard-to-read [21]] or rare [42] states goals.
network (using e.g., [2]), while the specification of by can be related
References
[1] A. Agarwal, S. Kakade, and L. F. Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Muchine Learning Research. PMLR, 2020.
[2] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. To- bin, P. Abbeel, and W. Zaremba. Hindsight experience replay. Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 5055-5065, 2017.
[3] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In COLT 23th Conference on Learning Theory, 2010.
[4] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration-exxllotttion tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):176--100,, 2009.
[5] M. G. Azar, R. Munos, and H. J. Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3):325-349) 2013,
10

---

[6] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR, 2017.
[7] P. Bartlett, V. Gabillon, J. Healey, and M. Valko. Scale-free adaptive planning for deterministic dynamies & discounted rewards. In International Conference on Machine Learning, pages 495-504. PMLR, 2019.
[8] P. L. Bartlett and A. Tewari. Regal: a regularization based algorithm for reinforcement learning in weakly communicating mdps. In Proceedings of the Twenty-Fifte Conference on Uncertainty in Artificial Intelligence, 2009.
[9] D. P. Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
[10] D. Bertsekas and N. Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595, 1991.
[11] D. P. Bertsekas and H. Yu. Stochastic shortest path problems under weak conditions. Lab. for Information and Decision Systems Report LIDS-P-2909, MIT, 2013.
[12] S. Bhatmagar, R. Sutton, M. Ghavamzadeh, and M. Lee. Natural actor-critic algorithms. Automatica, 45(11 +5(11):2471-2482 2009.
[13] R. I. Brafman and M. Tennenholtz. R-max-a general polynomial time algorithm for opttimlltmall reinforcement learning. Journal of Machine Learning Research, ((Oct): 2002.
[14] A. Carpentier, A. Lazaric, M. Ghavamzadeh, R. Munos, and Auer. bound algorithms for active learning in multi-armed bandits. In International Conference on Algorithmic Learning Theory, 2011.
[15] Y. Chen, L. Li, and M. Wang. Scalable bilinear ı learning using state and action features. arXiv preprint 1804. 10328, 2018.
[16] Y. Chen and M. Wang. Stochastic primal-dual methods and sample complexity of reinforcement learning. arXiv preprint 16 2016.
[17] W. C. Cheung. Exploration-exploitaaioo trade-off in reinforcement learning on online markov decision processes with global concave rewards. arXiv preprint arXiv: arXiv:1905. 964666 2019.
[18] W. C. Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. In Advances in Neural Information Processing Systems, pages 724-734 2019.
[19] O. Dekel, J. Ding, T. Koren, and Y. Peres. Bandits with switching costs: T2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459-467, 2014.
[20] F. d'Epenoux. A probabilistic production and inventory problem. Management Science, 10(1)988-00, 1963.
[21] C. Florensa, D. Held, X. Geng, and P. Abbeel. Automatic goal generation for reinforcement learning agents. In International conference muchine learning, pages 1515-1528. PMLR, 2018.
[22] R. Fruit, M. Pirotta, and A. Lazaric. Improved analysis of ucr12 with empirical bernstein inequality. arXiv preprint arXiv:2007.05444 2020.
[23] R. Fruit, M. Pirotta, A. Lazaric, and R. Ortner. Efficient bias-span-constrriied exploration- exploitation in reinforcement learning. ICML 2018-The 35th International Conference on Machine Learning, volume 80, pages 1578-1586, 2018.
[24] E. Garcelon, M. Ghavamzadeh, A. Lazaric and M. Pirotta. Conservative exploration in reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1431-1441. PMLR, 2020.

---

[25] J.-B. Grill, M. Valko, and R. Munos. Blazing the trails before beating the path: Sample- efficient monte-carlo planning. In Advances in Neural Information Processing Systems, pages 4680-4688 4688, 2016.
[26] E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681-266 1681-2691, 2019.
[27] D. J. Hsu, A. Kontorovich, and C. Szepesvári. Mixing time estimation in reversible markov chains from a single sample path. In Advances in neural information processing systems, pages 1459-1467, 2015.
[28] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, (1AAp)):15331100) 2010.
[29] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863 4873, 2018.
[30] C. Jin, A. Krishnamurthy, M. Simchowitz, and T. Yu. Reward free exploration for reinforcement learning. In International Conference Machine Learning, pages 4870-4879. PMLR, 2020.
[31] E. Kaufmannn Ménard, O. D. Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891. PMLR, 2021.
[32] A. Kazerouni, M. Ghavamzadeh, Y. Abbasi, and B. Van Roy. Conservative contextual linear bandits. In Advances in Neural Information Processing Systems, pages 3910-3919, 2017.
[33] M. Kearns, Y. Mansour, and A. Y. Ng. A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine learning. 49(2-3):193-205 2002.
[34] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2-3):209-33,, 2002.
[35] M. J. Kearns, Y. Mansour, and A. Y. Ng. Approximate planning in large pomdps via reusable trajectories, In Advances in Neural Information Processing Systems, pages 1001-1007, 2000.
[36] T. Koren, R. Livni, and Y. Mansour. Bandits with movement costs and adaptive pricing. In Conference on Learning Theory, pages 1242-1268. PMLR, 2017.
[37] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[38] G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 2020.
[39] Ménard, O. D. Domingues, A. Jonsson, E. Kaufmann, E. Leurent, and M. Valko. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning, pages 7599-7608. PMLR, 2021.
[40] R. Ortner. Regret bounds for reinforcement learning via markov chain concentration. Journal of Artificial Intelligence Research, 67:1 2020.
[41] D. Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20, 2015.
[42] V. Pong, M. Dalal, S. Lin, A. Nair, S. Bahl, and S. Levine. Skew-fit: State-covering self- supervised reinforcement learning. In International Conference on Machine Learning, pages 7783-7792. PMLR, 2020.
[43] M. I.. Puterman. Markov Decision Processes.:: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[44] J. Qian, R. Fruit, M. Pirotta, and A. Lazarie. Exploration bonus for regret minimization in discrete and continuous average reward mdps. Advances in Neural Information Processing Systems, pages 4891-4900, 2019.
12

---

[45] A. Rosenberg, A. Cohen, Y. Mansour, and H. Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pages 8210-8219. PMLR. 2020.
[46] A. Sidford, M. Wang, X. Wu, L. Yang, and Y. Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pages 5186-5196, 2018.
[47] A. L. Strehl, L. Li, and M. L. Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Machine Learning Research, 10(Nov):2413-2244, 2009.
[48] A. L. Strehl and M. L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8): 1309-1309-1110 1330--1311, 2008.
[49] B. Szörényi, G. Kedenburg, and R. Munos. Optimistic planning in markov decision processes using generative model. Advances in Neural Information Processing Systems, 27:1035- 2014.
[50] Tarbouriech, E. Garcelon, M. Valko, M. Pirotta, and A. Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference on Machine Learning, pages 9428-9437. PMLR, 2020.
[51] J. Tarbouriech and A. Lazaric. Active exploration in markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 974-982, 2019.
[52] Tarbouriech, M. Pirotta, M. Valko, and Lazaric. Improved sample complexity for in- cremental autonomous exploration in mdps. In Advances in Neural Information Processing Systems, volume 33, pages 1123--12284, 2020.
[53] J. Tarbouriech,, M. Pirotta, M. Valko, and A. Lazaric. Sample complexity bounds for stochastic shortest path with a generative model. In Algorithmic Learning Theory, pages 1157-1178 PMLR, 2021.
[54] J. Tarbouriech, S. Shekhar, M. Pirotta, M. Ghavamzadeh, and A. Lazaric. Active model estimation in markov decision processes. In Conference on Uncertainty in Artificial Intelligence, pages 1019-1028. PMLR, 2020.
[55] F. Trevizan, S. Thiébaux, P. Santana, and B. Williams. Heuristic search in dual space for constrained stochastic shortest path problems. In Twenty-Sixth International Conference on Automated Planning and Scheduling, 2016.
[56] D. Vial, A. Parulekar, S. Shakkottai, and R. Srikant. Regret bounds for stochastic shortest path problems with linear function approximation. arXiv preprint arXiv:2105.011 0193, 2021.
[57] M. Wainwright. Course on mathematical statistics, chapter 2: Basic tail and concentration bounds. University of California at Berkeley, Department of Statistics, 2015.
[58] M. Wang. Primal-dual æ learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint arXiv: 11X.v:1700.06100, 2017.
[59] Y. Wang, K. Dong, X. Chen, and L. Wang. Q-learning with ueb exploration is sample efficient for hnfinite-horizon mdp. In International Conference on Learning Representations, 2019.
(60] C.-Y. Wei, M. Jahromi, H. Luo, H. Sharma, and R. Jain. Model-free reinforcement learning in infinite-horizon average-reward markov decision processes. In International Conference on Machine Learning, pages 10170-10180 PMLR, 2020.
[61] A. Zanette and E. Brunskill. Tighter without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
regret bounds in reinforcement learning
[62] A. Zanette, M. J. Kochenderfer, and E. Brunskill. Almost horizon-free structure-aware best policy identification with a generative model. In Advances in Neural Information Processing Systems, pages 5626-5635, 2019.
13

---

[63] X. Zhang, Y. Ma, and A. Singla. Task-agnostic exploration in reinforcement learning. In 34th Conference on Neural Information Processing Systems, pages 11734-11743, 2020.
[64] Z. Zhang, S. Du, and X. Ji. Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXin:2010.05901, 2020.
[65] Z. Zhang and X. Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. In Advances in Neural Information Processing Systems, pages 2823-2832, 2019.
[66] Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model-free reinforcement learning via reference- advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020.
14


Reviews:
[{"review_id": "fD9cI7c54LS", "reviewer": "Reviewer_dGom", "summary": "The paper proposes to decouple the exploration problem in RL into an objective-specific part with access to a sampling oracle, and an objective-agnostic exploration part. For the objective-agnostic part, the paper proposes the GOSPRL algorithm with bounds on its sample complexity to meet the sampling requirement. Then GOSPRL is then combined with some sampling oracle-based algorithms to provide sample complexity for three types of RL problems.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Exploration-exploitation in RL is a very challenging problem, and the paper proposes to tackle the problem by decoupling it into a objective-specific part and an objective-agnostic part. The approach is inspired by the algorithms with sampling oracles in the literature which assume to have access to sampling oracles providing samples for a given state-action pair. Such sampling oracle-based algorithms can be used for the objective-specific part, so the paper focuses on the remaining objective-agnostic exploration part.\n\nThe objective-agnostic exploration part can be viewed as an extension of the pure-exploration approach by introducing the sampling requirement function for each state-action pair. By utilizing techniques from stochastic shortest path problems, the paper proposes the GOSPRL algorithm to collect samples specified by the sampling requirement. Sample complexity bounds are provided by connecting the sample collection problem to a sequence of stochastic shortest path problems.\n\nFor certain problems when sampling oracle-based algorithms are available, combined with GOSPRL we can get some good sample complexity bounds for these exploration problems. The paper provides three examples: one is the sparse reward discovery problem where the sampling requirement is trivial, another one is model estimation without considering the reward, and the third one is on reward-free exploration which extends prior finite-horizon results. Simulations are provided to verify the theoretical analysis.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The settings where the proposed method works are clearly stated.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "XgRTUba7WQm", "reviewer": "Reviewer_2PPM", "summary": "The paper showcases a polynomial sample complexity for the problem of simulating a generative model through online interactions with a communicating MDP. The approach works as follows: It first prescribes the samples to be taken in each state-action pair for a specific objective, and it actively collects these samples by addressing a sequence of SSP problems. The paper includes a numerical validation in illustrative domains.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "This work provides a simple paradigm to translate any generative-model algorithm into a provable efficient online learning procedure, effectively bridging the gap between two fundamental settings of theoretical RL. \nThe paper is clean, the approach and the problem are well-motivated, and the related discussion is really thorough. It also includes the analysis of a bunch of relevant objectives that can be targeted with the proposed procedure. Especially, the goal-free and cost-free exploration setting (Sect. 4.3), which generalizes the reward-free exploration framework to infinite-horizon and goal-conditioned RL, might be of independent interest, and a nice direction for future works developing objective-specific approaches.\nOverall, I think that this work will provide a strong contribution to the theoretical RL field, and I recommend accepting it.\nSome additional comments and questions to the authors can be found below.\n\nSAMPLE COMPLEXITY AND THE LOWER BOUND\n\nThe paper reports a lower bound of $\\Omega(BD)$ samples for simulating the generative model, and the sample complexity of GOSPRL is upper bounded by $\\widetilde{O} (B D + D^{3/2} S^2 A)$. Whereas the authors note that with large sample requirements the term $\\widetilde{O} (B D)$ is dominating, I am wondering under which assumptions on b(s, a) the term $\\widetilde{O} (S^2 A)$ is unavoidable. Do the authors think that a careful construction might give a lower bound with an explicit dependence on $S^2 A$, which would tie the sampling problem to the one of estimating the transition model for every $(s,a)$ up to a certain confidence?\n\nMODEL-FREE APPROACHES\n\nThe GOSPRL algorithm is inherently model-based, as it relies on empirical transitions to instantiate each SSP problem $M_k$, and the analysis is also based on concentrating empirical transitions around the real model. I am wondering if the model-based feature is really a requirement of the nature of the problem or just how the analysis is carried out. Do the authors think that it is possible to address this setting with model-free approaches?\n\nRELATION WITH RF-RL-EXPLORE AND FUTURE DIRECTIONS\n\nFrom my understanding, the GOSPRL algorithm and RF-RL-EXPLORE [30] are built on similar ideas (in a significantly different context), as they both learn policies to seek for a specific state-action pair in the inner loop. The crucial difference is that RF-RL-EXPLORE solves finite-horizon problems (with EULER) as opposed to SSP problems in GOSPRL.\nSubsequent works in reward-free exploration [30, 31, 39, 64] have adopted alternative schema to improve sample complexity upper bounds. Do the authors think that similar routes could be followed for the sample collection problem?\nIn addition, a direct analysis of the sample complexity that GOSPRL would achieve in the (finite-horizon) reward-free exploration could draw an interesting connection between the two settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the limitations are well-discussed in the paper and the appendix, which provide details on how to relax the main assumption (communicating MDP) and how to improve the empirical performance of GOSPRL.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "CUbYWQECJX8", "reviewer": "Reviewer_WDCy", "summary": "This paper considers the problem of learning to sufficiently explore an MDP in order to effectively provide a generative model that can be used for downstream learning tasks by algorithms that require a generative model. An algorithm is given that leverages SSP results in order to force exploration of certain state-actions that may be required by the arbitrary down-stream algorithm. Sample complexity upper and lower bounds are proved to demonstrate the samples required to meet the budget prescribed by the downstream algorithm. Several example tasks that require non-trivial exploration are shown to make use of the algorithm.", "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": "Overall I think this is a nice paper that presents some interesting theoretical results via both upper and lower bounds on sample complexity. To the best of my knowledge, the algorithm seems new. The principle behind it is fairly straightforward in that it leverages SSP algorithms to do the heavy lifting but in a convenient way to properly explore to meet the budget. The example applications are definitely appreciated and it is promising to see that the algorithm yields competitive results theoretically in these settings. As a result, the work certainly seems thorough and there are some promising directions for future work, for example, by understanding how this extends in the function approximation setting. The related work seems to sufficiently distinguish this paper from others. The experiments are also fairly comprehensive and nicely complement the theory for the most part.\n\nDespite the interesting results, my main reservation regards the applicability of those results. There seems to be a bit of a mismatch between how the problem is motivated in the beginning and how the results are demonstrated in the main content. From the introduction, the impression is that the sampling oracle developed in this paper is to be used along with a generative model algorithm in two stages to solve a particular downstream RL problem that would otherwise require an online algorithm. But to this, my question is: why not just use an online algorithm which is already fairly flexible and skip the two stages? This is the case for the treasure problem. The model estimation task doesn’t really specify a downstream task, so this seems to be in some conflict with the initial motivation of the paper too. The cost-free goal-free task seems to be the most convincing of three since no signal can be used by an online algorithm (but they could still be used for reward-free exploration). In summary, I am not entirely convinced of the general applicability of the results or the potential impact of solving this particular problem. \n\nIn the experiments, for the treasure problem, I am a bit skeptical of setting the budget to 10 as this is not exactly what was advertised in the problem statement in the theory. The algorithm is also only slightly better than UCRL and only in one domain (which is not necessarily a bad thing), but this leaves the reader wondering what the performance on the actual problem would be, burn-in phase and all.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review for limitations and suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "AOAjNMhha0Z", "reviewer": "Reviewer_hnJg", "summary": "The authors introduce a general technique for exploring the MDP in an SSP problem. Their approach extends the notion of reward-free exploration to  an \"objective-agnostic\" scenario, in which the goal is to generate a prescribed amount of samples from any state and action. The authors analyze the proposed algorithm and provide a sample complexity bound.\n\nThen, the authors show this technique can be leveraged to solve specific scenarios which fit the communicating MDP setup. For these scenarios, the authors show the superiority of their approach with respect to previous works.", "questions": "", "limitations": "", "rating": 7, "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": "\n\nThis paper tackles the question of how to learn the transition model up to a prescribed accuracy (in terms of amount of samples). \nIn terms of originality, the proposed method combines two established ideas in the RL community, reward-free exploration (in finite horizon MDPs), and exploration in the SSP problem. Therefore, the path to the analysis is quite clear and incremental in nature. Still, the problem at hand is interesting and the solution is natural and clean, so this is not necessarily a flaw. Furthermore, the authors extend the notion of reward free exploration, generalizing it to a wider set of possible tasks.\nThus, overall this paper is significant - as it provides a simple provable methodology to solve many different tasks in the SSP regime.\n\nAn interesting question regarding this approach is whether it can be interestingly extended to a case where there are several (sequential/simultaneous) tasks at hand. Indeed, in the finite horizon setting, reward-free exploration is usually analyzed to allow for a \"zero-shot\" solution of the MDP for any (known) reward function. Yet, in the scenario discussed in this paper, where there are no-resets and the horizon is infinite, it is worthwhile to understand what happens when there is more than one task. Do the authors have any thoughts or comments regarding this question?\n\nExperiments: Can you add the experiment with the original treasure problem? I did not understand the comment about the \"burn-in\" phase, is there something fundamental here? Is it still problematic when the MDP gets bigger?\n\nClarity:\nI enjoyed reading this paper. It is well written, the main points are well-developed and coherent and the discussions are informative and discuss the related literature properly.\n\n\nSmall typo:\n- Lines 204,353 - \"Finally,\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was well-received by the reviewers who all agreed that the paper studies an interesting problem and offers a solid solution. There were only minor concerns raised by one reviewer, but these were adequately addressed in the author response. Eventually, the reviewers all agreed that the paper should be accepted for publication at the conference.
Decision: Accept (Spotlight)