When is Agnostic Reinforcement Learning Statistically Tractable?
Authors: Zeyu Jia
Gene Li
Alexander Rakhlin
Ayush Sekhari
Nathan Srebro
Venue: NeurIPS 2023 poster (2023)
Keywords: Agnostic Reinforcement Learning
Sample Complexity
Learning Theory
Complexity Measure

Abstract: We study the problem of agnostic PAC reinforcement learning (RL): given a policy class $\Pi$, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required to learn an $\epsilon$-suboptimal policy with respect to \(\Pi\)? Towards that end, we introduce a new complexity measure, called the \emph{spanning capacity}, that depends solely on the set \(\Pi\) and is independent of the MDP dynamics. With a generative model, we show that the spanning capacity characterizes PAC learnability for every policy class $\Pi$. However, for online RL, the situation is more subtle. We show there exists a policy class $\Pi$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for agnostic learnability between generative access and online access models (as well as between deterministic/stochastic MDPs under online access). On the positive side, we identify an additional \emph{sunflower} structure which in conjunction with bounded spanning capacity enables statistically efficient online RL via a new algorithm called POPLER, which takes inspiration from classical importance sampling methods as well as recent developments for reachable-state identification and policy evaluation in reward-free exploration.

When is Agnostic Reinforcement Learning Statistically Tractable?*
Zeyu Jia
Gene Li²
Alexander Rakhlin'
Ayush Sekhari'
Nathan Srebro
MIT, 2TTIC
Abstract
We study the problem of agnostic PAC reinforcement learning (RL): given policy class II, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required learn an e-suboptimal policy with respect to II? Towards that end, we introduce a new complexity measure, called the spanning capacity, that depends solely on the II and is independent of the MDP dynamics. With a generative model, we show that for any policy class II, bounded spanning capacity characterizes PAC learnability. However, for online RL, the situation is more subtle. We show there exists policy class II with bounded spanning capacity that requires superpolynomial number of samples to learn. This reveals surprising separation for agnostic learnability between generative access and online access models (as well as between deterministic/stocaatii MDPs under online access). On the positive side, we identify an additional sunflower structure, which in conjunction with bounded spanning capacity enables statistically efficient online RL via new algorithm called POPLER, which takes inspiration from classical importance sampling methods as well as techniques for reachable-stan identification and policy evaluation in reward-fres exploration.
Introduction
Reinforcement Learning (RL) has emerged as a powerful paradigm for solving complex decision- making problems, demonstrating impressive empirical successes in a wide array of challenging tasks, from achieving superhuman performance the game Go (Silver et al., 2017) to solving intricate robotic manipulation tasks (Lillicrap et al., 2016; Akkaya et al., 2019; Ji et al., 2023). Many practical domains in RL often involve rich observations such as images, text, or audio (Mnih et al., 2015;
Li et al., 2016; Ouyang et al., 2022). Since these state spaces be vast and complex, traditional tabular RL approaches (Kearns and Singh, 2002: Brafiman and Tennenholtz, 2002; Azar et al., 2017; Jin et al., 2018) cannot scale. This has led to need develop provable and efficient approaches for RI that utilize function approximation to generalize observational data to unknown states/actions.
The goal of this paper is to study the sample complexity of policy-based RI,, which is arguably the simplest setting for RL with function approximation (Kearns et al., 1999; Kakade, 2003). In policy-based RL, an abstract function class 11 of policies (mappings from states to actions) is given to the learner. For example, II can be the set of all the policies represented by a certain deep neural network architecture. The objective of the learner is interact with unknown MDP to find policy that competes with the best policy in II, i.e., for some prespecified e, the policy â satisfies
V > max V E,
(1)
FEll
where V denotes the value of policy the underlying MDP. We henceforth call Eq. (1) the "agnostic PAC reinforcement learning" objective. Our paper addresses the following question:
Authors are listed in alphabetical order of their last names.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

What structural assumptions on II enable statistically efficient agnostic PAC reinforcement learning?
Characterizing (agnostic) learnability for various problem settings is perhaps the most fundamental question in statistical learning theory. For the simpler setting of supervised learning (which is RL with binary actions, horizon 1, and binary rewards), the story is complete: a hypothesis class II is agnostically learnable if and only if its VC dimension is bounded (Vapnik and Chervonenkis, 1971, 1974; Blumer et al., 1989; Ehrenfeucht et al., 1989), and the ERM algorithn-which returns the hypothesis with the smallest training loss-is statistically optimal (up log factors). However, RL (with H > 1) is significantly more challenging, and we are still far from a rigorous understanding of when agnostic RL statistically tractable, or what algorithms to use in large-scale RL problems.
While significant effort has been invested over the past decade in both theory and practice to develop algorithms that utilize function approximation, existing theoretical guarantees require additional assumptions on the MDP. The most commonly adopted assumption is realizability: the learner can precisely model the value function the dynamics of the underlying MDP (see, e.g.. Russo and Van Roy, 2013; Jiang et al., 2017; Sun et al., 2019; Wang et al., 2020c; Du et al., 2021; Jin et al., 2021a; Foster al., 2021a). a)). Unfortunately, realizability is fragile assumption that rarely holds in practice. Moreover, even mild misspecification can cause catastrophic breakdown of theoretical guarantees (Du al., 2019b; Lattimore al., 2020). Furthermore, in various applications, the optimal policy x-' := arg e V may have succinct representation, but the optimal value function V can be highly complex, rendering accurate approximation of dynamics/value functions infeasible without substantial domain knowledge (Dong et al., 2020). Thus, we desire algorithms for agnostic RL that can work with no modeling assumptions on the underlying MDP. On the other hand, it also well known without any assumptions on II, when II is large and the MDP has a large state and action space, agnostic RL may be intractable with sample complexity scaling exponentially in the horizon (Agarwal et al., 2019). Thus, some structural assumptions on II are needed, and towards that end, the goal of our paper is to understand what assumptions are sufficient or necessary for statistically efficient agnostic RI., and to develop provable algorithms for learning. Our main contributions are:
We introduce new complexity measure called the spanning capacity, which solely depends on the policy class II and is independent of the underlying MDP. We illustrate the spanning capacity with examples, and show why it is natural complexity measure for agnostic PAC RL (Section 3).
We show that the spanning capacity is both necessary and sufficient for agnostic PAC RL with a generative model, with upper and lower bounds matching up to log [I] and poly(H) factors (Section 4). Thus, bounded spanning capacity characterizes agnostic PAC learnability in RL with a generative model.
Moving to the online setting, we first show that the bounded spanning capacity by itself insufficient for agnostic PAC RL by proving superpolynomial lower bound on the sample complexity required to learn a specific II, thus demonstrating a separation between generative and online interaction models for agnostic PAC RL (Section 5).
Given the previous lower bound, propose additional property of the policy class called the sunflower property, that allows for efficient exploration and is satisfied by many policy classes of interest. We provide whenever the given policy class has both bounded spanning capacity and the sunflower property (Section 6). POPLER leverages importance sampling as well reachable state identification techniques to estimate the values of policies. Our algorithm and analysis utilize a new tool called the policy-specific Markov reward process, which may be of independent interest.
agnostic PAC RL algorithm called POPLER that is statistically efficient
2 Setup and Motivation
We begin by introducing our setup for reinforcement learning (RL), the relevant notation, and the goal of agnostic RL.
2.1
RL Preliminaries
We consider reinforcement learning in an episodic Markov decision process (MDP) with horizon H.

---

Markov Decision Processes. Denote the MDP as M = MDP which consists of a state space S, action space A, horizon H, probability transition kernel P S A + ASS). reward function R: S x A + A((0, 1)), and initial distribution μ E A(S). For ease of exposition, we assume that and are finite (but possibly large) with cardinality and respectively. We assume a layered state space, i.e., S S U S2 U .... U SH where S; n Sj = 0 for all i * j. Thus, given a state E S, it can be inferred which layer St in the MDP it belongs to. We denote a trajectory action as E A is played, a reward
(51, (,1,, fi,,,,,,,,....... Pl...... HH, dg, TH), where at each step h E [H] rh is drawn independently from the distribution (8,,, an ). and each subsequent state 8h+1 is drawn from P(-Is,, 0n). Lastly, assume that the cumulative reward of any trajectory is bounded by 1.
Policy-based Reinforcement Learning. We assume that the learner is given a policy class II C A 2 For any policy π E A we denote (s)) as the action that takes when presented a state s. We use [ and [p][|] to denote the expectation and probability under the process of a trajectory drawn from the MDP M by policy Additionally, for any h, h' I H, say that partial trajectory T
(Sn, ag, Sp+1 :: Oh+11..- Spr, axr) is consistent with π if for all h S i S h', we have T(s;) = az. We use the notation ~ denote that is consistent with π.
The state-value function (also called V V-fucttio) and state-action-value function (also called Q- function) are defined such that for any n, and s,
(s) = E Σ ((sw,ak) Sh = ). QR(,,a)=E
R(sw (ww; = s,an Liv=
Σ
Furthermore, whenever clear from the context, we denote V = V/ Finally, for any policy E -AS, we also define the occupancy measure (s, Pd [*[ss, 8, an a| and di == pd [sh s].
Models of Interaction. We consider two standard models of interaction in the RL literature:
Generative Model. The learner has access to simulator which it can query for any (s, a), and observe sample (s',r) drawn as s' ~ P(- a) and r R(s, a).²
Online Interaction Model. The learner can submit a (potentially Markoviaan) policy म and receive back trajectory sampled by running स on the MDP. Since online access can be simulated via generative access, learning under online access is only more challenging than learning under generative access (up to factor of H). Adhering to commonly used terminology, we will refer to RL under the online interaction model as "online RL".
We define Mato as the set of all (stochastic and deterministic) MDPs of horizon If over the state space S and action space A. Additionally, we define M C Msto and M Mddee to denote the set of all MDPs with deterministic transitions but stochastic rewards, and of all MDPs with both deterministic transitions and deterministic rewards, respectively.
2.2 Agnostic PAC RL
Our goal is to understand the sample complexity of agnostic PAC RL, i.e., the number of interactions required to find a policy that can compete with the best policy within the given class II for the underlying MDP. An algorithm A is an (e, PAAC RL algorithm for an MDP M, if after interacting with M (either in the generative model or online RL), returns policy क that satisfies the guarantee*
max V - E, KET
Throughout the paper, we assume that the policy classes II under consideration consist of deterministic policies. Extending our work to stochastic policy classes is an interesting direction for future research.
"Within the generative model, one can further distinguish between more restrictive "local" access model (also called the "reset" model), where the leamer can query (s, a) for any 8 E S that it has seen already, or "global" access, where the learner can query for any (s, a) without restriction. For the generative model, our upper bounds hold in the local access model, while our lower bounds hold for the global access model.
*Our results are agnostic in the sense that we do not make the assumption that the optimal policy for the underlying MDP is in 11. but instead, only wish to complete with the best policy in 11. We also do not assume that the learner has value function class or model class that captures the optimal value functions or dynamics.
3

---

with probability at least 1 - 5. For a policy class II and a MDP class M. we say that A has sample complexity non M; (resp. (II, E, if for every MDP M M, A is an (e, PAC RL algorithm and collects at most non MM; o) trajectories in the online interaction model (resp. generative model) in order return n.
We define the minimux sample complexity for agnostically learning over M as the minimum sample complexity of any (c, (e,8)-PAC RL algorithm, i.e.
To (1,,6, min n Mi,,0)) and ?gge (II, (1,, == min geen M;,,
For brevity, when M = M we will drop the dependence on M in our notation, e.g.. we will write Ron E1 and Rggen eII; to denote non MI; and rggen (ge, =; 8) respectively.
Known Results in Agnostic RL. We first note the following classical result which shows that agnostic PAC RL is statistically intractable in the worst case.
Proposition (No Free Lunch Theorem for RL; Krishnamurthy et al. (2016)). There exists a policy class 11 for which the minimax sample complexity under generative model is at least "gen (11; e, 8) = [[minn[A". | S=))
Since online RL is only harder than learning with generative model, the lower bound in Proposition I extends to online RL. Proposition is the analogue of the classical No Free Lunch results statistical learning theory Schale--Shware and Ben-Davin 2014); it indicates that without placing further assumptions on the MDP or the policy class II (e.g.. by introducing additional structure or constraining the state/action space sizes, policy class size, or the horizon), sample efficient agnostic PAC RL is not possible.
Indeed, an almost matching upper bound of on (II; 5) 6) Óminn(A" |II|, HSAA/=")))) is quite easy to obtain. The [=] guarantee can simply be obtained by iterating over и E II. collecting (1/=²) trajectories per policy, and then picking the policy with highest empirical value. The HSA/E² guarantee can be obtained by running known algorithms for tabular RL. (Zhang et al., 2021b). Finally, the A /c² guarantee is achieved by the classical importance sampling (IS) algorithm (Kearns et al., 1 1999; Agarwal et al., 2019). Since importance sampling will be an important technique that we repeatedly use and build upon in this paper, we give a formal description of the algorithm below:
ImportanceSampling:
Collect n = ((4 H log II| / trajectories by executing (ai,..., aH) ~ Uniform (A
Return ãे arg max Vis where is = 4 Σ - 1f
(E (0)
For every и II, the quantity Tis is an unbiased estimate of Va with variance A the sample complexity result follows by standard concentration guarantees (see, e.g., Agarwal et al., 2019).
Towards Structural Assumptions for Statistically Efficient Agnostic PAC RL. Of course, No Free Lunch results do not necessarily spell doom-for example, in supervised learning, various structural assumptions have been studied that enable statistically efficient learning. Furthermore, there has been substantial effort in developing complexity measures like VC dimension, fat-shattering dimension, covering numbers, etc. that characterize agnostic PAC learnability under different scenar- ios (Shalev-Shwart and Ben-David, 2014). In this paper, we consider the agnostic reinforcement learning setting, and explore whether there exists a complexity measure that characterizes learnability for every policy class II. Formally, can establish complexity measure C (a function that maps policy classes to real numbers), such that for any II, the minimax sample complexity satisfies
Ron (II; 8) = (poly (C(I), H, s-,,,..,,,. log ",,g,_ 1)))))))))
where ((T) denotes the complexity of IT. We mainly focus on finite (but large) policy classes and assume that the log [I] factors in our upper bounds are mild. In Appendix G, discuss how results can be extended to infinite policy classes.
Is Proposition 1 Tight for Every II? In light of Proposition 1, obvious candidate is C(II) A [1I, SA}. While E(II) is definitely sufficient to upper bound the minimax

---

sample complexity for any policy class II up to log factors, a priori it is not clear if it is also necessary for every policy class II. In fact, our next proposition implies that ((I)) is indeed not the right measure of complexity by giving an example of policy class for which C(II) := min A [II], SA} exponentially larger than the minimax sample complexity for agnostic learning for that policy class, even when is constant.
Sh. = (s(L)) : [K]] for all h E [H], and A = {0, 1). Consider the singleton policy class: Naing == (U( :' E [K], h' E {HH),. where T(P'ke) takes the action 1 on state N(), and O everywhere else. Then minfA", [I iigg SA} = 2 but Ton (olainngg E, 8) & Õ(H3 log(1/6)/=²).
Proposition 2. Let H E.
The above upper bound on minimax sample complexity holds arbitrarily large values of K, and can be obtained as a corollary of our more general upper bound in Section 6. The key intuition for why Usinn can be learned in poly (f) samples is that even though the policy class and the state space are large when K is large, the set of possible trajectories obtained by running any т E Isiing has low complexity. In particular, every trajectory has at most one a₁ = 1. This observation enables to employ the straightfowward modification of the classical IS algorithm: draw poly(H) log((16))/ samples from the uniform distribution over Ioroe { h E [H] where the policy лy takes the action I on every state at layer and everywhere else. The variance of the resulting estimator Vis is 1/H H, so the sample complexity of this modified variant of IS has only poly(H) dependence by standard concentration bounds.
In the sequel, present a new complexity measure that formalizes this intuition that policy class ll is efficiently learnable if the set of trajectories induced by policies II is small.
3 Spanning Capacity
The spanning capacity precisely captures the intuition that trajectories obtained by rumning any π E II have "low complexity." We first define a notion of reachability: in deterministic MDP M E M we say (s, is reachable by π II if (s, a) lies the trajectory obtained by running on M. Roughly speaking, the spanning capacity measures "complexity" of II as the maximum number of state-action pairs which are reachable by some π E II in any deterministic MDP
Definition 1 (spanning capacity).
Fix deterministic MDP M E Eddot, We define the cumulative reachability at layer h E [H) denoted by Creach (II: M). as
Ch (1I; M) := [((s a) : (s, a) is reachable by 11 at layer hi)l.
We define the spanning capacity of II as
C(I) := max RE(H) MEM
Czeach (11; M).
To build intuition, we first look at some simple examples with small spanning capacity:
Consider the standard formulation of contextual bandits (i.e., RL with H = 1). For any policy class 1eb.. since H 1, the largest deterministic MDP we can construct has a single state $1 and at most A actions available on $1, so ((leb)) S A.
Contextual Bandits:
Tabular MDPs: Consider tabular RL with the policy class Il.b A consisting of all determin- istic policies on the underlying state space. Depending on the relationship between S, A and H, we have two possible bounds ((T..t.) S. min{ A ,S).. If the state space is exponentially large in H. then it is possible to construct a full A-ary "tree" such that every (s, a) pair at layer H is visited, giving us the A bound. However, if the state space is small, then the number of (s, a) pairs available at any layer H is trivially bounded by SA.
Bounded Cardinality Policy Classes: For any policy class II, we always have that C(II) S [II. since in any deterministic MDP, in any layer E [H]. cach π E II can visit at most one new (s, a) pair. Thus, for policy classes [IImmatl| with small cardinality (c.g. [Igmaatl| O(poly (H, A)). the
spanning capacity is also small; Note that in this case, we allow our sample complexity bounds to depend on |
Singletons: For the singleton class we have ((Tsigg)= = H + 1, since once we fix deterministic MDP, there are at most H states where we can split from the trajectory taken by the policy which
5

---

always plays a 0, so the maximum number of (s, a) pairs reachable at layer h E [H] is h + 1. Observe that in light of Proposition 2, the spanning capacity for Hsinn is "on the right order" for characterizing the minimax sample complexity for agnostic PAC RI..
Before proceeding, we note that for any policy class IT, the spanning capacity is always bounded. Proposition 3. For any policy class II, we have C(TT) I m (
Proposition 3 recovers the worst-case upper and lower bound from Section 2.2. However, for many policy classes, spanning capacity is substantially smaller than upper bound of Proposition 3. In addi- tion to the examples we provided above, we list several additional policy classes with small spanning capacity. For these policy classes we set the state/action spaces to be S {S(L.N) : [K]] for all h E [H] and A = {0, }. respectively. All proofs are deferred to Appendix B.
f-tons: A natural generalization of singletons. We define to == T S G. where the policy πy is defined s.t. (s) { E 1} for any E S. Here, C(Lle-ton) = O 1-Active Policies: We define [[j-act to be the class of policies which can take both possible actions single state $1,,) in each layer h, but other states (s,h) for i # must take action O. Formally, 11 = (T b E {0, 1] " where for any E {0, 1] the policy mb is defined such that (s))) = b[h] if s ((1,)). and (s) = 0 otherwise.
All-Active Policies: We define _ = { b E {0, 1) where for any E 1) the policy T6 is defined such that (s))) = b[h] if s S(AA), and TT(s) = otherwise. We let
nact
م j= M act. Here, C(Imact) 2)
K
A natural interpretation of the spanning capacity is that it represents the largest "needle in a haystack" that can be embedded
deterministic MDP using the policy class IT. To see this, let (M+, h²)
((I)) be the set of state-action pairs be the MDP and layer which witnesses C(II), and let [(s;, a.)) { reachable by since every trajectory visits a single (st, a;) at layer h², we need at least C(IT) samples in order to discover which state-action pair has the hidden reward. Note that in this agnostic learning setup, we only need to care about the states that are reachable using II, even though the h" layer may have other non-recchable states and actions.
M* at layer li* Then one can hide reward of on one of these state-action pairs;
3.1 Connection Coverability
The spanning capacity has another interpretation as the worst-case coverability, a structural parameter defined in a recent work by Xie et al. (2022).
Definition 2 (Coverability, Xie et al. (2022)). For any MDP M and policy class II, the coverability coefficient C is denoted
dh
COV M1): =
inf PL sell)
sup
max
Σ sup (s. TEn
(2)
RE(H]
The last equality is shown in Lemma 3 of Xie et al. (2022), and it says that the coverability coefficient equivalent to a notion of cumulative reachability (one can check that their definition coincides with ours for deterministic MDPs).
Coverage conditions date back the analysis of the classic Fitted Q-Iteration (FQI) algorithm (Munos, 2007; Munos and Szepesvári. 2008), and have extensively been studied in offline RL. Various models like tabular MDPs, linear MDPs, low-rank MDPs, and exogenous MDPs satisfy the above coverage condition (Antos et al., 2008; Chen and Jiang, 2019; Jin et al., 2021 b; Rashidinejad et al., 2021; Zhan al., 2022; Xie et al., 2022), and recently, Xie et al. showed that coverability can be used to prove regret guarantees for online RL, albeit under the additional assumption of value function realizability.
It is straightforward from Definition 2 that our notion of spanning capacity is worst-case coverability when we maximize over deterministic MDPs, since for any deterministic MDP, supxen di (8, a) 1 {(s, a) is reachable by IT layer h). The next lemma shows that notion of spanning capacity is exactly worst-case coverability even when we maximize over the larger class of stochastic MDPs. As consequence, there always exists a deterministic MDP that witnesses worst-case coverability.
Lemma 1. For any policy class 11, we have sup M cov (II; MI) C(II.

---

While spanning capacity is equal to the worst-case coverability, we remark that the two definitions have different origins. The notion of coverability bridges offline and online RL, and was introduced in Xie et al. (2022) to characterize when sample efficient learning is possible in value-based RI., where the learner has access to realizable value function class. On the other hand, spanning capacity is developed for the much weaker agnostic RI setting, where the learner only has access to a policy class (and does not have access to a realizable value function class). Note that a realizable value function class can be used to construct a policy class that contains the optimal policy, but the converse not true. Furthermore, note that the above equivalence only holds in a worst-case sense (over MDPs). In fact, as we show in Appendix C, coverability alone is not sufficient for sample efficient agnostic PAC RL in the online interaction model.
Generative Model: Spanning Capacity is Necessary and Sufficient
In this section, we show that for any policy class, the spanning capacity characterizes the minimax sample complexity for agnostic PAC RL under generative model.
Theorem 1 (Upper Bound for Generative Model). For any 11. the minimax sample complexity (s, 6PC learning 11 is at most rggen (II; E, 6) S O H-C(I)) log [II
8
The proof be found in Appendix D. and is a straightforward modification of the classic trajectory tree method from Kearns et al. (1999): using generative access, sample (logg [ /s²) trajectory trees from the MDP get unbiased evaluations for every II; the number of generative queries made is bounded since the size of the maximum deterministic tree is at most H C(II).
deterministic
Theorem 2 (Lower Bound for Generative Model). For any II. the minimax sample complexity (s, - learning Il is at least r'gen (II; e, 6) 2 Ω ((I)) 2 log
e,I;,,
The proof can be found in Appendix D.2. Intuitively, given an MDP M which witnesses C(IT), one can embed bandit instance the relevant (s, a) pairs spanned by II in M* The lower bound follows by a reduction to the lower bound for (c, OePA) learning in multi-armed bandits.
Together. Theorem I and Theorem 2 paint relatively complete picture for the minimax sample complexity of learning any policy class II, in the generative model, up to an H log/Il| factor.
Deterministic MDPs. A similar guarantee holds for online RL over deterministic MDPs.
Corollary 1. Over the class of MDPs with deterministic transitions, the minimax sample complexity of (e, 8)C learning any II is
2 c(I)) log 1 S non (II, MdelP, ;e,8) S 50( (H.C
log
11I
The upper bound follows because the trajectory tree algorithm for deterministic transitions samples the same tree over and over again (with different stochastic rewards). The lower bound trivially
extends because the lower bound of Theorem actually uses an MDP M Meet (in fact, the transitions of M are also known to the learner).
5 Online RL: Spanning Capacity is Not Sufficient
Given that fact that spanning capacity characterizes the minimax sample complexity of agnostic PAC RL in the generative model, one might be tempted to conjecture that spanning capacity is also the right characterization online RL. The lower bound is clear since online RL is at least as hard as learning with generative model, so Theorem 2 already shows that spanning capacity is necessary. But is it also sufficient?
In this section, we prove a surprising negative result showing that bounded spanning capacity by itself is not sufficient characterize the minimax sample complexity in online RL. In particular, we provide an example for which we have a superpolynomial (in H!) lower bound on the number of trajectories needed for learning in online RL, that is not captured by any polynomial function of spanning capacity. This implies that, contrary to RL with generative model, one can not hope for Ton [1l; ()) 6) @(poly(C(1I), e log 8 d-)) in online RL.
7

---

Theorem 3 (Lower Bound for Online RL). Fix any sufficiently large H. Let E (1/20(m, O(LHH)) and & E 1 H such that 1/EL < 2" There exists a policy class 11(() of size ((1/E)) with E(II0) I ( and a family of MDPs M with state space S of size 20(1), binary action space, and horizon H such that: for any (e.1/8)-PAC algorithm, there exists an MDP M E &M for which the algorithm must collect at least [1 f / online trajectories in expectation.
Informally speaking, the lower bound shows that there exists a policy class IT for which non (TT; 2. = 1 L/ e(TT), In order to interpret this theorem, we can instantiate choices of = = -1/2Vl and (= VH to show an explicit separation.
Corollary 2. For any sufficiently large H, there exists a policy class IT with C(T)- = 20( H log H) such that for any (1/2vH, 1/88-PAC algorithm, there exists MDP for which the algorithm must collect at least ( online trajectories in expectation.
In conjunction with the results of Section 4, Theorem 3 shows that (1) online RL is strictly harder than RI. with generative access, and (2) online RI. for stochastic MDPs is strictly harder than online RL. for MDPs with deterministic transitions. We defer the proof of Theorem 3 to Appendix H. Our lower bound introduces several technical novelties: the family M utilizes a contextual variant of the combination lock, and the policy class II is constructed via careful probabilistic argument such that it is hard to explore despite having small spanning capacity.
6 Statistically Efficient Agnostic Learning in Online RL
The lower bound in Theorem 3 suggests that further structural assumptions on II are needed for statistically efficient agnostic RL under the online interaction model. Essentially, the lower bound example provided in Theorem 3 is hard to agnostically learn because any two distinct policies T, n' E II can differ substantially on a large subset of states (of size least e -222).. Thus, we cannot hope to learn "in parallel" via low variance IS strategy that utilizes extrapolation to evaluate all policies x E II, as we did for singletons.
In the sequel, we consider the following sunflower property to rule out such problematic scenarios, and show how bounded spanning capacity along with the sunflower property enable cample-efficieee agnostic RL in the online interaction model. The sunflower property only depends on the state space, action space, and policy class, and is independent of the transition dynamics and rewards of the underlying MDP. We first define a petal, a key ingredient of a sunflower.
Definition 3 (Petal), For a policy set II, and states C S, policy π is said to be a S-petal on πi if for all h S h' & H, and partial trajectories 7 (8h; "...... 882, ag) that are consistent with m: either 7 is also consistent with some n' E TI, or there exists i E (h, h/) s.I. 8; E S.
Informally, v is a S-petal on IT if any trajectory that can be obtained using n can either also be obtained using policy in TI or must pass through S. Thus, any policy that is a S-petal on IT can only differentiate from Il in a structured way. A policy class is said to be a sunflower if it is a union of petals as defined below:
Definition& 4 (Sunflower). A policy class 11 is said to be a (K, D)-sunflowwrr if there exists set Ilcore of Markovian policies with [oooel S K such that for every policy π E 11 there exists a set S₂ C S, of size at most D, that is an -petal on Ioore.
Our next theorem provides a sample complexity bound for Agnostic PAC RL for policy classes that have (K, D)-sunflower structure. This bound is obtained via a new exploration algorithm called POPLER that takes as input the set Iecoe and corresponding petals {Sx)rer and leverages importance sampling as well as reachable state identification techniques to simultancously estimate the value of every policy in II.
Theorem 4. Let E, > O. Suppose the policy class II satisfies Definition 1 with spanning capacity (II), and is a (K, -usuuflooe.r Then, for any MDP M, with probability least 8, POPLER (Algorithm 1) succeeds in returning policy स that satisfies y max V s, after collecting
o(( (DD K2 log
[TI 0
online trajectories in M.
8

---

The proof of Theorem 4, and the corresponding hyperparameters in POPLER needed to obtain the above bound, can be found in Appendix F. Before diving into the algorithm and proof details, let us highlight several key aspects of the above sample complexity bound:
Note that class IT may be a (K, D) -ssuftoower for many different choices of K and D. Barring computational issues, one can enumerate over all choices of Toooe and (S₂ = and check if II is a (K, --suufloowrr for that choice of K corel and D max=en|S,). Since our bound in Theorem 4 scales with K and D, we are free to choose K and D to minimize the corresponding sample complexity bound.
In order to get a polynomial sample complexity in Theorem 4, both ((IT) and (K, D) are required to be poly H,, log MT). All of the policy classes considered in Section 3 have the sunflower property, with both K, D = poly (Hf), and thus our sample complexity bound extends for all these classes. See Appendix B for details.
Notice that for Theorem to hold, we need both bounded spanning capacity as well as the sunflower structure the policy class with bounded (K,D). Thus, one may wonder if we can obtain a similar polynomial sample complexity guarantee in online RL under weaker assumptions. In Theorem 3, we already showed that bounded C(11) alone is not sufficient to obtain polynomial sample complexity in online RL. Likewise, as we show in Appendix F, sunflower property with bounded (K, D) alone is also not sufficient for polynomial sample complexity, and hence both assumptions cannot be individually removed. However, it is an interesting question if there is some other structural assumption that combines both spanning capacity and the sunflower property, and is both sufficient and necessary for agnostic PAC learning in online RL. See Section 7 for further discussions on this.
Why Does the Sunflower Property Enable Sample-Efficient Learning? Intuitively, the sunflower property captures the intuition of simultaneous estimation of all policies т E II via importance sampling (IS), and allows control of both bias and variance. Let π be a Seeet on He Any trajectory т ~ that avoids S must be consistent with some policy in Meore. and will thus be covered by the data collected using n' Uniform c.oore) Thus, using IS with variance scaling with K, one can create biased estimator for V*, where the bias is only due to trajectories that pass through S,. There are two cases. If every state in S has small reachability under т, i.c. dm (s) << for every E Sx, then the IS estimate will have a low bias (linear in (S,(), so we can compute V up to error at most e ) On the other hand, cd (s) is large for some s E Sn, it is possible to explicitly control the bias that arises from trajectories passing through them since there are at most D of them.
6.1 Algorithm and Proof Ideas
POPLER (Algorithm 1) takes input a policy class II, as well as sets Teore and (Sx) which can be computed beforehand by enumeration. POPLER has two phases: a state identification phase, where it finds "petal" states E Uren S that are reachable with sufficiently large probability; and an evaluation phase where it computes estimates V for every π E II. It uses three subroutines DataCollector, EstReachability, and Evaluate, whose pscudocodes are stated in Appendix F.2.
The structure of the algorithm is reminiscent of reward-free exploration algorithms in tabular RL, e.g. Jin et al. (2020), where we first identify (petal) states that are reachable with probability least MeeDD) and build a policy cover for these states, and then use dynamic programming to estimate the values. However, contrary to the classical tabular RL setting, because the state space can be large, our setting is much more challenging and necessitates technical innovations. In particular, we can no longer enumerate over all petal states and check if they are sufficiently reachable by some policy T E IT (since the total number of petal states S could scale linearly in [T a factor that we do not want to appear our sample complexity). Instead, the key observation that we rely on is that if spanning capacity is bounded, then by the equivalence of spanning capacity and worst-case coverability (Lemma 1) and due to (2), the number of highly reachable (and thus relevant) petal states is also bounded. Thus, we only need to build policy cover to reach these relevant petal states. Our algorithm does this in a sample-efficient sequential manner. For both state identification as well as evaluation, we interleave importance sampling estimates with the construction of a policy-specific Markov Reward Processes (MRPs), which are defined for every अ E II. The challenge is doing all of this "in parallel" for every E II through extensive sample reuse to avoid blowup of [T] or S in the sample complexity. For the exact construction of these policy-specific MRPs and how they are used in the algorithm, please see Appendix F22

---

Algorithm Policy OPtimization by Learning & E-Reachable States (POPLER)
Require: Policy class 11, Sets Heore and {(S] J
Parameters K, D, 11 f22 ò. 1: Define an additional start state ST (at h = 0) and end state $1 (at h H + 1).
2: Initialize Sech = {sT}. + ((ST.Null)
and for every π E II, define S := S (ST.
3: DT t- DataaColector(sst Null, Ieroe. 711
4: Identification of Petal States that are Reachable with Q(e/D) Probability */
5: while Terminate = False do
6: Set Terminate True.
7: for 11 do
8:
Compute the set of already explored reachable states Si S n and the remaining states S = Sx \ (Srch {si]).
9:
Estimate the policy-specific MRP g... according to (14) and (15). for E Spem do
11:
Estimate probability of reaching EstReachability(S27 g.ah.) 8).
8
under
π
as
12:
dd) ($) 2 f/6D then
Update Srch + Srch (3), TU and set Terminate Falsc.
14: end if
Collect dataset Dj +- DataCollector(3, T, I Ieore; 112).
15:
16: end for
17: end for
18: end while
19: /* Policy Evaluation and Optimization +/
20: for E do
21: 1" +- EvaluateeTTooree Stch, (Da) R).
22: end for
23: Return E arg max, 7.
7 Conclusion and Discussion
In this paper, we investigated when agnostic RI. is statistically tractable in large state and action spaces, and introduced spanning capacity as a natural measure of complexity that only depends on the policy class, and is independent of the MDP rewards and transitions. We first showed that bounded spanning capacity both necessary and sufficient for agnostic PAC RL under the generative access model. However,
also provided negative result showing that bounded spanning capacity does not suffice for online RL, thus showing a surprising separation between agnostic RL with a generative model and online interaction. We then provided an additional structural assumption, called the sunflower property, that allows for statistically efficient learning in online RL. Our sample complexity bound for online RL is obtained using novel exploration algorithm called POPLER that relies on certain policy-specific Markov Reward Processes to guide exploration, and takes inspiration from the classical importance sampling method and reward-free exploration algorithms for tabular MDPs.
Our results pave the way for several future lines of inquiry. The most important direction exploring complexity measures to tightly characterize the minimax sample complexity for online RL. On the upper bound side, Theorem 4 shows that bounded spanning capacity along with an additional sunflower property is sufficient for online RL. On the lower bound side, while bounded spanning capacity is necessary (by Theorem 2), we do not know if the sunflower property is also necessary. Another direction is understanding if one improve the statistical complexity of policy- based learning using stronger feedback models; in Appendix we explore whether receiving expert feedback in the form of the optimal value function {Q' aae the visited states can help. Surprisingly, the answer depends on realizability of the optimal policy x² E II: when π E II, Q' feedback can be utilized to achieve an (ppoly (log] 111 H, 1/a)) sample complexity bound, with no dependence on C(II; if n- & II, then one can not hope to learn with less than (II( samples in the worst case. Understanding the role of π m--realizability and exploring the benefits of other feedback models in agnostic RL are interesting future research directions. Other research directions include sharpening the sample complexity bound in Theorem 4, extending POPLER for regret minimization, and developing computationally efficient algorithms.
10

---

Acknowledgments and Disclosure of Funding
We thank Dylan Foster, Pritish Kamath, Jason Lee, Wen Sun, and Cong Ma for helpful discussions. GL and NS are partially supported by the NSF and the Simons Foundation. Part of this work was completed while GL was visiting Princeton University. AR acknowledges support from the ONR through award 900014-20-1-2336 ARO through award W911NF-21-1-0328 and from the DOE through award DE-SC0022199.
References
Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692-3702. PMLR, 2019.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. PC-PG: Policy cover directed explo- ration for provable policy gradient learning. Advances in Neural Information Processing Systems, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-455 2021.
Naman Agarwal, Brian Bullins, and Karan Singh. Variance-reduced conservative policy iteration. In International Conference Algorithmic Learning Theory, pages 3-33. PMLR, 2023.
Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's 's cube with robot hand. arXiv preprint 11110:1910.07113. 2019.
Aymen Al-Marjani, Andrea Tirinzoni, and Emilie Kaufmann. Active coverage for pac reinforcement learning, arXiv preprint arXiv:2306. 13601, 2023.
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private pac learning implies finite littlestone dimension. In Proceedings of the 51 Annual ACM SIGACT Symposium Theory of Computing, pages 852-860, 2019.
Philip Amortila, Nan Jiang, Dhruv Madeka, and Dean P Foster. A few expert queries suffices for sample-efficient rl with resets and linear value approximation. arXiv preprint arXiv:2207.00 08342, 2022.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
James Bagnell, Sham M Kakade, Jeff Schneider, and Andrew Ng. Policy search by dynamic programming. Advances neural information processing systems, 16, 2003.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods, arXiv preprint XX06:/906.01 2019.
Anselm Blumer, Andrzej Fhrenfeucht, David Haussler, and Manfred Warmuth. Learnability and the vapmik-chervonenkis dimension. Journal of the ACM (JACM), 36(4))929-96 1989.
11

---

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Léon Bottou, Jonas Peters, Joaquin Quifonero-Candela. Denis X. Charles, D. Max Chickering, Elon Portugaly, Dipankar Ray. Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 2013.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, (10ct))213-231, 2002.
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability, In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943-955. IEEE, 2022a.
Nataly Brukhim, Elad Hazan, and Karan Singh. A boosting approach to reinforcement learning. Advances in Neural Information Processing Systems, 15:33806-33817, 2022b.
Jinglin Chen and Nan Jiang. Information-theeorticc considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019.
algorithms. MIT press, 2022.
Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference Learning Theory, pages 287-316. PMLR, 2014.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient PAC RL with rich observations. In Advances Neural Information Processing Systems, 2018.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
Kefan Dong. Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International conference on machine learning, pages 2627-2637. PMLR, 2020.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dud'ik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, 2019a.
Simon Du Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836 PMLR, 2021.
Simon Du, Sham M Kakade, Ruosong Wang, and Lin Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv: 19/003//0 2019b.
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Provably filtering exogenous distractors using multistep inverse dynamics. In International Conference on Learning Representations, 2021.
Yonathan Efroni, Dylan J Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford. Sample-efficient reinforcement learning the presence of exogenous information. In Conference on Learning Theory, pages 2027-5127. PMLR, 2022.
Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-261, 1989,
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2 13487, 2021a.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Conference on Learning Theory, 2021b.
12

---

Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. restance-dependee complexity of contextual bandits and reinforcement learning: A disagreement- bbssdd perspective. Conference on Learning Theory, 2021c.
Dylan J Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the seccision-sstimaan coefficient. arXiv preprint arXiv:2301.08215, 2023.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of
regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91: 325-349, 2013.
Noah Golowich and Ankur Moitra. Can q-learning be improved with advice? In Conference on Learning Theory, pages 4548-465 4619. PMLR, 2022.
Omer Gottesman, Yao Liu, Scott Sussex, Emma Brunskill, and Finale Doshi-Velez. Combining parametric and nonparametric models for off-policy evaluation. In International Conference on Machine Learning, pages 2366-2377 2375. PMLR, 2019.
Abhishek Gupta, Aldo Pacchiano, Yuexiang Zhai, Sham Kakade, and Sergey Levine. Unpacking reward shaping: Understanding the benefits of reward engineering sample complexity. Advances in Neural Information Processing Systems, 35:11281-15295 2022.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1): 3487-3602, 2015.
David Haussler and Philip M Long. A generalization of sauer's lemma. Journal of Combinatorial Theory, Series A, (122)2119-240, 1995.
Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforcement learning in low-rank mdps with density features. arXiv preprint arXiv:2302.02252. 2023.
Yandong Ji, Gabriel B Margolis, and Pulkit Agrawal. Dribblebot: Dynamic legged manipulation in the wild. arXiv preprint arXiv:23304.0 0/ 159, 2023.
Nan Jiang and Lihong Li. Doubly robust off oollcy value evaluation for reinforcement learning. In International Conference Machine Learning, pages 652-661. PMLR, 2016.
Nan Jiang. Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4879. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406 11344661141888 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, 2021b.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267-274, 2002.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
13

---

Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time.
Machine learning, 49:209-253 232, 2002.
Michael Kearns, Yishay Mansour, and Andrew Ng. Approximate planning in large pomdps via reusable trajectories. Advances in Neural Information Processing Systems, 12, 1999.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning. pages 5662-56700 5670. PMLR, 2020.
Sergey Levine and Vladien Koltun. Guided policy search. In International conference on machine learning, pages 1 1-9. PMLR, 2013.
Gen Li, Yuling Yan, Yuxin Chen, and Jianqing Fan. Minimax-optimal reward aggossic exploration in reinforcement learning. arXiv preprint arXiv:2304.07278 2023.
Gene Li, Pritish Kamath, Dylan Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems. 15-23737-23755 2022.
Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. Deep reinforce- ment learning for dialogue generation. arXiv preprint 1606v:1606../554/ 2016.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference Learning Representations, 2016.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reducel) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 13:7724-76366 2020.
Devroye Luc, Györfi László, and Lugosi Gábor. A probabilistic theory of pattern recognition, volume 31 of applications of mathematics, 1996.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-am aalti-armed bandit problem. Journal of Machine Learning Research, 5(Jun):633 648, 2004.
Pierre Ménard, Omar Darwiche Domingues. Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, pages 7509-7608. PMLR, 2021.
Zakaria Mhammedi, Dylan J Foster, and Alexander Rakhlin. Representation learning with multi-step inverse kinematics: An efficient and optimal approach to rich-observation rl. arXiv preprint arXiv:2304.05888, 2023.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Wenlong Mou, Zheng Wen, and Xi Chen. On the sample complexity of reinforcement learning with policy space generalization. arXiv preprint arXiv:2008.0735: 2020.
Rémi Munos. Performance bounds Lp-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-561, 2007. 2007.
14

---

Rémi Munos and Csaba Szepesvári. Finite- time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 2019.
Balas K Natarajan. On learning sets and functions. Machine Learning. 4:67-97, 1989.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744 2022.
David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning, 2022.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 2021.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint vrXiv:1406.5979 2014.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems, 26, 2013.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. (rXiv:/707.06347) 2017.
Ayush Sekhari, Christoph Dann, Mchryar Mohri, Yishay Mansour, and Karthik Sridharan. Agnostic reinforcement learning with low-rank MDPs and rich observations. Advances in Neural Information Processing Systems, 2021.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou. Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of without human knowledge. narure, 550(7676):354 359, 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning, pages 1139-2148. PMLR, 2016.
15

---

Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learning: the restance-dependent view. In International Conference on Algorithmic Learning Theory, pages 1460-1480. PMLR, 2023.
Faraz Torabi, Garreu Warnell, and Peter Stone. Behavioral cloning from observation. arXiv preprint arXiv: /805.00944 2018.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv:2110.04652, 2021.
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974.
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971.
Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35:5968-508 -9881, 2022.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free rl is harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning, pages 22430-22456. PMLR, 2022.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances neural information processing systems, 18:17816-178222 2020a.
Ruosong Wang. Dean P. Foster, and Sham M. Kakade. What the statistical limits of offline RL with linear function approximation?, 2020b.
Ruosong Wang. Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2133-635,541 2020c.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with ineeaaly-realizable optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36, 2022.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforce- ment learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint arX1w:2210.04157, 2022.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9948-3958. PMLR, 2020.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. In International Conference on Machine Learning, pages 12287-12297. PMLR, 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 1756-1 166,, 2020.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: generalized framework with linear convergence. arXiv preprint 2155v:2005.11066 2021.
16

---

Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference Learning Theory, pages 2730-2775. PMLR, 2022.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 34: 1582-1593, 2021a.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528-4533 4. PMLR, 2021b.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. CoRR, 2022.
17

---

Contents of Appendix
Detailed Comparison to Related Works
20
Examples of Policy Classes
22
C
Proofs for Section 3
24
C.I Proof of Lemma
24
C,2 Coverability Not Sufficient for Online RL
26
Proofs for Section
26
D.1 Proof of Theorem
26
D.2 Proof of Theorem 2
27
D.3 Proof of Corollary
................................
27
E Proofs for Section 5
28
E.1 Construction State Space, Action Space, and Policy Class
................................
28
E,2 Construction MDP Family
28
E.3 Proof of Theorem 5
30
E,4 Proof of Lemma
E.5 Proof of Lemma 3
E,6 Change of Measure Lemma
37
Proofs for Section
39
F.1
Algorithm Sketch
39
F2
Algorithmic Details and Preliminaries
40
F3 Supporting Technical Results
43
F4
Proof of Theorem 4
49
F.5
Sunflower Property Insufficient By Itself
49
G
Infinite Policy Classes
51
G.1
Definitions and Preliminary Lemmas
51
G.2
Generative Model Lower Bound
G.3 Generative Model Upper Bound
52
G.4 Online RL Upper Bound
53
H Connections to Other Complexity Measures
54
H.1 Definitions and Relationships
H.2 Bounds on Spanning Capacity
55
H.2.1 Proof of Theorem
56
Extension: Can Expert Feedback Help in Agnostic PAC RL.
57
L.1 Upper Bound under Realizability
57
18

---

I.2 Lower Bound in Agnostic Setting
58
J Technical Tools
60
19

---

A Detailed Comparison to Related Works
Reinforcement Learning (RL) has seen substantial progress over the past few years, with several different directions of work being pursued for efficiently solving RL problems that occur in practice. The classical approach to solving an RL problem is to model it as a tabular MDP. A long line of work (Sutton and Barto, 2018; Agarwal al., 2019; Kearns and Singh, 2002: Brafman and Tennenholtz, 2002; Auer et al., 2008; Azar et al., 2017; Gheshlaghi Azar et al., 2013; Jin et al., 2018) has studied provably sample-efficient learning algorithms that can find the optimal policy in tabular RL. Unfortunately, the sample complexity of such algorithms unavoidably scales with the size of the state/action spaces, so they fail to be efficient in practical RL problems with large state/action spaces, In order to develop algorithms for the more practical large state/action RL settings, various assumptions have been considered in the prior works. the following, we provide a detailed comparison of our setup and assumptions with the existing literature.
RL with Function Approximation. A popular paradigm for developing algorithms for MDPs with large state/action spaces is use function approximation to either model the MDP dynamies or optimal value functions. Over the last decade, there has been a long line of work (Jiang et al., 2017; Dann et al., 2018; Sun et al., 2019; Du et al., 2019a; Wang et al., 2020c; Du al., 2021; Foster et al., 2021a; Jin et al., 2021a; Zhong et al., 2022: Foster et al., 2023) in understanding structural conditions on the function class and the underlying MDP that enable statistically efficient RL. However, all of these works rely crucially on the realizability assumption, namely that the true model / value function belong to the chosen class. Unfortunately, such an assumption is too strong to hold in practice. Furthermore, the prior works using function approximation make additional assumptions like Bellman Completeness that are difficult to verify for the underlying task.
In our work, we study the problem of agnostic RL to sidestep these challenges. In particular, instead of modeling the value/dynamics, the learner now models "good policies" for the underlying task, and the learning objective is to find a policy that can perform as well as the best in the chosen policy class. We note that while realizable value class/dynamics class F can be converted into a realizable policy class II by choosing the greedy policies for each value function/dynamics, the converse is not true. Thus, our agnostic RI. objective relies on a strictly weaker modeling assumption.
Connections to -attimtttttttttion Coefficient (DEC). The seminal work of Foster et al. (2021a) provides unified complexity measure called terizes the complexity of model-based RL. Given the generality of the E2D algorithm of Foster et al. (2021a), one may be wondering if our results can be recovered using their framework via model-based approach. In particular, can we recover the sample complexity bound in Theorems I or 4 by considering the model class deet or Ms along with the decision set 11. To the best of our knowledge, the framework of Foster et al. (2021a) do not directly recover our results, however, the complexity measures are closely related. Note that one can upper-bound the DEC by the coverability coefficient Xie et al. (2022); furthermore we show that (II) is worst-case coverability (Lemma 1) so it follows that DEC is upper- bounded by C(II). However, the algorithm in Foster et al. (2021a) achieves regret bounds which scale with DEC log] Moto, which can be vacuous in the large state- space setting since losoo x [S|; In contrast, our upper bounds have no explicit dependence on (S).
Coefficient (DEC) that charac-
RL with Rich Observations. Various settings have been studied where the dynamics are determined by simple latent state space, but instead of observing the latent states directly, the learner receives rich observations corresponding to the underlying latent states. These include the Block MDP (Krishnamurthy al., 2016; Du al., 2019;; Misra et al., 2020; Mhammedi et al., 2023). Low- Rank MDPs (Uchara et al., 2021; Huang et al., 2023), Exogenous MDPs (Efroni et al., 2021; Xie al., 2022: Efroni al., 2022), etc. However, all of these prior works assume that the learner is given a realizable decoder class (consisting of functions that map observations to latent states) that contains the true decoder for the underlying MDP. Additionally, they require strong assumptions on the underlying latent state space dynamics, e.g. it is tabular or low-rank, in order to make learning tractable. Thus, their guarantees are not agnostic. In fact, given a realizable decoder class and additional structure on the latent state dynamics, one can construct a policy class that contains the optimal policy for the MDP, but the converse is not true. Thus, our agnostic RL setting strictly more general.
20

---

Relation to Exponential Lower Bounds for RL with Function Approximation. Recently, many statistical lower bounds have been developed in RL with function approximation under only real- izability. A line of work including (Wang et al., 2020b; Zanette, 2021; Weisz et al., 2021; Foster et al., 2021b) showed that the sample complexity scales exponentially in the horizon H for learning the optimal policy for RL problems where only the optimal value function Q' is linear w.r.t. the given features. Similarly, Du et al. (2019b) showed that one may need exponentially in H even if the optimal policy is linear w.r.t. the true features. These lower bounds can be extended to our agnostic RL setting, giving similar exponential in lower bounds for agnostic RL, thus supplementing the well-known lower bounds (Krishnamurthy et al., 2016) which show that agnostic RL is intractable without additional structural assumptions on the policy class. However, to recall, the focus of this paper is to propose assumptions, like Definition or 4, that circumvent these lower bounds and allow for sample efficient agnostic RI..
Importance Sampling for RI., Various importance sampling based estimators (Xie et al., 2019; Jiang and Li, 2016; Gottesman et al., 2019; Yin and Wang. 2020; Thomas and Brunskill, 2016; Nachum et al., 2019) have been developed in RL literature to provide reliable off-policy evaluation in offline RL. However, these methods also require realizable value function approximation and rely on additional assumptions on the off- policy/offline data, in particular, that the offline data covers the state/action space that is explored by the comparator policy. We note that this line of work does not directly overlap with our current approach but provides valuable tool for dealing with off-policy data.
Agnostic RL in Low-Rank MDPs. Sekhari et al. (2021) explored agnostic PAC RL in low-rank MDPs, and showed that one can perform agnostic learning w.r.t any policy class for MDPs that have small rank. While their guarantees are similar to ours, i... they compete with the best policy in the given class and do not assume access to a realizable dynamics/ value-function class, the key objectives of the two works are complementary. Sekhari et al. (2021) explore assumptions on the underlying MDP dynamics which suffice for agnostic learning for any given policy class, whereas ask what assumptions on the given policy class suffice for agnostic learning for any underlying dynamics. Exploring the benefits of structure in both the policy class and the underlying MDP in agnostic RL is an interesting direction for future research.
Policy Gradient Methods. A significant body of work in RL, in both theory (Agarwal et al., 2021; Abbasi- Yadkori et al., 2019; Bhandari and Russo, 2019; Liu et al., 2020; Agarwal et al., 2020; Zhan et al., 2021; Xiao, 2022) and practice (Kakade, 2001; Kakade and Langford, 2002; Levine and Koltun, 2013; Schulman et al., 2015, 2017), studies policy-gradient based methods that directly search for the best policy in a given policy class. These approaches often leverage mirror-descent style analysis, and can deliver guarantees that are similar to ours, i.e. the returned policy can compete with any policy in the given class, which is an agnostic guarantee in some sense. However, these works primarily study smooth and parametric policy classes, e.g. tabular and linear policy classes, which limits their applicability for a broader range of problem instances. Furthermore, they require strong additional assumptions to work: for instance, that the learner is given good reset distribution that can cover the occupancy measure of the policy that we wish to compare to, and that the policy class satisfies a certain "policy completeness assumption": both of which are difficult to verify in practice. In contrast, our work makes no such assumptions but instead studies what kind of policy classes are learnable for any MDP.
CPI, PSDP, and Other Reductions to Supervised Learning. Various RL methods have been developed that return a policy that performs as well as the best policy in the given policy class, by reducing the RL problem from supervised learning. The key difference from policy-gradient based methods (discussed previously) is that these approaches do not require a smoothly parameterized policy class, but instead rely on access to a supervised learning oracle w.r.t. the given policy class. Popular approaches include Conservative Policy Iteration (CPI) (Kakade and Langford, 2002; Kakade, 2003; Brukhim et al., 2022b; Agarwal et al., 2023), PSDP (Bagnell et al., 2003), Behavior Cloning (Ross and Bagnell, 2010; Torabi et al., 2018), etc. We note that these algorithms rely on additional assumptions, including "policy completeness assumption and a good sampling / reset distribution that covers the policies that we wish to compare to; comparison, we do not make any such assumptions in our work.
21

---

Efficient RL via reductions to online regression oracles w.r.t. the given policy class has also been studied, see, e.g., DAgger (Ross al., 2011), Aggre VaTe (Ross and Bagnell, 2014), etc. However, these algorithms rely on much stronger feedback. In particular the learner, on the states which it visits, can query an expert policy (that we wish to complete with) for its actions or the value function. On the other hand, in this paper, we restrict vesselves to the standard RL setting where the learner only gets instantancous reward signal. In Appendix we investigate whether such stronger feedback can be used for agnostic RL.
Reward-Free RL. From a technical viewpoint, our algorithm (Algorithm 1) share similaries to algorithms developed in the reward-free RL literature (Jin et al., 2020). In reward-free RL, the goal of the learner is to output a dataset or a set of policies, after interacting with the underlying MDP, that can be later used for planning (with no further interaction with the MDP) for downstream reward functions. The key ideas in our Algorithm I, particular, that the learner first finds states I that are (()) reeecbbee and corresponding policies that can reach them, and then outputs datasets {Da that can be later used for evaluating any policy π E II, share similarities to algorithmic ideas used in reward-free RL. However, our algorithm strictly generalizes prior works in reward-free RL, and in particular can work with large state-action spaces where the notion of reachability as well as the offline RL objective, is defined w.r.t. the given policy class. In comparison, prior reward-free RL works compete with the best policy for the underlying MDP, and make structure assumptions on the dynamics, e.g. tabular structure (Jin et al., 2020; Ménard et al., 2021; Li et al., 2023) or linear dynamics ( (Wang et al., 2020a; Zanette et al., 2020; Zhang et al., 2021a; Wagenmaker et al., 2022), to make the problem tractable.
Instance Optimal Measures. Several recent works including Wagenmaker and Jamieson (2022); Tirinzoni et al. (2023); Bottou et al. (2013); Al-Marjani et al. (2023) have explored instance-dependenn complexity measures for PAC RL. At a high level, these pestance-depender bounds are obtained via similar algorithmiic ideas to ours that combine reward-free exploration with policy climination. However, there are major differences. Firstly, these prior works in instance-dependen operate under additional modeling assumptions the MDP dynamics, e.g., that is a tabular or linear MDP. Secondly, they require additional reachability assumptions on the state space, which is restrictive for MDPs with large states/actions; in fact, their sample complexity bounds typically have a dependence on the number of states/actions in the lower order terms. Finally, they implicitly assume that the optimal policy π II, and thus the provided algorithms do not transfer cleanly to the agnostic PAC RL setting considered in our paper.
PAC RL
Other Complexity Measures for RL. A recent work by Mou et al. (2020) proposed new notion of eluder dimension for the policy class, and provide upper bounds for policy-based RL when the class II has bounded eluder dimension. However, they require various additional assumptions: that the policy class contains the optimal policy, the learner has access to a generative model, and that the optimal value function has gap. On the other hand, do not make any such assumptions and characterize learnability in terms of spanning capacity or the size of the minimal sunflower II. We discuss connections the eluder dimension, as well as other classical complexity measures in learning theory in Appendix H.
B Examples of Policy Classes
In this section, will prove that examples in Section 3 have both bounded spanning capacity and the sunflower property with small K and D. To facilitate our discussion, we define the following notation: for any policy class II we let
C. (II) = max Creeach (II; (II: M),,
MEM'
where CTeach (II: .M) is defined in Definition 1. That is, (II) is the per-layer spanning capacity of II. Then as defined in Definition 1, we have
C(II) max (II).
bE[H]
Tabular MDP. Since there are at most [Sp] states layer h, is obvious that C, (IT) < SSp A, so therefore C(II) < S.A. Additionally, if we choose Ioroe {IT Ta(s) a, E A} to be the set
22

---

of policies which play the constant for each a E AA and S = S for every x E II, then any partial trajectory which satisfies the condition in Definition of the form (8), ap), which is consistent with Tag E core- Hence IT is (A,
Contextual Bandit. Since there only one layer, any deterministic MDP has single state with at most A actions possible, so (II) I A. Additionally, if we choose Horre a : (s) = a. a E A], and S = for every π II. then any partial trajectory which satisfies the condition in Definition is in the form a), which is consistent with Ta Iorre Hence II is a (A, 0) sunffoooo
H- L-LLyer Contextual Bandit. By induction, it easy see that any deterministic MDP spans at most A states in layer h, each of which has at most A actions. Hence C(I) S A". Additionally, we choose
more a .ay Tai, .a (5%) ah₁ 01. aH A}
and S = for every π II, then any partial trajectory which satisfies the condition in Definition in the form (s1, "1,-. 8H, az), which is consistent with Tai ag. (A ,) Suuullooo.r
Iloorre Hence 1I is
f-tons. In the following, we will denote IT. := ITg-ton- We will first prove that e(ITe) < 2H To show this, we will prove that Cn (II,) S 24 by induction on H. When H 1, the class is subclass of the above contextual bandit class, hence we have (ITe) S 2. Next, suppose (IT,) S 2(h 1) Fix any deterministic MDP and call the first state $1. Policies taking a = 1 states in the following layers. Such policies reach at most C (IT states in layer h. Policies taking 0 at can only take a = 1 on at most states in the following layers. Such policies reach at most C₁ (IL,) states in layer h. Hence we get
at 81 can only take a = on at most
Cn (IL,) S (HI-(- + ( S 2(h 1) + 2(h - 10) S 2h4.
This finishes the proof of the induction hypothesis. Based on the induction argument, we get
C(Il)) = max (lTe) S 2H'
bE[#]
Additionally, choose
Horre = [m)} (mh :1 h H}:
where (s) 0, and TT chooses the action 1 on all the states at layer h. i.e., Ta(s) := 1(s E S. For every π E TTg, we choose S₂ to be the states for which =(s) = (there are at most & such states). Fix any partial trajectory
(8h,4h 4h .4...... 8k' asr) which satisfies for all E (h, h", 8; & S.. Then we must have a; = 0 for all E (h, N". Hence Th ~ T (if aj = 1) or To ~~ (if an = 0), and consistent with some policy in locre. Therefore, 11g is an (H + 1, -)ssufloower.
Suppose that
1-Active Policies. We will first prove that C(T S 2H. For any deterministic MDP, Sr to denote the set of states reachable by IT at layer h. We will show that S, < 2h by induction on h. For h this holds since any deterministic MDP has only state in the first layer. Suppose it holds at layer h. Then, we have
Satll [[(s, ((s)
Sr. III)--
Note that policies II - must take a = on every & & {((1.)) ((1.)) .. , (1,8)) Hence [[(s, T(s)) s E Sn, π E [T) consequence we have C, (II)
< |5a| + < h + 1. Thus, the induction argument is complete, As
< 2h for all h,
C(Il act] = max (111-ac)) S 2H.
kE(H]
Additionally, if we choose S ((1,1)):11.22)) ... ( for all x Il as well as
Ioooee {TH} U {TA 1 h < H}.
where (s)s) = and (s) == is E Sn). Now fix any partial trajectory = (8h, Oh ... 8h', (p.)
which satisfies π ~ T. If we have i E (h, 1d]. 8; & Sr, then we must have a; = 0. Thus, Ta (if
aj = 1) or 3o ~ T (if az = 0), so r is consistent with some policy in II Teore- Therefore, I[--cct act. is
(H + 1, H sunflower.
23

---

All-Active Policies. For any deterministic MDP, there is single state sG:1) in the first layer. Any policy which takes a at state SG.1) must belong I1 j Hence such policies can reach at most - (Ll (et)-act) states in layer h. For polices which take action 0 at state all these policies will transit to a fixed state in layer 2. Hence such policies can reach at most e (Haact states at layer h. Therefore, we get
En (Tl S Cn-1 + max en-
I ( + 2(h 1).
By telescoping, we get
(TTctt S 1(h 1.011 1),
which indicates that
e(Ilcc)
max (Ilcc) H(H - 1). k
Additionally, if we choose S {. (.m) for all π alyy as well as
Tooe = { U ( 1 1 h < H):
where (s) := 0 and (s) 1(s E Sn Now fix any partial trajectory (5h, Oh. 5h', 0p.')
which satisfies т ~e J. we have E (h, [d]]. & Sn, then we must have a; = O. Thus, Ty ~- 7 (if ag = 1) or To (if as 0), so is consistent with some policy in Ioore. Therefore, laac is
(H + -unffloer.
Policy Classes for Continuous State Spaces. In some cases, it is possible to construct policy classes over continuous state spaces that have bounded spanning capacity. For example, consider ming. which is defined over a discrete (but large) state space. We can extend this to continuous state space by defining new state spaces Sn. (8(w..)) E R] for all h E [H]. action space A = {0, 1}.
and policy class
E [M]]- Essentially, we have expanded each state to be an interval on the real line. Using the same reasoning. + One can also generalize this construction the policy class Io and preserve the same value of e
nsing= == (T(A)) ((()))))((()))))) = 1 fx E [1,1+1) and h =
we have the bound ((llsing)
However, in general, this expansion to continuous state spaces may blow up the spanning capacity. Consider a similar modification to I (again, with the same new state space and action space A {0, 1}):
II act == for TT (((,))) = 0f [0, 1)]}
While -(I)) = OHH), it is easy to see that C(Il) = 2 since one can construct H-layer deterministic tree using states in [0, 1) as every (s, a) pair at layer Hl will be reachable by 11, -lg-act-
C Proofs for Section
C.1 Proof of Lemma
Fix any M Mato, as well [H]. We claim that
T = Σ sup d% (sh; M..M)) S max
Creech (II; M').
(3)
EA TAESS.OREAL EAA,
well
M'EMaes
Here, di (3,, an; M) is the state-action visitation distribution of the policy on MDP M.
We first set up additional notation. Let us define prefix any tuple of pairs of the form
(s1, 01 $2, 02 .2..... ... Sk, ak) or (s1, 01 82, a2..... Sk. . agg 8k+1).
'To compute the (K, D) values of Ion the previous arguments do not go through, since the sets S, are infinite. With suitable extension of Definition 4 to allow for non-Markovian Hore. it is possible to show that
Ie ton is an ())((())))s)nlliliie sunflowerr; Furthermore, the proof of Theorem 4 can be easily adapted to work under this extension.
24

---

We will denote prefix sequences as ($1:k, (1sk) or ($1=-1, (1:x) respectively. For any prefix ($i a1aa (similarly prefixes of the type ($1*+1, (1=)) we let di (sh.aa ($1.2 d1 M) de- note the conditional probability of reaching (8h, as) under policy я given one observed the prefix (81:k, 01:k) in MDP M, with djj (sh, Oh (S1:k, 01:k); M) = if + (81:k, (1ss) or и f (Sh, On).
In the following proof, we assume that the start state $1 is fixed, but this is without any loss of generality, and the proof can easily be adapted to hold for stochastic start states.
Our strategy will be to explicitly compute the quantity Fa in terms the dynamics of M and show that we upper bound it by "derandomized" MDP M which maximizes reachability at layer h. Let us unroll one step of the dynamics:
TA
E EA
sup di, (Sh, anz M)
Tell
Sy MES
sup di (s), an M1;
AE TEll
18
sup
Σ
(sn, an $1, 01; M)
S S.S EA
wEll
aETE
(1i1)
Σ
E
sup di (Sp: as 11, sEll
aLEA SEE
The equality (i) follows from the fact that M always starts at 81. The equality (ii) follows from the fact that n is deterministic, so there exists exactly one a' (()) for which di (sh, an. 81, a'; M). di (sh, an 81; M), with all other a" * a' satisfying di (sp, an a = 0. The inequality (Mii follows by swapping the supremum and the sum.
Continuing in this way, we can show that
TA =A= = Σ
Σ
sup TEN
Σ
P(s2(s1,a1)
Σ agEd
di. (sh, an (8122
d1 8y ES
$2ES
< Σ
Σ
p(s2(s1,a1)
Σ
sup (s),,, an (1)) Tell
A S
agE E.
Σ
Σ P(s2(s1,a1)
E... agEA
Σ
1(sh-11th-
8h-1 6Sa-1
X Σ
Σ
sup (8h, an (5th-1,41hh1):
Rh- E. E.E.AAAEEESR SAES EA
tEN
1): M). Observe that can be Now we examine the conditional visitation di (sh, an Ci rewritten as
di. (Sh, an ( M)- = P(sn [1nn|sh-1.40 an-1) 1 1( ~y (Bish, a13)).
Plugging this back into the previous display, and again swapping the supremum and the sum, get that
DA S
Σ
Σ
P(sn|5h-1:00 0n-1)
Σ sup 1( (81:h:01))
EA
SKES
a arEA
=ell
Σ
P(sp|5h-1,9h-
Σ
1 II (Sish {1+))
E.A
SAES,
R,EA
Our last step is to derandomize the stochastic transitions in the above stochastic MDP, simply by taking the sup over the transition probabilities:
F' <
Σ sup Σ
sup Σ Sy ES aLEA
1(3T Il:: n ~ (11H, =
max C Crreach (II; M').
M M
A
25

---

The right hand side of the inequality is exactly the definition of max g Ch (II; M'), thus proving Eq. (3). In particular, the above process defines the deterministic MDP which maximizes the reachability at level h. Taking the maximum over h as well as supremum over M, we see that su Crow (TT; M) C(TT). Furthermore, from the definitions we have
IIII=
sup MEMdet
C Coo S
sup MEMMtt
C (II; M).
This concludes the proof of Lemma
C.2 Coverability is Not Sufficient for Online RL
In this section, we observe that bounded coverability by itself is not sufficient to ensure sample efficient agnostic PAC RL in the online interactive model. First note that Theorem already shows this indirectly. In particular, spanning capacity that is hard to learn in online RL. However, recall Lemma which implies that any policy class with bounded spanning capacity must also have bounded coverability; and thus the lower bound in Theorem 3 can be trivially extended to argue that bounded coverability by itself does not suffice for statistically efficient agnostic online RL.
Theorem
we show that there exists policy class with bounded
However, we can also show the insufficiency of coverability through a much simpler route by directly invoking the lower bound construction in Sekhari al. (2021). In partieular, Sckhari et al. (2021) provides a construction for low rank MDP with rich observations which satisfies Ceoo (II: M) (11) for every M E M, but still needs 20(H) many samples for any (0(1), 0(1))- PAC learner (see Theorem in their paper for more details; simply set d ((H) get lower bound).
We do not know if coverability is also insufficient for the generative model setting: conjecture that one may be able to show, using a similar construction, that coverability is insufficient when C(TI) is large, showing that one cannot adapt benign problem instances.
D Proofs for Section 4
D.1 Proof of Theorem
Algorithm Trajectory (Kearns et al., 1999)
Require: Policy class 11, generative access to the underlying MDP M, number of samples n Initialize dataset of trajectory trees D = 0.
2: for i = 1,..., do
3: Initialize trajectory tree T; = 0.
4: Sample initial state s (i)
fl.
5: while Truc do
// Sample transitions and rewards for trajectory tree
6: Find any unsampled (s, a) s.t. (s,a) is reachable in 7, by some E IT. no such (s, a) exists then break
7:
8:
end if
9: Sample s' ~ P(-|s, a) and r ~ -H(s a)
10: Add transition a, s') to T,.
end while
12:
D D+DUU DUD
end for
14: for
E do
// Policy evaluation
15: Set V
4 E 07, where oर is the cumulative reward of n on T;.
16: end for
Return - arg max+en V=
17:
We show that, with minor changes, the Trajectory Tree algorithm of Kearns et al. (1999) attains the guarantee Theorem 1. The pseudocode can be found in Algorithm The key modification line 6: simply observe that only (s, a) pairs which reachable by some Il in the current
26

---

tree T, need to be sampled (in contrast, in the original algorithm of Kearns et al. (1999), they sample all A transitions).
Fix any π E IT. For every trajectory tree E [n]. the algorithm has collected enough transitions so that iy is well-defined, by line 6 of the algorithm. By the sampling process, it is clear that the values {oz higjnl are i.i.d generated. We claim that they are unbiased estimates of V Observe that one way of defining V the expected value of the following process:
(1) For every (s,a) E S x A, independently sample next state s' ~ a(-)s,a) and a reward r R(s, a) define a deterministic MDP M
(2) Return the value iT to be the value of x run on M.
Define the law of this process as Q The sampling process of Trajectory Tree (call the law of this process Q) can be viewed as sampling the subset of M which is reachable by some II. Thus, we have
V = M~ (0" -->
E 1"
[
- pl
where the second equality is due to the law of total probability, and the third equality is due to the fact that TTh is measurable with respect to the trajectory tree T. Thus, (07 Jeej are unbiased estimates of V=
Therefore, by Hoeffding's ss inequality (Lemma 17) we see that V V7 S 1og(2/6) Applying union bound we that when the number of trajectory trees exceeds 2 log( /5) with probability at least - 8, for all π E II, the estimates satisfy -V V^ I e/2. Thus the Trajectory Tree algorithm returns e-optimal policy. Since each trajectory tree uses most H ((II queries the generative model, we have the claimed sample complexity bound.
2n
D.2 Proof of Theorem 2
Fix any worst-case deterministic MDP M which witnesses C(Il) at layer h" Since C(II) is property depending on the dynamics of M we can assume that M has zero rewards. We can also assume that the algorithm knows M and h" (this only makes the lower bound stronger). We construct a family of instances M* where all the MDPs in M have the same dynamics as M but different nonzero rewards the reachable (s, a) pairs layer h².
Observe that we can embed multi-armed bandit instance with C(II) arms using the class M The value of any policy E II exactly the reward that it receives at the unique (s, a) pair in layer h² that reaches. Any (s, 8 algorithm that works over the family of instances M must return a policy t that reaches (s, a) pair in layer h- with near-optimal reward. Furthermore, in the generative model setting, the algorithm can only receive information about a single (s, a) pair. Thus, such a PAC algorithm must also be able to PAC learn the best arm for multi-armed bandits with C(II) arms. Therefore, we can directly apply existing PAC lower bounds which show that the sample complexity of (c, 8)C learning the best arm for K K-armed multi-armer bandits is at least 22 2 log 3) (see, e.g., Mannor and Tsitsiklis, 2004).
K
D.3 Proof of Corollary
The upper bound is obtained by simple modification of the argument in the proof of Theorem 1. In terms of data collection, the trajectory tree collected every time is the same fixed deterministic MDP (with different rewards); furthermore, one can always execute line 6 and line 9 for deterministic MDP since the algorithm can execute a sequence of actions to get to any new (s, a) pair required by line 9. Thus in every episode of online interaction are guaranteed to add the new (s, a) pair to the trajectory tree.
The lower bound trivially extends because the proof of Appendix D.2 uses a family of MDPs with deterministic transitions (that are even known to the algorithm beforehand).
27

---

E Proofs for Section 5
In this section, we prove Theorem 3, which shows superpolynomial lower bound on the sample complexity required to learn bounded spanning capacity classes, ruling out (eI)( H, log IT] sample complexity for online RL. We restate the theorem below with the precise constants:
Theorem 5 (Lower bound for online RL). Let hg E IN and (0, 1) be universal constants. Fix any H 2 ha- Let E (1/2 ,1 1/(100H) and & E (2...., H3 such that 1/cº S 22 There exists a policy class II() of size 1/(6')) with E(TI(() I ((H4++2) and family of MDPs M with state space S of size H 22H+1, binary action space, horizon such that: for any (e/16, 1/8)-PAC algorithm, there exists M E M in which the algorithm has to collect at least
24/3-3
min 120
online trajectories in expectation.
E.1
Construction of State Space, Action Space, and Policy Class
State and Action Spaces. We define the state space S. In every layer h [H], there will be 22H+1 states. The states will be paired up, and each state will be denoted by either j[b] or j' [h]. so Sz. [j[h] j E [22H]] U ["[[h] j [2 For any state E S, we define the index of s. denoted is)(s) as the unique j E [2 such that 8 E (ibbeee U ((([)))) In total there are H 22H+1 states. The action space is A = {0, 1}.
show via probabilistic argument the existence of large policy class II(e) which has bounded spanning capacity but is hard to explore. We state several properties in Lemma 2 which will be exploited in the lower bound.
Policy Class. For the given and l E ( H),
We introduce some additional notation. For any j E [22#] we denote
u = [N E 19 3h [M], [((h)) 1},
that is, 1 are the policies which take an action a = on at least one state with index j.
We also define the set of relevant state indices for a given policy π E II(e) as
To (j 12 =
For any policy æ we denote * (fi.)) == (J(()))..... - (j(HH) 10, to the vector that represents the actions that takes on the states in index j. The vector T( is defined similarly.
Lemma 2. Let H, E, and & satisfy the assumptions of Theorem 5. There exists a policy class (1(e) of size N =/((6=) which satisfies the following properties.
(1) For every j [22H] we have 5 E 2eN]
(2) For every π E 11 we have J 2 8/2 22H
(3) For every n E e the vector T(j.H) is unique and always equal to π <((..).
(4) Bounded spanning capacity: C(I1()) I e- 14442 for some universal constant 0.
E.2 Construction of MDP Family
The family M (M ) emr ,600 will be a family of MDPs which are indexed by a policy xt as well as a decoder function Φ : S + (GOOD, BAD). which assigns each state to be "good" or "bad" in sense that will be described later on. An example construction of an MDP M . is illustrated in Figure 1. For brevity, the bracket notation used to denote the layer that each state lies in has been omitted in the figure.
28

---

Relevant Combination Lock for Mar all transitions deterministic
ty Her
Ber (F)
Uniform over gad combination locks
Fw m Ber (3)
2
For Ber
Inooevant Combination Lock for Mar.i all transitions uniform to next loval
50p
30
50p
Ber
230
h
Figure I: Illustration of the lower bound from Theorem 3. Blue arrows represent taking the action x² (s), while red arrows represent taking the action 1- xx (s). Purple arrows denote uniform transition to the states in the next layer, regardless of action. The MDP Ma+,. a uniform distribution of 22H combination locks of two types. In the relevant combination locks (such as Lock in the figure), following л² keeps one in the "good" chain and gives reward of Ber(3/4) in the last layer, while deviating from x² leads one to the "bad" chain and gives reward of Ber(1/2) In irrelevant combination locks (such as Lock 50 in the figure), the next state is uniform regardless of action, and all rewards at the last layer are Ber(1/2).
Decoder Function Class. The decoder function class & will be the set of all possible mappings which for every E [22H] and h 2 2 assign exactly one of j[h] or j'[h] to the label GOOD (where the other is assigned to the label BAD). There are (2H-1)2"* such functions. The label of state will be used to describe the transition dynamics. Intuitively, a learner who does not know the decoder function will not be able to tell if certain state has the label GOOD or BAD when visiting that state for the first time.
Transition Dynamics. The MDP M will be a uniform distribution over 22H combination locks (CL)) with disjoint states. More formally, 81 Uniform( ((i()) From each start state _[].. only the 2H - states corresponding to index j at layers h 2 2 will be reachable in the combination lock CL,.
In the following, we will describe each combination lock CLj, which forms the basic building block of the MDP construction.
Good/Bad Set. At every layer h E [H], for each j[h] and j'[h, the decoder function assigns one them to be GOOD and one them to be BAD. We will henceforth denote [o] to be the good state and jo [h] to be the bad state. Observe that by construction in Eq. (7), for every E I and h [H] we have π (ig [h]) (jo(At)).
Dynamics of CL,, j E J Here, the transition dynamics of the combination locks are deterministic. For every h [H].
On good states [h] we transit the next good state iff the action π":
f1ss' ig (h + I}}. if = x² (jg [b) 1fss julh + 1]}
P(s' j.]
if x* (ig h)).
On bad states [b] we always transit to the next bad state:
P(s' 1is[h), a) 1fs' jolh + 1}}, for all a A.
29

---

Dynamics of CL if & Jeel If j is not relevant index for nT, then the transitions are uniformly random regardless of the current state/action. For every h [H],
P(-1ig(h),d) P(- jo[h], a) Uniform (1ight + 11. 1J},, for all A. Reward Structure. The reward function is nonzero only layer H, and is defined as
R(s, Ber
1(x² n 1(s jg ( (2y(H)))
That is, we get 3/4 whenever we reach the H-th good state for index j which is relevant for n², and 1/2 reward otherwise.
Reference MDPs. We define several reference MDPs.
the reference MDP Mo. the initial start state again taken to the uniform distribution, i.c., 81 (niform((jj4]) (eee))) ). and all the combination locks behave the same and have uniform transitions the next state along the chain: for every [H] and j [22*].
P( jhh, a) = P( 1 J'[b), = Uniform (fish + 1), + 1}}), for all a E A.
The rewards for Mo are Ber(1/2) for every (s, a) E SH x A. For any decoder 4, the reference MDP Mo o has the same transitions as Ma but the rewards are Ber (1/2) for every (s, a) E Sh X A.
E.3
Proof of Theorem 5
We now ready prove the lower bound using the construction of the MDP family M.
Value Calculation. Consider any M E MM. For any policy и A we use ( to denote the value of running in MDP Ma-.e- By construction
that
1 1 V ( = - P [id((1)) E Jei and (idxx(11) = (
(4)
where in the above, we defined for any (idx(s1)1.:) where j denotes idx(s1). Informally speaking, the second term counts the additional reward that
x(i.H) = (= (j(H))),
gets for solving a combination lock rooted at relevant state index idx(s1) ) E J.i By Property (2)
and (3) of Lemma 2, we additionally have Vn+ (x=) 2 1/2 + E/8, as well as V=r.o(T) = 1/2 for
all other ı * n' E (T)))
By Eq. (4), if is E/ 16--mmti policy on Ma it must satisfy
P P idx(si) Jæ and ((ix((s) (.:) n" (idxx()1))m)) E
Averaged Measures. We define the following measures which will be used in the analysis.
Define P-+1- = [
I Eoco [o[ to be the averaged measure where we first pick uniformly among all decoders and then consider the distribution induced by M
Define the averaged measure Po.-- [-] = क Eeeo Po,-= [ where we pick uniformly and then consider the distribution induced by Mo
For both averaged measures the expectations E,,, and Eu,x are defined analogously.
Algorithm and Stopping Time. Recall that an algorithm A is comprised of two phases. In the first phase, collects some number of trajectories by interacting with the MDP in episodes. We use to denote the (random) number of episodes after which A terminates. We also use A to denote the intermediate policy that the algorithm runs in round t for E [n]. In the second phase, outputs a
'We present the lower bound for the class of deterministic algorithms that output a deterministic policy. However, all the arguments could be extended to stochastic algorithms.
30

---

policy т. We use the notation A, (-(0 measurable function of collected data.
Frelv) H A to denote the second phase of A which outputs
For any policy n², decoder Φ, and dataset D we define the event
, A (D)) == {Px [ix((1)
Tra and (D())xxx()11 x (idx(s1 (1)x((1)1:HH) 2
e
4
The event ( Φ (D)) is measurable with respect the random variable D, which denotes the collected data.
Under this notation, the PAC learning guarantee on & implies that for every n' E 11(0), & + have
P (e.,e((('...A(())) .o)) 7/8.
Moreover via an averaging argument we also have
Pa- o, (D))] 2 7/8.
(5)
Lower Bound Argument.
We apply a truncation to the stopping time 1). Define Tiax == 2// 1/8 for some n² E [1(e) then the lower bound immediately follows,
Observe that if a. [1 > T max] since
max E lnl
Px > maax] Tmax > Ex- [n] 2
Tuaxx/.
#E
so there must exist an MDP Marc for which A collects at least Tmax/8 = 2H/3-3 samples in expectation.
Otherwise we have Pn > T maax] S 1/8 for all n¹ E IT(). This further implies that for all π E IT(()
Pxt 11 < Taax and A, = (P('E AD() - P.. In Tmax and (Tt",,,A((D)) 3/4.
(6)
However, in the following, we will argue that if Eq. (6) holds then & must query significant number of samples in My.
Lemma 3 (Stopping Time Lemma). Let 6 E (0, 1/8). Let be an (E/16,8)-PAC algorithm. Let Thax N. Suppose that Px in < Tmax and E(Tt, o, (D)) 2 28 for all E I1((), The expected stopping time for A on Mo is at least
EoIn| 2
[I
log
1
(
Tmax² 2
Tmax + log
2
26
26
Using Lemma 3 with d = 1/8 and plugging in the value of [IT((]] and Tmax, we see that
EoIn] 2
(
log
(
Tmax² 2
Tmmxx + log 1
1
>
[T(0]]
2
25
7
26
20
For the second inequality, we used the fact that > 2, H1 2 10a, and ε < 1/107.
We have shown that either there exists 23/3-3 samples in expectation, & must query least |/20 1/(120e5) trajectories in expectation in Mg. Putting it all together, the lower bound on the sample complexity is at least
MDP Ma for which A collects at least Tmax/8
min
1/3333
This concludes the proof of Theorem 5.
E.4 Proof of Lemma 2
To prove Lemma 2, first use probabilistic argument construct certain binary matrix B which satisfies several properties, and then construct ( using B and verify it satisfies Properties (1)-(4)
31

---

Binary Matrix Construction. First, we define a block free property of binary matrices.
Definition (Block-free Matrices), Fix parameters k. l, N, d E IN where k S N and S d. We say binary malrix B {0, 1] is (ki E)-block-free the following holds: for every I C [N] with [|] = k, and J - [d] with []] = E there exists some (i, E x J with Bi- = 0.
In words, matrices which are (k, -l.bbloo--frree do not contain k block of all 1s.
Lemma 4. Fix any E (0, 1/10) and & I.. For any
168 log(1/e) 1
20 exp 1
there exists binary matrix B E {0, 1) with = 1/66 E²) such that:
(1) (Row sum): for every row E [N], we have Ej Bij ed/2.
(2) (Column sum): for every column j E [d], we have E, Bij E [=N/2,
33) The matrix B is (E log d, E)-block-free.
Proof of Lemma 4. The existence of B is proven using the probabilistic method. Let B
{0, 1) 11jxddd be random matrix where each entry is i.i.d. chosen to be 1 with probability E.
By Chernoff bounds (Lemma 18), for every row E [AV], we have PIE, By I a S exp(-=d/8); likewise for every column [d], we have PlE, B.y & TEN 2=N]] S 2 eexp(-eN/8) By union bound, the matrix satisfies the first two properties with probability at least 0.8 as long as
d 2 (8 log 10N)/e, and N 2 (8log2d))/s.
One can check that under the choice of N = 1/(6 E²) and the assumption on d, both constraints are met.
Now we examine the probability of satisfies the block-free property with parameters (k: == é log d, f). Let X be the random variable which denotes the number of submatrices which violate the block-free property B, i.e.
= = J: [N), c [d]. || B, (1.))
By linearity of expectation, we have
E[X] & EK
We now plug in the choice A: é log d and observe that long N S 1/(2e ef) have E[X] < 1/2. By Markov's s inequality, P[X = 0] 2 1/2.
Therefore with positive probability, / satisfies all 3 properties (otherwise we would have contradic- tion via inclusion-exlusion principle). Thus, there exists matrix B which satisfies all of the above three properties, proving the result of Lemma 4.
Policy Class Construction. For the given and f (2...., H) we will use Lemma 4 to construct policy class IT(O) which has bounded spanning capacity but is hard to explore. We instantiate Lemma with the given é and d 22H and use the resulting matrix B construct (I(() { with [ = (.
Recall that we assume that
1
H 2 ho: and
2nH
100H
We claim that under these assumptions, the requirement of Lemma 4 is met:
168 log(1/s)
48 ]
d = 221 E
20
32

---

For the lower bound, we can check that:
16l log(1/e) 16H cH 2cH < 22H,
where we use the bound & < H and & 2 2 The last inequality holds for sufficiently small universal constant E (0, 1) and sufficiently large H hg-
For the upper bound, we can also check that
1
1
100H
22H
exp
exp
20
48at-1
20
48
where the bound L 2 2 and E S (100H).. The last inequality holds for sufficiently large H.
We define the policies as follows: for every म, (I(())
we set
[bit (Eag Baj)
if Bij 1, if Bij = 0.
for every j E [2 mi(i)) ग. ('(M)
(7)
The function bit 12" - 1] + {0, 1} selects the h-th bit in the binary representation of the input.
Verifying Properties (1) (4) of Lemma 2. Properties (1) (3) are straightforward from the construction of B and (1(), since प, E 1150) if and only if Big = 1. The only detail which requires some care is that require that 2 2 in order for Property (3) hold, since otherwise cannot assign the behaviors of the policies according to Eq. (7). However, by assumption, this always holds, since N 1/(3=f=1) s 2d
We now prove Property (4) that (T()) has bounded spanning capacity. To prove this we will use the block-free property of the underlying binary matrix B.
Fix any deterministic MDP M which witnesses ((II()) layer h" To bound ((I) need to count the contribution to Cgeach (II: M²) from trajectories t which produced by some E II( on M. We first define a layer decomposition for a trajectory T ($1 a1, $2, .g...., SH, aH) as the unique tuple of indices (h1, h22...h.. hm), where each h& E [H) that satisfies the following properties:
The layers satisfy h1 < h2 < ... < hm-
The layer hú represents the first layer where Oh,
The layer la represents the first layer where ahg 1 some state 8hg such that idx(sh2) & (idx(s),). }}.
The layer ha represents the first layer where Ohg = 1 on some state Shg such that
idx(shg) & {idx((s,,) idx(s)))))
More generally the layer h2. k E [m] represents the first layer where are = on some state She such that
idx(sh.) & (idx(sk,) ..... idx(sh._,)}
other words, the layer by represents the k-th layer for where action is a = 1 on new state index which has never played a 1 on before.
We will count the contribution to C (II; M*) by doing casework on the length of the layer decomposition for any That is, for every length m (O..... H), we will bound Cy. (m), which is defined to be the total number of (s, a) at layer h" which, for some II((), trajectory w that has a m-length layer decomposition visits. Then we apply the bound
H
C
creachh (II: II: S Σ Cn-)m).
(8)
w==
Note that this will overcount, since the same (8, a) pair can belong multiple different trajectories with different length layer decompositions.
33

---

Lemma 5. The following bounds hold:
For any m S E, (m)) - H I=== (2kH) = O(HLm).
We have Emze+1 Ch. (m) S Ole H(+t)..
Therefore, applying Lemma 5 to Eq. (8), we have the bound that
Σ Eourm)) + O (.--11-11 ((144t))
e(I(0)=
mge
This concludes the proof Lemma 2.
Proof of Lemma 5. All of our upper bounds will be monotone in the value of ht,, we will prove the bounds for CH (m) In the following, fix any deterministic MDP M
First we start with the case where m = O. The trajectory T must play a = 0 at all times; since there is only one such T, we have Cи (0) = 1.
Now we will bound C# (m)), for any m (I....,A). Observe that there are (
H ways to
pick the tuple (hi...., hhmm) Now will fix (hı,..., hm) and count the contributions Ch (m) for trajectories T which have this fixed layer decomposition, and then sum up over all possible choices of Nl,,...,
In the MDP M there a unique state 8h, which must visit, In the layers between h; and h2, all trajectories are only allowed take on states with index idx(s)g) ). but they are not required to. Thus we can compute that the contribution to Ch, (m) from trajectories with the fixed layer decomposition to be most 2H. The reasoning is as follows. At h1, there is exactly one (s, a) pair which is reachable by trajectories with this fixed layer decomposition, since any T must take a = at Sha Subsequently we can add most two reachable pairs in every layer h (h1 1 1...... h2 1} due to encountering state j [hh or j'[h] where j = idx(s ). and at layer h2 we must play a = 1, for a total of 1 2(h₂ h1 1) < 2H. Using similar reasoning the contribution to Cny (m) from trajectories with this fixed layer decomposition is at most (2H)- (4H), and so on. Continuing in this way. we have the final bound of I- (2kH). Since this holds for fixed choice of (hi,...,,mm in total (2kH) 4mH
have CH (m) 11
When m 2 é + 1, observe that the block-free property on B implies that for any J S [2"] with [J] we have [Nşe S flog222, So for any trajectory 7 with layer decomposition such that m f can redo the previous analysis and argue that there is at most & log 2n multiplicative factor contribution to the value Cn (m) due to all trajectories which have layer decompositions longer than & Thus we arrive at the bound Emzet1 (m() S O(H#) flog 22H < O H O
E,5
Proof of Lemma 3
The proof of this stopping time lemma follows standard machinery for PAC lower bounds (Garivier et al., 2019; Domingues et al., 2021; Sekhari et al., 2021). In the following we use (T((PIQQ) to denote the Kullback-Leibler divergence between two distributions P and Q and kl(pllq) denote the Kullback-Leibler divergence between two Bernoulli distributions with parameters p, q E [0, 1].
For any x* E ( we denote the random variable
RA
N
Σ
1((((ix((s1))111) = x² (idx(s1)1:1) and idx(s1) E Jee
the number of episodes for which the algorithm's policy round E [n A T Tmax] matches that of on a certain relevant state of n².
In the sequel will prove upper and lower bounds on the intermediate quantity Σxeen Eo [o[N="] and relate these quantities to En].
34

---

Step 1: Upper Bound.
First we prove upper bound. We can compute that
Eo N
T
Lo 10 +- 1311 ((dix((s)): = x (ididx(s)) 11HH and idx(s1) Trai H
1= x Ell
Tmux
Fo
1 13 Σ
1 {{ (idx(((1))))))) (idx(s1))11) and idx(s1) Trii }
x ElI
Eo < Foly A T maxx S Fo[n]-
(9)
Here, the first inequality follows because for every index j and every x²* E m each x² admits unique sequence of actions (by Property (3) of Lemma 2), so any policy A can completely match with at most one of the n²
Step 2: Lower Bound.
Now we turn to the lower bound. We use a change of measure argument.
(6) Eo,-
Eg
N
N - Tmxx A(Tmax)
Ea,or ob [NTT*] I Tmax A(aaxA(Tmad))
DE
KL FanTuxx
|| ||PFagaaa)) Tmax A (Tmax)
2
0,00
NE
(6i) 1
KT,
FanTmox 0,57
p FRATTaa
Tmmax A(T (Tmax)
7
The inequality (i) follows from a change of measure argument using Lemma 6, with m(Tmax) Tmax 2 2/22++3_ Here, FAJATae denotes the natural filtration generated by the first 1) A Tmax episodes. The inequality (ii) follows from Lemma 7, using the fact that Mo, and M have identical transitions and only differ in rewards at layer H for the trajectories which reach the end of a relevant combination lock. The number of times this occurs is exactly N=*, The factor 1/7 is a lower bound on 2 The inequality (iii) follows by the convexity of KL divergence.
Now we apply Lemma to lower bound the expectation for any FAIATaa -meauurable random variable Z E [0, 1] as
Fo N=
>
7 1l(
1
- T Timxx A (T (Tmax)
1 (1 Eu, (21) log
1
log(2) T Tmax A (Tmax);
Ex [2]
where the second inequality follows from the bound kl(pplg) 2 (1 - p) log(1/(11 - 9)) - -log(2) (see, e.g., Domingues al., 2021, Lemma 15).
Now we pick = Z == 1 (n < Tmux and E(rt, Φ, (D))) and note that Fx, [Z. 2 assumption. This implies that
28 by
1
log(2)
Eo N
2 (1- Lo,s- (2n-]) 7 log
Tmax A (Tmax).
28
Another application of Lemma gives
Eo N= 2 (1 - Eo[Z=.]) 7
1
log
log(2)
A(T A(Tmax)
Tmax + 7
log
1
28
7
28
35

---

Summing the above over xt" E II,,), we
Σ Eo N*
2 | - EolZx.] 7
1
log
1
(1(
log (2)
| A(T
[Tmax + 7
log
28
28
(10)
remains prove an upper bound on Ex Lo[Za.]. We calculate that
En [
=
Eo(d < Tmax and E(T", o, A (D))
- Σ Ep 1 T. idx(s1) E Jei and (D) =iddix((s1)ax))
2 +
$
Eo
Σ P
idx(s1) E Jaa and (D) IT ((ddx((51)::HH)
(11)
The last inequality is an application of Markov's 's inequality.
Now we carefully investigate the sum. For any & E Φ the sum can be rewritten as
Σ P a- idx(s1) Jei and (D) 11):.) (idx(s1)1:H1)
Pr o [s1] P [id((s1) E Jui and A (D) =idxixx(s))x
| s1
SiES
Pr [dx((s)) e Jei and A (D) = x* (idx(s1)).))
$1
[S
#1ES
(
1
Σ #1ES
Σ
(idx(s1) E Thi and A, (D) = n" (idx(((1)
(12)
S1
The equality (i) follows because regardless of which MDP M, we in, the first state is distributed uniformly over Sj. The equality (ii) follows because once we condition on the first state the probability either or
Fix any start state 81. We can write
Σ ((dxx(()) E Jeii and (D) (1) )r" (idx(s1)1.H))
Σ
((d(())(i T (idx((s))).H) = 1,
x¹ TT (ds(o1)
where the second equality uses the fact that on any index j. each ' E m1 behaves differently (Property (3) Lemma 2), so (D) can match at most one these behaviors. Plugging this back into Eq. (12), averaging over & E o, and combining with Eq. (11), arrive at the bound
Σ EoIZZ.11 4
We now this in conjunction with Eq. (10) arrive at the final lower bound
Ep
N
N
[
log
26 - [
log(2)
(1 A(Tmax)
Tmuxx + log
7
7
28
(13)
Step 3: Putting it All Together. and simplifying get
Combining Eqs. (9) and (13), plugging in our choice of A ((Tmax)
Eo EoIn]
2 | =
log
1 (1)())
log(2)
|| A(Tmax
Timx + + log
1
25
26
36

---

[II(9]
log
- [TT(6]
T Tmxx
Tmax + log
1
26 )
2
25
2H+3
7
The last inequality follows since 1/8 implies log(1/(26)) 2 21og(2). This concludes the proof of Lemma 3.
E.6 Change of Measure Lemma
Lemma 6. Let Z E [0, 1] be a Frims- meeauurable random variable. Then, for every x² E II1))
T Tmax 2
Eo|Z| E0,r- [2]] s (TTmax)
22++3
Proof.
First, we note that
Tmax
Eo|2] Eo. [2]] S TV (P) Timxx T
Here [o[-]FF]] denotes the conditional distribution of the t-th trajectory given the first & trajectories. Similarly -- Fi] is the averaged over decoders condition distribution of the t-th trajectory given the first &
trajectories. The second inequality follows by chain rule of TV distance (see, e.g.. Polyanskiy and Wu, 2022, pg. 152).
Now examine each term (Pol--FF--)) Po. Fix history Fi-1 and sequence $1:H where all 8; have the same index. We want to bound the quantity
P Po. (
Fi-1
Po $ 81:1
Fr-1]
81:H
where it is understood that the random variable ((1) is drawn according to the MDP dynamics and algorithm's 's policy A, (which turn a measurable function of F,
We observe that the second term is exactly
Po s
$1.8
Fi-1
[
1
2H-1'
since the state 81 appears with probability 1/|S,| and the transitions in Mo are uniform to the next state the combination lock, so each sequence is equally as likely.
For the first term, again the state 81 appears with probability 1/[St]. Suppose that idx(s1) é Tri Then the dynamics of Po for all Φ E are exactly the same as Mg. so again the probability in this case is 1 (2- Now consider when idx(s;) Jzi At some point h [ + 1], the
policy A, will deviate from x for the first time (if A never deviates from 'T we set = H + 1). The layer h is only function of $1 and A and does not depend on the MDP dynamics. The correct decoder must assign (8181,
GOOD and (8% = BAD, so therefore we have
P Pu [ $1:H
Fi-1 = Po,x* 66 1 = GOOD and ( = BAD Fe-1
81 & Fr-1, i.e., we are seeing 81 for the first time, then the conditional distribution over the labels given by Ø is the same the unconditioned distribution:
Po. ( GOOD and ((5 = BAD Fi-1]
1
S1
211
Otherwise, if 81 E Fi then we bound the conditional probability by 1.
Fo,x+
(1)
$1:H
Fe-1 s S
Putting this all together we can compute
if idx(s1) & J
|S
24
idx(s1) E J and 81 $ Fi-1;
Po,x (((0) = 81.H
Fo-1
[Si]
2
idx(s1) E J and 81 F otherwise.
[
37

---

Therefore we have the bound
Po..* 1::1 = 81:11
Fi-1] Po
(1 = 81:11
Fi-1
1
1
[dxx(s)) E Tw E eFr-1
[
Summing over all possible sequences 81.H1 we have
1 (t 1) 2#
TV(P 1-F-111) Σ
2 |
since the only sequences 81:11 for which the difference in the two measures are nonzero are the ones for which $1 E Ft of which there are (t 1) 2 of them.
Lastly, taking expectations and summing over to Tmax and plugging in the value of [Si] 2 we have the final bound.
The next lemma a straightforward modification of (Domingues et al., 2021, Lemma 5), with varying rewards instead of varying transitions.
Lemma 7. Let M and M' be two MDPs that are identical in transition and differ in the reward distributions, denote (s, a) and ry (s, (), Assume that for all (8,a) we have ra(s,a) & r (8) Then for any stopping time with respect to (F")e2 that satisfies PMr < <x]=1,
KL (P KT.(P't (1p))))
Σ
EMIN Ma KL(a(ss,))lr((ss..))
where N Na,. == Ei 1f = (s,a) and L, Q + UciI
[ is the
random vector representing the history up to episode 17.
Lemma 8 (Lemma 1, Garivier al. (2019)). Consider a measurable space (S, F) equipped with two distributions P1 and P2. For any F-meusurable function Z : Q + [0, 1] we have
KL(Pi 1l2) 2 ||(E/1/]1E2/2))
38

---

F Proofs for Section 6
F.
Algorithm Sketch
In this section we provide high level sketch of Algorithm 1. We will descrihe the key algorithmic ideas, as well as the empirical estimation of policy-speeific MRPs, in the two phases of POPLER.
State Identification Phase
The goal of the state identification phase is to discover all such petal states that are reachable with probability ( The algorithm proceeds in a loop and sequentially grows the set T, which contains tuples of the form (s, TT), where s E Urem Sa is a sufficiently reachable petal state (for some policy) and ng denotes a policy that reaches s with probability D)) We also denote Srch = (s (s, nT)) E ' to denote the set of reachable states T. Initially, T only contains a dummy start state ST and null policy. We will collect data using the DataCollector subroutine that: for a given (s, R2) E T, first run ne to reach state 5, and we succeed in reaching s, restart exploration by sampling policy from Uniform(llexp). Note that DataCollector will be sample- efficient for any (s. Ns) since (2(/D) fraction of the trajectories obtained via я. are guaranteed to reach s (by definition of π. and construction of set T). Initially,
DataCollector using Uniform (Tlxx) from the start, where we slightly abuse the notation and assume that all trajectories in the MDP start at the dummy state 8T time step h = 0.
In every loop, the algorithm attempts to find a new petal state & for some be (le/D))-reachable by æ. This is accomplished by constructing a (estimated and partial) version of the policy-specific MRP using the datasets collected up until that loop (line 9). In particular given a policy ग and a set S = S n Stch, we construct Di Sreh = MRP f ftr,, H, 8T, (T,81) which essentially compresses our empirical knowledge of the original MDP relevant the policy x. In particular, for any states E S, U {sT} } and s' E S U } residing in different layers h < h in the underlying MDP, we define:
that guaranteed to
Transition a-+ as:
pm
por
1 Dee
1lTT no Thin'}
1
{
Th- goes from s' without passing through any other s" S.
Mecral Ex'eteen 1( as Then
TED,
(14)
Transition :TT as:
1
Thiik goes from to s Mearel Ex 1 1a as Thit' without passing through any other s" e
R(Twe)) 18 no Thah'
D
S.
TED.
(15)
Clearly, the above definition implies that P P = O and Py... = 0 for any & S since D, would be empty corresponding to these unexplored states. Furthermore, p = 1 and R +s 0.
Note that since the set Srch is changing in each iteration of the loop the algorithm collects more data, the splicy-specific MRP Sm also changes in every iteration of the loop -opp-ii in particular, more and more transitions/rewards are assigned nonzero values due to new states being added to grch More details on speccfcc MRPs is given in Appendix F.2.
The key advantage of constructing the empirical versions of popicc-specific MRPs that they allow us to explore and find new leaf' states in S which are reachable with probability at least ((f/6D). In particular, using standard dynamic programming (subroutine EstReachability), we can check whether a candidate petal is reachable with decent probability by и (lines 1 11-12); If it is, then we add (8. x) to the set T and collect a fresh dataset using DataCollector (lines 13-14). Crucially, the importance sampling technique enables us to be sample efficient, since the same dataset D, can be used to evaluate transitions/rewards in Eqs. (14) and (15) for multiple π II for which Furthermore, the number of such datasets we collect must be bounded-eand (s, T.) E T contributes ((e/ D) to cumulative reachability, but since cumulative reachability bounded from above by C(IT) (Lemma 1), we know that [T| < O(D ((II)/E).
a petal state.
39

---

Evaluation Phase
Next, POPLER moves to the evaluation phase. Using the collected data, it executes the Evaluate subroutine for every II to get estimates V/ (line 21) corresponding to V For given II. the Evaluate subroutine also constructs an empirical policy-specific MRP D for every π e Il
and computes the value of ıT via dynamic programming 2 S.a. While the returned estimate 7 biased, in the complete proof, we will show that the bias negligible since now only due to the states in the petal S which are not Qet/ -reechbbbl Thus, we can guarantee that V closely estimates V for every IT, and therefore POPLER returns near-optimal policy.
F.2 Algorithmic Details and Preliminaries
In this subsection, we provide the details of the subroutines that do not appear in the main body, in Algorithms 3, 4, and 5. The transitions and reward functions in line 5 in Algorithm 5 are computed using Eqs. (19) and (20), which are specified below, after introducing additional notation.
Algorithm 3 DataCollecter
Require: State: Reacher policy: Ta. Exploration policy set: Iocoee Number of samples:
1: if ST then
// Uniform sampling for start state sT
2: fort= 1, ..... do
3: Sample x' ~ Uniform([lcord) and run T' to collect T = ($1, a1 ... (H,0H).
4: D. t- D, J (T].
5: end for
6: else
// basbdd sampling for all other states + Identify the layer such that E Sn-
7:
8: for t. 1,.... do
9:
Run ग. for the first h - time steps, and collect trajectory (81, 01, ... 8h-1, 1hh-1,0h111 1, Sh). if 84 then
11:
Sample n' ~ Uniform(Ueor)) and run n' to collect remaining (sh, Oh, ... , 8H,aH) aH) D. D, U (T ($1, "r, sH az az)).
13:
end end for
15:
end if'
Return dataset D..
Algorithm 4 EstReachability
Require: State space Çtab MRP MR, State Stab
1: Let P be the transition of M.
2: Initialize (s)) = 1{s = $} for all s gtab,
3: Repeat H + times:
4: For all 8 E Stab calculate V(s) + Eveston Pa-es V(d)).
// Dynamic Progr aaggraniing
5: Return (ST)).
We recall the definition of petals and sunflowers given in the main body (in Definitions 3 and 4). In the of this section, we assume that 1I is (K, -Jssulolower with Horee and Sz for any II. Definition (Petals and Sunflowers (Definitions and in the main body)). For a policy set Î1, and states S S policy π is said to be a S-petal on Il for all h' < H, and partial trajectories T = (sh, ... S/,, awy) that are consistent with n: either T is also consistent with some n' e II, or there exists i (h, h/] s.t. S; S.
A policy class II is said to be a (K, D)-sunflower if there exists a set Neore of Markovian policies with [eurl < K such that for every policy π. E II there exists set S S. of size at most D, so that N is an Sx-petal on I.ooe-
Additional notation. Recall that we assumed that the state space S = S x x...SH is layered. Thus, given state 8, we can infer the layer i such that Sp. By definition sT belongs the layer h 0 and belongs to the layer h = H. In the following, we define additional notation:
40

---

Algorithm 5 Evaluate
Require: Policy set Ieree. Reachable states Stch Datasets (Da)aeseeh, Policy x to be evaluated. $ Stch and Ştab =Saa Sych {s1}.
1: Compute S
2: for s, in Stab do
Compute transitions and rewards on g 3: Let h, h be such that E Sp. and s' Si then Pe P 8-t8' according to (19) and (20);
4: if
5:
Calculate P
6: else
7: Set P 8-t0r +- 0, Po 8-48' f- 0.
8: end
9:
end for
10:
Set (s) = for all E Stab
11:
11 Evaluate by dynamic programming 12: For all 8 E Stab, calculate V(s) t Ega Pa Po- (P--s) + V(6))
Repeat for H + times:
Return (ST).
(a) Sets I(s s': For any set S, and states s, E S, we define I(s + -S) as the set of all the trajectories that go from to s' without passing through any state in S in between. More formally, let state be layer h, and s' be layer h.. Then, I(s - s': denotes the set all the trajectories r (81, 41, 8, 0.) that satisfy all of the following:
S/ = 8, where 8ú is the state at timestep h in r.
S/' 8', where is the state at timestep h in T.
For all h < < h', the state 87 at time step h in does not lie in the set S.
Note that when N' S h, we define I(s + s': 55: 0. Additionally, we define I(sT SS- as the set of all trajectories that go to s' (from a start state) without going through any state in S in between. Finally, we define II(s + s1i -S: as the set of all the trajectories that go from at time step h to the end of the episode without passing through any state in S in between.
Furthermore, we use the shorthand I=(s - + s') := I(s + s'; -S) to denote the set of all the trajectories that go from to s' without passing though any leaf state S,.
(b) Using the above notation, for any E S and set S S S, we define d=(s;; SS) as the probability of reaching (from a start state) without passing through any state in S in between, i.e.
ddd (s; -5) px [ reaches without passing through any state S before reaching s) px T I(sT +: SS)].
(16)
We next recall the notation of Markov Reward Process and formally define both the population versions of policy-specific MRPs
Markov Reward Process (MRP). A Markov reward process M = P, $1) is defined over the state space S with start state sT and end state s1, for trajectory length H + 2. Without loss of generality, we assume that {8T,81} E S. The transition kernel is denoted by P: S + [0, 1], such that for any E S. Σ.' Ps-ss' 1; the reward kernel is denoted R S x S + A(O0, 1)). Throughout, we use the notation + to signify that the transitions and rewards are defined along the edges of the MRP.
trajectory in 27 of the form T = (ST,81," (H, where sp E S for all h E [M]]. Further- more, from any state E S, the MRP transitions" to another state s' E S with probability Pa-s' and
"Our definition of Markov Reward Processes (MRP) deviates from MDPs that we considered the paper, in the sense that we do not assume that the state space S is layered in an MRP. This variation is only adapted to simplify the proof's and the notation in the rest of the paper.
41

---

obtains the rewards re-to ~ Ro-o Thus,
H
p [r] = Pat
II h=1
Pen Pa-toass
Pan
and the rewards
H Tan 78h41 + Tan -811
(T) -8
hml
Furthermore, in all the MRPs that consider in the paper, we have Poi-te 1 and Tai-sa 0.
Policy-Specific Markov Reward Processes. A key technical tool in analysis will be poliey- specific MRPs that depend on the set Stch of the states that we have explored so far. Recall that for any policy x. S S U {ST, s s_). St = n Srch and Stem St (Stch U {s_]). We define the expected and the empirical versions of policy-specific MRPs below; see Figure 2 for an illustration.
(a) Expected Version of Pplicf-Specific (T, (1) where
MRP. We
define
D
MRP ,T" H,
Transition Kernel p*; For any E Stcc and s' E S we have
P = E [1{T E (s - +s s))} = s]
(17)
where the expectation above w.r.t. the trajectories drawn using æ in the underlying MDP, and h denotes the time step such that E S₁ (again, in the underying MDP). Thus, the transition P denotes the probability of taking policy и from and directly transiting to s' without visiting any other states in S Furthermore, P 5-25'
1 = } for all 8 E Srem U {
Reward Kernel ; For any E STch and s' E S we have
1 3- = E" [ E (s
s/) = s].
(18)
where R(Th:)) denotes the reward for the partial trajectory Thch' in the underlying MDP. The reward r "--=* denotes the expectation of rewards collected by taking policy from s and directly transiting to s' without visiting any other states in S,.. Furthermore,
r 3 0 for all s E Stem U {s.).
Throughout the analysis, we use pT == pm whenever clear from the context.
greh grch [-] and I [.] := E 200
greh [+]
a shorthand,
(b) Empirical Version of Policy-Speciiee MRPs. Since the learner only has sampling ac- to the underlying MDP, it not directly construct the MRP M Instead, in Algorithm 1, the learner constructs an empirical estimate for My defined as Sech MRP(S; PTm FF H. S1) where
Transition Kernel pa: For any Stch and s' E St. have
[earee Dal
1(x ~m Thch)
Por
Σ Σ En'elloor 1( Thsk')
1 -1 s')},
(19)
TED,
where Herre denotes the core of the sunflower corresponding to and D. denotes a dataset of trajectories collected via DataCollector(s, n,, Iecre, n2). Furthermore,
f P = 1is' FTe for all Stem U (ss)).
Reward Kernel : For any E Srch and s' St, we have
I Toorel DDal
11 1 an Think
for
Σ TED,
Er 1( ~9 Thec 1[r E Ix(s+ +=) (20)
where Heore denotes the core of the sunflower corresponding to II, D, denotes a dataset of trajectories collected via DataCollector(s, n., I. n2), and R(Thar) Em' W--1 Furthermore, F = 0 for all E Svem.
r4.
The above approximates the MRP given by (14) and (15) the main body.
42

---

ST
0
P 0.2
P Fy-
0.35
fyms 0.05
R
0.1
9/-12
R1
R
$
h =
Py 0.4
Pa 0.1
R
0.1
$3
h =
pe 0.5
$2
h =
Jumns Ry
Pr
R
$1
pr
h=4
R
Figure 2: Illustration of an MRP 2 Srah with S₂ {si, 82, 83} and Srch {51 82 J. In the original MDP M, $1 E S1, $2 E Sz, and 83 E S2. The edges are labeled with the values p.,.' and R R Notice that (1) there
edges from 82 83 83 $2 because trajectories cannot go from later layers to earlier ones; (2) since $3 & Srch, there is no edge from $3 + $2, and instead we have and 12 1
pr 481
0; (3) 81
absorbing state with rewards.
Properties of Trajectories in the Policy-Specifie MRPs. We state several properties of trajectories in the policy-specific MRPs, which will be used in the proofs. Let = (ST, $1, 8H $1) denote trajectory from either M.g.... Di7
Socla
(1) For some & < H we have "....... ... E S. and 8841 ... = 81 = 81 (if = H we say the second condition is trivially met).
2 Each state in "1, 8k is unique.
(3) Letting h()) denote the layer that state E S.r is in, have h(s1) <... h(sk)-
Either (a) "1, 8 E Stch (b) 81, 8k-1 E Sych and 8 grem
Parameters Used in Algorithm 1. Here, we list all the parameters that used in Algorithm 1 and its subroutines:
C1 (D (D+1)*K** K) (D
22
n2 = C2 D3(D + K3 log ( ( 1)2/8)
(21)
where C1, C2 > 0 are absolute numerical constants, which will be specified later the proofs.
F.3
Supporting Technical Results
We start by stating the following variant of the classical simulation lemma (Kearns and Singh, 2002:
Agarwal et al., 2019; Foster et al., 2021a). Lemma (Simulation lemma (Foster et al., 2021a, Lemma F.3)), Ler 22 = (S, P,r,H.TT,S.. be markov reward process. Then, the empirical version M (S,P,. H, ST, $1) corresponding to M
43

---

satisfies:
VMRP
PMRPI
Σ don(s)
1 Pa--ss Po-sol Ir-sss Fonse
#ES
where (s) is the probability of reaching under WR, and VMRP and VMRP denotes the value of ST under Wi and Mi respectively.
The following technical lemma shows that for any policy æ, the empirical version of policy-specific MRP closely approximates its expected version.
Lemma 10.
S of the while loop in line with the instantaneous set Stch, Further, suppose that [Da] 2 24D for all
Let Algorithm be run with the parameters given in Eq. (21), and consider any iteration
E Stch Then, with probability at least 1 8, the following hold:
(a) For all π E II, 8 E Sech and s' E Ex
max [P
P Pr
P5 Pe-as
8 12D(D 1)
(b) For all π E II and s' E S² (8L1)
max -ss
Pe
p P
E 12(D + 1)2
In the sequel, we define the event that the conclusion of Lemma 10 holds Eest.
Proof. Fix any x II. We first prove the bound for Srch Let at layer h. Fix any policy II, and consider any state s' E S. U {a J. where s' is at layer h'. Note that since II is a (K, D)- sunflower, with its core Hoore and petals (S ) we must have that any trajectory a + 8)) is also consistent with at least one E Nenre. Furthermore, for any such we have
-111
1 [Thak |sh sh= =
II
P[s++1 86, Te(s), sh
i=h
-
II i=h
P[s++1 (s, = Pd [Thske 8h =
(22)
where the second line holds because both π ~ Thil' and ne ~t Thskr. Next, recall from Eq. (17), that
p
[L
I + ('s s).
(23)
Furthermore, from Eq. (19), recall that the empirical estimate pm Pr given by:
Σ (s TED
P...
(24)
[D,
[eore] Em.en..... 1( ~ Thike }
where the dataset D, consists of i.i.d. samples, and is collected in lines 10-12 in Algorithm (DataCollector). by first running the policy т. for / timesteps and if the trajectory reaches s, then executing ne Uniform(Hloow for the remaining time steps (otherwise this trajectory is rejected). Let the law of this process be q. We thus note that,
Pa Errng
1x 1 |8h
= -Eng
Moorel Em 1itee mn Thoh)
Σ
PylThake 88 = 8)
=
Er. Elloora 1 1s Thek
(x-t8)))))
Meorol
44

---

Σ
Σ
1(T E Tx.(s (x-())))))) 87} pnd [Thche 8h =
Horel
[ecorll E the Elleore 1f7e Thihd
st, eTlore
(8)
Σ
pM (To 8h = 8]
11 in Thine]
Meare
Teoore Lx, ElTeare L LTee Thih'
#fElloure
Σ
[TTTh 8h =s]
(5-58)))))
(180 ETL 88) 8h = P
where (i) follows from the sampling strategy in Algorithm after observing 8/, = 8, and (ix) simply uses the relation (22) since both T'' Thilk and π Thih hold. Finally, in (fii), we use the relation (23).
We have shown that p is an unbiased estimate of Pa for any and s, E S Thus, using Hoeffding's s inequality (Lemma 17), followed by union bound, we get that with probability at least 1 8/4, for all II, Srch, and s' S U {si}.
2 log (II
P
P P-
D
where the additional factor of K appears because for any E (s - s'), there must exist some Te E Ueooe that is also consistent with T (as we showed above), which implies that each the terms in Eq. (24) satisfies the bound a.s.:
E (n (+ +()}
M K.
[ En.EBeoore 1fie no Thcke
Since [Da]
by assumption, we have
21D
48D (oD 1)/6)
P P
pa
S K
En1
Repeating a similar argument for the empirical reward estimation in Eq. (19), we get that with probability least 1 - 8/4, for all II, and Stch and s' E S {s }, we have that
48D [ + 1)/8)
F
T roool S K
Cn2
Similarly, we can also get for any π E and s' S U [8 with probability at least - 8/2,
2 [ + 1)/8)
max 1 r ro- P px P S sKV
[D,7]
[ + 1)/6)
K V
71
where the last line simply uses the fact that [D., n1. The final statement due to union bound on the above results. This concludes the proof of Lemma 10.
Lemma Fix a policy क E and a set of reuchable states grch, and consider the policy- specific MRP We (as defined by Eqs. (17) and (18)). Then for any E Srrm the quantity d= (s: Stom) ) d (s), where a (s) is the occupancy of state in My
Proof. We use F to denote a trajectory in My and 7 to denote "corresponding" (in sense which will be described shortly) trajectory in the original MDP M. For any E Stem we have
())
Σ
2
7
=
Σ
Σ
p = (ST, 81 3b 8,88111 ...)..)))
st.
SEP
K=
51.5g." Stch
45

---

The first equality is simply due to the definition of d For the second equality, we sum up over all possible sequences which start at ST, pass through some (variable length) sequence of states $1,".. E Sh then reach and the terminal state By definition of the policy-specific MRP, we know that once the MRP transits to state E Srem, it must then transit to T1 and repeat $.1. until the end of the episode.
Now fix a sequence 81,-... 5k corresponding trajectories in the original MDP M. To avoid confusion, we let sh...... Sh, Stch denote the corresponding sequence of states in the original MDP, which are unique and satisfy hn < h2
Stch, We relate the term in the summand to the probability of
hR- We also denote 8ha11 8.
Using the definition of greh we write
D F (ST, $1 ... S,8. ..]
P M Thichets (sh. + shet)) r[hs] shh]
ppM. V E [k: +
1), r[bs] = Sh1 and wh [Mx+1])((bs hx+1 =[1]] & Sz).
Now we sum over all sequences 31.-" 5k E Stch to get
d
H
Σ
Σ
PM PM.IIVi ik 11, r[h]] = sh. and 4h E (h1. h4t1h r[h] $ S
0= "ha""" .8hg ESrch
[MM E T and vh [h6+1 1], 7[h] & Sx
I E I(S + s: - d (s: -
The second equality follows from the definition of Srem, and the last line is the definition of the d notation. This concludes the proof of Lemma 11.
Lemma 12. With probability al least - 25, any (3, T) that is added into T (in line 13 of Algorithm 1) satisfies dt (8) 2 $/12n.
Proof. For any (8, E T, when we collect D3 in Algorithm 3, the probability that a trajectory will be accepted (i.e. the trajectory satisfies the "if" statement in line 10) is exactly d= (3). Thus, using Hoeffding's 's inequality (Lemma 17), with probability at least 1 - 6/DII
D2 dt (5) f22
2 2og (ogg())1))6))))
f2
Since 'T S DI. by union bound, the above holds for every (8, E ' with probability at least
1 - 8. Let us denote this event as Edata. Under Edatas for any (8, π) that satisfies d' (8) 2 12D
Dal 2 nzd log (oogloDD/////0 2
En2
En2
En2
(25)
12D
24D
24D*
where the second inequality follows by the bound on d (3) and our choice of parameter n2 in Eq. (21).
In the following, we prove by induction that every (8) that is added into T in the while loop from
lines 7-17 in Algorithm satisfies dd (8) 2 12D This is trivially true initialization when T {(ST, Null)), since every trajectory starts at the dummy state ST, for which we have dNlll (ST) 1.
We now proceed to the induction hypothesis. Suppose that in some iteration of the while loop, every tuple (8, T) E T satisfies d' (3) > $/12D, and that (8', x²) is new tuple that will be added to T. We will show that (5', n²) will also satisfy d=' (s') 2 5/12D.
Recall that S Ser U {ST,8) }. Szch S n Stch, and Stem S Stch, Let Si MRP(St, pr rr (H, be the pppicy-specific MRP, where px and pr defined in Eqs. (17) and (18) respectively for the policy n'. Similarly let M.
46

---

MRP(S pr ST. denote the estimated policy-specific MRP, where fx and r" are defined using (19) and (20) respectively. Note that for any state E S the bound in (25) holds.
For the rest of the proof, assume that the event &est, defined in Lemma 10, holds (this happens with probability at least 8). By definition of Eest we have
P
P Paowls +2)(++1)) for all
U
(26)
Furthermore, note that d=' (8') + EstReachability (S7, Wi.... , 8¹) since in Algorithm 4 we start with V(s) = l(s 3'}. Furthermore, using Lemma 9, we have
(8) d
por 8-s8' pe 8
sup SEST ,'EES
(27)
12D(D+1) +1+ = 12D
where the second inequality follows from (26). Additionally, Lemma 11 states that (s"(s)) d' (..m), Therefore we obtain
rd (5':-5Tm)) d'' (5') <
E
12D
Thus, the new state-policy pair (8', n') is added into T, we will have
d'
(5'; S Srem
6D
12D
12D
Furthermore, by definition of d we have
d'' (s': (s': = pm ITE + +3::-5 {
[T== d' (8))
so we have proved the induction hypothesis d=' (3') 2 e/12D for the next round. This concludes the proof of Lemma 12.
The next lemma establishes that Algorithm 1 will terminate after finitely many rounds, and that after termination will have explored all sufficiently reachable states. Lemma 13. With probability least 1 28,
(a) The while loop in line in Algorithm will terminate after at most DC rounds.
After the termination of the while loop, for any π IT, the remaining states E Stem that are not added to Stch satisfy d= (s:-8tem) S 5/AD.
Notice that according Therefore, | < DI and the maximum number of rounds of the while loop is DJI (i.e., the while loop eventually terminates).
algorithm, the same state cannot be added multiple times into Srch
Proof. We prove each part separately.
(a) First, note that from the definition of coverability and Lemma we have
Σ sup d= (s) S HC (II:M) < HC(I).
#ES Tenl
Furthermore, Lemma 12 states that every (s, nx) T satisfies d= d= 2 4/12n. Thus, any point in Algorithm 1, we have
Σ tec
sup d (s) 2 Σ d (s) IT
12D
Stch
47

---

Since, Stch C S, the two bounds indicate that
12HDE(1T)
IT|
S
E
Since every iteration of the while loop adds one new (8, to T, the while loop terminates after at most 12/1// many rounds.
(b) We know that once the while loop has terminated, for every have d= (3) S f/6D, or else the condition in line 12 in Algorithm is violated.
and Stem, must
Fix any such (5, T) pair. Inspecting the proof of Lemma 12, we see that
(3; Stea
L (3) 5 12D
To conclude, get
dh (s: ST I +
6D
12D
4D
Lemma 14. Suppose that the conclusions of Lemmas 10 and 13 hold. Then for every ι e II, the estimated value v computed in Algorithm I satisfies
- S..
Proof. We will break up the proof into two steps. First, we show that for any the value estimate VE obtained using the empirical policy-specific MRP S. is close to its value in the policy-specific MRP Wg Srca as defined via (17) and (18). We denote this quantity as VRRP. Then, we will show that V MRP is close V=, the value of the policy ı in the original MDP M.
Part tT is close to MRR. Note that the output 7Th of Algorithm is exact the value function of MRP Di grah defined by Eqs. (19) and (20). When D by part (b) of Lemma 10, we obtain
Mnrl = 1
T ST +
12(D + 1) S 2
When D 2 1. using Lemma 10, we have
In
po - <
p P
px
ST - <
Ys' Sx U (TL}
+s
12(D + 1)2
12(D + 1)2
Fr 1
vs S s' S U(
12D(D + +1)'
12D +1)
By the simulation lemma (Lemma 9), get
V
V MRP| 2(D++2) 2)
max
(
+ 1ra20 Po
s.s'ESt
E 12D(D
< 2(D+2)
12D(D+1)
As in the proof of Lemma 11, let us consider different trajectories 7 that are possible in 2.g.... We can represent 7 (ST, 51, 5K,, s1, where the states 81.... are distinct and all except possibly 8, belong to Srch and the states after are just repeats $1 until the end of the episode. Let Sh. sh....., Sh2 be the same sequence (in the original MDP M) Again, we have
Part 2 VRR is close Va_
p (8T, 81,. ... , BR. 8 ......)]
Pd P" [ke], 7[h4] = Sher and Vh HH]f,, had. T(h] & Sz).
48

---

where recall that pa denotes probability under the V and P denotes the probability under trajectories drawn according to и in the underlying MDP: E and Ex are defined similarly. Furthermore, the expectation of rewards we collected in 2 with trajectories
E 2T [[(7) 51, , 3R,, -..---)) =E" [[ [k), r[h,] sh, and vh [HM hha 7[h] & S.
Next, we sum over all possible trajectories. However, note that the only trajectories that are possible in M whose corresponding trajectories not accounted for in D are precisely those that visit states in Sr, after visiting some 8h, in the remaining states S (since, by construction, the MRP transitions directly Ts after encountering a state Sa Thus,
MR (1 (r S = 0) + 1 ( [H]
Sh. S and vh > h1 8h $ Sx)),,
where the first term corresponds to trajectories that do not pass through S and the second term corresponds to trajectories that passes through state in Spem but then does not go through any other state in Sn. On the other hand,
V [*(Rr]]]
Clearly, VMRP I V" Furthermore, we also have
V" MRR E [R[r]
1
grem * 0]
E E
[M] Sha E S and vh 11 8h & S
< E [ Stem + 0]]
8 8
< D
4D 4
where the first inequality follows by just ignoring the second indicator term, and the second inequality follows by taking a union bound over all possible values of grem well the conclusion of Lemma 13.
Putting it all together, get that
VMRPl + 15 VRRPl - + E < 2
V
This concludes the proof of Lemma 14.
F.4 Proof of Theorem
We assume the events defined in Lemmas 10, 12 and 13 hold (which happens with probability at least
1 - 26). With our choices n1, n2 in Eq. (21), the total number of samples used in our algorithm
most
12HDE - 112
= (( (DDCCL))
II 5
71
K2
log
After the termination of the while loop, we know that for any policy II and Srem we have
E
(" -(e: <
40
Therefore, by Lemma 14, we know for every क E II, v मे E arg max, xx satisfies
V'
< E. Hence the output policy
max V V < 2$ V. V < 2s.
hell
Rescaling e by 2e and by 28 concludes the proof Theorem 4.
F.5 Sunflower Property Insufficient By Itself
We give an example of policy class IT for which the sunflower property holds for K, D = poly (H) but ((T)) 2H Therefore, in light of Theorem 2, the sunflower property by itself cannot ensure statistically efficient agnostic PAC RL in the online access model.
49

---

The example is as follows: Consider a binary tree MDP with 2 1 states and action space A {0, The policy class II will be able get to every (s,0) a) pair in layer H. To define the policies, we consider each possible trajectory == (1, 8H, as)) and let:
di if 8 T, otherwise,
TT (T)
o
Thus it is clear that C(1l) 2 but the sunflower property holds with K 1, D = H. by taking Horee = { (the policy which always picks = 0).
50

---

G Infinite Policy Classes
In this section we discuss the extensions our results to infinite policy classes.
G.1 Definitions and Preliminary Lemmas
We will state our results in terms of the Natarajan dimension, which is a generalization of the VC dimension used to study multiclass learning. We note that the results in this section could be stated in terms of other complexity measures from multiclass learning such as the graph dimension and DS dimension (see, e.g., Natarajan, 1989; Shalev-Shwartz and Ben-David, 2014; Daniely and Shalev- Shwartz, 2014; Brukhim et al., 2022a); for simplicity we analyze guarantees in terms the Natarajan dimension.
Definition 7 (Natarajan Dimension (Natarajan, 1989)). Let X' be an instance space and y be finite label space. Given class H S y* we define its Natarajan dimension, denoted Ndim to be the maximun cardinality of a set C C X that satisfies the following: there exists ho, h1 :C - y such that for all x & C, ha(x) + h1 (z), and for all C C, there exists h E H such that for all E B, h(x)= = ho(r) and for all C, h(()) h1 (z).
notation we will use throughout the projection operator. For hypothesis class H C y and a finite set X (I1, Inn) X", we define the projection of H. on to X as
H/ x == {(h(x)), ... h(xx)) h E H))
Lemma 15 (Sauer's Lemma for Natarajan Classes (Haussler and Long, 1995)), Given a hypothesis class H C yd with |V K and Ndim(H) S d, we have for every X (Z1,--) (nn) E X""
[neeK (K + 1)2
d
74 1
2d
Theorem 6 (Multiclass Fundamental Theorem (Shalev-Shward Shwartz and Ben-David, 2014)). For any class H. C yx with Ndim (H) = d and [3]| K, the minimax sample complexity of (e, 8) agnostic PAC learning H can be bounded as
d + log(1/5) 2
S en S o
( ddlog K + log(1/0)
22
e²
Definition (Pseudodimension). Let X be an instance space. Given a hypothesis class H. C Rt its pseudodimension, denoted Pdim(H{). is defined as Pdim(H) = VC(H+), where Ht {(x,6) 0) + 1()(z)= S 8} h E H}.
Definition (Covering Numbers). Given hypothesis class S. R > and X (I1,.". In) E X", the covering number (N(H, a, XX) is the minimum cardinality of set C' C R" such that for any h H. there exists a Cuch that Σn E;=1h((z))
c,l S a.
Lemma 16 (Jiang et al. (2017), see also Pollard (2012); Lue et al. (1996)). Let H C j0, 1] be a real- valued hypothesis class, and let X (x1, ,Ta) be ii.d samples drawn from some distribution 'D on X. Then for any a >> 0
na?
P sup
-(h())]]()]]] > S SEIW)((L, exp
NEW
n
128
Furthermore (P) < d then we have the bound
Σ M(x.)) [E(()) a < Se(d +
16e
na²
P sup hEA
.exp
128
which is at most 5 as long as
128 (dlog 16c + log(Sc(d 1)) log }))
G.2 Generative Model Lower Bound
First we address the lower bound. Observe that it is possible to achieve a lower bound that depends on Ndim(lI) with the following construction. First, identify the layer h e [H] such that the witnessing
51

---

set C' contains the maximal number of states in Sk; by pigeonhole principle there must be at least Ndim H such states in layer h. Then, we construct an MDP which "embeds" hard multiclass learning problem at layer over these states. A lower bound of 22 Ndim(TT) log } follows from Theorem 6.
By combining Theorem 2 with the above we get the following corollary.
Corollary 3 (Lower Bound for Generative Model with Infinite Policy Classes), For any policy class II, the minimax sample complexity (e, 6 learning II is at least
((II) + Ndim (d)m(II)HH log 8
ngenn II: 6, Ω
5²
Again, since the generative model setting is easier than online RL, this lower bound also extends to the online RL setting.
Our bound is additive in C(II) and Ndim(II); we do not know if it is possible to strengthen this to be a product of the two factors, as we will achieve in the upper bound in the next section.
G.3 Generative Model Upper Bound
For the upper bounds, we can replace the dependence on log with (II (and additional log factors). In particular, we can modify the analysis of the Trajectory Tree to account for infinite policy classes, Recall that our analysis of Trajectory Tree required us prove uniform convergence guarantee for the estimate 77; with probability at least - 6, for all æ E II, we have V V S e. We previously used union bound over [TT), which gave us the log [T] dependence. Now we sketch an argument to replace with (II.
Let T be the set of all possible trajectory trees. We introduce the notation oz T + R to denote the function that takes as input trajectory tree T (for example, sampled by Trajectory and returns the value of running ı on Then we can rewrite the desired uniform convergence guarantee:
w.p. at least 1 - 5, sup
(T:) - L ("
S
(28)
==1
In light of Lemma 16, we will compute the pseudodimension for the function class yil {uT n E I.I. Define the subgraph class
DI = { (T,,0) - 1f (0) 50 : Em c 10,
By definition, Pdim(V"l) VC(V Fix any (1) (Ta, 0a) (T Ryd. In order to show that VC(V & d for some value of d it suffices to prove that | |x| < 2d.
For any index E [d]. we also denote π (5;)) E (T)(( to be the vector of actions selected by क on all II-rachablee states in T; (of which there are most H C(IT)). We claim that
bu S ((((((5)). ((a)) III =: [
(29)
This is true because once the trajectory trees are fixed, for every π E II, the value of the vector / x E {0, 1]dd determined by the trajectory that æ takes in every trajectory tree. This in turn is determined by the assignment of actions to every reachable state in all the d trajectory trees, of which there are at most C(II) d of. Therefore, we can upper bound the size of III++ x by the
number of ways any
assign actions every state in Ti,... Ta.
Applying Lemma 15 to Eq. (29), we get that
He(MD)de e (A 1)+ Ndim(II)
111++ x <
2IIim(II)
52

---

For the choice of d = (Id)m the previous display is at most 2 thus proving the bound on Pdim Lastly, the bound can plugged back into Lemma 16 to get bound on the error of TrajectoryTrees Tree: the statement in Eq. (28) holds using
n = 1
He(u)
(TT + log
samples.
This in turn yields guarantee on मे returned by Trajectory
G.4 Online RL Upper Bound
The modified analysis for the online RI. upper bound (Theorem 4) proceeds similarly; we sketch the ideas below.
There are two places in the proof of Theorem which require union bound over []]] the event Eest (defined by Lemma 10) that the estimated transitions and rewards of the MRPs are close to their population versions, and the event Edata (defined by Lemma 12) that the datasets collected are large enough. The latter is easy to address, since we can simply modify the algorithm's 's while loop to break after O DC(I)
iterations and union bound over the size of the set [T] instead the worst-case
bound on the size DIIT]. For Edatas we follow similar strategy as the analysis for the generative model upper bound.
Fix state 8. Recall that the estimate for the probability transition kernel in the MDP in Eq. (19) takes the form
P 5
Σ Σ
18 ~M Thah' FED, [errel ExeHlo 1i o9 Thek'
1(7 E +(}}
[Da
(The analysis for the rewards is similar, omit it from this proof sketch.)
We set up some notation. Define the function p5- (S A R) + [Icooll as
1f Thck')
P (
1 E ( s')},
(30)
Meorll Ex.n..... 1 1 T
with the implicit restriction of the domain trajectories for which the denominator nonzero. We have Elp (T) = p...'. Also let II, = {I E :I:s sE Sz}.
Restated in this notation, our objective is to show the uniform convergence guarantee
w.p. at least 1 - 8, sup TEII,
(T)
S.
(31)
[D. rED.
Again, in light of Lemma 16, we need to compute the pseudodimension for the function class pll. = {pT : E II,, E Sz), since these are all possible transitions that we might use the dataset D. to evaluate. Define the subgraph class
pll., ((T,0) 1 (1% S 0) TT,
Fix the set X = ((T(((())))))))) ..)........... ... (Ta, 0a)} E ((S x A x RRdd where the trajectorics Tí, Ta pass through We also denote Sx to be the union of all states which appear in TI, Ta. In order to show a bound that Pdim I d suffices to prove that |pll..+ xx 2d.
We first observe that plll..t|
11
Σ (T) 00)...... ... 10 (Ta) S fd)) : T I.H))-
x
8'ESx
The inequality follows because for any choice s' & Sx, have
(1(T S 0.)..... 1p S 0z))
no matter what is, contributing most to the count. Furthermore, once we have fixed s' and the (-i.-.. Tab the quantities Meaae Ex 1 [T ~* Ty,hir) for every i E [d] are constant (do not
depend on x), so we can reparameterize 0f 0, I Er 1 (Te ~o Tr } to get:
pll.. 11 Σ ((bI(T),,.. ba(T)) IT},
(32)
e'ESx
53

---

where : := in Ta Hit E (x(s 0,).
Now we count how many values the vector (& (T).. .eb)).,,,bb()))) bu(T)) can take for different т E II Without loss of generality,
can (I) assume that the o 0 (since product of indicators can only take values in {0, 1), and 8' 2 1 then we must have bę(TT) = 1 for every T), and (2) [d] (otherwise bi(T)) 0 for every E IT). So { ~ Ti,hoh {T; E (x + 8²)}. For every fixed choice of s' we upper bound the size of the set
s' T. for each
rewrite (T)
(T),()) " ba(z)) E
[[((1( ~n TIAoh a  ~n Td,hih : E 11I
((((1 E Ex(s + 8')),"" 1(aa Es(s + +())) ITII
{{((t ( T() , ((6(())) n - x ((118000 100 E....... [ 1 (f))ames.))) t e
=
(AH c(A + 1)2 Ndii((1))
( 2N1
x (dH)
(33)
The inequality (i) follows by upper bounding by the Cartesian product. The incquality (ii) follows because (1) for the first term, the vector (I{ Ti ). ..... 1{
Td,tck }) is determined by
the number of possible behaviors π has over all dH states in the trajectories, and (2) for the second term, the vector (1 E (s
s')),... 1(Ta E (s dH states in the petal set for S.. The inequality (dit) follows by applying Lemma 15 to the first
s'))) is determined by which of the
term and Sauer's Lemma the second term, further noting that every petal S set has cardinality most D.
Combining Eqs. (32) and (33) we get the final bound that
ppll.t| xl $ + (dH))+1, ( (dH-e(A+I) e((+1)² Ndim(II) 211im(11)
To conclude the calculation, we observe that this bound is < 2d whenever d= Ō(D + (IIm, which we can again in conjunction with Lemma 16 to prove the desired uniform convergence statement found in Eq. (31). Ultimately this allows us replace the log| with Ö(D + Ndim(II)) in the upper bound of Theorem 4; the precise details are omitted.
H Connections to Other Complexity Measures
We show relationships between the spanning capacity and several other combinatorial measures of complexity.
For every h E [H] we denote the state space at layer h as S₁ == ($G.)) j E [K]} for some K E N. We will restrict ourselves to binary action spaces A = {0, 1}. but the definitions and results can be extended larger (but finite) action spaces. In addition, we will henceforth assume that all policy classes II under consideration satisfy the following stationarity assumption.
Assumption 1. The policy class II satisfies stationarity: for every E II we have
T()(,1) = n (
x((G,H)) for every j E [K].
For any E 11 and E [K], use (T] as shorthand to denote the value of (((().))) for every h.
The stationarity assumption is not required but is useful for simplifying the definitions and results.
H.1 Definitions and Relationships
First, we state several complexity measures in learning theory. For further discussion on these quantities, see (Foster et al., 2021c; Li et al., 2022).
Definition 10 (Combinatorial Eluder Dimension). Fix any stationary base policy म. The combi- natorial eluder dimension of II w.r.t. म, denoted dime (II; R), is the length of the longest sequence (j,, (1,1.)..... TN) such that for every E [N]:
Te(ie) * #(je), and Vk < l, Telix) #(ju).
54

---

We define the combinatorial eluder dimension of II as (ime@(I)) sun dimg R). Definition 11 (Star Number (Hanneke and Yang, 2015)). Fix any stationary base policy т. The star number of II w.r.t R. denoted dims (II; R). is the length of the longest sequence (f1, Ti)...., (JN, TN)
such that for every & E [
Te(je) * and vk + L, Te(in) #(ia)
We define the star number of II di == ren dims (TI; 7t.
Definition 12 (Threshold Dimension (Alon al., 2019; Li al., 2022)), Fix any stationary base policy n. The threshold dimension of II w.r.t. h, denoted dimy (II; 7), is the length of the longest sequence (11,T1),-. ..)...., TN) such that for every E [N]:
Vm 2 me(sm) + # (jm), and Ak Te(ia) 7 (je).
We define the threshold dimension of as (II = sun dint((I; (I:;
Relationships Between Complexity Measures. From (Li al., 2022, Theorem we have the relationship for every II:
max (dims (II), dimm((T) S dlimg()) (II S (I))
(34)
The lower bound is obvious from the definitions and in general cannot be improved: the upper bound also cannot be improved beyond constant factors in the exponent (Li al., 2022).
We also remark that it is clear from the definitions that VC dimension lower bound on all three (eluder, star, threshold); however, VC(II) can be arbitrarily smaller.
H.2 Bounds Spanning Capacity
Now we investigate bounds on the spanning capacity in terms of the aforementioned quantities.
Theorem 7. For any policy class II satisfying Assumption I we have
maxo min(sims (II), H 1}, 220os, dimr 2 C(II) < 2dine (II)
We give several remarks on Theorem 7. The proof is deferred to the following subsection.
is interesting understand what degree we can improve the bounds in Theorem On the lower bound side, we note that the each of the terms individually cannot be sharpened:
For the singleton class Hiing we have C(ILsing) = min K, + 1} and dims = K. For the threshold class Ihres == (T) 7 [ 2 i} E [K]]. when K is a power of two, can be shown that ((I min ( K, 2" and dimy (Ilthes)) K.
While we also provide upper bound in terms of dlimg(II), between the lower bound and the upper bound. In fact, our upper bound is likely very loose since we are not aware of any policy class for which the upper bound is non-vacuous, i.c. 2dime << min(2" [I1], 2K } (implying that our bound improves to understand how to improve the upper bound (possibly, to scale polynomially with dimg or more directly in terms of some function of (II)s(TT) and dimi (II);; we leave this as a direction for future research.
note that there can be huge gap
Proposition 3). It would be interesting
Lastly, remark that the lower bound of ((IT) > min min(A( (IT)). 24) } is generalization of previous bounds which show that linear policies cannot be learned with poly (f) sample complexity (e.g.. Du al., 2019b), since linear policies (even in 2 dimensions) have infinite threshold dimension.
*Our definition of the combinatorial eluder dimension comes from Li et al. (2022) and also called the "policy eluder dimension" in the paper Foster et (2021c). In particular, is defined with respect to a base function æ. This differs in spirit from the original definition (Russo and Van Roy, 2013) as well as the combinatorial variant (Mou et al., 2020), which for every l asks for witnessing pairs of policies me, n/. Our definition is never larger than the original version since require that a'e = be fixed for every E [N).
55

---

H.2.1 Proof of Theorem 7
We will prove each bound separately.
Star Number Lower Bound. Let E II and the sequence (ii, Si,, ...., (iN, TN) witness (II) = N. We construct a deterministic MDP M for which the cumulative reachability at layer Amax == min(N, H3 (Definition 1) is least min H + 1]. The transition dynamics of M are as follows; we will only specify the transitions until max (afterwards, the transitions can be arbitrary).
The starting state of M at layer h = is 8(1.1))
(On-Chain Transitions): For every h < hmaxx
[1fs' 8 + if a (s))
P(s (Un,))):)) 0)
(1(5-= -
if + (())))))
(Off-Chain Transitions): For every h hmmax state index j * jn. and action a E A,
P(s' (. -185 = s(,,+1)3 }
We now compute the cumulative reachability at layer mmmax IN S H. the the number of (s, a) pairs that II can reach in M is N (namely the pairs (S( 1),... ... (N), 1)). On the other hand, if N >>> H, then the number of (s, a) pairs that II can reach in M is H + (namely the pairs (8)..)); 1); ". (H), 1), (S(jn 0)). Thus we have shown that C(TT 2 min(N, H + 13.
Threshold Dimension Lower Bound. Let से E II and the sequence (i1, m)) (JN. TN) witness dimy (II) = N. We define a deterministic MDP M as follows. Set hmax = min [log2 NJ. H). Up until layer hmaax the MDP will be full binary tree of depth hmaxi afterward, the transitions will be arbitrary. It remains to assign state labels to the nodes of the binary tree (of which there are 2 1 < N). We claim that it is possible to do in way that every policy ne for E [2Ammxe] reaches a different state-action pair at layer /max- Therefore the cumulative reachability of II on M is at least 2/ = min (2 logg N1 21, as claimed.
It remains to prove the claim. The states of M are labeled j2. J2hmmax according to the order they are traversed using inorder traversal of full binary tree of depth hmax (Cormen et al., 2022). One can view the MDP M binary search tree where the action O corresponds to going left and the action I corresponds to going right. Furthermore, if we imagine that the leaves of the binary search tree at depth Amaa are labeled from left to right with the values 1.5, 2.5, ... 22hmax + 0.5, then it is clear that for any l E [2 the trajectory generated by running Te on M is exactly the path obtained by searching for the value é + 0.5 in the binary search tree. Thus we have shown that the
cumulative reachability of II on M is the number of leaves at depth Amax. thus proving the claim.
Eluder Dimension Upper Bound. Let dimg (II) N. We only need to prove this statement when N S H, as otherwise the statement already follows from Proposition 3. Let (M*, ) be the MDP and layer which witness C(IT). Also denote i to be the starting state of M For any state we denote childo (+) and child, (s) to be the states in the next layer which are reachable by taking a = and = 1 respectively.
For any reachable state at layer in the MDP M we define the function fs) as follows. For any state at layer h², we set f() == 1 if the state-action pairs (s, 0) and (s, 1) are both reachable by II; otherwise we set f(s) == O. For states in layers h h** we set
f f(s)= = (s)
(child((s)) +1
if both (s, 0) and (s, 1) are reachable by II,
if only (s, 0) is reachable by 11, if only (s, 1) is reachable by II.
(child) (s))
We claim that for any state s, the contribution to ((I)) by policies that pass through s is at most 20))) We prove this by induction. Clearly, the base case of [s) = 0 or (()) = 1 holds. only one child of a is reachable by IT then the contribution to C(IT) by policies that pass through equal to the
contribution to C(T)) by policies that pass through the child of If both children of a are reachable
by II then the contribution towards C(II) by policies that pass through is upper bounded by the
56

---

sum of the contribution towards ((II) by policies that pass through the two children, i.e. it is at most ((ch + (child < 2f(s), This concludes the inductive argument.
Now we bound f(1).. Observe that the quantity ((11 counts the maximum number of layers hi, ... hy that satisfy the following property: there exists a trajectory r = ($1, A1,'. -8 0.) for which we can find policies Ii, T ".. , so that each policy my when run on M (a) reaches She and (b) takes action TH (T( * Ohg- Thus, by definition of the eluder dimension we have f(s)) N. Therefore, we have shown that the cumulative reachability of II in M* is at most 2
I Extension: Can Expert Feedback Help in Agnostic PAC RL?
For several policy classes, the spanning capacity may be quite large, and our lower bounds (The- orem 2 and 3) demonstrate an unavoidable dependence on C(T). In this section, we investigate whether it is possible to achieve bounds which are independent of ((T)) and instead only depend on poly(A, H, log under a stronger feedback model.
Our motivation comes from practice. It is usually uncommon to learn from scratch: often we would like to utilize domain expertise or prior knowledge to learn with fewer samples. For example, during training one might have access to a simulator which can roll out trajectories to estimate the optimal value function Q*, or one might have access to expert advice/ demonstrations. However, this access does not come for free; estimating value functions with simulator requires some computation, or the "expert" might be human who is providing labels or feedback on the performance of the algorithm. Motivated by this, we consider additional feedback in the form of an expert oracle.
Definition 13 (Expert oracle). An expert oracle Oexp" S x A - R is a function which given an (s, a) pair as input returns the Q value of some expert policy nu, denoted Q=a (=,
Definition 13 is natural formulation for understanding how expert feedback can be used for agnostic RL in large state spaces. We do not require T, to be the optimal policy (either over the given policy class II over all AS). The objective is compete with n.. i.e., with probability at least 8, return a policy रे such that v 2 7T e using few online interactions with the MDP and calls to Oexp-
A sample efficient algorithm (one which uses at most (A, H, [ and calls to the oracle) must use both forms of access. Our lower bounds (Theorem 2 and 3) show that an algorithm which only uses online access to the MDP must use (IT( samples. Likewise, an algorithm which only queries the expert oracle must use ((SA) queries because it does not know the dynamics of the MDP, so the best it can do is just learn the optimal action every state.
online trajectories
Relationship to Prior Works. The oracle Oexp is closely related to several previously considered settings (Golowich and Moitra, 2022: Gupta et al., 2022: Amortila al., 2022). Prior work (Golowich and Moitra, 2022; Gupta et al., 2022) has studied tabular RL with inexact predictions for either the optimal Q* or V* They assume access to the entire table of values; since we study the agnostic RL setting with a large state space, we formalize access to predictions via the expert oracle. Amortila et al. (2022) study a related expert action oracle under the assumption of linear value functions. They show that in a generative model, with poly(d) resets and queries to an expert action oracle, one can learn an e-optimal policy, thus circumventing known hardness results for the linear value function setting. Up to factor of A, one can simulate queries to the expert action oracle by querying Oexp (s, a) for each a E A.
L.1 Upper Bound under Realizability
Under realizability (namely, T. E IT), it is known that the dependence on E(IT) can be entirely removed with few queries to the expert oracle.
Theorem 8. For any TI such that n. E TT, with probability at least 1 - 6, the Aggre algorithm (Ross and Bagnell, 2014) computes an e-optimal policy using
n1 = 0
H²H 62
log [II
online trajectories and n22 = 0
A²H² 22
II]
.log
calls to Oexp-
5
57

---

The proof is omitted; it can be found in (Ross and Bagnell, 2014: Agarwal et al., 2019). We also note that actually we require a slightly weaker oracle than oxxp the Aggre VaTe algorithm only queries the value of QT on (s, a) pairs which are encountered in online trajectories.
VaTe
1.2 Lower Bound in Agnostic Setting
Realizability of the expert policy used for Oexp a rather strong assumption in practice. For example, one might choose to parameterize II as a class of neural networks, but one would like to use human annotators to give expert feedback on the actions taken by the learner; here, unreasonable to assume that realizability of the expert policy holds.
We sketch a lower bound in Theorem 9 that shows that without realizability (n. & IT), we can do no better than (IT() queries to a generative model or queries to Oexp-
Theorem 9 (informal). For any H E N. C E [2*), there exists policy class IT with C(IT) I|| C, expert policy T. & II, and family of MDPs M with state space S of size )2 binary action space, and horizon H such that any algorithm that returns 1 1/4-optimal policy must either use SI(C) queries to a generative model or St(C) queries to the Oexp
Before sketching the proof, several remarks are in order.
By comparing with Theorem 8, Theorem 9 demonstrates that realizability of the expert policy is crucial for cireumventing the dependence spanning capacity via the expert oracle.
In the lower bound construction of Theorem 9, to is the optimal policy. Furthermore, while & II, the lower bound still has the property that V*a = V* = max V"; that is, the best-in-class policy गे == arg max V attains the same value as the optimal policy. This is possible because there exist multiple states for which (ss) # To (s), however these states have of (s) O. Thus, we also rule out guarantees of the form V max V* -E.
Since the oracle Oexp is stronger than the expert action oracle (Amortila et al., 2022) (up to factor of A), the lower bound extends this weaker feedback model. Investigating further assumptions that enable statistically tractable agnostic learning with expert feedback is an interesting direction for future work.
Proof Sketch of Theorem 9. We present the construction as well as intuition for the lower bound, leaving out formal cntermation-thhoreeee proof.
Construction of MDP Family, We describe the family of MDPs M. In every layer, the state space is Sn = [Sty.)) : J E [2^1], except at Sh where we have an additional terminating state, Sμ = (S( J E [2 U {8_). The action space is A = 10.
The MDP family .M = [Mo, beedd is parameterized by a bit sequence b E AA" -- 1 as
well as labeling function f* E AASH The size of M is 2 We now describe the transitions and rewards for any Mr. In the following, let St E SH-1 be the state that is reached by playing the sequence of actions (b(1). ((2). MHH - 2)) for the first
layers.
Transitions. For the first HI 2 layers, the transitions are the same for Ma. E M. At layer Hl 1,, the transition depends on
For any 21,,.... - 2], the transitions are deterministic and given by a tree process: namely
[1 =()---()) if 0, if =
P(s' ((),))
At layer H 1, for the state St. the transition is P(s' a) 11s = }1} for any a E A. For all other states, the transitions are uniform to Sh. i.e. for any E SH
A, the transition is P(- 1, a, Uniform(SH {(s1)).
Rewards. The rewards depend the b E H-1 and f ASn
58

---

The reward at layer H - 1 R(s,a) = 1fs Sb. b|H - 1]]
The reward at layer H is
a)) =0 R(s,a) = 1(a=
for any E A. for any / $18 0 A.
From the description the transitions and rewards, we can compute the value of Q' (;))).
Layers 1,.... H 2: For any s U u U USH-2 and a E A, the Q-value is (* =
Layer H 1: At 8b, the Q-value is (s,, a) 1aa b|H 1]}. For other states 8 E Su-i\\(>)) the Q-value Q" (s, a) = for any a E A.
Layer H: At 81, the Q-value is Q" (8) = for any A. For other states SHM[sh, the Q-value is (*, a) = 1(a f*(s))
Lastly, the optimal value is V* 1.
Expert Oracle. The oracle Oexp returns value (s,
Policy Class.
The policy class II is parameterized by bit sequences of length H - 1. Denote the function bin 10.1,...,2"* 21-11 + A that returns the binary representation of the input. Specifically,
= (mp {bin(i) : 10, C-1))
where each is defined such that (s) == b[h] if Sh, and mb(s) otherwise. By construction it is clear that (II) = II C.
Lower Bound Argument. Consider any Mo where b E (bin(i) : {0, 1.. ---CC-1) 1}} and f' E SHH There are two ways for the learner to identify a 1/4-optimal policy in Ma
Find the value b, and return the policy my which has V =
Estimate f f*, and return the policy of which picks arbitrary actions for any s e Si U. U...U SH-1 and picks mp(() = f(s) on 8 E Sn.
We claim that in any case, the learner must either use many samples from a generative model or many calls Oexp. First, observe that since the transitions and rewards layers 1,... known and identical for all Mr.g- E .M, querying the generative model on these states does not provide the learner with any information. Furthermore, layers 1, ... H 2, every (s, a) pair has Q*(ss a) = 1, so querying Oxxp on these (s, a) pairs also does not provide any information to the learner. Thus, we consider learners which query the generative model or the expert oracle at states in layers H and H.
2
In order identify b, the learner must identify which (s, a) pair layer H achieves reward of 1. They can do this either by (1) querying the generative model at a particular (s, a) pair and observing r(s, a) (or if the transition goes s)); (2) querying Oexp particular (s, a) pair and observing if Q" (s, a) = 0 (which informs the learner that sp = and b[ll - = - a). In either case, the learner must expend ((C') queries in total order identify
To learn f*, the learner must solve a supervised learning problem over SH'SH (ss They can learn the identity of f* by querying either the generative model or the expert oracle on SH. Due to classical supervised learning lower bounds, learning f" requires Ω ((VC(AA())) 52(2H) queries.
D
59

---

J Technical Tools
Lemma 17 (Hoeffding's Inequality). Let -,, Zn be independent bounded random variables with Zi E (a, for all E [n]] Then
2nt²
P
2
- E|2,1l 2 -
S 2 exp
(00=))3
a)²
Lemma 18 (Multiplicative Chernoff Bound). Let -,. Zn be i..dd random variables taking values in {0, 13 with expectation p. Then for any 8 >
]
82
P
Zz 2 (1+
S exp
n
2
Furthermore for any E (0,
52pmm
P
(1-
2,
cxxp
7
60


Reviews:
[{"review_id": "oKJpQ8AlLm", "reviewer": "Reviewer_yJrU", "summary": "This work studies agnostic learning in RL, and seeks to characterize when, given some policy class $\\Pi$, it is possible to learn an $\\epsilon$-optimal policy in $\\Pi$ regardless of the MDP. They propose a novel complexity measure—the spanning capacity—which depends only on the policy class $\\Pi$ (i.e. is independent of the underlying MDP) which they show is both a necessary and sufficient measure of learnability when the learner has generative access to the MDP. In the fully online setting, however, it is shown that the spanning capacity is no longer a sufficient measure of capacity. To characterize efficient learning in the online setting, they introduce the notion of a ``sunflower’’ policy class, and show that if a policy class has bounded spanning capacity and is a sunflower class, then efficient learning is possible in the online setting as well. ", "questions": "1. The DEC [4] is a recently proposed measure of complexity that applies in the realizable setting. While the setting considered here does not assume realizability, and so is not directly comparable to the DEC, some comparison with the DEC would be helpful. In particular, one could apply the DEC to the model class $\\mathcal{M}$ the set of all MDPs with no more than $S$ states, $A$ actions, and horizon $H$ (and with the decision space set to the given policy class $\\Pi$). One would get realizability for free in this setting, so the characterization given by the DEC could be compared to the spanning capacity. How would the DEC scale with this choice of $\\mathcal{M}$ for the policy classes presented on lines 200-204? \n\n2. Are there examples where $S$ and $H$ are both large, the policy set is reasonably expressive (e.g. it contains an $\\epsilon$-optimal policy for a reasonable class of MDPs), and the spanning capacity is bounded? For example, say we have some featurization $\\phi(s,a) \\in \\mathbb{R}^d$, and our class $\\Pi$ is defined as $\\Pi = ( \\pi^w \\ : \\ w \\in \\mathcal{W} )$ for $\\pi^w(s) = argmax_{a} \\phi(s,a)^\\top w$ and $\\mathcal{W}$, for example, a cover of $\\mathbb{R}^d$. Can the spanning capacity be shown to scale polynomially with $d$ in this case, or is the best that can be shown still the bounds given in Proposition 3? It is known that smoothed versions of such policy classes are sufficient for settings such as linear MDPs when $\\mathcal{W}$ is an $\\epsilon$-cover of $\\mathbb{R}^d$ (that is, such a policy class can be shown to contain an $\\epsilon$-optimal policy class for any linear MDP), so if the spanning capacity is bounded by $poly(d)$ in this case (even though $|\\Pi|$ scales exponentially in $d$) would provide a compelling large state-space example where spanning capacity scales reasonably. \n\n[4] Foster, Dylan J., et al. \"The statistical complexity of interactive decision making.\" arXiv preprint arXiv:2112.13487 (2021).", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. I believe this work makes an interesting and novel contribution to the RL literature. There has been much interest over the last several years in developing general complexity measures that characterize when efficient learning in RL is possible, but existing work has typically made stronger assumptions—for example, access to a model or value function class where realizability holds (i.e. the true model/value function is in the class)—than this work, which does not assume realizability, and simply considers the question of finding the best policy in some set of policies.\n2. The results in this work show that there is a formal separation between the generative model setting and online access setting in policy learning framework considered here. To my knowledge, such a result has not been previously known, and is an interesting observation. \n3. In the generative setting, the characterization given by the spanning capacity is very clean: for any policy class $\\Pi$, efficient learning is possible if and only if the spanning capacity is small. While this is minimax over MDPs (see below), it is not minimax over policy classes—it applies to any policy class. \n4. The spanning capacity is a very intuitive measure of complexity and admits a clean interpretation.\n5. The paper is very well-written and reads very nicely. ", "weaknesses": "1. While the spanning capacity does provide a clean characterization of the learnability of a given policy class, it is a very worst-case measure over problem instances. It could be the case that the spanning capacity of a given policy class is very large, implying that efficient learning is not possible in general with the given policy class, but where on many MDPs efficient learning with the given policy class is still possible. In particular, for the spanning capacity to be large, there only needs to exist a single deterministic MDP for which it is difficult to find the optimal policy in class on—there could be many MDPs where it is very easy to find the optimal policy in class on, but this is not captured by the spanning capacity. In contrast, in practice we are typically interested not just in the policy class but the interaction between the policy class and the underlying dynamics of the MDP, as this characterizes how feasible it is to actually learn a good policy for a given problem. Due to this worst-case nature, for settings with large state or action spaces, the examples given of policy classes with bounded spanning capacity are very simple and not representative of the sorts of policy classes that would actually be used (in theory or practice). \n2. While it is shown that the sunflower condition is a sufficient condition for learning in the online setting, it is not clear it is a necessary condition (and furthermore, the scaling on $(K,D)$ given in Theorem 4 is likely not tight). Some discussion of this would be helpful. \n3. In principle, ignoring computation cost, I believe the optimal values of $K$ and $D$ for Theorem 4 could be computed a priori (before interacting with the MDP). This would be helpful to clarify around Theorem 4 (in particular on lines 296-298). Since POPLER takes as input $K$ and $D$, the bounded stated in Theorem 4 cannot be optimized for $K$ and $D$ after the fact, but can be optimized if the optimal $K$ and $D$ are computed before running POPLER (I found this somewhat unclear from the discussion on 296-298).\n4. I understand that the main contributions of this paper are statistical, but it would still be helpful to comment on the computational efficiency of the proposed algorithms.\n5. Several additional papers that should be cited: [1] also considers agnostic RL (albeit with stronger assumptions on the realizability of the model class). [2,3] are additional works on RL with function approximation that are generally relevant to this work.\n6. Minor typo: line 103 should read “access” not “saccess”. \n\n[1] Wagenmaker, Andrew, and Kevin G. Jamieson. \"Instance-dependent near-optimal policy identification in linear mdps via online experiment design.\" Advances in Neural Information Processing Systems 35 (2022): 5968-5981.\n\n[2] Foster, Dylan J., Noah Golowich, and Yanjun Han. \"Tight guarantees for interactive decision making with the decision-estimation coefficient.\" arXiv preprint arXiv:2301.08215 (2023).\n\n[3] Zhong, Han, et al. \"GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond.\" CoRR (2022).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and time. Below we respond to your questions and points.\n\n**Spanning Capacity is Worst-Case.**\nWe agree with the reviewer that spanning capacity is a worst-case notion, much like classic learning theoretic quantities like VC dimension and Littlestone dimension. \n\nIn fact, understanding complexity measures that depend on the model class (and thus implicitly the policy class corresponding to optimal policies for those models) is already an active area of research in the RL theory community (see our Appendix A for several representative papers). On the other hand, our work considers the other extreme when the learner only has access to a policy class. This approach, to the best of our knowledge, is not well-studied in the RL theory community, and our work is the first to consider (worst-case) *structural* assumptions on the policy class.\n\nUnderstanding the complexity of restricting to both specific model classes and policy classes is an important direction in RL theory, and we see our work as taking a step towards that direction.\n\n**Unclear if Sunflower Property is Necessary.** We address this concern, along with other questions/points on the sunflower property, in a joint response to all the reviewers. Furthermore, we note that we did not focus on optimizing the polynomial dependence on $D, K$, and $1/\\epsilon$ in our Theorem 4. \n\n**On $(K,D)$ in Theorem 4.** We apologize for any confusion. The reviewer is correct that leaving computation aside, the optimal choices of $K$ and $D$ can be computed a priori (before running POPLER) by explicitly enumerating over all possible choices for $\\Pi\\_\\mathrm{core}$ and $\\\\{ \\mathcal{S}\\_\\pi  \\\\}_{\\pi \\in \\Pi}$ and finding the best values of $K$ and $D$ that optimize the bound in Theorem 4. We will clarify this in the final version. \n\n**Computational Complexity of Our Algorithms.** Given $K$, $D$, $\\Pi\\_{\\mathrm{core}}$, the sets $\\\\{\\mathcal{S}\\_{\\pi}\\\\}\\_{\\pi \\in \\Pi}$, our algorithm POPLER has running time that scales polynomially with $|\\Pi|$ as well as $S, A, H$, which we agree is prohibitive for large scale RL problems appearing in practice. However, as the reviewers also noted, our focus in this paper is to understand the statistical complexity of agnostic RL, which is the first step towards getting practical algorithms in agnostic RL and to the best of our knowledge has not been explored before. Getting computationally or oracle-efficient algorithms for agnostic RL is a fascinating direction for future research. \n\n**Additional References.** We thank the reviewer for the additional references, which will be incorporated into the final version.\n\n**Relationship to DEC.** Let $\\mathrm{Dec}(\\mathcal{M}; \\Pi)$ denote the DEC of the model class $\\mathcal{M}$ consisting of all stochastic MDPs (with state space S and action space A) and decision class $\\Pi$. Let $\\mathfrak{C}(\\Pi)$ denote the spanning capacity of $\\Pi$. Further, for the sake of comparison, assume that $\\epsilon = O(1)$ and ignore constant and $H$ dependent factors. On the upper bound side, we have that $\\mathrm{Dec}(\\mathcal{M}; \\Pi) \\leq \\mathfrak{C}(\\Pi)$. This is because: \n\n- As suggested by Xie et al. 2022, $\\mathrm{Dec}(\\mathcal{M}; \\Pi)$ is upper-bounded by the worst-case coverage of any MDP in $\\mathcal{M}$ with decisions limited to $\\Pi$. (see Section 6.1 in their paper for details). \n- As proved in our Lemma 1, $\\mathfrak{C}(\\Pi)$ is equal to the worst-case coverage of any $\\mathcal{M}$ with decisions limited to $\\Pi$. \n- The two results together imply that the DEC is upper bounded by the spanning capacity. \n\nOn the lower bound side, it is not clear if $\\mathfrak{C}(\\Pi) \\leq \\mathrm{Dec}(\\mathcal{M}; \\Pi)$. A direct comparison of our results with those for Foster et al. 2021 with the model class $\\mathcal{M}$ and decision space $\\Pi$ is not fruitful. On the one hand, our Theorem 2 suggests that the lower bound for Agnostic RL scales as $\\mathfrak{C}(\\Pi)$. On the other hand, Foster et al. 2021 obtain an upper bound of $\\mathrm{Dec}(\\mathcal{M}; \\Pi) \\log(|\\mathcal{M}|)$ samples. Comparing the two establishes $\\mathfrak{C}(\\Pi) \\leq \\mathrm{Dec}(\\mathcal{M}; \\Pi) \\log(|\\mathcal{M}|)$ which is a vacuous comparison as  $\\log(|\\mathcal{M}|) \\propto |\\mathcal{S}|$ could be prohibitively large for the set of all stochastic MDPs. \n\n\n**Examples of Expressive Policy Classes with Bounded Spanning Capacity.** Since spanning capacity is a worst-case measure, many natural examples do not admit policy classes with bounded spanning capacity. For the class of ``linear policies'' that the reviewer asked about, from the prior works, we know that:\n\n  - Linear MDP assumption + linear policy class: it is possible to find an $\\epsilon$-optimal policy in $\\mathrm{poly}(d)$ samples (see Theorem 3.1 of [1]).\n  - Linear policy class: if we don't assume some form of realizability (either of the dynamics class or value functions), there is an exponential in $H$ lower bound (see Theorem 4.3 of [2]).\n\nIn fact, we can show, more generally, that any policy class with large threshold dimension (a learning theoretic dimension which is qualitatively equivalent to Littlestone dimension) must also have a large spanning capacity. This recovers the exponential in $H$ lower bound in [2] for linear policies. We will add more details discussing this in the final version. \n\n[1] Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan. \"Provably Efficient Reinforcement Learning with Linear Function Approximation.\"\n\n[2] Simon S. Du, Sham M. Kakade, Ruosong Wang, Lin F. Yang. \"Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?\""}, {"review_id": "JeEOH61Hvn", "reviewer": "Reviewer_Gfxz", "summary": "This paper studies conditions on which agnostic reinforcement learning is statistically tractable. The paper introduces a new concept of complexity measure called spanning capacity, which sorely depends on the policy class. The authors studies in what cases the sample complexity of agnostic RL can be polynomial to spanning capacity.\nThe contributions include 1) for generative model, the authors show spanning capacity is a necessary and sufficient complexity measure for agnostic RL, 2) for online model, the authors show spanning capacity is insufficient: they prove a lower bound superpolynomial to the spanning capacity of policy class. 3) the authors propose a strong assumption of the policy class called sunflower structure, and propose an algorithm that is statistically efficient to spanning capacity under the sunflower structure assumption.", "questions": "- in Definition 2, how is the second equation established? It is not clear to me how to make the inf on $\\mu$ to the sum on $(s,a)$ pairs.\n- It seems coverability coefficient is always no larger than the span capability. Is coverability a sufficient complexity measure for generative model? Moreover, I note that the authors claim coverability is insufficient for online RL. However, considering that spanning capability is also insufficient for online RL, where is the key difference.\n- in appendix Lemma 2(1), what does $N$ means. The authors have not introduced this notation in Section E.\n\n\nOne minor error: in appendix Line 865 and 867, it should be $j\\in [2^{2H}]$ instead of $j\\in [2^{H}]$.\n\n", "limitations": "Theoretical work. No limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clarify: the paper is very well-written. I appreciate the intuitions and examples given in the main text. In addition, the proofs in the appendix are well organized and easy to follow.\n- Novelty and Significance: While prior work has studied the sample complexity for RL problems, what assumptions are sufficient or necessary for statistically efficient is still not clear. The concept spanning capability is new and reasonable to me.\n- Technical correctness: I didn’t find any technical errors in the proofs included in the appendix, but I admit I was not able to go through all the details in the appendix. ", "weaknesses": "- The (K,D)-sunflower structure is an overly strong assumption and not reasonable enough. It seems to only work when there is a small subset of policies (so K is small) that covers most states (so D is small). \n- Although Algorithm 1 is sample efficient and only needs to collect polynomial trajectotires, the algorithm itself is not efficient: the algorithm needs to traverse all policies in $\\Pi$ to find the policy that can reach states which cannot be reached by $\\Pi_{\\text{core}}$. The complexity of Algorithm 1 is at least $O(|\\Pi|)$.\n- For Theorem 4, it seems the sample complexity is about $O({1}/{\\epsilon^4})$, which is not optimal on the order of $\\epsilon$. This also implies the sample complexity will be larger than $\\widetilde{\\mathcal{O}} (\\min\\{A^H. |\\Pi|, HSA\\}/\\epsilon^2)$ when $\\epsilon$ is small enough.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and time. Below we respond to your questions and points.\n\n**The Sunflower Property is Overly Strong.** \nWe address this concern, along with other questions/points on the sunflower property, in a joint response to all the reviewers.\n\n**Regarding Definition 2.**\nThe equivalence in the second equation follows by setting $\\mu\\_h(s,a) \\propto \\max\\_{\\pi \\in \\Pi} d^\\pi\\_h(s,a)$. This result was established in the prior work [1] in their Lemma 3. We refer the reviewer to look at [1] for a detailed proof and more intuition.\n\n**Is Coverability Sufficient for Generative Model?** \nWe do not know, but we conjecture that one can show that coverability itself is insufficient when $\\mathfrak{C}(\\Pi)$ is large, i.e., one cannot adapt to ``easy'' instances. It may be possible to provide such a lower bound using low-rank MDPs (for example, see the lower bound construction in [2]).\n\nA related point: for online RL, we can actually replace $\\mathfrak{C}(\\Pi)$ by the smaller coverability coefficient in the theorem. However, in this setting, we need to make the additional sunflower property assumption.\n\nUnderstanding when we can get guarantees in terms of coverability (or similar instance-dependent measures) is an exciting direction for future work.\n\n**Lemma 2 (1)** This is a typo. Here, $N$ denotes the size of $\\Pi^{(\\ell)}$.\n\n**Minor Error.** Yes, you are correct. This mistake is made in a couple of places, and we will correct it.\n\n[1] Tengyang Xie, Dylan J. Foster, Yu Bai, Nan Jiang, Sham M. Kakade. \"The Role of Coverage in Online Reinforcement Learning\".\n\n[2] Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, Karthik Sridharan. \"Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations\"."}, {"review_id": "go3Zo0bU40", "reviewer": "Reviewer_c49B", "summary": "This paper studies the minimax sample complexity of learning the best policy within a given policy class $\\Pi$, i.e., the best sample complexity of learning $\\argmax_{\\pi\\in \\Pi}V^\\pi$ in the worst-case MDPs. As a motivation, Proposition 1 shows that without future assumptions on the structure of $\\Pi$, the best policy is not PAC-learnable in the worst case MDPs. Hence, this paper proposes a new complexity measure, spanning capacity, that counts maximum number of reachable states by policies in $\\Pi$ for all deterministic MDP. With generative models, this paper shows that the spanning capacity characterizes the minimax sample complexity of learning $\\Pi$. For online RL, this paper requires an additional structural assumption called sunflower property and proves corresponding upper bounds.", "questions": "-\tAlg. 1 takes as input the set $S_\\pi$ and $\\Pi_{core}$ defined by Def. 3. They depend on the underlying MDP (because the partial trajectory is generated by the MDP, if I understand correctly). Is the algorithm assumed to have the knowledge of $S_\\pi$ and $\\Pi_{core}$? If not, how should the algorithm compute $S_\\pi$ and $\\Pi_{core}$?\n\n-\tIn Theorem 3, the spanning capacity is $H^{O(\\ell)}$, while the sample complexity lower bound is $\\epsilon^{-\\ell}$ with $\\epsilon=H^{O(1)}$, which means that the sample complexity lower bound is polynomial in the spanning capacity. Then why is the spanning capacity not sufficient to characterize the minimax sample complexity?\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper studies a novel aspect of PAC learning in MDPs (called agnostic reinforcement learning) --- learning the best policy within a policy class with no modeling assumptions for the dynamics or value function class. The agnostic reinforcement learning problem could be a new approach toward RL with function approximations since the realizability assumptions on the complicated dynamics/value function class are no longer needed, and it is indeed unclear whether those assumptions hold for practical environments.\n\nThis paper proves novel upper bounds agnostic reinforcement learning setting by introducing a new complexity measure called the spanning capacity. With generative models, this paper proves that the spanning capacity is necessary and sufficient for agonistic reinforcement learning. This is morally a strong result albeit the simplicity of its proof. This paper also proves results for the classic online RL setting with additional structural assumptions on the underlying MDP. \n\nThis paper is well-written --- exposition of the results is clear with the help of concrete examples. The results and assumptions in this paper are well motivated by corresponding lower bounds (Proposition 1 and Theorem 2). \n\nThis paper mainly focuses on the minimax complexity of agonistic RL. While this perspective eliminates the dependence on the realizability assumptions on the underlying MDP, it is possible that the resulting complexity is over-pessimistic. It would be interesting to have an instance-dependent complexity measure that depends on some property of the underlying MDP.\n", "weaknesses": "The sunflower structure in Section 6 lacks necessary motivations and seems a bit out of nowhere. I understand that this assumption helps extend the IS technique to the online RL setting. However, it’s unclear to me whether this assumption is necessary/nature for agonistic RL. Intuitively, why/when should we expect the sunflower structure to hold?\n\n[Minor] The computation complexity of the algorithm is linear in the size of the policy class. Is it possible to have some efficient implementation with the help of some standard computation oracles?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and time. We respond to your questions and points below.\n\n**Sunflower Structure Lacks Motivation.** We address this concern, along with other questions/points on the sunflower property, in a joint response to all the reviewers. \n\n**Computational Complexity.** Yes, the reviewer is correct that our algorithm POPLER will have computational complexity which depends polynomially on $|\\Pi|$, which is prohibitively large for practical RL scenarios. Getting computationally or oracle-efficient algorithms for agnostic RL is a fascinating direction for future research.\n\n**The sets $\\mathcal{S}\\_\\pi$ and $\\Pi\\_{\\mathrm{core}}$.** We apologize for any confusion. We would like to correct the reviewer here: the sets $\\\\{\\mathcal{S}\\_\\pi \\\\}\\_{\\pi \\in \\Pi}$ and $\\Pi\\_{\\mathrm{core}}$ do not depend on the underlying MDP dynamics, but only on the policy class $\\Pi$ (as well as $\\mathcal{S}, \\mathcal{A}, H$). The partial trajectories in Definition 3 can be arbitrary as long as they are consistent with the policy. \n\nWe can assume that POPLER takes as input  $\\\\{\\mathcal{S}\\_\\pi \\\\}\\_{\\pi \\in \\Pi}$ and $\\Pi\\_{\\mathrm{core}}$ because these sets can be computed before by enumerating over all possible choices, and picking the ones which optimize the bound in Theorem 4. This point will be clarified in the final version.\n\n**The Sample Complexity Lower Bound.** We thank the reviewer for pointing out this issue. This can be fixed by expanding the range of acceptable $\\epsilon$ and $\\ell$. Here is an updated version of Theorem 3.\n\n**Theorem 3.** *Fix any sufficiently large $H$. Let $\\epsilon \\in (1/2^{O(H)}, O(1/H))$ and $\\ell \\in \\\\{2, 3, \\dots, H\\\\}$ such that $1/\\epsilon^\\ell \\le 2^H$. There exists a policy class $\\Pi$ of size $O(1/\\epsilon^\\ell)$ with $\\mathfrak{C}(\\Pi) \\le O(H^{4\\ell + 2})$ and a family of MDPs $\\mathcal{M}$ with state space $\\mathcal{S}$ of size $2^{O(H)}$, binary action space, and horizon $H$ such that: for any $(\\epsilon, 1/8)$-PAC algorithm, there exists an $M \\in \\mathcal{M}$ for which the algorithm must collect at least $\\Omega(\\min \\\\{ 1/\\epsilon^\\ell, 2^{H/3}\\\\})$ online trajectories in expectation.*\n\nTo interpret this result, let us pick $\\epsilon = 1/2^{\\sqrt{H}}$ and $\\ell = \\sqrt{H}$. Then we get the following corollary, which demonstrates that the sample complexity for learning this class cannot be a polynomial function of $\\mathfrak{C}(\\Pi)$, $\\epsilon$, and $\\log |\\Pi|$.\n\n**Corollary.** *For any sufficiently large $H$, there exists a policy class $\\Pi$ with $\\mathfrak{C}(\\Pi) = 2^{O(\\sqrt{H} \\log H)}$ such that for any $(1/2^{\\sqrt{H}}, 1/8)$ PAC algorithm, there exists an MDP for which the algorithm must collect at least $2^{\\Omega(H)}$ online trajectories in expectation.*\n\nWe will include this correction in the final version of the paper."}, {"review_id": "s46o29DXcf", "reviewer": "Reviewer_HA2Z", "summary": "The authors study the problem of sample complexity in finite horizon MDPs from an agnostic perspective. More specifically, the term agnostic refers to the following setting: given a (finite) policy class $\\Pi$, they aim at understanding the number of samples that are required to output a policy that is $\\epsilon$-optimal w.r.t. the best policy within $\\Pi$ is. \n\nTo study the problem, they introduce the concept of *spanning capacity*, a novel complexity metric that depends solely on $\\Pi$ and is independent of the MDP dynamics. \n\nThen, the authors study two interaction settings (i.e., generative model and online setting) and derive the following results:\n- Generative model setting. The authors show that the spanning capacity describes the learning complexity up to an $H \\log(|\\Pi|)$ factor. This is proven by deriving lower and upper bounds that are explicitly dependent on the spanning capacity.\n- Online setting. In this case, the results can be summarized as follows:\n    - The spanning capacity fails at describing the complexity of online RL. Indeed, the authors present a lower bound that shows that a superpolynomial-in-the-horizon number of samples are still needed for agnostic learning (i.e., it cannot be lower-bounded by any polynomial function of the spanning capacity). \n    - By restricting the set $\\Pi$ to \"sunflower\" policies, provably efficient learning is possible. In this sense, the authors propose POPLER, an algorithm whose complexity scales with the spanning capacity and characteristic that depends on the structure of $\\Pi$.\n\n", "questions": "1) I invite the authors to discuss the relationship between their work and problem-dependent learning complexity analysis (e.g., \"Optimistic PAC RL: the instance-dependent view\", Tirinzoni et al., ALT 2023). \n\n2) See the point on sunflower policies in the weakness section.", "limitations": "The authors discuss the limitations of their work as open questions in the conclusion section.\n\nPotential negative societal impact: the paper deals with foundational research on the sample complexity of RL. I don't see a direct path to negative applications. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Provably efficient learning is a significant and open problem for RL agents, with a longstanding history of different methods and approaches. The authors thoroughly review existing works (Appendix A) and properly contextualize their results within the field. \nIn this sense, novel ideas, such as the ones proposed by the authors, are of interest to the NeurIPS community that is interested in RL theory. \n\nMore specifically, the notion of spanning capacity is, to the best of my knowledge, original and of potential interest. \nIndeed:\n1) As the authors show in Proposition 3, this metric recovers, in worst-case scenarios, existing upper and lower bounds available in the literature. Furthermore, in more favorable settings, it is significantly smaller. \n2) Furthermore, as the author shows in Theorem 1 and 2, it describes the min-max sample complexity (up to H*log(\\Pi) factors) in the generative model setting. Although, due to this mismatch, the problem is still open, the progress remains significant. \n\nIn the online interaction setting, this metric turns out to be not descriptive enough (i.e., Theorem 5, a superpolynomial-in-the-horizon number of samples are still needed for agnostic learning). Although, in some sense, this is a drawback (see weaknesses below), this negative result can potentially provide insights to guide future research in metrics that properly describe provably efficient agnostic RL in online settings. \n\nFinally, (minor) by carefully restricting the set of policies, the authors are able to show that the spanning capacity can be used to upper-bound the complexity in the online setting as well. This adds an additional (but minor, see below why) point in favor of the spanning capacity. \n\nOn the clarity. Overall, the paper is a nice read, and it is relatively easy to follow (except a minor suggestion, see below).\n", "weaknesses": "**Online RL**\nAs commented above, the authors show that the spanning capacity turns out to be not descriptive enough for providing polynomial bounds on the sample complexity of agnostic RL in an online interaction setting. Nevertheless, the metric is in itself something that the authors propose. For this reason, one might object that this is a potential drawback of the metric that is *designed* by the authors. \nA main question, in this sense, remains open: Is there any metric (e.g., a generalization of the spanning capacity) that characterizes both scenarios? \n\n\n**On sunflower policies: online RL under restrictive assumptions on $\\Pi$**\nCurrently, this point seems the major weakness of the presented work. Indeed, I find their definition quite involved, and it is unclear if it is the result of an artifact of the analysis rather than something necessary to reach polynomial sample complexity in the online setting. The fact that a lower bound is missing reinforces this doubt. I invite the authors to comment on this point. \n\n\n**On the clarity**. I would suggest the authors to improve the clarity on line 206-213, maybe by introducing some figures. Indeed, I still miss this natural interpretation of the spanning capacity. \n\n\n**Minors**:\n- The term \"surprising\" to refer to the mismatch between online RL and the generative model setting might be mitigated. Indeed, the generative model setting is intuitively easier.\n- It is remarked multiple times that other works make stronger assumptions that are rarely satisfied in practice (e.g., realizability). Nevertheless, stronger theoretical results (\\epsilon-optimality) are usually achieved under these assumptions. This should be stated more clearly in my opinion. \n- line 176 typo: \"loogmk\"\n- The definition of the set of MDPs seems improper. To the best of my understanding, state, and action spaces are fixed over this class. In this sense, e.g., M^sto is not the set of all MDPs with horizon H, but the set of all MDPs with horizon H and state-action spaces given by (S,A)\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and time. Below we respond to your points and questions.\n\n**A Metric that Characterizes Both Scenarios.** To the best of our knowledge, there is no metric that captures the complexity of agnostic PAC RL in both generative and online RL settings. We introduced and investigated spanning complexity because: \n\n- It is the right complexity measure in the generative model setting.\n- Since online RL is at least as hard as RL with a generative model, spanning complexity also lower bounds the sample complexity in online RL. \n- It is closely related to the notion of coverability, which was introduced in prior work [1] for realizable value-function based RL.\n\nWe view this as an important question for future research.\n\n**Sunflower Property.** We address this concern, along with other questions/points on the sunflower property, in a joint response to all the reviewers. \n\n**A Natural Interpretation of the Spanning Capacity.** In the final version, we will include a clearer exposition of the spanning capacity, as well as figures that illustrate it.\n\n\n**Separation between Online RL and Generative Model.** In light of our results in Section 4, it was natural to conjecture that spanning capacity also characterized online RL. Indeed, this was true for many nontrivial policy classes we considered.\n\nWe agree with the reviewer that the generative model is intuitively easier, since one can simulate online RL with a generative model. However, separation results between the generative model and online RL are exceedingly rare, and in this sense we view this separation as ``surprising''. In fact, the only policy classes for which we can show a separation are the nonexplicit constructions from Theorem 3 based on the probabilistic method  (specifically, see our Lemma 4).\n\n**Definition of Set of MDPS.** You are correct, we will clarify this in our revision.\n\n**Comparison to Problem-Dependent Learning.** We thank the reviewer for bringing [2] to our attention. Please find below a summary of the key differences: \n\n- [2] studies instance-dependent guarantees for tabular RL. Their bounds depend on the suboptimality gaps as well as reachability probabilities. Furthermore, their bound in Theorem 2 has a linear dependence on $|\\mathcal{S}|$, the state space size. In contrast, our work focuses on the large state space setting where we do not want any extraneous dependence on the state space size. We also do not investigate instance-dependent bounds. It would be interesting to see if POPLER can be adapted to achieve refined instance-dependent bounds.\n- Algorithmically, the work [2] uses an optimism-based approach. In contrast, POPLER is based on reachable state identification. In this sense, POPLER is actually more similar to MOCA [3], which studies instance-dependent PAC RL for tabular (again, note that we work in the more general large state space setting, which necessitates technical innovations for efficient exploration). \n\nWe will add a citation to [2, 3], and a more detailed comparison, in the final version of the paper.\n\n[1] Tengyang Xie, Dylan J. Foster, Yu Bai, Nan Jiang, Sham M. Kakade. \"The Role of Coverage in Online Reinforcement Learning\".\n\n[2] Andrea Tirinzoni, Aymen Al-Marjani, Emilie Kaufmann. \"Optimistic PAC Reinforcement Learning: the Instance-Dependent View.\"\n\n[3] Andrew Wagenmaker, Max Simchowitz, Kevin Jamieson. \"Beyond No Regret: Instance-Dependent PAC Reinforcement Learning.\""}]

Author rebuttal:
We thank all the reviewers for their time and valuable feedback. Since concerns about the sunflower property were raised by all the reviewers, please find a shared response below. If you have any further concerns, please let us know, and we would love to discuss further.

**Necessity of the Sunflower Property.** While we show that the sunflower property is sufficient (in addition to bounded spanning capacity), we do not know if the sunflower property is also necessary for agnostic PAC RL in the online interaction model. However, we believe that it is necessary and have *strong evidence* to support this belief:
  
  - All the explicit examples of policy classes that we considered in Section 3, and which are agnostic PAC learnable in online RL, satisfy it. To the best of our knowledge, we do not know of any policy class that is agnostically PAC learnable in online RL but does not satisfy the sunflower property.
  - The *only* policy class we know of that is not agnostically PAC learnable in online RL despite having bounded spanning capacity (the policy class from Theorem 3) violates the sunflower property. Furthermore, even the construction in Theorem 3 is *nonexplicit* (based on a probabilistic argument) so we think finding an explicit construction would be nontrivial.


Exploring the necessity of the sunflower property, and/or establishing the necessary conditions on $\Pi$ for agnostic learnability in online RL is an exciting direction for future work. 

**Further Intuition on the Sunflower Property.**  At a high level, the sunflower property captures the intuition that there exists a small set of policies $\Pi\_{\mathrm{core}}$ that 
 when executed can cover most of the trajectories that are be explored by other policies in $\Pi$. In particular, each policy $\pi \in \Pi$ can only deviate from $\Pi\_{\mathrm{core}}$ on a small set of states $\mathcal{S}\_\pi$. Intuitively, the sunflower property allows the learner to extrapolate data collected by executing a small set of policies $\Pi\_{\mathrm{core}}$ to estimate other policies in  $\pi \in \Pi$. Informally speaking, a shared structure similar to what is captured by the sunflower property seems to be crucial in order to avoid a linear dependence on $\Pi$. In the prior works that make further assumptions on the model dynamics, e.g. in Bellman-Eluder classes, etc. such shared structure was enforced via *modeling assumptions on the MDP*; our work explicitly aims to avoid making any MDP modeling assumptions. 

 Finally, we also remark that, even with the sunflower structure, the problem is challenging as the number of leaf states $\\{\mathcal{S}\_\pi\\}\_{\pi \in \Pi}$ could be very large (in fact, it can scale linearly with $\Pi$ for some of our examples). Our algorithm performs non-trivial and a novel exploration approach using policy-dependent Markov Reward Processes in order to figure out the relevant leaf states and achieve sample complexity that only scales with $D$ and $K$.

Meta-review: This work studies the problem of agnostic PAC reinforcement learning. The authors propose a novel complexity measure—the spanning capacity—which depends only on the policy class and which they show is both a necessary and sufficient measure of learnability when the learner has generative access to the MDP. This is no longer true in the online setting. In this setting they propose a sunflower property instead and show it is sufficient to guarantee efficient learning. The reviewers agreed this work would be a solid addition to the Neurips 2023 program.
Decision: Accept (poster)