A Provably Efficient Sample Collection Strategy for Reinforcement Learning
Year: 2021

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 Õ ( BD +DSA ) time steps to collect the B = ∑ 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.

text: ( BD +D3/2S2A ) time steps to collect the
B = ∑ 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.

heading: 1 Introduction
text: 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. Whenever the agent needs to gather information about a specific region of the Markov decision process (MDP), it must plan for a policy to reach the desired states, despite not having exact knowledge of the environment dynamics. This makes solving the exploration-exploitation problem in RL highly non-trivial and it requires designing a specific strategy depending on 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].
A 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 a next state s′ drawn from the transition probability p(·|s, a) and a reward r(s, a). In this case, it is possible to focus exclusively on where and how many samples to collect, while disregarding the problem of finding a suitable policy
35th Conference on Neural Information Processing Systems (NeurIPS 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 ε-optimal policy. SO-based algorithms can be as simple as prescribing the same amount of samples from each state-action pair [e.g. 35, 33, 5, 16, 46, 1, 38] or they may adaptively change the sample requirements on different stateaction pairs [e.g. 15, 58, 62]. An SO is also used in Monte-Carlo 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 exploration-exploitation problem in online RL by drawing inspiration from the SO assumption. Specifically, we define an approach that is decoupled in two parts: 1) an “objective-specific” 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.1 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 satisfy the prescribed sampling requirements. Leveraging recent techniques on exploration in the stochastic shortest path (SSP) problem [45, 50], we propose GOSPRL (Goalbased Optimistic Sampling Procedure for RL), a conceptually simple and flexible exploration algorithm that learns how to “generate” the samples requested by any SO-based algorithm and we derive bounds on its sample complexity. • Leveraging the generality of our approach, we combine GOSPRL with problem-specific SO-based algorithms and readily obtain online RL 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 or better than state-of-the-art algorithms in a range of problems. 1) GOSPRL solves the problem of sparse reward discovery in Õ ( D3/2S2A ) 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. a 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 baselines in various problems.
Related work. While to the best of our knowledge no other work directly addresses the problem of simulating an SO, a 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 exploration-exploitation algorithms, such as UCRL2 [28] in the undiscounted setting or RMAX [13] in the discounted one, implicitly encourage exploration to 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 a Frank-Wolfe approach that optimizes a smooth aggregate function of the state visitations.
Recent works on reward-free exploration (RFE) in the finite-horizon setting [e.g., 30, 31, 39, 64] provide sufficient exploration so that an ε-optimal policy for any reward function can be computed. Our proposed solution shares high-level algorithmic principles with RFE approaches which incentivize 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 performance 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-agnostic 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
1Alternatively, we can view it as a general approach to take any SO-based 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 GOSPRL can serve as a sample collection component to tackle various learning problems other than regret minimization.

heading: 2 Problem Definition
text: We consider a finite and reset-free MDP [43] M := 〈S,A, p, r, s0〉, with S := |S| states, A := |A| actions and an arbitrary starting state s0 ∈ S. Calling an SO in any state-action pair (s, a) leads to two outcomes: a next state sampled from the transition probability distribution p(·|s, a) ∈ ∆(S), and a reward r(s, a) ∈ R. A stationary deterministic policy is a mapping π : S → A from states to actions and we denote by ΠSD the set of all such policies. For any policy π and pair of states (s, s′), let τπ(s→ s′) be the (possibly infinite) hitting time from s to s′ when executing π, i.e., τπ(s→ s′) := inf{t ≥ 0 : st+1 = s′| s1 = s, π}, where st is the state visited at time step t. We introduce
Dss′ := min π∈ΠSD E[τπ(s→ s′)], Ds′ := max s∈S\{s′} Dss′ , D := max s′∈S Ds′ ,
where Dss′ is the shortest-path distance between s and s′, Ds′ 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 t ≥ 1 the agent receives a function bt : S ×A → N, where bt(s, a) defines the total number of samples that need to be collected at (s, a) by time step t. We consider that (bt)t≥1 is an arbitrary sequence with each bt measurable w.r.t. the filtration up to time t (i.e., it may depend on the samples observed so far).2 We focus on the objective of designing an online algorithm that minimizes the time required to 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 state-action pair, we denote by Nt(s, a) := ∑t i=1 1{(si,ai)=(s,a)} the number of visits to state s and action a up to (and including) time step t. Given a sampling requirement sequence b := (bt)t≥1 with bt : S ×A → N and a confidence level δ ∈ (0, 1), we define the sample complexity of a learning algorithm A as
C ( A, b, δ ) := min { t > 0 : P ( ∀(s, a) ∈ S ×A, Nt(s, a) ≥ bt(s, a) ) ≥ 1− δ } .
With no additional condition, it is trivial to define problems such that C(A, b, δ) = +∞ 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 < +∞. Assumption 2. There exist an unknown and bounded function b : S × A → N such that the sequence (bt)t≥1 verifies: ∀t ≥ 1, ∀(s, a) ∈ S ×A, bt(s, a) ≤ 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 it 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. 1 is well-posed and the sample complexity is bounded.
A variety of problems can be cast under our decoupled approach, in the sense that they can be tackled by solving the problem of Def. 1 under a specific instantiation of the sampling requirement sequence (bt)t≥1. 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 bt(s, a) = 1. In Sect. 4 and App. I, we review problems where defining bt can be as simple as computing the sufficient number of samples needed to reach a certain level of accuracy in estimating a quantity of interest (e.g., model estimation) or can be directly extracted from existing literature (e.g., ε-optimal policy learning).
We now provide a simple worst-case lower bound on the sample complexity (details in App. D). 2Allowing adaptive sampling requirements enables to pair GOSPRL with SO-based algorithms that adjust their requirements online as samples are being generated (see e.g., Sect. 4.2).
Algorithm 1 GOSPRL Algorithm Input: sampling requirement sequence (bt)t≥1 with bt : S ×A → N revealed at time t (or anytime before). Initialize: Set G1 := {s ∈ S : ∃a ∈ A, b1(s, a) > 0}, time step t := 1, counters N1(s, a) := 0, attempt index k := 1 and attempt counters U1(s, a) := 0, ν1(s, a) := 0. while Gk is not empty do
Define the SSP problem Mk with goal states Gk, and compute its optimistic shortest-path policy π̃k. Set flag = True and counter νk(s, a) := 0. while flag do
Execute action at := π̃k(st) and observe next state st+1 ∼ p(·|st, at). Increment counters νk(st, at) and Nt(st, at). if st+1 ∈ Gk or νk(st, at) > {Uk(st, at) ∨ 1} then
Set flag = False. end if Set t += 1.
end while if st ∈ Gk then
Execute an action a s.t.Nt(st, a) < bt(st, a), observe next state st+1 ∼ p(·|st, a) and set t += 1. end if Set Uk+1(s, a) := Uk(s, a) + νk(s, a), k += 1. Update the set of goal states Gk := { s ∈ S : ∃a ∈ A, Nt−1(s, a) < bt−1(s, a) } .
end while
Lemma 1. For any S ≥ 1, there exists an MDP with S states satisfying Asm. 1 such that for any sampling requirement b : S → N satisfying Asm. 2,
min A C ( A, b, 12 ) = Ω (∑ s∈S Dsb(s) ) .
Lem. 1 shows that the (possibly non-stationary) policy minimizing the time to collect all samples requires Ω (∑ sDsb(s) ) time steps in a worst-case MDP. We also notice that when the total sampling requirement B is concentrated on the state s for which Ds = D (i.e., b(s′) = 0, ∀s′ 6= s), the previous bound reduces to Ω(BD).

heading: 3 Online Learning for SO Simulation
text: We now introduce our algorithm for the problem in Def. 1, bound its sample complexity and discuss several extensions.

heading: 3.1 The GOSPRL Algorithm
text: In Alg. 1 we outline GOSPRL (Goal-based Optimistic Sampling Procedure for Reinforcement Learning). At each time step t, GOSPRL receives a sampling requirement bt : 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, 2, . . . and denote by tk the time step at the start of attempt k and by Uk := Ntk−1 the number of samples available at the start of attempt k. At each attempt, GOSPRL goes through the following steps: 1) Cast the under-sampled states as 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 or a stopping condition is satisfied; 4) If a sought-after goal state denoted by g has been reached, execute an under-sampled action (i.e., an action a such that Nt(g, a) < bt(g, a)). The algorithm ends when the sampling requirements are met, i.e., at the first time t ≥ 1 where Nt(s, a) ≥ bt(s, a) for all (s, a). Step 1. At any attempt k we begin by defining the set of all under-sampled states
Gk := { s ∈ S : ∃a ∈ A, Ntk−1(s, a) < btk−1(s, a) } .
We then cast the sample collection problem as a goal-reaching objective, by constructing a multi-goal SSP problem [9] denoted by Mk := 〈Sk,A, pk, ck,Gk〉, with:3
3If the current state stk is under-sampled (i.e., stk ∈ Gk), we duplicate the state and consider it to be both a goal state in Gk and a non-goal state from which the attempt k starts (and whose outgoing dynamics are the same as those of stk ), which ensures that the state at the start of each attempt cannot be a goal state.
• Gk denotes the set of goal states, Sk := 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.e., pk(s′|s, a) := p(s′|s, a) and pk(g|g, a) := 1 for any (s, s′, a, g) ∈ Sk × S ×A× Gk. • The cost function ck is defined as follows: for any a ∈ A, any goal state g ∈ Gk is zero-cost (ck(g, a) := 0), while the non-goal costs are unitary (ck(s, a) := 1 for s ∈ Sk).
From [10], Asm. 1 and the positive non-goal costs ck entail that solving Mk is a well-posed SSP problem and that there exists an optimal policy that is proper (i.e., that eventually reaches one of the goal states with probability 1 when starting from any s ∈ Sk). Crucially, the objective of collecting a sample from the under-sampled states Gk coincides with the SSP objective of minimizing the expected cumulative cost to reach a goal state in Mk.
Step 2. Since pk is unknown, we cannot directly compute the shortest-path policy for Mk. Instead, leveraging the samples collected so far, we apply an extended value iteration scheme for SSP which implicitly skews the empirical transitions p̂k 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 π̃k.
Step 3. π̃k is then executed with the aim of quickly reaching an under-sampled state. Along its trajectory, the counter Nt is updated for each visited state-action. Because of the error in estimating the model, π̃k may never reach one of the goal states (i.e., it may not be proper in pk). Thus π̃k is executed until either one of the goals in Gk is reached, or the number of visits is doubled in a state-action pair in Sk ×A, a standard termination condition first introduced in [28]. If a sought-after goal state is reached, the agent executes an under-sampled action according to the current sampling requirements at that state. At the end of each attempt, the statistics (e.g., model estimate) are updated.
The algorithmic design of GOSPRL is conceptually simple and can flexibly incorporate various modifications driven by slightly different objectives or prior knowledge, without altering Thm. 1 (cf. App. B).

heading: 3.2 Sample Complexity Guarantee of GOSPRL
text: Thm. 1 establishes the sample complexity guarantee of GOSPRL (Alg. 1). Theorem 1. Under Asm. 1 and 2, for any sampling requirement sequence b = (bt)t≥1 and any confidence level δ ∈ (0, 1), the sample complexity of GOSPRL is bounded as
C ( GOSPRL, b, δ ) = Õ ( BD +D3/2S2A ) , (1)
C ( GOSPRL, b, δ ) = Õ (∑ s∈S ( Dsb(s) +D 3/2 s S 2A )) , (2)
where the Õ notation hides logarithmic dependencies on S, A, D, 1/δ and b(s) := ∑ a∈A b(s, a)
and B := ∑ s∈S b(s). Recall that Ds ≤ D is the SSP-diameter of state s and captures the difficulty of collecting a sample at state s starting at any other state in the MDP.
We notice that in practice GOSPRL stops at the first random step τ at which the sampling requirement bτ (s, a) is achieved for all (s, a). Thm. 1 provides a worst-case upper bound on the stopping time of GOSPRL using the possibly loose bound bτ (s, a) ≤ b(s, a). On the other hand, in the special case of b : S → N when the requirements are both time-independent (i.e., given as initial input to the algorithm) and action-independent, the actual sampling requirement b(s) (resp.B := ∑ s∈S 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 GOSPRL to the regret accumulated over the sequence of multi-goal SSP problems Mk generated across multiple attempts. Indeed we can define the regret at attempt k as the gap between the performance of the SSP-optimal policy π?k solving Mk (i.e., the minimum expected number of steps to reach any of the states in Gk starting from stk ) 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 it leads to the bound Õ ( BD+D3/2S2A ) where B := ∑ s∈S b(s). On the other hand, the refined bound in Eq. 2 requires a more careful analysis, where we no longer directly
translate regret bounds into sample complexity and we rather focus on relating the performance to state-dependent quantities Ds 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. 1 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 a cost of Ds to collect a sample at state s, which better captures the connectivity of the MDP. In fact the lower bound in Lem. 1 shows that this cost of Ds is unavoidable in the worst case, and that GOSPRL is only constant and logarithmic terms off w.r.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 Ds,4 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., problem-dependent) bounds in SSP and how they could be leveraged in our case.
Optimal solution. GOSPRL targets a greedy-optimal strategy, which seeks to sequentially minimize each time to reach an under-sampled state. Alternatively, one may wonder if it is possible to design a learning algorithm that approaches the performance of the exact-optimal solution, i.e., a (nonstationary) policy explicitly minimizing the number of steps required to fulfill the sampling requirements.5 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 GOSPRL where the (possibly large or infinite) diameter D is fittingly replaced by L.

heading: 4 Applications of GOSPRL
text: 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.

heading: 4.1 Sparse Reward Discovery (TREASURE)
text: A number of recent methods focus on 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 a 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., a measure of closeness to the treasure). Thus the agent must perform exhaustive exploration to find the treasure.
Definition 2. Given a confidence δ ∈ (0, 1), the TREASURE sample complexity of a learning algorithm A is defined as CTREASURE(A, δ) := min { t > 0 : P ( ∀(s, a) ∈ S ×A, Nt(s, a) ≥ 1 ) ≥ 1− δ } .
4For instance, consider a simple deterministic chain with a requirement of one sample per state. If the agent starts on the leftmost state, then a policy that keeps moving right has sample complexity S without extra factorD.
5Notice 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, a 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(s, a) = 1 for each (s, a) and from Thm. 1 with B = SA we obtain the following guarantee.
Lemma 2. GOSPRL with b(s, a) = 1 verifies CTREASURE(GOSPRL, δ) = Õ ( D3/2S2A ) .
We now compare this result to 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/1-UCRL, which runs UCRL by setting a reward of 1 to under-sampled states and 0 otherwise. However, we obtain a TREASURE sample complexity for 0/1-UCRL of Õ (∑ s∈S D 3 sS 2A ) , which is always worse than the bound in Lem. 2.
• Second, we can adapt the MAXENT approach [26] to state-action coverage so that it targets a policy whose stationary state-action distribution λ maximizes H(λ) := −∑s,a λ(s, a) log λ(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 (λ) := min(s,a)∈S×A λ(s, a). We show that the learning algorithm of [17] instantiated to maximize F yields a TREASURE sample complexity of at least Ω ( min { D2S2A/(ω?)2, D3/(ω?)3 }) with ω? := minλ F (λ) ≤ (SA)−1,
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-stationary strategy that gradually collects the required samples by tackling successive learning problems.

heading: 4.2 Model Estimation (MODEST)
text: We now study the problem of accurately estimating the unknown transition dynamics in a 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 a confidence level δ ∈ (0, 1), the MODEST sample complexity of an online learning algorithm A is defined as
CMODEST(A, η, δ) := min { t > 0 : P ( ∀(s, a) ∈ S ×A, ‖p̂A,t(·|s, a)− p(·|s, a)‖1 ≤ η ) ≥ 1− δ } ,
where p̂A,t is the estimate (i.e., empirical average) of the transition dynamics p after t time steps.
Unlike in TREASURE, here the sampling requirements are not immediately prescribed by the problem. To define the SO-based algorithm we first upper-bound the estimation error using an empirical Bernstein inequality and then invert it to derive the amount of samples bt(s, a) needed to achieve the desired level of accuracy η (see App. F). Specifically, letting σ̂2t (s
′|s, a) := p̂t(s′|s, a)(1− p̂t(s′|s, a)) be the estimated variance of the transition from (s, a) to s′ after t steps, we set
bt(s, a) := ⌈57(∑s′ σ̂t(s′|s, a))2
η2 log2
( 8e( ∑ s′ σ̂t(s ′|s, a))2 √ 2SA√
δη
) + 24S
η log
( 24S2A
δη
)⌉ . (3)
Since the estimated variance changes depending on the samples observed so far, the sampling requirements are adapted over time. Given that σ̂2t (s
′|s, a) ≤ 1/4, bt(s, a) is always bounded so Thm. 1 provides the following guarantee.
Lemma 3. Let Γ := maxs,a‖p(·|s, a)‖0 ≤ S be the maximal support of p(·|s, a) over the stateaction pairs (s, a). Running GOSPRL with the sampling requirements in Eq. 3 yields
CMODEST(GOSPRL, η, δ) = Õ (DΓSA
η2 + DS2A η +D3/2S2A
) .
Lem. 3 improves over the result of [54] in two important aspects. First, the latter suffers from an inverse dependency on the stationary state-action distribution that optimizes a 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.

heading: 4.3 Goal-Free & Cost-Free Exploration in Communicating MDPs
text: 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 is provided. The problem has been analyzed in the finite-horizon setting [e.g., 30, 39, 64]. Here we study the more general and challenging setting of goal-conditioned 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 goal-conditioned policy for any goal state and any cost function (w.l.o.g. we consider a maximum possible cost cmax = 1). Recall that given a goal state g and costs c, the (possibly unbounded) value function of a policy π is
V π(s→ g) := E [ τπ(s→g)∑
t=1
c(st, π(st)) ∣∣ s1 = s].
Given a slack parameter θ ∈ [1,+∞], we say that a policy π̂ is (ε, θ)-optimal if 7
V π̂(s→ g) ≤ min π:E[τπ(s→g)]≤θDs,g V π(s→ g) + ε.
In this setting, constructing an efficient SO-based algorithm is considerably more complex than TREASURE and MODEST. Relying on a sample complexity analysis for the fixed-goal SSP problem with a 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. 1 and the goal-free cost-free exploration problem with accuracy level 0 < ε ≤ 1, confidence level δ ∈ (0, 1), minimum cost cmin ∈ [0, 1], slack parameter θ ∈ [1,+∞]. We can instantiate GOSPRL so that its exploration phase (i.e., number of time steps) is bounded with probability at least 1− δ by
Õ
( D4ΓSA
ωε2 + D3S2A ωε + D3ΓSA ω2
) ,
where ω := max { cmin, ε/(θD) } > 0 (thus, either cmin = 0 or θ = +∞, but not both simultaneously). Following the exploration phase, the algorithm can compute in the planning phase, for any goal state g ∈ S and any cost function c in [cmin, 1], a policy π̂g,c that is (ε, θ)-optimal.
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 to 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 to 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 on 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 finite-horizon, the value of cmin has an important impact on the type of performance guarantees we can obtain; in particular our analysis distinguishes between positive and non-negative costs (as also done in existing SSP analysis [11, 50, 45]).

heading: 5 Experiments
text: In this section we report a preliminary numerical validation of our theoretical findings. While GOSPRL can be integrated in many different contexts, here we focus on the problems where our theory suggests that GOSPRL performs better than state-of-the-art online learning methods.
6While an approach was proposed in [52], it is restricted to considering only the incrementally attainable goal states from a resettable reference state s0.
7This reduces to standard ε-optimality for θ = +∞. We only consider θ < +∞ in the case of minimum possible cost cmin = 0 and it ensures that the algorithm targets proper policies (see App. H).
Garnet 1 Garnet 2 Garnet 3 Garnet 4 Garnet 5
4
6
8
·103
S a m p le
co m p le x it y
5 random instances of G(10, 5, 5)
Garnet 1 Garnet 2 Garnet 3 Garnet 4 Garnet 5
2
2.2
2.4 ·104 S a m p le co m p le x it y
5 random instances of G(50, 5, 5)
Figure 2: Sample complexity boxplots of GOSPRL (in red) and 0/1-UCRL (in blue). Each column represents 30 runs on a randomly generated Garnet G(S,A = 5, β = 5) with randomly generated state-action sampling requirements b : S ×A → U(0, 100). Left: S = 10, Right: S = 50.
0 1 2 3 4 5
·104
0
1
2
3 ·10−1
time t
` 1 -e rr o r E t
NoisyRiverSwim(36)
Uniform Weighted MaxEnt GOSPRL
0 1 2 3 4 5
·104
0
2
4
6
8
·10−2
time t
` 1 -e rr o r E t
Wheel(30)
Uniform Weighted MaxEnt GOSPRL
0 1 2 3 4 5
·104
0
0.5
1
1.5 ·10−1
time t
` 1 -e rr o r E t
Garnet(50,5,25)
Uniform Weighted MaxEnt GOSPRL
Figure 3: MODEST problem: `1-error Et := (SA)−1 · ∑ s,a‖p̂t(·|s, a) − p(·|s, a)‖1, averaged over 30 runs. Left: NoisyRiverSwim(36), Center: Wheel(30), Right: Randomly generated Garnet G(50, 5, 25).
s0 s1 s2 a0
ν
1− ν
a0
a0ν1− ν
a1
101 102 103 102
103
104
Diameter D (≈ 1/ν)
S am
p le
co m p .( G O S P R L )
Figure 4: Simple three-state reward-free domain [23] and TREASURE-10 sample complexity of GOSPRL (averaged over 30 runs) as a function of the diameter D ≈ 1/ν.
TREASURE-type problem. We consider a TREASURE-type problem (Sect. 4.1), where for all (s, a) we set b(s, a) = 10 instead of 1 (we call it the TREASURE-10 problem).8 We begin by showing in Fig. 4 that it is easy to construct a worst-case problem where the sample complexity scales linearly with the diameter, which is consistent with the theoretical discussion in Sect. 2 and 3.
We compare to two heuristics based on UCRL2B [28, 22]: 0-UCRL, where the reward used in computing the optimistic policy is set proportional to ([N(s, a) − b(s, a)]+)−1/2, and 0/1-UCRL with reward 1 for undersampled state-action pairs and 0 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. K for details and more results). Fig. 1 reports the proportion Pt of states that satisfy the sampling requirements at time t. Our metric of interest is the time needed to collect all required samples, and we see that GOSPRL reaches the Pt = 1 line of success consistently, and faster than 0/1-UCRL, while the other heuristics struggle. The steady increase of Pt illustrates GOSPRL’s design to progressively meet the sampling requirements, and not exhaust them state after state.
8Since GOSPRL and our baselines are all based on upper confidence bounds, they tend to display similar behaviors in the initial phases of learning, since the estimates when N(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 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 a variety of randomly generated configurations, that we define as follows: each configuration corresponds to i) a randomly generated Garnet environment G(S,A, β) (with S states, A actions and branching factor β, see [12]), and ii) randomly generated requirements b(s, a) ∈ U(0, U), where the maximum budget is set to U = 100 to have a 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-UCRL, 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 WEIGHTEDMAXENT 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 (NoisyRiverSwim 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 GOSPRL-forMODEST algorithm where the sampling requirements are computed using a decreasing error η (see App. K for details). We observe in Fig. 3 that GOSPRL outperforms the WEIGHTEDMAXENT heuristic.

heading: 6 Conclusion
text: In this paper, we introduced the online learning problem of simulating a sampling oracle (Sect. 2) and derived the algorithm GOSPRL with its sample complexity guarantee (Sect. 3). We then illustrated how it can be used to tackle in a unifying fashion a variety of applications without having to design a 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-the-shelf 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 a specific state (e.g., via adequate discretization 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 bt 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 goal-conditioned network (using e.g., [2]), while the specification of bt can be related to goal-sampling selection mechanisms that elect hard-to-reach [21] or rare [42] states as goals.

Review summaries:
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.

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.

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.  Then, 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.

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.