The Role of Coverage in Online Reinforcement Learning
Authors: Tengyang Xie
Dylan J Foster
Yu Bai
Nan Jiang
Sham M. Kakade
Venue: ICLR 2023 notable top 5% (2023)
Keywords: reinforcement learning theory
online RL
offline RL
learnability
general function approximation

Abstract: Coverage conditions---which assert that the data logging distribution adequately covers the state space---play a fundamental role in determining the sample complexity of offline reinforcement learning. While such conditions might seem irrelevant to online reinforcement learning at first glance, we establish a new connection by showing---somewhat surprisingly---that the mere existence of a data distribution with good coverage can enable sample-efficient online RL. Concretely, we show that coverability---that is, existence of a data distribution that satisfies a ubiquitous coverage condition called concentrability---can be viewed as a structural property of the underlying MDP, and can be exploited by standard algorithms for sample-efficient exploration, even when the agent does not know said distribution. We complement this result by proving that several weaker notions of coverage, despite being sufficient for offline RL, are insufficient for online RL. We also show that existing complexity measures for online RL, including Bellman rank and Bellman-Eluder dimension, fail to optimally capture coverability, and propose a new complexity measure, the self-normalized coefficient, to provide a unification.

Published as a conference paper at ICLR 2023
THE ROLE OF COVERAGE IN ONLINE REINFORCEMENT LEARNING
Tengyang Xie UIUC txi@gillinois.edu
Dylan Foster" Microsoft Research dylanfos wew.ffostrriiccccmm rerriiccoooot
Yu Bai
Salesforce Research yu www@saleesorre..ccm
Nan Jiang UICC nanjiangeillinois.c
Sham M. Kakade
Harvard University
sham@seas. harvard.
ABSTRACT
Coverage conditions-whiee assert that the data logging distribution adequately covers the state sance-play a fundamental role determining the sample complex- ity of offline reinforcement learning. While such conditions might seem irrelevant to online reinforcement learning at first glance, we establish a new connection by surprisingly-
the mere existence of a data distribution with good coverage can enable sample-efficien online RL. Concretely, we show that coverability that is, existence of data distribution that satisfies a ubiquitous cover- age condition called concentrability- can be viewed as structural property of the underlying MDP, and can be exploited by standard a algorithms for sample-efficient exploration, even when the agent does not know said distribution. We complement this result by proving that several weaker notions of coverage, despite being sufficient for offline RL, are insufficient for online RL. We also show that existing complexity measures for online RL, including Bellman rank and Bellman Eluder dimension, complexity measure, the
fail to optimally capture coverability, and propose sequential extrapolation coefficient, to provide a unification.
INTRODUCTION
The last decade has seen development of reinforcement learning algorithms with strong empirical per- formance in domains including robotics (Kober et al., 2013; Lillicrap et al., 2015), dialogue systems (Li al., 2016), and personalization (Agarwal et al., 2016; Tewari and Murphy, 2017). While there is great interest in applying these techniques to real-world decision making applications, the number of samples (steps of interaction) required do often prohibitive, with state-of-the- algorithms requiring mil- lions of samples to reach human- level performance in challenging domains. Developing algorithms with improved sample efficiency, which efficiently generalizing across high- dighe-iinnnionall states and ac- tions while taking advantage of problem structure modeled practitioners, remains major challenge.
Investigation into design and analysis of algorithms for sample-efficient rentorremen learning has largely focused on two distinct problem formulations:
Online reinforcement learning, where the learner can repeatedly interact with the environment by executing a policy and observing the resulting trajectory.
Offline reinforcement learning, where the learner has access to logged transitions and rewards gathered from fixed behavioral policy (e.g.. historical data or expert demonstrations), but cannot directly interact with the underlying environment.
While these formulations share common goal (learning near-optimal policy), the algorithms used to achieve this goal and conditions under which it can be achieved are seemingly quite different. Focusing on value function approximation, sample-effcciet algorithms for online reinforcement learning require both (a) representation conditions, which assert that the function approximator is flexible enough to represent value functions for the underlying MDP (optimal or otherwise), and (b) exploration conditions
"quull contribution

---

Published as a conference paper at ICLR 2023
(or, structural conditions) which limit the amount of retooaattioonuuuuueeeeee to learn a nearr-ottimll policy- typically by enabling extrapolation across states or limiting the number of effective state distributions (Russo and Van Roy. 2013; Jiang et al., 2017: Sun et al., 2019; Wang et al., 2020b; Du et al., 2021; Jin et al., 2021 Foster et al., 2021). Algorithms for offline reinforcement learning typically require similar representation conditions. However, since data is collected passively from fixed logging policy/distribution rather than actively, the exploration conditions used in online RL are replaced with coverage conditions, which assert that the data collection distribution provides sufficient coverage over the state space (Antos et al., 2008; Chen and Jiang, 2019; Xie and Jiang, 2020; 2021; Jin et al., 2021222265 b;; Rashidinejad al.,, 2021; Foster etal., 2022; Zhan al., 2022). The aim for both lines of research (online and offline) is to identify the weakest possible conditions under which learning is possible, and design algorithms that take advantage of these conditions. The two lines have largely evolved in parallel, and it is natural to wonder whether there are deeper connections. Since the conditions for sample-efficient online RL and offline RL mainly differ via exploration versus coverage, this leads us to ask:
If an MDP admits a data distribution with favorable coverage for offfine RL, what does this imply about our ability to perform online RL efficiently?
Beyond intrinsic theoretical value, this question is motivated by the observation that many real- world applications lie a spectrum between online and offiine. It is common for the learner to have access to logged/offtine data, yet also have the ability to actively interact with the underlying environment, possibly subject limitations such as an exploration budget (Kalashnikov et al., 201 8). Building a theory of real-world RL that can lead to algorithm design insights for such settings requires understanding the interplay between online and offline RL.
1.1
OUR RESULTS
We investigate connections between coverage conditions in offline RL and exploration in online RL by focusing on the concentrability coefficient, the most ubiquitous notion of coverage in offline RL. Concentrability quantifies the extent to which the data collection distribution uniformly covers the state-action distribution induced by any policy. We introduce a new structural property, coverability, which reflects the best concentrability coefficient that can be achieved by any daia distribution, possibly designed by an oracle with knowledge of the underlying MDP. Our main results are as follows:
1. We show (Section 3) that coverability (that is, mere existence of a distribution with good concen- trability) is sufficient for sample-efficient online exploration, even when the learner has no prior knowledge of this distribution. This result requires no additional assumptions on the underly- ing MDP beyond standard Bellman completeness, and and--erhaps surprisingly-is achieved using standard algorithms (Jin et al., 2021a), albeit with analysis ideas that go beyond existing techniques.
2. We show (Section 4) that several weaker notions of coverage in offline RL., including single-policy concentrability (Jin et al., 202 bb; Rashidinejad et al., 2021) and conditions based on Bellman residuals (Chen and Jiang, 2019; Xie et al., 2021a), are insufficient for sample-efficient online exploration. This shows that in general, coverage in offline reinforcement learning and exploration in online RL not compatible, and highlights the need for additional investigation going forward.
Our results serve starting point for systematic study of connections between online and offline learnability in RL. To this end, we provide several secondary results:
1. We show (Section 5) that existing complexity measures for online RL, including Bellman rank and Bellman-Fluder dimension, do not optimally capture coverability, and provide new complexity measure, the sequential extrapolation coefficient, which unifies these notions.
2. We establish (Appendix C) connections between coverability and reinforcement learning with exogenous noise, with applications to learning in exogenous block MDPs (Efroni et al., 2021; 2022a).
We give algorithms for reward-free exploration (Jin et al., 2020a; Chen et al., 2022) under coverability (Appendix G).
While our results primarily concern analysis of existing algorithms rather than algorithm design, they highlight a number of exciting directions for future research, and we are optimistic that the notion of coverability can guide the design of practical algorithms going forward.
Notation. For an integer n N, we let [n] denote the set [1.....m]. For a set X, we let ( denote the set of all probability distributions over X. We adopt standard big-oh oh notation, and write fō) to denote that f Ogg-0(g9m) max(1 .polyoog(g))) and a S shorthand for a= (bb).
2

---

Published as a conference paper at ICLR 2023
2 BACKGROUND: ONLINE/OFFLING RL, COVERAGE, AND COVERABILITY
Markoy decision processes. We consider an episodic reinforcement learning setting. Formally, a Markov decision process M = (X, R. H,,1 consists of (potentially large) state space X, action space A, horizon H, probability transition function P = [ 1/1 where Py Pr: A-- A(t), reward function R= ) where Ra: XX' x A - [0,1], and deterministic initial state I E X. A (randomized) policy is sequence of per-timestep functions = {TT; :X'>> AAA) The policy induces a distribution over trajectories
via the following process. For
h I.. ag ~ (T( (t.). (8n)..7, T' - R& (n), and Th+1 Pa (.-131),))) For notational convenience, we use 1-1 to denote a deterministic terminal state with zero reward. We let [+] and IP [-] denote expectation and probability under this process, respectively.
The Q-function for policy ι is Q7 == R [E#= T = I. = =a] the value function for π is V/, (z) == Ea (+1x) (x,a))) and the expected reward for π is (T)) = (z1). We let x* denote the optimal (deterministic) policy, which maximizes Q% (x,aa) for all (2,a) E x A simultancously, we define Vi₃ = V and Q7 = =0 We define the occupancy measure for policy π via d% (1r.a))=== := IPT [. 2. = and di (x):= Pp Ih =x] We let Tn denote the Bellman operator for layer h. defined via [Tn]]xz,)) .) R, (x.a) +Ey (2 mmax,r f( .a') for f: RR. We also assume that rewards are normalized such that 5 Th E [0,1] To simplify technical presentation, we assume that X' and A are countable; we anticipate that this assumption can be removed.
Online Reinforcement Learning. Our main results concern online reinforcement learning in an episodic framework, where the learner repeatedly interacts with an unknown MDP by executing a policy and observing the resulting trajectory, with the goal of maximizing total reward.
Formally, the protocol proceeds in I' rounds, where at each round t= I.....T,, the learner; i) Selects a to execute in the (unknown) underlying MDP M ii) Observe the resulting
policy x { (1)
(4) he[H]]
trajectory (x/(² .0 .r(")) ).....(..] H (t)). The learner's goal is to minimize their cumulative regret, defined via Reg EnerTy
To achieve sample-efficient online reinforcement learning guarantees that do not depend on the size of the state space, one typically appeals to value function approximation methods that take advantage of function class F (X' x A-RR) that attempts to model the value functions for the underlying MDP M (optimal or otherwise). An active line of research provides structural conditions under which such approaches succeed (Russo and Van Roy, 2013; Jiang et al., 2017: Sun et al., 2019; Wang et al., 2020b; Du 2021; Jin al., 2021a; Foster al., 2021), ), based on assumptions that control the interplay between the function approximator F and the dynamics of the MDP A These results require (i) representation conditions, which require that F is flexible enough to model value functions of interest (e.g., Q* F or FT,Fi+ Fi) and (ii) exploration conditions, which either explicitly or implicitly limit the amount of exploration required for a deliberate algorithm learn a near-optimal policy. This is typically accomplished by either enabling extrapolation from states already visited, or by limiting the number of effective state distributions that can be encountered.
Offline Reinforcement Learning and Coverage Conditions. Our aim is investigate parallels between online and offline reinforcement learning. In offline reinforcement learning, the learner cannot actively execute policies in the underlying MDP M Instead, for each layer h. they receive a dataset Dn of n tuples (I), "h, .'h 1141) with rh = R2 (I,,,,), Tn+1 Pr (x.,)))))) and (z,,ar) ) ~ pt i.i.d., where μt E A(X x A) is the data collection distribution; we define μ ]ee[H) The goal of the learner is to use this data learn an e-optimal policy म, that is: J()))
Algorithms for offline reinforcement learning require representation conditions similar those re- quired for online RL. However, since it is not possible to actively explore the underlying MDP, one dispenses with exploration conditions and instead considers coverage conditions, which require that each data distribution μa, sufficiently covers the state space. As an example, consider Fitted Q-tteration (FQI), one of the most well-studied offline reinforcement learning algorithms (Munos, 2007; Munos and Szepesvári, 2008; Chen and Jiang, 2019). The algorithm, which uses lcast-squares to approxi- mate Bellman backups, is known to succeed under (i) a representation condition known as Bellman completeness (or "completeness" )) which requires that Tr.f f F,F, for all f FF and (ii) coverage condition called concentrability. To state, the result, recall that || := max; [r.]| for x ER..
While our results assume that the initial state is fixed for simplicity, this assumption is straightforward relax.
3

---

Published as a conference paper at ICLR 2023
Definition 1 (Concentrabilityy) The concentrabilitty coefficient for data distribution μ {pu { h== and policy class II is given by
/ poll
Concentrability requires that the data distribution uniformly covers all possible induced state dis- tributions. With concentrability" and completeness, FQI can learn an s-optimal policy using poly( (Coone ,lo]]F,HH coefficient Conne (p) and the capacity log] F for the function class, and has no explicit dependence on the size of the state space. There is a vast literature which provides algorithms with similar, often more refined guarantees (Chen and Jiang, 2019; Xie and Jiang, 2020; 2021; Jin al., 2021b; Rashidinejad et al., 2021; Foster et al., 2022; Zhan et al., 2022).
samples. Importantly, this result scales only with the concentrability
The Coverability Coefficient. Having seen that access to a data distribution j with low concen- trability Coone (1) is sufficient for sample-efficient offline RL, we now ask what existence of such distribution implies about our ability to perform online RL. To this end, we introduce a new structural parameter, the coverability coefficient, whose value reflects the best concentrability coefficient that can be achieved with oracle knowledge of the underlying MDP M*.
Definition 2 (Coverability). The coverability coefficient Ceov > 0 for a policy class II is given by Ceov inf p (A(XX.A) (Ccone (1))
Coverability is an intrinsic structural property of the MDP M which implicitly restricts the complexity of the set of possible state distributions. While it always the case that Ccov S ||A|, the coefficient can be significantly smaller (in particular, independent of (1)) for benign MDPs such as block MDPs and MDPs with low-rank structure (Chen and Jiang, 2019, Prop 5); see Appendix C for details.
With this definition in mind, we ask: If the MDP M* satisfies low coverability, is online reinforcement learning possible? Note that if the learner were given access to data from the distribution js that achieves the value of Ceov. it would be possible to simply appeal to offline RL methods such as FQI, but since the learner has no prior knowledge of μu, this question is non-trivial, and requires deliberate exploration.
COVERABILITY IMPLIES
EFFICIENT ONLINE EXPLORATION
We now present our main result, which shows that low coverability is sufficient for sample-effice efficient online exploration. We first describe the algorithm and regret bound, then sketch the proof and give intu- ition (Section We conclude (Section 3.2) by applying the main result to give regret bounds for learn- ing in exogenous block MDPs (Efroni et al., 2021), highlighting structural properties of coverability.
Function approximation. We work with a value function class F = Fi X ... x FH, where Fn C (X' x A + [0, 1)), with the goal of modeling value functions for the underlying MDP. We adopt the convention that fu+1 = 0, and for each f E F, we let I denote the greedy policy with =rrg:a, A.f (z,a). (z,,) and we use (A( = (--=) (fr (I,aa) for any The We take our policy class be the induced class II II: { F for the remainder of the paper unless otherwise stated. We make the following standard completeness assumption, which requires that the value function class closed under Bellman backups (Wang et al., 2020b; Jin al., 2020b; Wang et al., 2021b; Jin et al., 2021a). Assumption (Completeness). For all E [H), we have Tafn+i Fnr all fa+ E F
Completeness implics that J is realizable (that is, F), but is a stronger assumption in general. We assume for simplicity that [F] < co, and our results scale with log] Fi; this can be extended to infinite classes via covering numbers using a standard analysis.
Algorithm and main result. Our result is based new analysis of the GOLF algorithm of Jin et al. (2021a), which is presented in Algorithm 1 of Appendix D for completeness. GOLF is based on the principle of optimism in the face of uncertainty. At each round, the algorithm restricts a confidence set F f(t)) e with the most optimistic estimate fi (I1 f.1 (x1)) for the total reward. The confidence sets FFl)) are based on an empirical proxy to squared Bellman error, and are constructed in a global fashion that entails optimizing over fn for all layers h he [H] simultaneously (Zanette et al., 2020a).
C F with the property that Q* E F()) and chooses ( = y based on the value function
SSpecifically, FQI requires concentrability with IT chosen to be the set of all admissible policies (see, e.g., Chen and Jiang, 2019). Other algorithms (Xie and Jiang, 2020) can leverage concentrability w.r. smaller policy classes.
4

---

Published as a conference paper at ICLR 2023
Note that while GOLF originally introduced to provide regret bounds based on the notion of Bellman-Eluder dimension, we show (Section 5) that coverability cannot be (optimally) captured by this complexity measure, necessitating a new analysis. Our main result, Theorem I, shows that GOLF attains low regret for online reinforcement learning whenever the coverability coefficient is small.
Theorem (Coverability implies sample-efficient online RL). Under Assumption 1, there exists an absolute constant such that for any 8 E (0.1) and T E N4, if we choose 3 = c log(TH)/(/)) in Algorithm then with probability at least 1 1-6, we have Reg S OHH (og.ooooggTT/// where Ccov is the coverability coefficient (Definition 2).
Beyond the coverability parameter Coov, the regret bound in Theorem depends only on standard problem parameters (the horizon H and function class capacity Fo) Hence, this result shows that coverability, along with completeness, sufficient for sample-efficient online RL. Additional features of Theorem 1 are as follows.
While coverability implies that there exists distribution μ for which the concentrability coefficient Cconc is bounded, Algorithm has no prior knowledge of this distribution. We find the fact that the GOLF algorithm-we whhic does not involve explicitly searching such a distribution surrcbeuioonsscceedds under this condition to be somewhat surprising (recall that given sample access J4, one can simply run FQI). Our proof shows that despite the fact that GOLF does not explicitly reason about μt, coverability implic- itly restricts the set of possible state distributions, and limits the extent to which the algorithm can be "surprised" by substantially new distributions. We anticipate that this analysis will find broader use.
Ignoring factors logarithmic in T, H, and d-1, the regret bound in Theorem 1 scales as H H [C which is optimal for contextual bandits (where Ceov = LA| and // = 2)," and hence cannot be improved in general (Agarwal al., 2012). The dependence on H matches the dimension (Jin et al., 2021a).
regret bound for GOLF based on
GOLF uses confidence sets based on squared Bellman error, but there are similar algorithms which instead work with average Bellman error (Jiang et al., 2017: Du et al., 2021) and, as result, require only realizability rather than completeness (Assumption 1). While existing complexity measures such as Bellman rank and Bellman-Fluder dimension can he used to analyze both types of algorithm, and our results eritically use the non-negativity of squared Bellman error, which facilitates certain "change- of-measure" arguments. Consequently, it is unclear whether the completeness assumption can be removed (i.e., whether coverability and realizability alone suffice for sample-efficient online RL).
On the algorithmic side, our results give guarantees for PAC RL via online-to-batch conversion, which we state here for completeness. We also provide an extension to reward-free exploration in Appendix G. Corollary 2. Under Assumption I, there exists an absolute consiant e such that for any ō E (0,1) and TE N+, ., we choose 3 c- colloo(TT ((( in Algorithm then with probability at least - 8, the policy (=))((()))))))))))))
f output by Algorithm has J(x²) - < 20(H H
3.1 PROOF SKETCH FOR THEOREM 1: WHY IS COVERABILITY SUFFICIENT?
We now sketch the main ideas behind the proof of Theorem 1, highlighting the role of coverability in limiting the complexity of exploration.
Regret decomposition and change of measure. For each t, we define (-.-) f() (..:)
(TwJi++))+>>)) which may viewed as a "test function"" at level induced by f EF. We adopt the shorthand dit" dj and we define / (I.a): = Σ di (z,a) the cumulative historical visitation for rounds prior to step f.
standard regret decomposition for optimistic algorithms (Lemma 13) allows to relate regret the average Bellman error under the learner's sequence of policies:
Reg Σ (E|
(a (21) (x))) (01)))
E nn (Tan-((TTTiiaee (1)
+E(T])E([]
(r.a)
We require H 2 to apply the result to contextual handits due to assuming the deterministic starting state. is the non-Markov policy obtained by sampling t~ [T] and playing (t)
5

---

Published as a conference paper at ICLR 2023
Fix h E [H]. We use change-of of
offeeesure- measure argument to relate the on-policy average Bellman error B ((o,))ad (6) (x.a) the in in-sample squared Bellman error under di writing Eq. (1) as
d (x,a)
1/2
(di (2,a)) NE[T] df (z,a)
ΣΣ (E(7) m.
dh (I.a)
8 (x,a)
ΣΣ
ΣΣ (x.0) (x.a)) tE|T)
d (x,a)
(T):xxtooolttion crmor
(II): in-sample squared Bellman emvor
where the inequality is an application of Cauchy-Schward As an immediate consequence of the confidence set construction in Eq. (3), completeness, and standard concentration argument (Lemma 12 in Appendix D), we can bound the in-sample error by (II) (0(VBT)
Bounding the extrapolation error using coverability. emror (I) is controlled by coverability. We have:
To proceed, we show that the extrapolation
(d)( ME[T] P.a (2,a)
max di [E[T] 1E 2.a
ΣΣ
(r.a) d (z,a)
max 20.0
di (a,a) di (x.a)) (E(T)
Σ maxdl (xra) (E(T]
1 (2,a)
(O(log(T) Lemma
S Caae by Lemma 14
Here, the incquality (a) uses a scalar variant of the elliptic potential lemma (Lemma 15; ef. Lattimore and Szepesvári (2020)), which we apply on a per-state basis. 5 The inequality (b) uses key result (Lemma 14 in Appendix D), which shows that coverability is equivalent to quantity we term cumulative reuchability, defined via E(e (xxa))xxxx suP d, (ar, a). Cumulative reachability reflects the variation in visitation probabilities for policies in the class IT, and boundedness of this quantity (which occurs when state-action pairs visited by policies in II have large overlap) implies that the contributions from potentials for different state-action pairs average out. See Figure for an illustration.
Density
d
d
(s. n)
Figure 1: An example of coverability < cumulative reachability (which is equal
total area of the shaded re- gion without double-counting overlaps. IT= (MI, dashed is
To conclude, we substitute the preceding bounds into the term (I), which gives Reg S E (n.))_ (x. (O(H Ccov (Too-)))l((T))
Note that to obtain the expression in term (I), proof critically uses that the confidence set construc- tion provides a bound on the squared Bellman error E (c.a)~771) (8% (z,a)²) in the change measure argument. This contrasts with existing works online RI. with general function approximation (e.g.. Jiang et al., 2017; Jin et al., 2021a; Du et al., 2021), which typically move from average Bellman error squared Bellman error lossy step, and only work with squared Bellman error because it permits simpler construction of confidence sets. Confidence sets based on average Bellman error will lead larger notion of extrapolation error which cannot be controlled using coverability (cf. Section 5).
3.2 RICH OBSERVATIONS AND EXOGENOUS NOISE: APPLICATION TO BLOCK MDPs
As an application of Theorem 1, we consider the problem of reinforcement learning in Exogenous Block MDPs (Ex-BMDPs), a problem which has received extensive recent interest (Efroni et al., 2021; 2022a;b; Lamb et al., 2022). Recall that the block MDP (Jiang et al., 2017; Du et al., 2019; Misra al., 2020) is model in which the ("observed"") state space X' is srge//hghhddmmnsionnd but can be mapped by an (unknown) decoder ø* to a small latent state space which governs the dynamics. Exogenous block MDPs generalize this model further by factorizing the latent state space into small controllable (" ("endogenous")) component S and large irrelevant ("exogenous") component E, which may be temporally correlated.
The main challenge of learning in block MDPs is that the decoder ø² is not known to the learner in applying
advance. Indeed, given access to the decoder, one can obtain regret (1,,))
Applying this result formally requires separate argument to handle early rounds in which pairs (z,a) have been visited very little; this is given Appendix D)

---

Published as a conference paper at ICLR 2023
tabular reinforcement learning algorithms to the latent state space. In light of this, the aim of the Ex-BMDP setting is to obtain sample complexity guarantees that are independent of the size of the observed state space | and exogenous state space [3], and scale as (|) F is an appropriate class of function approximators (typically either a value function class F or a class of decoders & that attempts to model Ø directly).
where
We show (Proposition 8 in Appendix C) that for any EX-BMDP, one has Coov S |S| |A, which which-through Theorem 1- 1-implies that GOLF attains Reg S
whenever Assumption 1 holds; critically, this result scales only with the cardinality |S| for the endogenous latent state space, and with the capacity Fo for the value function class. is the first result for this setting that allows for stochastic latent dynamics and emission process, albeit with the extra assumption of completeness. Existing algorithms either require that the endogenous latent dynamics pendo are deterministic (Efroni et al., 2021) or allow for stochastic dynamics but heavily restrict the observation process (Efroni al., 2022a). and existing complexity measures such as Bellman Rank and Hellman-Fluder dimension can be arbitrarily large for this setting (see discussion in Section 5). See Appendix C. for details and discussion.
4 ARE WEAKER NOTIONS OF COVERAGE SUFFICIENT?
In Section 3, we showed that existence of a distribution with good concentrability (coverabilityy is sufficient for sample-efficient online RL. However, while concentrability is the most ubiquitous coverage condition offline RI., there are several weaker notions of coverage which also lead to sample-efficient offline RI. algorithms. In this section, we show that analogues of coverability based on these conditions, single-polic concentrability and generalized concentrability for Bellman residuals, do not suffice for sample-efficient online RL. This indicates that in general, the interplay between offline coverage and online exploration is nuanced.
Single-policy concentrability. Single-polic concentrability is widely used coverage assumption in offline RI. which weakens concentrability by requiring only that the state distribution induced by x covered by the offline data distribution μr, as opposed requiring coverage for all policies (Jin et al., 202 lb; Rashidinejad et al., 2021).
Definition (Single- policy concentrability). The single ponngee-poliy concentrability coefficient a data distribution μl (n4, | is given by (+) /Pall
For offline RL, algorithms based on pessimism provide sample guarantee complexity guarantees that scale with Cn (1) (Jin et al., 2021b; Rashidinejad et al., 2021). However, for the online setting, it is trivial to show that an analogous notion of "sinnle-policyy coverability" (i.e., existence of distribution with good single-policy coverability) is not sufficient for sample-effiee cunple-efficient learning, since for any MDP, one can take ja = d= to attain Cionnc (/4) = 1. This suggests that any notion of coverage that suffices for online RL must be more uniform in nature.
Generalized concentrability for Bellman residuals. Another approach to weaker coverage in offline RL is to relax concentrability by only requiring coverage with respect to the Bellman residuals for value functions in F (Chen and Jiang, 2019; Xie et al., 202 Cheng et al., 2022); the following setting.
definition adapts this notion to the
Definition 4 (Generalized concentrabilityy. We define the generalized concentrability coefficient (1 F) a policy class TI and value function class F as the least constant > such that the offline data distribution = {mm) h= satisfies that for all E and E II, Σneim Bag [(a((s,an)- (T]sht))(nn, )) C. Eme(n Eyr. [Ja(ss,aa)) (Trn))))))Tnn1111)) (s).))))))(
Note that Ecanc (I, & Ceone(pi (in particular, they coincide if one chooses F to be the set of all functions over X' x A) but in general (cone can be much smaller. For example, in the linear Bellman-complett setting, it is possible to bound Cconc () in terms of feature coverage conditions (Wang et al., 202 Zanette et al., 2021). Using offline data from μ. sample complexity guarantees that scale with Conn (). can be obtained under Assumption via MSBO (see, e.g., Xie and Jiang, 2020, Section 5) or by running a "one-step" variant of GOLF (Algorithm 1); we provide this result (Proposition 16) in Appendix E for completeness. Given that this notion leads to positive results for offline RI,, it is natural to consider generalized notion of coverability based upon it.
7

---

Published as a conference paper at ICLR 2023
Definition 5 (Generalized coverability). We define the generalized coverability coefficient for policy class II value function class F and as p E (X A) (1,
inf
Unfortunately, show that this condition does not suffice for samplc-efficient online RL, even when the number of actions is constant and Assumption 1 is satisfied.
Theorem 3. For any X, K.H.C& E N, there exists a family of MDPs with |x|= 1AI=2 horizon H and a function class F with log S H Hog(2) such that: i) Assumption 1 (completeness) is satisfied for F and we have Ceou(F) C and ii) Any online RI. algorritm that returns a 0.1 1op-mml policy with probability 0.9 requires at least Ot (min X x,200())))))))))))))))))) (,,200))22((0)) ,2(()))) trajectories.
Theorem 3 highlights that in general, notions of coverage that suffice for offline RL-even those that are uniform in nature- can fail to lead to useful structural conditions for online RL. Briefly, the issue is that bounding regret for online RL entails controlling the extent to which a deliberate algorithm that has observed state distributions " can be "surprised" by a substantially new state distribution d/ here, surprise is typically measure in terms of Bellman residual. The proof of Theorem 3 shows that existence of a distribution with good coverage with respect to Bellman residuals does suffice to provide meaningful control of distribution shift. We caution, however, that the lower bound construction makes use of the fact that Definition 5 requires coverage only on average across layers, and it is unclear whether similar lower bound holds under uniform coverage across layers. Developing more unified and fine- meee-griied understanding of what coverage conditions lead to efficient exploration is an important question for future research.
A NEW STRUCTURAL CONDITION FOR SAMPLE-EFFICING
ONLINE RL
efficient online RL, an immediate question is whether this structural condition is related to existing complexity measures such as Bellman-Eluu Eluder dimension (Jin et al., 2021a) la) and GellmannBBilinee rank (Jiang al., 2017: Du al., 2021). which attempt to unify existing approaches to sample-efficient RI. We now show that these complexity measures are insufficient to capture coverability, then provide new complexity measure, the Sequential Extrapolation Coefficient, which bridges the gap.
Having shown that coverability facilitates
5.1 INSUFFICIENCY OF EXISTING COMPLEXITY MEASURES
Bellman Bellman-Eluder dimension (Jin et al., 2021a) and Bellman/Bilinear rank (Jiang et al.. 2017: Du et al., 2021) can fail to capture coverability for two reasons: (i) insufficiency of average Bellman error (as opposed to squared Bellman error), and (ii) incorrect dependence on scale. To highlight these issues, we focus on Q-type Bellman- Eluder dimension (Jin et al., 2021a), which subsumes Bellman rank. See Appendix F for discussion of other complexity measures. Let D = {dī x e 11} and Fr, - Fn++ := fhr- Tr E F}. Following Jin et al. (2021a), we define the (Q-type) Hallman-Eludde dimension as follows.
Definition 6 (Bellman-Elee -luder dimension). The Bellman Bellman-Eluder dimension dimBE (F,IBBEFFIII... (F,ll.s,h for the
layer h is the largest d E N, such that there exist sequences {d), a 3..,0 ...,dh..) C
D and (5) ,....,0, 1/2)) S
Fn Fh+11 such that for all E [d]. 20 16 > e(t), and V EE
[E N 1) 7
< _0 for
g0 ...,,((() 2E. We define dimgE [F -I,.e) [ dimBe (F.I...h).
Issue #1: Insufficiency of average (vs. squared) Bellman error. The Bellman-Eluder dimension reflects the length of the longest consecutive sequence of value function pairs for which can be "surprised" by a large Bellman residual for a new policy if the value function has low Bellman residual on all preceding policies. Note that via Definition 6, the Bellman- Eluder dimension measures the size of the surprise and the error on preceding points via average Bellman error (e.g., E Eggo ()) On the
other hand, the proof of Theorem 1 critically uses squared Bellman error E [ bound regret
by coverability; this because the (point- (point-wise) nonnegativity of squared Bellman error facilitates change-of-measee measure in similar fashion to offline reinforcement learning. The following result shows that this issue fundamental, and Bellman-Eludes dimension can be exponential large relative to the regret bound in Theorem 1.
Proposition For any de N. there exists an MDP M with H = and |A| 2, policy class 11 with [TI d, and value function class F with F d satisfying completeness. such that C.ov 0(1,, but the Bellman- Eluder dimension has dimBe (F, ((mm)))((mmmmmm))..mm
(d) for any E 1
'Q-type and V-type are similar, but define the Bellman residual with respect different action distributions.
8

---

Published as a conference paper at ICLR 2023
The lower bound in Proposition 4 is realized by exogenous block MDP (Appendix C), with d representing the number of exogenous states. The result gives an exponential separation between what can be achieved using Bellman-ENl Eluder dimension and coverability, because GOLF attains Reg S O(yTlog d)) (ef. Corollary 9). yet we have dimge(F,II.1))
(dd). The construction, which is based on Efroni et al. (2022b, Section B.1), critically leverages cancellations in the average Bellman error; these cancellations are ruled out by squared Bellman error, which is why Theorem gives a regret bound that scales only logarithmicully in d. Bilinear rank (Du et al., 2021) and V-type Bellman rank suffer from similar drawbacks; see Appendix for further discussion.
Issue #2: Incorrect dependence on scale. In light of the previous example, seemingly reasonable fix is to adapt the Bellman-Eluder dimension to consider squared Bellman ertor rather than average Bell- man error (i.e., use v E>= (R (())) Se(0) in Definition 6). We show (Appendix F.1) that while is possible to bound this modified Bellman- Bellman-Eluder dimension in terms of the coverability parameter, the dependence on the scale parameter is polynomial, and it is not possible to derive regret bounds better than T/3 under coverability with this approach. Informally, the issue is scale: Bellman-elude di- mension only checks whether the average Bellman error violates the threshold E, and does not consider how far the error violates the threshold (e.g. | g [8] >E and |E ( [ >
are counted the same).
5.2 THE SEQUENTIAL EXTRAPOLATION COEFFICIENT
To address the issues above, we introduce a new complexity measure, the Sequential Extrapolation Coefficient (SEC), which i) leads to regret bounds via GOLF and ii) subsumes both coverability and the dimension. Conceptually, the Sequential Extrapolation Coefficient should thought of as minimal abstraction of the main ingredient in regret bounds based on GOLF and other optimistic algorithms: extrapolation from in-sample error to on-policy error. We begin by stating a variant the Sequential Extrapolation Coefficient for abstract function classes, then specialize it to RL.
Definition 7 (Sequential Extrapolation Coefficient). Let be an abstract set. Given a test function class V C (2 R. and distribution class 2 C (2), the sequential extrapolation coefficient for length
given by
E (05) [2bcco12 - g ( [(x51))2]
= (0 D,,()
sup
sup
( E ,t.)..... ( ED
IE T
To apply the Sequential Extrapolation Coefficient to RL, we use Bellman residuals for F as test functions and consider state-action distributions induced by policies in II.
Definition (SEC for RI... We define SECRL (I,11 == = - -TrFF++1,
The following result, which is a near-immediate consequence of the definition, shows that the Sequential Extrapolation Coefficient leads to regret bounds via GOLF; recall that II {T. I.f FF is the set of greedy policies induced by F.
Theorem 5. Under Assumption 1, there exists an absolute constant e such that for any 5 E (0,1] and TEN if we choose == c- wo..ooo(((F///.. in Algorithm 1, then with probability at least 5, we have Reg S O /SEERLL [I,II,T) -oo.TTT"--loo("" (TTH
We defer the proof of Theorem to Appendix F, and conclude by showing that the Sequential Extrapolation Coefficient subsumes coverability Ccov (Definition 2) and Hallman-Elluded dimension. Proposition 6 (Coverability = SEC). SECRL (J (1,77 (O(Coo (Tg(
Proposition 7 (Bellman-Fluder dim. SEC). SECRL SECRL(F,I1,T) (F,IIT7) OddimBe (F, llg)))
The Sequential Extrapolation Coefficient can likely be generalized further along many directions (e.g.. by allowing for different test functions in the vein of Du al. (2021)). Further unifying these notions is an interesting question for future research; see Appendix F.3 for further discussion.
CONCLUSION
This paper initiates the systematic study of parallels between online and offline learnability in rein- forcement learning and uncovers surprising connections. The possible future directions include general theories under weaker notions of coverability or approximation conditions (see Appendix A for open problems) well as the connection to the practical algorithm design.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Nan Jiang acknowledges funding support from ARL Cooperative Agreement W911NF-17-2-019. NSF AIS-2112471 NSF CAREER award, and Adobe Data Science Research Award. Sham Kakade
acknowledges funding from the Office of Naval Research under award X00014-22-112377 and the National Science Foundation Grant under award #CCF-1703574.
REFERENCES
Yasin Abbasi- Yadkori, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz. Exploration-enhanced politex. arXiv preprint arXiv:1908. 10479, 2019.
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646, 2014.
Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen Lee, Jiaji Li, Dan Melamed, Gal Oshri, Oswaldo Ribas, Siddhartha Sen, and Aleksandrs Slivkins. Making contextual decisions with low technical debt. arXiv:1606.000 03966, 2016.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1);89-129, 2008
Jinglin Chen and Nan Jiang. information-theerede considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-frree free exploration in non- non-linear rl. arXiv preprint arXiv:2206,10777 2022.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. International Conference on Machine Learning (ICML), pages 3852-3878. PMLR, 2022.
Kefan Dong and Tengyu Ma. Asymptotic instance-optimal algorithms for interactive decision making. arXiv preprint 2263162206.023326, 2022.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665- 1674. PMLR, 2019.
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. International Conference on Machine Learning, 2021.
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Prov- ably 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 in the presence of exogenous information. Conference Learning Theory (COLT), 2022a.
Yonathan Efroni, Sham Kakade, Akshay Krishnamurthy, and Cyril Zhang. Sparsity in partially controllable linear systems. In International Conference on Machine Learning, pages 5851-5860. PMLR, 2022b.
Amis-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 23, 2010.
10

---

Published as a conference paper at ICLR 2023
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making, arXiv preprint x7X1::2112.1388,22200 2021.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement
learning: Fundamental barriers for value function approximation. Conference Learning Theory (COLT), 2022.
Nan Jiang and Jiawei Huang. Minimax value interval for off- evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2758, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Contextual decision processes with low Bellman rank PAC-learnable. In International Conference Machine Learning, pages 1704-1713, 2017.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870 4879.4879. PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 34: 13406-13418 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021b.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robol Learning, pages 65 1-633. PMLR, 2018
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 1238177123-
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1844 1848, 2016.
Alex Lamb, Riashat Islam, Yonathan Efroni, Aniket Didolkar, Dipendra Misra, Dylan Foster, Lekan Molu, Rajan Chari, Akshay Krishnamurthy, and John Langford. Guaranteed discovery of control- lable latent states with multi-step inverse models. arXiv preprint (ikiv:2207.082299 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Jiwei Li, Will Monroe,, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao. Deep reinforcement learning for dialogue generation. In EMNLP, 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, arXiv preprint arXiv:1509.02971, 2015.
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, pages 6961-6977 PMLR, 2020.
Rémi Munos. Error bounds for approximate policy iteration. In International Conference on Machine Learning, 2003.
Rémi Munos. Performance bounds in f--norm for approximate value iteration. SIAM Journal on Control and Optimization, 2007.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
11

---

Published as a conference paper at ICLR 2023
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34: 101111112111111 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, pages 2256-2264, 2013.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, and John Langford. Model-based
RL in contextual decision processes: PAC bounds and exponential improvements model-free approaches. In Conference on learning theory, pages 2898-2933 PMLR, 2019.
Ambuj Tewari and Susan A. Murphy. From ads interventions: Contextual bandits in mobile health. In Mobile Health, 2017.
Andrew Wagenmaker and Kevin Jamieson. Instance-dependent near-optimal policy identification in linear MDPs via online experiment design. arXiv preprini arXiv:2207.0257 2022.
Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond regret: Instance-dependent PAC reinforcement ieninfrrremeenttaaiingggg Conference on Learning Theory, pages 358-418. PMLR, 2022.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:17816-17826. 2020a.
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,
Ruosong Wang. Dean Foster, and Sham M. Kakade. What are the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations (ICLR), 2021a.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in rein- forcement learning with generalized linear function approximation. International Conference on Learning Representations, 2021b.
Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pages 550-559. PMLR, 2020.
Tengyang Xie and Nan Jiang. Batch falue-function approximation with only realizability. In Interna- tional Conference on Machine Learning, pages 1404-11413. PMLR, 2021.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consisten pessimism for offline reinforcement learning, Advances in neural information processing systems, 34:6683-6694, 2021a. 2021aa
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27407, 2021b.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 13::::116111111 1711117766-6666611 2020b.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:1 13626- 13640, 2021.
12

---

Published as a conference paper at ICLR 2023
Wenhao Zhan, Baihe Huang, Audrey Huang. Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single- 2730-2775. PMLR, 2022.
single-policy policy concentrability. In Conference on Learning Theory, pages
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:1 13:11173-11744 2020.
13

---

Published as a conference paper at ICLR 2023
APPENDIX
Discussion and Open Problems
14
B Additional Related Work
15
Application to Exogenous Block MDPs
15
C.1 Invariance of coverability
16
C.2 Proofs
17
Proofs and Additional Details from Section 3
18
D.1 GOLF Algorithm and Proofs from Section
18
Proofs and Additional Details from Section 4
21
E.1 Additional Details: Offline RL
E.2 Proofs from Section
22
F
Proofs and Additional Results from Section
23
F.I
Additional Details: Sequential Extrapolation Coefficient versus Bellman Elaudrr di- mension
23
F22 Proofs from Section
26
F3 Discussion: Relationship to Additional Complexity Mcasures
32
G Extension: Reward-Free Exploration
34
G.I Algorithm and Theoretical Analysis
35
G.2 Proofs
37
A DISCUSSION AND OPEN PROBLEMS
Toward general theory beyond this paper, we highlight some exciting and challenging open problems for future research.
Linear feature coverage. Our results in Section 4 show that the generalized coverability condition (Definition 4), which exploits the structure of the value function class F, is not sufficient for online exploration. For the special case of linear functions (F {(xraa) (#(x,a) θ c cRd) a natural strengthening of this condition (Wang et al., 2021a; Zanette et al., 2021) is to as- sert the existence of data distribution μ {ua, ) such that Eaz C E,, (b(an,an (< for some coverage parameter C. Is this condition (or variant) sufficient for sample-efficient online exploration?
<
Further conditions from offline RL. There are many conditions used to provide sample-efficient learning guarantees in offline RL beyond those considered in this paper, including (i) pushforward concentrability (Munos, 2003; Xie and Jiang, 2021), (ii) Lp variants of concentrability (Farahmand al., 2010; Xie and Jiang, 2020), and (iii) weight function realizability (Xie and Jiang, 2020; Jiang and Huang, 2020; Zhan et al., 2022). Which of these conditions can be adapted for online exploration, and to what extent?
14

---

Published as a conference paper at ICLR 2023
B ADDITIONAL RELATED WORK
In this section we briefly highlight some relevant related work not otherwise discussed.
Online RL with access to offline data. separate line of work develops algorithms for online reinforcement learning that assume additional access to offline data gathered with known data distribution il or known exploratory policy (Abbasi- Yadkori et al., 2019; Xie al., 2021b). These results are complementary to our own, since we assume only that good exploratory distribution exists, but do not assume that such distribution is known to the learner.
Further structural conditions for online RL.. While we have already discussed connections to Bellman Rank, Bilinear Classes, and Bellman-EElder Dimension, another more general complexity measure is the Esstiattn-tttiiiionnn Coefficient (Foster et al., 2021). One can show that the Decision- Estimation Coefficient is bounded by coverability, but to apply the algorithm in Foster et al. (2021), one must assume access a realizable model class M, which leads regret bounds that scale with log|M| rather than llI
Instance-dependent algorithms. Wagenmaker et al. (2022) provide instancc-dependent guarantees for tabular RAC-RL which scale with quantity called gap- pup-visitatiin complexity. It possible to bound the gap-visitation complexity in terms of coverability, but the lower-order sample complexity terms in this result have explicit dependence the number of states, which results avoid. For future work, would be interesting to understand deeper connections between coverability and instance-dependen complexity measures (Wagenmaker al., 2022; Wagenmaker and Jamieson, 2022: Dong and Ma, 2022). See also Wagenmaker and andJaameee Jamieson (2022), which provides similar guarantees for linear MDPs.
C APPLICATION TO EXOGENOUS BLOCK MDPs
As an application of Theorem 1, we consider the problem of reinforcement learning in Exogenous Block MDPs (EX-BMDPs). Following Efroni et al. (2021), an EX-BMDP A (X,A, H is defined by an (unobserved) latent state space, which consists of an endogenous state s, E S and exogenous state & E, and an observation process which generates the observed state Iy- We first describe the dynamics for the latent space. Given initial endogenous and exogenous states ES and Ei E E, the latent states evolve via
Sh+1 ~ PA pendo (sh.on), and E (P (En):
that is while both states evolve in temporally correlated fashion, only the endogenous state s, evolves as function of the agent's 's action. The latent state (s),E)) is not observed. Instead, we observe
Ih qh (8h.En))
where 0h :S A(X) is an emission distribution with the property that supp(gn (s, E)) supp(gn (s' -('))=)= if ( ("). This property (decodability) ensures that there exists a unique mapping o S that maps the observed state Iy, to the corresponding endogenous latent state s).- We assume that (x,xxa ( (x).a). which implies that optimal policy π depends only on the endogenous latent state, i.c. 77 (z) 7 (0) (z)).
The main challenge of learning in block MDPs is that the decoder o' is not known to the learner in advance. Indeed, given access to the decoder, one can obtain regret poly(H, (H (S),AA)) ..AAA).// -T by applying tabular reinforcement learning algorithms the latent state space. In light of this, the aim of the EX-BMDP setting is to obtain sample complexity guarantees that are independent of the size of the observed state space | and exogenous state space [E], and scale as poly Ho, where F is an appropriate class of function approximators (typically either value function class F or class of decoders & that attempts to model o² directly).
EX-BMDPs present substantial additional difficulties compared to classical block MDPs because we aim to avoid dependence on the size | of the exogenous latent state space. Here, the main challenge is that executing policies whose actions depend on &n can lead to spurious correlations between endogenous exogenous states. In spite of this apparent difficulty, we show that the coverability coefficient for this setting is always bounded by the number of endogenous states.
15

---

Published as a conference paper at ICLR 2023
Proposition 8. For any Ex-BMDP, Ceov S |||-|A
This bound a consequence of a structural result from Efroni et al. (2021), which shows that for any (s.a) S x A, all æ E X' with e* (z) admit common policy that maximizes dj, (a. and this policy is endogenous, i.e., only depends on the endogenous state sn = 0% (2x). As a corollary, we obtain the following regret bound.
Corollary 9. For the Ex-BMDP setting, under Assumption 1, Algorithm ensures that with probability least 1 ô
Reg S (H O / (1))A//( /o)log(T)).
Critically, this result scales only with the cardinality [S] for the endogenous latent state space, and with the capacity log FI for the value function class.
Let us briefly compare to prior work. For general Ex- Bx-BBDPs, existing complexity measures such as Bellman Rank and Bellman- Dellmmn-Ellder dimension be arbitrarily large (see discussion in Section 5), Existing algorithms either require that the endogenous latent dynamics pendo are deterministic (Efroni al., 2021) allow for stochastic dynamics but heavily restrict the observation process (Efroni et al., 2022a). Corollary 9 is the first result for this setting that allows for stochastic latent dynamics and emission process, albeit with the extra assumption of completeness. This result is best thought of as a "luckiness" guarantee in the sense that is unclear how to construct value function class that is complete for every problem instance," but the algorithm will succeed whenever F does happen to be complete for a given instance. Understanding whether general Ex EX-BMDPs are learnable without completeness is an interesting question for future work, and we are hopeful that the perspective of coverability will lead to further insights for this setting.
C.I INVARIANCE OF COVERABILITY
Proposition 8 is a consequence of two general invariance properties of coverability, which show that Coov is unaffected by the following augmentations to the underlying MDP: (i) addition of rich observations, and (ii) addition of exogenous noise.
The first property shows that for given MDP M, creating new block MDP M' by equipping M with a decodable emission process (so that M acts as latent MDP), does not increase coverability.
Proposition 10 (Invariance to rich observations). Let an MDP M = HS, Let M' (X,A,P ".',A,,,''AAA 1I) be the MDP defined implicitly by the the following process. For each h E [H]:
8h41~ Pr (8) and r Rn (8h, Here, 8n unobserved, and may be thought of as latent state.
on (sk). where qr SS S- ((X) is emission distribution with the property that supp(qh (s)))) supplga (s')) 2 for s
Then, writing Ceav (M) ) to make the dependence on M explicit, we have
Coor (Mo))Cco(M)))
The second result shows that coverability is also preserved if we expand the state space to include temporally correlated exogenous state whose evolution does not depend on the agent's 's actions.
Proposition 11 (Invariance to exogenous noise). Let an MDP M (S,A,P P. R, H,S1), conditional distribution pexe; ; 3 A(E), and & E be given, where E an abstract set. Let x= E, and M'= let = (XX "'.,', RR HHxi)) be the MDP with state IT (sh,En) defined implicitly by the following process. For each h (H):
$141 Sht1~P((sH,aa)) T== Ri, (sh.
En+1 ~ (pxx0(e)))
Then we have
Ccov (co'(M)) S Ceov(M)
For example, it not clear how to construct complete value function class given access to class of decoders T that contains
16

---

Published as a conference paper at ICLR 2023
This result is non-trivial because policies that act based the endogenous state 8/, and En can cause these processes to become coupled (Efroni et al., 2021), but holds nonetheless.
Proposition 8 can be deduced by combining Propositions 10 and 11 with the observation that any tabular (fiiie-statc/actioo)) MDP with S states and A actions has Ccov S S.A. However, Propositions 10 and 11 yield more general results, since they imply that starting with any (potentially non-tabular) class of MDPs M with low coverability and augmenting with rich observations and exogenous noise preserves coverability.
C.2 PROOFS
Proof of Proposition 8. Let h E [H] be fixed. Let == (s).Eh) For each 2 (s.{) E S x let di (2) == PM (2h =2. Proposition of Efroni et al. (2021) shows that for all (s.g), if we define
TT argmax PTT (sn s). then
maxd (=) - (=).
well
That is, n. maximizes Pa (2 = (s.E)) for all E simultaneously. With this in mind, let us define
Na (x,a) = SA|A
Σ 5% (x). aES
We proceed to bound the concentrability coefficient for μ.. Fix IT Il X, and let (8,E) be the unique latent state such that (supp(y.ss..) We first observe that
di (x,a)
(x)
S A
JAn (x,aa
C (x)
Next, since 2n (2k),, we have
9 (x|2)))7(
dT(2)
2h (I 2d
d (z)
Finally, by Eq. (2), we have
dax (x)
=1.
dR (z)
d
Since this holds for all x E simultaneously, this choice for μal certifies that that Ccov S (||AA)
Proof of Proposition 10. Let denote the space all randomized policies acting on the latent state space S, and let IT' denote the space of all randomized policies acting the observed state space X. Let IPT denote distribution over trajectories in M induced by E 11, and let Q denote the distribution over trajectories in induced by N EII..
Fix he [H]. and let /4 E (AS A) witness the coverability coefficient for M. Define
(x,a) ( (x 6* (²())) (Ø' (x),a),
where : S is the decoder that maps E to the unique state s S such that x E supp(qu (s)). For any x' II' and (I,a) E X x A. letting of, (z), we have
d (I,a) gn s) (s) = s.a, =a) Q" (s), -s,0, =0) max Q" (s), =8,a) 1.00),00 =a) 16 (2,a)
gr ()))
(M(5,0)
(n(sa))
Finally, because the observation process is decodable, we have max,'en L (sh, 9,4g = a) max (s), =,00 a)) and
max (s), =s,ap =00 =Q)
< <Coor(M)
(s,a)
17

---

Published as a conference paper at ICLR 2023
Proof of Proposition 11. Let II denote the space all randomized policies acting the latent state space S, and let IT' denote the space all randomized policies acting on the observed state space X'. Let denote distribution over trajectories in M induced by E II, and let Q" denote the distribution over trajectories in M induced by n' ETI'
Fix E [M]] and μа E EASS x A) witness the coverability coefficient for M. For (x. let
where Q&A = is the marginal probability of the event that EΛ = in M', which does not depend on the policy under consideration.
For any n' E and (s,E,a) ESxExA, we have
(z,a) Q = - (I,a) Q - E) (s,0))
Q - ())
From Propositions 3 and 4 of Efroni et al. (2021), we have max Q (sh = 8,54 = 5, = =a) =
Q(A ean Q (sh = s.0%, =a) = Q(E = -) PP* (s), = s,0n = a), so that
max Q" (sh- = = = =E
QEA = ( Ppx 88,0 =a)
Q mn
< (M). max (s), = 8,0, =a)
(n(s,a)
D PROOFS AND ADDITIONAL DETAILS FROM SECTION
D.1 GOLF ALGORITHM AND PROOFS FROM SECTION 3
Algorithm 1 GOLF (Jin et al., 2021a)
input: Function class F, confidence width 3> initialize: F FF, DD +- Ø E
1: for episode 1=1,2...,,T do
2: Select policy T + (e, where prt
3: Execute ( for one episode and obtain trajectory (I (x) (1)
4: Update dataset: D/ -D(( (z) 1o = Whe(H)
5: Compute confidence set:
F + 30+{1EEt (EF: ( (fr.fhi)) min fi ( R.FF
(3)
where (f.'')
Σ
((e.o)-r-maxf((edd)) ( d'EA
6: Output न = unif (n.)( //Fo For PAC guarantee only.
Lemma 12 (Jin et al. (2021a, Lemmas 39 and 40)). Suppose Assumption holds. Then if B > is selected as in Theorem 1, then with probability at least for all t Algoorihn I satisfies
1. Q* FF.
(O all fEFW
Lemma 13 (Jiang et al. Lemma 1)). For any value function f (fI)...fH..
H
-21)) -
E (.
18

---

Published as a conference paper at ICLR 2023
Lemma 14 (Equivalence of coverability and cumulative reachability). The following definition is equivalent to Definition 2:
Cov
max he H
Σ
supdy (x,a)
(2.0)EXxx
Proof of Lemma 14. We relate coverability and cumulative reachability for each choice for h [H]. Coverability bounds cumulative reachability. follows immediately from the definition of coverability that if μ. ( x A) realizes the value of Coou, then
Σ
maxdi (z,a)=
Σ
(x(zaa)
Tell
(n(Iaa)
(x;a)xXxA
(z,a)ExXX
Σ
Coov Choviih(Cee (1.,a)
(by Definition 2)
(x,a)
= =Coov
Cumulative reachability bounds coverability. Define μa (z,a) max (2.a). Then for any π 11 and any (I,a) E x A, we have
di (x,a)
(x,a)
14h (x,a)
max max Maxx (z,a)/ (or)/EErsse aeeaa (x',0")
maxd (z',a))
Fell
(a
This completes the proof.
Proof of Theorem 1. Equipped with Lemma 14, we prove Theorem 1.
Preliminaries. For each we define
which may be viewed as
"test function" level h induced by E. We adopt the shorthand di = =d and define
df Ph
2 (x.a))
hh (I,a), and P
argmin sup AT
That is, Th unnormalized average of all state visitations encountered prior to step t, and μú is the distribution that attains the value of Ccov for layer h. Throughout the proof, we perform a slight abuse of notation and write E [zo - 1i= (00 [f] for any function :''' x:X'x A
(-1g
Regret decomposition. As a consequence of completeness (Assumption and the construction of Fl), a standard concentration argument (Lemma 12) guarantees that with probability at least 1 1-6, 6, for all t [T]: (i) Q" E and (ii)
(5)
We condition on this event going forward. Since Q' F we are guaranteed that f is optimistic (i.e., fi (x1 y (#1)) 2 (x m f-, (xn ))), and regret decomposition optimistic algorithms (Lemma 13) allows us to relate regret to the average Bellman error under the learner's sequence of policies:
H
Reg
(10 (z ( (11)
(a.a)=af())
((0 (I,a) (T.f))))
00 (x,a)
$If the minimum in Eq. (4) is not obtained, we repeat the argument that follows for each element of limit sequence attaining the infimum.
19

---

Published as a conference paper at ICLR 2023
To proceed, we use change of measure argument to relate the on-policy average Bellman error E (x.a))=a))) (6% (z,a)) appearing above to the in-sample squared Bellman error E (z.a)>= (6x (z,a))] the latter is small
consequence of Eq. (5). Unfortunately, naive attempts applying change-of- measure fail because during the initial rounds of exploration, the on-policy and in-sample visitation probabilities be very different, making it impossible relate the two quantities (i.e., any natural notion of extrapolation error will be arbitrarily large).
To address this issue, we introduce the notion of a "burn-in" phase for each state-action pair (I,a) E N' A by defining
Th (x,aa)=min (1 (x,a) Ccov
Ceov Coov (1,,))
which captures the earliest time at which (2,a) has been explored sufficiently; we refer to / (,, the burn-in phase for (z.a).
Going forward, let h [H] be fixed. We decompose regret into contributions from the burn-in phase for each atate-action pair, and contributions from pairs which have been explored sufficiently and reached stable phase "stable phase".
T
T
E ((
10% (2xaa)
(naa)af (2.0))
(z.0)aaft) ( (1,,)
cn-policy average Bellman error
burn-in phase
stable phase
We will not show that every state-action pair leaves the burn-in in phase. Instead, we use coverability to argue that the contribution from pairs that have not left this phase is small on average. In particular, use that (6%-' I 1 to bound
E (e.a))) [o [[<T
Σ
Σ
dee (x,a)
Edanionn Fondnen) (I,a) 22 (ui(1,0) 2C
2,0 (2.0)
where the last inequality holds because Je (x.a)) (x,a)= = d (a,))
"(r,a)+ + +d (ont.. (xx S 20 (oCooo//f (x,a),
which follows from Eq. (4) and the definition of Th- For the stable phase, we apply change-of- as follows:
T
(r.a)) (x.a)]]
(0
(0)
t=1
T
(I,a)
d (z,a)
Jo (I,a)
t= 2,a
1 (2, (I,a))
T
dh (x.a) (z,a))²
(6)
(x.a)
(=1 x,
(I): extraplaaiion emvor
(II): in sample squared Bellman error
where the last inequality is application of Cauchy-Sehwarzz Using part (II) of Eq. (5), bound the in-sample error above by
(II) (0((BT()
Bounding the extrapolation error using coverability. To proceed, we show that the extrapolation error (I) is controlled by coverability. We begin with scalar variant of the standard elliptic potential lemma (Lattimore and Szepesvári, 2020); this result is proven in the sequel.
Lemma 15 (Per-state-an aattte elliptic potential lemma). Let d _d (....r be an arbitrary sequence of distributions over a set Z (e.g., Z X x A), and let E AZZ) be a distribution such that d (z)/ C for all (z,t) E Z [T). Then for all Z, we have
T
(z)
d (2)+C()())) <Ologg()).
20

---

Published as a conference paper at ICLR 2023
We bound the extrapolation error (I) by applying Lemma 15 on aper- basis, then using coverability (and the equivalence to cumulative reachability) to argue that the potentials from different state- action pairs average out. Observe that by the definition of The have that for all Th (s, a). d (a.a) 2 Cooul (a,a)= = d (x,a) 2 2 (d)) (x,0) Ccouti (x,a)). which allows us bound term (I) of extrapolation error by
(1 (z, (I)
d (I,a) -dj (x,aa)
dn (x,a)
dh (I +Coor u (xxaa
220
d (I,a)
2
max dh (x,aa) JEE2
di (I, Ceov (I,a)
t=1
dh (x,a)
1 2
maxd
HE h (x.a)
max (s,a) 1= de (I,a)+ C 1 (x,a)
2,0
2Caa by Lomma
<O(log(T) by Lemma
< <O(CovloggT))
(8)
To conclude, we substitute Eqs. (7) and (8) into Eq. (6), which gives
H
Reg <
16 (x,a) 0o H (( (2.
Proof of Lemma 15. Using the fact for any U [0.1], u 2log(1 [+ u), we have
T
(z)
T
d (I,a)
Σ
Eie dia (z)+ (2)+ (.lla,))
<
log
1+
(2) (z)+CC
t=1
(since d' (I0
T
Eisuta d (3)
= 2 -
log
Eicrdo +C-H((z,)
t=1
Eiertid' (2) +C-
2log
Exendo (2) +(,,a(
(=1
T
(=)
= 22og
C-p(x,a)
< 2log(T++)..
(since d (xza))/([z (T)
This completes the proof.
E PROOFS AND ADDITIONAL DETAILS FROM SECTION 4
E. ADDITIONAL DETAILS: OFFLINE RL
Proposition 16 (Generalized concentrability is sufficient for offline RL). Given access to an offline data distribution μ satisfying generalized concentrability (Definition 4), if satisfies Assumption 1, one can find an E-optimal policy using (f. F(.-1) samples.
Proof of Proposition 16. Given an offline dataset D= (D with n samples for each layer h E [H] under the distribution pa. the MSBO algorithm (c.g., Xie and Jiang, 2020) produces value function f E F of the form
H Σ
f 8t argmin JEF
Cn(fn.htt))
min La Lulthrfita). R.FFF
21

---

Published as a conference paper at ICLR 2023
where (x(ff)==
E ((x,a))--max(( yI,f
(s.o,ra"))Di,
By adapting the proof of Theorem of Xie and Jiang (2020) (or Lemma 12), one can show that under Assumption 1, with probability at least 1- satisfies
E (2,0)/m (ChhCo,a)) ((f(t..)-TThhtttlGe) Tnhnt))aaa)))
log((
n
The result now follows by applying adaptation of Xie and Jiang (2020, Corollary 4), which shows that for any FEF,
2max
B (a (1fa(1,))) -
a
H
2
Hmax Tell hml
E (2.a) (ee
H Heoone( > Aml
22
E [ (h (by Definition 4)
Cconc (u,, (1/15)
/211
E.2 PROOFS FROM SECTION
Proof of Theorem Assume without loss of generality that H (X), this does hold, the result is obtained by applying the argument that follows with H' =71= (ox,
We consider family of deterministic MDPs with horizon H. We use a layered state space XU---XHH where only states in X₁ are reachable at layer h. The state space is binary tree of depth X states. The are two actions, left and right, which determine whether the next state is the left or right successor in the tree.
1-1, which has Σ (o),(()) (X)
For each MDP in the family, we allow single action at a single leaf h= H to have reward r = 1, give reward to all actions in all other states. For each such MDP, use (x],,a,,) denote the single state-action pair with r 1. We also use (27, .7,)) for & [H] to denote the unique path from æı to (xfr,at)) Note that the optimal policy is to follow this path, i.e.
dx (I.a)
(2t,
We choose Fn, to be the set of all possible indicator functions for a single stte-acciion pair:
Fr = [fn('' ,a') =z'== V(z,a) E AA..
define F F H. Note that for each [
(* (2), - ,j = = E
In addition, have log =
Completeness. We first verify that the construction satisfies completeness. Fix fn E Fú, and let fa( [(x a af.n) for some (z E Xr x A. Then for any (0=-1;0)-1) Xn-1 x A. we consider two cases. First, if o is not the unique successor of (zh-1,0p.. 1), then (Th ( Otherwise.
(Th (Tn-1fh)Eh =
> P(N 2k-1. (maee))...m
= =( (h-1,(h-1>>
(as maxa, (n 1 (x)A)
xF
1.
This means TR-1fh fr. E F because there exists a single (#n-1.4h-1) pair in X x such that TT-)f/)( (.)0))11,,0.11)) 1,0
22

---

Published as a conference paper at ICLR 2023
Generalized coverability. We now show that the construction satisfies generalized coverability. Fix an MDP in the family with optimal path ((r),aa))) We will show that for all f f1:H E if fuH + Qu. then there exists h E [H]] such that
Edg; (Uxx,waww (Th (TwJe Jw (x ,xx)) = (Ju (1 (Tw (1) ( =1
(9)
From here, the result will follow by choosing JAn d% vh E [H]. Indeed, using the boundedness of fun FF,, we have
Ed Eag (fh(T)) (Th SH,
for all E II, meaning that Eq. (9) implies that (co S this problem instance.
We proceed to prove Eq. (9).
Based on the definition of F. know that 10 for all h [H]. Therefore, if we assume by contra-
(fi - (xt
diction that fu. + Qi:H and there does not exist an h' E [H] that satisfies Eq. (9), we must have
(10) By the condition Eq. (10), we have (TH fH (1 (z) (1 (H) = which implies that fa(a))e)))) = for all h E [H] From the construction of F, we know Qi.H is the only function with Q7 (1) =1 for all E (H). which gives the desired contraction, and proves that such h [H] must exist, establishing Eq. (9).
=
WhElu).
Lower bound on sample complexity. A lower bound of 20(H) samples to learn 0.1-optimal with probability 0.9 follows from standard lower bounds for binary tree-structured MDPs (Krishnamurthy al., 2016; Jiang al., 2017) (recall that since there are 2 leaves layer H, and only one has non-zero reward, finding a policy with non-trivial regret is no easier than solving multi-armed bandit problem with 2/2 actions and binary rewards).
F PROOFS AND ADDITIONAL RESULTS FROM SECTION
F.1 ADDITIONAL DETAILS: SEQUENTIAL EXTRAPOLATION CORFFICIENT VERSUS BELLMAN-ELUDER DIMENSION
The discussion in Section 5 (in particular, Proposition 4 shows that Bellman-Eludee dimension and Bellman rank fail to capture coverability as a result of only considering average Bellman error rather than squared Bellman error. In light of this observation, a seemingly reasonable fix is to adapt the Bellman-Elude Eluder dimension to consider squared Bellman error rather than average Bellman error. Consider the following variant.
Definition 9 (Squared Bellman-Eludee dimension). We define the Squared Bellman-Eluder dimension dim (F A.l,,h))for layer h is the largest dE N such that there exist sequences (dh, ,0h ,...,d,, C and (8% "...,%%") F Fh+, such that for all te [d].
E co
e(())
and
Σ E [T
(11)
for c()) ....,E(() E. We define dim
dai sq F.III,,h.)
This definition is identical to Definition 6, except that the constraint
E (E df (o 2 S in Def-
V E [(W S which uses squared Bellman error instead of average Bellman error. By adapting the analysis of Jin et al. (2021a) it possible to show that this definition yields Reg < Ö (H /inf/iinfaaaa/ fo -oeff=TT-immm dim [F., Fl). If one could show that dim (F.IT.c) S Cco. powy-oolllloee (1 this would recover Theorem 1. Unfortunately, it turns out that in general, one can have dim (F.II.=) ((Coov/E), which leads to suboptimal 22/3-type -type
inition 6 has been replaced by the constraint
regret using the result above. The following result shows that this guarantee cannot be improved without changing the complexity measure under consideration.
23

---

Published as a conference paper at ICLR 2023
Proposition 17. I TeN, and let Ey There exist MDP class/policy class/value function class tuples (M1,I11FF)) and (M2,llg.F2) with the following properties.
All MDPs Mi (resp. M2) satisfy Assumption with respect Fi (resp. F2). In addition, (1).
2. For all MDPs in Mi, we have ( (Fi, x 1/ET, and any algorithm must have E [[Reg] forsome 3. For all MDPs in M2, we also have dim BE (F2,IIl,,TT) x 1/er, yet Ceov =11) and GOLF altains
(((T23)) forr some MDP in the class
E| E[Reg] [[Reg]= =Ö(VT).
This result shows that there are two classes for which the optimal rate differs polynomially (S2(T2/3) vs. Ö(VT)), yet the Bellman- Eluderr dimension has the same size, and implies that the Bellman- Eluder dimension cannot provide rates better than 22(22/5) for classes with low coverability in general. dimension fails capture the optimal rates for the problem instances in Proposition 17 is that the definition in Eq. (11) only checks whether the average Bellman error violates the threshold e, and does not consider how far the error violates the threshold (e.g.. 2 [] >E
Informally, the reason why Bellman-
and // "] 1 are counted the same).
In spite of this counterexample, it is possible to show that the Bellman -arudrr dimension with squared Bellman error is always bounded by the Sequential Extrapolation Coefficient up a poly(e factor, and hence can always be bounded by coverability, albeit suboptimally.
Proposition 18. Let F be [0, va-uudd function class. For all T N and > 0, we have minfdim@e va (F,,Idi (F,, SF, 22
F.1.1 PROOFS FROM ADDITIONAL DETAILS
Proof of Proposition 17. Let the time horizon T E N be fixed. We first construct the class Mi and verify that it satisfies the properties the statement Proposition 17, then the same M2.
Class Mi. We choose Mi to be class of bandit problems with H 1. Let a parameter E E [0,1/2] be fixed, and let A ===E; E We define Mi - (M ...,M,))), where for each ();
The action space is A A= A=
The reward distribution for action E A state xn is
We define F= (f() and 11= { If f Note that since H = 1, completeness of F is immediate.
For each EM the mean reward function 1/1
Lower bounding the Bellman-Fludde dimension. Let M(A) be the underlying instance. We will lower bound the Bellman-Eliee Eluder dimension for layer h = 1. Consider the sequence di "...,dA-"", where
d = ,(()))) and 8ih) ,.....fA 1) where 81 := f(() - Tife = f1 fi (recall that we adopt the
convention fH+1 =). Observe that for each E [A- 1]. we have
1 (21 (z (
yet
ΣB [6 (1) (1)))
Σ
(z)
This certifies that dim (F.I.))2A-122
for all <
Lower bounding regret. A standard result (e.g.. Lattimore and Szepesvári, 2020) that for any family of mulli--rred bandit instances of the form (M ((",) where M has Bemoulli rewards with mean 1/2 + A1 (a=i) for A < 1/4, any algorithm must have regret
A A
E Reg] 2(1) -iin
AT
for some instance. We apply this result with the class Mi, which has = and A= which gives
E [Reg]] 2 2-1)
T 7
Choosing 61 ==r====--- yields E RRegg 2 (33333 whenever is greater than absolute constant.
24

---

Published as a conference paper at ICLR 2023
Class M2.
Let parameter E2 [0,1/2] be fixed, and let A == Ez' (we assume without loss of
generality that Eg E I)). We define M2 {M ,(.,,, where cach MDP M is defined follows:
We have -, and there is layered state space X' 21 22, where X1 (21) and X22 {v.2).
The action space is A 4 A].
xj is the deterministic initial state, Regardless of the action, we transition a with probability 1 1- and with probability 82.
For each MDP M all actions have zero reward in states 21 and z. For state y, action has reward 1 and all other actions have reward O.
We let f( denote the optimal Q-function for M which has:
(z" =2 and ( -2.)
f2 (yy.a)=
We define F=(f")= is clear that this class satisfics completeness. define [I= for states where there are multiple optimal actions (i.e., fr, fx,, we take (z) )) to be the optimal with the least index, which implies that y, ,,2 for fEF.
Verifying coverability. u2(yaa) = W for E A. is immediate that coverability is satisfied with constant for 1. For h=2, we have that for all π ETI,
We choose μN (z, a) 1f 21,a 1}. We choose μ2 1) and
(2,1) 1-82
2
p2(2,1)
1/2
and
d3 (y,a)
82
22
pz(yya)
#2 (2(y,a)
Hence, we have Coov S 2; note that this holds for any choice of 22.
Lower bounding the Bellman-Eluder dimension. Let M(4) the underlying MDP. We will lower
bound the -Eluder dimension for layer h = 2. Consider the sequence d²" :...,d2 ...,,dA--), where (()) d² = ,010) and 0/2 ....,5=-- where 5552) == f(t) T2f
f2" f/ (recall that we adopt the
convention fu+1 =0) Observe that for each t 1]. we have
1g 10 (x2,)2))) (y,t)-f22 f(a² (y.t)l
yet
Σ E 5o (8h (Iz, = > (v.i) -v.1)-12 f2- (w.i))
i<t
This certifies that dim (F I1, 1212 /2 for all <E2-
Upper bound regret. To conclude, set E2 ET 1/7-1/3 With this choice, have dim (2,, 2 (((7" ). Since the construction satisfies completeness (Assumption 1) and has Coon < and 22, Theorem yields
Reg
Proof Proposition 18. Fix h [H]] and n E N, and consider sequences (dht ,d ...,.d.)) and (5%)) ,60 ,...,6h") that satisfy Eq. (11) (that is, the sequences witness the value of dimBe (i)),,,))) Then
det
20 [8
dimen sq
(F,IL,,))))
(eco)2
25

---

Published as a conference paper at ICLR 2023
IE [0%
%
1
(E01)
1+
1-1
E do
13%
1=1
(by
Σ 18 b/
10
18 - (E(11)3
(+(01)
E [
(e
1+
E dh
18
E
2
h
(by 600)
<
<|E 22
10% 11)
(ew))
2
1 Σ 1=
TE 100
10
2
E
(by - 2c)
12
SECRL RL (F,Ilm)
g2
This implies for any 7'>0, 0,
SECRL (F,IITT)
min(dimge (F...
(
g2
F.2 PROOFS FROM SECTION 5
Proof of Proposition 4. We present counterexample for both Q-type and V -tpp Bellman-Elude dimension. We recall that the V-type Sillman-Eludee dimension is defined by replacing Fn. - -TrFr+1 with VF,, P7 -T.Fa and DH with D in Definition 6, where VF, VT. 12 {(A= TT (((p))) fEF) C (X' + IR) and D h.r = (d)(() (-): 11] C ((X); see Appendix F.3.1 or Jin et al. (2021a) for more background on -typee Bellman-Elude dimension.
V-type Bellman- dimension. The hard instance for V-type Bellman- Eluder dimension based on the construction of Efroni et al. (2022a, Proposition B.1). which shows that for any d = 2 (i E N), there exists an exogenous MDP (ExoMDP) with |S|=3 = endogenous states, AA = 2, H = 2, and d exogenous factors, with the following properties:"
1. There exists a function class F such that Q* E E and [ = d. In addition for all E with f+Q".
y is 1/8-suboptimal
2. For all f.f' F\Q",, we have (note that H 2)
E
of
(2(
11
(12)
SowaT 5.2
3. Ccov <6; this is consequence of Proposition 8 and the fact that the ExoMDP model in Efroni et al. (2022a) is special case of the Ex-BMDP model in Section 3.2.
This means that if we take (f()) f(t.)( to be any ordering of the set of functions in F\(Q), then set 880) h/ = f Taffit and df = d;, (())
we have that for all [d-1]. 1].
E
Ba a 2
[o80] - and Σ Ba and 2
(52 2 =0.
This implics that the V-type Bellman-Eluder dimension dimgE-v (F, s) at least - for all << 1/2. is straightforward to verify that this construction in Efroni et al. (2022a) satisfies Assumption 1 (completeness), because functions in the class have fa =T=2 (that is, zero Bellman error at h- 1). As result, since H = 2, completeness for this construction is implied by Q" F.
Technically, the construction in Efroni el. al. (2022a) has stochastic initial state with known distribution. This be embedded in our framework, which has deterministic initial state, by lifting the horizon from to
26

---

Published as a conference paper at ICLR 2023
Q-type Bellman-Eludee dimension. The construction above immediately extends to Q-type. This is because in the construction, the value of R2(x,)) and f2(2.)) depends only on z (i.e., is independent of the action) for all E F (ef. Efroni et al., 2022a, Proposition B.1). Therefore, for any f.g E F, we have,
B By ,
(13)
This implies that the Q-type Bellman residual matrix
E (noo))aa (o(a,,a)RR(a,aa)) 1.8'F
embeds the scaled identity matrix and, via the same argument as for V-type above. immediately implies that dimBE (I,,I,))) 2 1 for e S 1/2.. before, we have Coov S 6, and F complete. O
For any deN, there exists an MDP M with H and |A| a policy class II with [|| dd, and value function class F with [F] =d satisfying completeness, such that Ccov= 0(1), yet OLIVE (Jiang et al., 2017) requires at least ((d) trajectories to return a 0.1 0.1-optimal policy.
Proposition 19.
-
Berrag--Bellmaa-errr--bbieee hypothesis elimination algorithm, also suffers from the lower bound in the construction from Proposition 4. By Eq. (12) (V-type OLIVE) and Eq. (13) (Q-type OLIVE), we know that any sub-optimal hypothesis fEF "Q" cannot be eliminated until y is executed. On the other hand, the construction ensures [ = 7/8 whereas J(xx)( 3/44. This means OLIVE will enumerate over Q* before finding a 001-optimal policy for this instance, and hence suffers from complexity of (dd [FF[=d).
Proof of Proposition 19. We now show that that OLIVE, a canonical
Proof of Theorem 5. As in Theorem 1, as consequence of completeness (Assumption 1), the construction F(9), and Lemma 12, we have that with probability least ô, for all [T]:
(i) Q' EF and (ii)
2 (2.a) (6), (z,a)) (z.,a)) <0(3).
and whenever this event holds,
T
T H
Reg < (o)) J(((())
[1 (x,a)
- -TToShh (x,a)
(a.a)~
1=111
(m,a)
To proceed, we have that for all / [[]],
T
T
1- 1v IVEi'B 69 [()
1/2
E
[8)o]
IvE (9) (8)
T
E 50
[
T
Iv
Σ E (00
)²1
E 40
[6
1=1
(by Seachh-Schwardd innquaall inequality)
T
E (2)
VBT
E g0
(8%0)2]
VSECRL (F -II.
(by Definition 13)
Therefore, obtain
Reg H (VSECRL((..IITT)
Plugging in the choice for 9 completes the proof.
27

---

Published as a conference paper at ICLR 2023
Proof of Proposition 6. We prove general result. Consider of distributions D C (2), and set test functions (2 (0,10. We define generalized form of coverability with respect to D by
Ccov ( (2): inf sup
(14)
HEA(2)dE3
We will show that, for any T > O,
SEC(V,D.T) Coou (D)
which is implies Proposition 6.
Going forward, we fix an arbitrary sequence (d " dd.......d (160) abez) .....bmr y. Following Eq. (4), we define
CC as well as an arbitrary sequence of
1 argminsup HEA(Z)dED
(15)
/
In addition, define d Eie For each 2 Z, let
r())==ming Σ d (2) 2 Coouti (2)
(16)
We decompose E [ub(t]
E ce [ Euco (=]]((]]]]]<+(( +Ex1) (1 (2)((
Then,
E ((t) (2)1)) 2
1= E Ea (1560))2]
E Ego0) (660)) (2) < (2)]
E Ego [et(*) (2) T (2)1]
(17)
IV IVE [[
1vE Eaco) [(vbr)]
(II)
where a S b shorthand for a 50(b) We first bound the term (I),
T (I) <
t=1
P
Eg0 [1(t<T
(by ( 00,1], V v)
t=1
Edto
[1[|<T[=)]]
(by Egt [[[[<<[=)]] 1
T
10 (x)1tt<(())
=
(1(s)- (2) (2)+))))))
zE2
(Cov(D))u"
xE2
< (2),
(18)
28

---

Published as a conference paper at ICLR 2023
where (a) follows because (2) (3) for all 2 E 2, as consequence of Eqs. (15) and (16).
(cov(
We now turn to the term (II). First, observe that
1 (2)
2E2
1/2 de) (2)
(2)dd()
1[t
(z)
26
Baco [[
(by Cauchy-SShwwrzzinequu inequality)
do)
ZE2
By rearranging this inequality, have
(())
(II)
(defining 0/0=0)
d=)
1=1E2
1|t2 (t))
2
(by Eq. (16)
1=1:Z CoeN' 1tt (2) - ((0)))
(2))
1l Coo 1tt (z)+ +1=+1110 (2)
T
d (2)
maxd (0) (2)
i5.
d (=) Coou' 10t (z)
1=1eZ
d (z)
Ccov
(r)
Σ
(by Eq. (14))
d (
ZEZ
S Ceov D
M (z)log(T)
(by Lemma 15)
ZE2
Ceov ( (T)).(
(19)
Substituting Eqs. (18) and (19) into Eq. (17), we obtain
DEC(V,D,T)& S Ceon (P))oO(T)
Proof of Proposition 7. This proof provides a slightly more general result. Consider set of be given. We consider an abstract
distributions A(Z) and set test functions C version of the Bellman- largest de such that there exist sequences (d _d .....de) } C D and {150) gi(e) 2l00) } C such that for all t [d].
dimension with respect to D and V. We define dimBE (V, ,,,s)
3) is the
(Eaco ((btt1) 2 (e(1)) for c() (...,((d) 2 c. We will show that, for any all TEN,
Egies [1)")))> and
(20)
SEC(W.D,T) inf + (V,BBeeVV))))))).)) (V.D,)))-log(T) e>0
which immediately implies Proposition 7.
This definition coincides with distributional Eluder dimension (see, e.g., Jin et al., 2021a), which only differs from Dellman-Fllude dimension the notation of test function. We overload the notation for dimsg over this proof for simplicity.
29

---

Published as a conference paper at ICLR 2023
A generalized definition of E-dependent sequence. In what follows, we rely a slightly different notion of an E-fin jijjdddeendent sequence from the one given in Jin al. (2021a, Definition 6) and Russo and Van Roy (2013). We provide background on both definitions below.
e-(in)dependent sequence (e.g,, Jin et al., 2021a, Definition 6). A distribution v E D is depeendent sequence ( ,...,, C if: When | [+i]] >E for some & E V, we also have Σ Zi=1 (1E [+)) e² Otherwise, is e e-independent if this does not hold.
Generalized e-(in)dependent sequence. A distribution v E 2 is (generalized) E-dependent on
sequence {1(t), .... ) D if: for all e' 22, if [[][ s' for some v E V, we also have Σ Gi=l 2i=1(B (E,(o] > E²2. We say that y/ is (generalized) e-independent if this does not hold, i.c., for some E'2 22. has [E/ e but (E, [+)))
The generalized definition above naturally induces new implication (which the original definition may not have): If 2E, E, then d-deendents sequence = e' e'-denendent sequence, or in other words, e' e'-ndependent sequence = E-independent sequence.
The definition of the distributional Eluder dimension (see Eq. (20)) can be written in two equivalent ways using original and generalized definition for a e-indeppendent sequence: dimBE (V, the largest d E N such that there exists sequence (dd),d0) .....d") C such that for all 1 [d]:
(i) d is E' -iddeppendenn of {d() ,d ....."'---") for some E' 22..
iii) de is (generalized) e-independent of {d .d..)....dd" "...,
lby the implication above]-> (dd"),d'e "...,""""."") } for some e' 2..
d is (generalized) s' e'independdent
This indicates that the distributional Eluder dimension can be equivalently written in terms of general- ized independent sequences. Going forward, we only use the generalized s-(in)dependent definition, and omit the word generalized.
Setup. Let use dimaE( (s) as shorthand for dimBE ( V V, By Eq. (20), we know dimBE(E) also upper bounds the length sequences {d(t) (( (....d(e) CD and (1b() abitt (..gg))))))))) } C V such that for all / [d].
Eu [800]|> e()) and Σ Eaco ((1300) (((3(co)]]set {e)
for (1)) "..,,,(((() = (note that the square is inside the expectation which is different from Eq. (20)). e(1) Now, for any {d d(t),.. ... d D and {1bt2, vire, .., 160 C, we define 3r0 > Easo [(160))7] We will study the sequence
EgeD [bmr]
Egca (ggs Egery 12
(21)
1v33
1V300
1V3
Fix a parameter a a>O0, 0, whose value will be specified later. For the remainder of the proof, we use L
to denote the number of disjoint a 1v 330 -dependent subsequences of d (d ddd ...... de for each E [T].
Step 1. Suppose the t-th term of Eq. (21) is greater than a², so that [E [b>(t)] IV From the definition of (9),, we know there have at least L (9) disjoint subsequences (d "....d (denoted by ())) (()())) such that
Z,(1)
Σ
Σ
(E,
(22)
(Ive@(+)
On the other hand, by the definition of ( we have
(t)
Σ
(E, (2)00)22
Baco (2)))))) BB0
(23)
Therefore, combining Eqs. (22) and (23) obtain that, if Eaa > TV/TT for some / [7),
[2/c0]]
1
g > I (1V8 1
(24)
a²
30

---

Published as a conference paper at ICLR 2023
Step 2. On the other hand, let ( be the longest subsequence of [T). where
E d(is) [00)]2
a bjEE
1V3%)
For compactness, use {u p (x) abbreviate { ,d ).).. We now argue that there exists j E [k], such that for plt there must exist at least
K
(25)
dimBE (a)
dimge(a)+1
a-dependent disjoint subsequences in {Da) ui8) , ,... ,u"" }} (the actual number of disjoint subse-
quences is denoted by L*). This is because can construct such disjoint subsequences by the following procedure:
(1) For j j G + {1 Then, stt +1.
(2) v dedependent on G "5.,..,66"" terminate the procedure (goal achieved).
(3) Otherwise, we know un) is a-independent on least one of (() G (denoted by 6*)
Update 6 (~())) J.j j++ and go to (2).
From the definition of dimBE (ax), we know if | N dimBE (a) + 1, any v E Dh must be a- dependent on t (for each i E [L*]. Therefore, such procedure must terminate before or on j(mmax) L di) Thus, if j(mas) K, termination in (2) must happen. This only requires L
to satisfy
L (d)mBE(a)+L* SK
L
dimBE(a)+1
That is, as long as L*
8 dime
the termination in (2) must happen for some j SK.
Step 3. As we discussed at the beginning, a-dependence implies a' deeeeddence for all a' 2 a. This means the L in Step lower bounds m [ in Step 1, because (d (it)) subset of ) ( d..)). Thus, combining Eqs. (24) and (25), obtain that,
K
max [E(T]
dimBE (a)+1 1.
a
This implies that
3dimBE +1.
SS 1
(dimBe(()) (1)))
(suppose S 1)
a²
a²
As consequence, for any (0,1), by setting a=
Egr [2/0012
3dimBE (Ve)
Σ
> e
+1.
(26)
1V30
4t e ( > 2.. ? denote the sequence in Eq. (21) reordered in a decreasing fashion. For any parameter E (0,1) be specified later, we have
20
12
T
E
1=1
T
< T w
(e (()))w))) >w).
1=1
Observe that for any & [T'] such that (
> w. if if (()) > 37 ws we have
T
Σ
1
(c>>1)
i=1
31

---

Published as a conference paper at ICLR 2023
3
dimBe (vn)+1
(by Eq. (26))
dimBE (Vi) +1
7
3d
S 1-1
(define d: di=dim (Vw))
6d
e S min
>1)
(t-1"
Therefore,
T
T
6d
1 (1) > w)
S d+
t-1
f=++1
d ddl
< <ii+eimeE (V 6dimBE (Vw) log (T).
Selecting w == implies
SEC(T) inf (S) (lo e>0
This completes the proof.
F.3 DISCUSSION: RELATIONSIIIP TO ADDITIONAL COMPLEXITY MEASURES
F.3.1 SEQUENTIAL EXTRAPOLATION COEFFICIENT: Q-TYPE VERSUS V-TYPE
The Sequential Extrapolation Coefficient, defined in Definition 8), can be thought of as general- ization of Q-type Bellman-Eludd dimension (Jin et al., 2021a). In this section we sketch how one can adapt Sequential Extrapolation Coefficient so as generalize V-type Bellman-Elude dimension instead. Note that V -ttppe Bellman-Eluder dimension subsumes the original notion of Bellman rank from Jiang et al. (2017).
We define the V-type Sequential Extrapolation Coefficient for RL as follows.
Definition 10 (Sequential Extrapolation Coefficient for RL, V-type). For each he [M]], let h. (d) II] ((X) and Vy, FT+F {(fr Tn FF + R). Then define,
SECRL
SEC( -T. D h. T)
AE(H
We recall that the V-type Bellman-Eluder dimension dimBE (F, (I,5) is defined analogously, by replacing Fú -T.F VF, -T,Fr11 and D + Dll h.a in Definition 6.
Lastly, we give Vttppe generalization of Definition 2 (i.e., coverability w.r.t. state only), for a policy class follows:
d
Ccovy :=
inf MI..., E (A( Ph 10o
sup
(27)
As a simple implication, we have Ceou.v S Coou S Ccov.v
Note that the V-type variants of sequential extrapolation coefficient, Bellman-Bluder dimension, and coverability differ from their Q-type counterparts only in the choices for the distribution and test function sets. Since proofs for Propositions and 7 hold for arbitrary distributions and test function sets, we immediately obtain the following V-type extensions of Propositions 6 and Proposition 20 (Coverability
SEC, V-type). Let Ceorv be the V-rype coverability coeffi- cient (Eq. (27)) with policy class II. Then for any value function class F. (F, & O (Ccovvv log(T)).
32

---

Published as a conference paper at ICLR 2023
Proposition 21 (Bellman-Eludce dimension = SEC, V-type). Suppose dimge-v(F, (F,II,E) be the V -type Bellman- Eluder dimension with function class F and policy II, then
(F,,L,(F,II,T)
inf (o + (F, log(()) =>0
As shown in Jin et al. (2021a), GOLF (Algorithm 1) can be extended to V-type by simply replacing Line 3 in Algorithm with sampling Sh.
x Tunif (8), - and a₁ uniff(A) each h E [H]. By slightly modifying the proof of Theorem 5 one can obtain similar sample complexity guarantees based on the -ttype Sequential Extrapolation Coefficient. We omit the details here, since the only differences are I) --type analog of Lemma 12 (provided by Jin et al., 2021a, Lemma 44); and 2) trivially upper bounding the quantity E df [(0% (used in SECRL.v) by |A 4/ a [(,
(controlled by in- in-sample error). Note, however, that due the uniform exploration, this algorithm leads to a sample complexity guarantee of the form
J(m*) {+)) H
T
but not regret bound.
F.3.2 CONNECTION TO BILINEAR CLASSES
The Bilinear class framework (Du et al., 2022) generalizes the notion of Bellman rank (Jiang et al., 2017), which captures various more structural conditions via an additional class of discrepancy functions. In this section we sketch how one can generalize the sequential extrapolation coefficient (SEC) further by allowing for the use of general discrepancy functions to form confidence sets and estimate Bellman residuals, the vein of Bilinear classes.
Definition 11 (EC). Let Z be an abstract set. Let v c (3 + ) be a function class, and let Dy(= (du: : th (.).B..d [p : 1p E V}) (()) be two corresponding distribution classes, and Co(= (lep v w)) C (2 + R) be a corresponding discrepancy function class. The Gen-SEC
length T is given by
E
[26501]]2
SEC (V, Fy Ev.
sup wit)
(28)
p
100)
apply the ee leanning, one can (for each each level Dw [d] (-::) E and B. = (dd, x Tes ((:)))= ((:-)):==I[]+) II)), where (dx (x.a)) == d(x) m (for any E (X), ग E (x + ((A) and (I,a) E x A), and Test.vs denotes the estimation policy depending on vua (e.g., greedy policy w.r.t. t/n or uniformly random policy over A). The discrepancy function class Lg can be selected according to the original Bilinear rank for covering various structural conditions, and setting Ly // recovers the original SEC.
By combining GOL.F and Theorem 5 with the approach from Du et al. (2021), one can provide sample complexity guarantees that scale with the Gen-SEC, We omit the details, but the basic idea is to form the confidence set using the discrepancy function class Eg rather than working with squared Bellman егror.
Bounding the generalized SEC by bilinear rank. In what follows, show that the abstract version of the Generalized SEC in Eq. (28) can be bounded by an abstract generalization of the notion of Bilinear rank from Du al. (2021).
Definition 12 (Bilinear rank, finite dimension (Du et al., 2021)). Let Z be an abstract set. Let
I (Z R) be a function class, and let Dy (== (dg. : v }. (== {ps & 4. A(Z) be two corresponding distribution classes, and Eg (:= (fg : E L }}) C (Z + R) be a corresponding discrepancy function class. The class vi is said have Bilinear rank d if there exists vi* T and functions X.W C C(V- such that 1) Eeeell [xb))la and E Ml (WW))) & Bw, and 2)
Edg [+]] < (W))))
VOEV
Ep f -((("")-((("" (X*)),XXX
We define dimsi (V. Dy e uo Ev the least dimension d for which this property holds.
33

---

4B T Published as a conference paper at ICLR 2023
Proposition 22 (Bilinear rank Gen-SEC). Suppose SEC Dv. By Ly. T) and
dimai V De, Fv 2x) be the gen-SEC and Bilinear rank defined in Definitions 11 and 12 with respect function class V, distribution classes D and D v, and discrepancy function class 2g. Then we have,
Lx, Stmmss dimsi B Lv Lv Hog 1+ 4B T
SEC De
Proof of Proposition 22. Throughout the proof, we use d plo and go as the shorthands of dgse) Puct) and Eyit). We study the quantity,
T
T
E Mc k
Epto
(2
E
pp
[20]2
1=1
By Definition 12, we have
2 (W -
and
Boo 1 = 1+ -
2 (W(v))) (b))
= -1(((b0))- -WW())--W(W))ll
where Σ,:= 4
I+ >/ 1== X ((vh(o)))) (1brr)))((5) (((()))
We bound
E Edces S/WW (())))
S [ (( ( (
which implies
T
T
1^ (nIX((111))1
E
Epts
[2
del(ET))
< 2log
det(En)
4B2 d
< 2dim (VI Bu Re log 1+
where the last two inequalities follow from the elliptical potential lemma (latttiore and Szepesvári, 2020, Lemma 19.4). Putting everything together, we obtain
SEcsen (V, Py 4dim (V,2g Ey E 1+
d
G EXTENSION: REWARD-FREE EXPLORATION
Reward-free exploration investigates is a problem where 1) the learning agent interacts with an environment without rewards, aiming to gather information that 2) in a subsequent offline phase, the information collected can be used to learn near eetrioptimal policies for a wide range of possible reward functions (Jin et al., 2020a; Zhang al., 2020; Wang al., 2020a; Zanette et al., 2020b; Chen et al., 2022). This section provides a reward- free extension our main results, and gives sample complexity bounds based on coverability for reward-free extension of GOL.F.
34

---

Published as a conference paper at ICLR 2023
Function approximation. We assume access value function class F, which is used for the offline optimization, and a function class, G, which is used for the reward frree exploration phase. Following the normalized reward assumption, assume 9n E & A [0.1], V(g.h) E G [
We define PA as be the "zero-reward" Bellman operator for horizon / [H]. That is, for any 9h E 9 and any h e [H],
(Pho)+)(Th,a))= Σ EPPlIan41 (n)aa)) (1+1(
an+ an+1EA O
We let R denote the target reward function used in the offline phase, which is not known to the algorithm in the offline exploration phase. We make the following assumption.
Assumption 2 (Reward- free completeness). Let TI:H be the Bellman operator with the target reward function R, and F be the function class used to optimize the target reward function. Then for all h [H]
(a) Pugn+1 Gh for all 91++1 gh++1
(b) -h S -
Analogous to Assumption 1, Assumption 2(a) is used to control the squared Bellman error with zero reward. Assumption 2(b) guarantees that the class of functions of interest for the reward-free exploration phase (9,, - PiGh++ for layer /a [H] see Algorithm 2) is sufficiently rich relative to the relevant class test functions for the offline phase (F,, Fhh-h=1 for layer E (H), J see Algorithm 3).
Without loss of generality, we assume that [ max ( [F.
Reward-free Sequential Extrapolation Coefficient. The main guarantees for this section are stated terms of reward-free variant the sequential extrapolation coefficient, which we define as follows. Definition 13 (Sequential Extrapolation Coefficient for Reward FFee RL). For each h [H), let D U1g
(df ग E lgg} and Gr. - PP == {gh- Phoh+1ig Then we define,
SECRL.
max SEC - -Pr9h+1.2) TI ,T). hE(H]
Using the same arguments (and same proofs) as Section 5.2, the reward-free variant of sequential extrapolation coefficient can be shown subsume coverability (as well as reward-free counterpart of the Bellman -luuder dimension, which we omit).
G.1 ALGORITIM AND THEORETICAL ANALYSIS
Algorithm 2 Reward- Free Exploration with GOLF
input: Function class for reward-free exploration G. initialize: i < Ø, Yh [/]. g +.
1: for episode t 1,2 do
2: Select policy π + (y) where gdd = -rrgaaxaeettt gega 119(11,7g.1).
3: Execute ( for one episode and obtain { [xft (t) .0 ..... (t) 20 -
4: Update historical data Di "DT (1)) Sh ). E
(o
5: Compute confidence set:
go - -0-f f
min Ch (horlhh.h441) Brr Ah Whelm)
(29)
% 69h
(olxa)) (4' 21 Vg.g' Eg.
where (h
Σ
(ED
6: Select t, + argmin,.rrpp (1)
7: Return data D 1) Wh [H].
35

---

Published as a conference paper at ICLR 2023
Algorithm 3 Offline GOLF with Exploration Data and Target Reward
input:
Target reward function, R.
Function class F for offiine RI..
Exploration data from Algorithm 2, denoted by Dr, Wh EH).
1: Compute confidence set:
Fllm t {EEF (
min Lix (Fhifut1) Whe(a1) REF
(30)
(110.))- (aaraa) 27
where 4% (f,f))=
E
VffEEF.
d'Ed
(
2: Return क c TT, where argaaarggaaaaaaam fro
Recall that the key ideas in GOLF are: 1) using optimism to relate regret to on-policy average Bellman error; 2) using squared Bellman error construct a confidence set, which ensures optimism. In the reward-fiee setting, one can apply these ideas by running GOLF (Algorithm 2) with rewards set to zero. Intuitively, this strategy ensures exploration because the algorithm must explore to rule out test functions in G. However, a-priori is unclear whether running some standard offline RL algorithms on the exploration data produced by this strategy should lead to a near-optimal policy, especially given that the PAC guarantee of GOLF relies outputting uniform mixture of all historical policies (see, e.g., Corollary 2).
To address such issues, one can imagine that, if we know which is the best over all historical policies (say, (**)) for some f.), could running one-step GOL.F on the exploration data f. (Algorithm 3) guarantee to find good policy? Note that, for the original GOLF algorithm (in the known-reward case), running so directly reproduces n(t>?, Although knowing which is the best over all historical policies seems impossible in the known-reward case, thanks to the reward-free nature, we will show that the value of g( g.11) directly captures "how bad g" (akin to the regret in the known-rewan case), which allow us to find the best step over the reward-free exploration phase.
The following result provides sample complexity guarantee for this strategy.
Theorem 23, Under Assumptions and 2, there exists an absolute constants eı and 02 such that for (T H (5) and 3 = (e1 02) (og(T)))55) in
any 8 E (0,1) and T E N4, we choose Bolf = C1 log( Algorithms 2 and 3, then with probability at least 1 - 5, the policy स output by Algorithm 3 has
V (C..L,
81/6)
J(A')
We defer the proof to Appendix G.2. We also introduce the following two lemmas, which are key to adapting the known-reward results to the reward-free case.
Lemma 24 (Reward-free exploration overestimates regret). For any J E F, let g be defined as 9h fm TT.f++ + Prgh+1 vh E [H]. Then any (I,a,h) X' x Ax x [H], we have gn (x,a)= 2
fa.a))) Q (z,a).
Since the Q-function for all policies in the zero-reward case are zero, Lemma 24 guarantees that, regret in the reward-free exploration phase- -gn (z1, -0) always upper bounds its counterpart of the offline phase (fi (1)1, 0% (x. Equipped with the optimism argument, we can show that is small, its corresponding म (the with fn - -Thf++1 1 = gh. Phgh+1. Vh E [M]) also
gı (æ1,7, (e1,, 1 has small regret.
Lemma 25 (Reward-free exploration has larger confidence set). Suppose Assumption 2 holds and under the same conditions as Theorem 23. For any f Fiot) (defined in Eq. (30)), there must exist E G tit. (defined in Eq. (29)), such that TTTTfh = -haghtt Whe [H].
Lemma 25 ensures that the reward-free version space G(t.-1) subsumes the offline version space Fl(e)
Thus, can use the metrics during reward-free exploration upper bound that of the offline phase.
36

---

Published as a conference paper at ICLR 2023
G.1.1 RELATED WORK
Our approach adapts techniques for reward-free exploration in nonlinear RL introduced in Chen et al. (2022). what follows, we discuss the connection to this work in greater detail. We focus on the Q-type results of Chen et al. (2022), but similar arguments are likely apply to the V-type.
Briefly, Chen al. (2022) extends the OLIVE algorithm the reward-free setting by using the idea of online exploration with zero rewards. The most important difference here is that, as discussed in Section since OLIVE only considers average Bellman residuals, it cannot capture coverability. Beyond this difference, let us compare the completeness assumptions in Assumption 2 to those made in Chen et (2022). We will show that the completeness assumption used by Chen et al. (2022, Assumption 2) is a sufficient condition for ours (Assumptions and 2). In our notation, Chen et al. (2022), use == V + R == (-. ( d E V for some function class during offline phase, and select G V V = ( 1' (:r:): wh v for the reward-free exploration phase. Thus for any / E [.]. we have: For Assumption and Assumption 2(a):
Tr.F = R₂ + P/ (P RR+11
C R v -===1 Fh.
(by Chen et al. (2022, Assumption 2))
Pa = Pn (V/ v/++1)
S 1++1 h+ = Gn.
(by Chen al. (2022, Assumption 2))
For Assumption 2(b):
Fn Th.TTi F1+11 Vn + Rh - Ra - V
= 1//n Pn(vn++1* n +Ra+1)
C 1/1 1/
(by Chen el. (2022, Assumption 2))
Gh - Ph-hh = 1/-1 1/A -Pa(V Wn+1)
2 1/= 1/1.
(0e Mh+1 x1+1)
Fr FT.1+11 C 9r. Ph
G.2 PROOFS
We first present the following form of Freedman's inequality for martingales (e.g., Agarwal et al., 2014).
Lemma 26 (Freedman's 's Inequality). Let (X X .....(()) be a real-valued martingale difference sequence adapted filtration ( go0) ((1) (i.e., E[x [- O. VI. (T))
[X S R almost surely for all EE (T), then for any E (0,1/n), with probability at least 1 - 5,
log(1/6)
Σx
[(( g |
now provide proofs from Appendix G.I.
Proof of Theorem 23, Over this section, the test function class selected as (T (In,as)) - 9/ (z),an) ( (Zn,a)), V(h,1) (()))
By Theorem 5 (setting reward to be zero and replacing everything regarding F to 9), we have
SH /TS/CSECRL...... (
((t) herf
(31)
For any ( (T). we have,
E Eg0 [[n, =B,r
Pa( (2 max ma (11 In
E
Pa Pa ( ( (1)+1.((1)
m"
(T) is the greedy policy of ())
37

---

Published as a conference paper at ICLR 2023
(32)
Therefore, we know
H
B t
800) h.rf
Σ de [gh -Phgh "1
H
df [ahh]] - B [ogit1]
(by Eq. (32))
h=1
B [oi"]
(x1
(33)
Now, since
4, = argming <E[T]
(1), (x
then,
1 (1
T
800
(by Eq. (33))
h.lf
11=1
SECRL (E, (9,Ilg.T)8.
$ HV
(34)
T
where the last inequality follows from Eq. (31).
By Lemma 25, know there exists a G(--)-)) such that fa. -Thfft+1 - -Ph0++ Vh [H] In addition, we can obtain
J( ((
(by Lemma 12)
$ (((1),T311)
(by Lemma 24)
Therefore, we have
J(T')- S ( Sg(1,
S 9 (ズ)μ (1.))
SECRL (G.II,,
< HHV
(by Eq. (34))
T
Plugging back the selection of Br completes the proof.
Proof of' Lemma 24. We establish the proof by induction. For f = H, the the inductive hypothesis holds because I# fu R₁ f=
Suppose the inductive hypothesis holds at / 1, we have for any IE
fn+ fn+1 (4, VaEA)
gh+1 (- 074
maxg fh+1 ( 2 (I,
aeA
9h+ ( (n+1 (z).
(35)
Then, as gh - fr- -Tafa Ph.gh+ we have for any (I,a) EX XAA
9h (1,a)) = Sn (x.0) (x. Exiza
max maxIn+11 (1' ,a) + +E a.
maxgh+1(2'.0)
d'E
o'EA
38

---

Published as a conference paper at ICLR 2023
- max (1)
a'EA
d'Ed
Jn (x,,0) (x( (atd)))BBBlaaaa S9++ (x (n+il (f
2 (z (x,a)) ()ala) (=f1(('))
(by Eq. (35))
= fu (z.0) (x,a)+ 12.a ( (z'))
fa (z.a) 0% (x,a).
Therefore, we prove that the inductive hypothesis also holds at h using the inductive hypothesis at h+11 This completes the proof.
Proof of Lemma 25. Over this proof, we use d/ as the shorthand of dī The proof of this lemma consists of two parts.
(i) There exists a radius 31, such that for any gEg. such satisfies
E go) [on -Pahhti SB, whe [
then E G(t
iii There exists another radius B2, where 32 5. For any f Foff, we have
Σ g -T.fn++ S 32,
Whe
Proof of part (i). For any (1,4,g) E [TT x H x XG, let yn (g) be defined
(g) = (gn (1)) . -
))
(2 ,0 gh+1 (n (1+1((1 1)))
Also, let ( be the filtration induced by (5f ,af ,02 .a2 (v) ..... 101 - and we then have
E
(1) h
(g)
5 1-1111
= 5/0 ( (gn - -Pngh++)))
(36)
and
V[y (g) T <E (a))
(
<2E Y (g)
F( 1 d/o [gg -hhhhhh
(g) Jh so that ()))()) is a martingale difference sequence adapts to the filtration {. 1= and ( (g) < 2 almost surely. Then, by applying
Now, let y x,)
Lemma 26 with union bound, we have for any (h.g)= [A] X9 and any 7E (0,1/2), with probability at least 1 1-
log (119/8)
Σ (g)
E (5 (g)))
((((-))
1
log (1/1/5)
(yx*) (g))²
$ 17
(variance bounded by the second moment)
1.11
E E[y: (g) [h log(#1s1/4)
(x)a))) < by its definition)
(g)
17
4-1
1--1
log( (19()))))))))))))))))))))))))))
y (g) S 1
E S (g)
84 "1
E [Y (g)
g "]
h
(by the definition of Y, (g)
39

---

Published as a conference paper at ICLR 2023
[|] 181/))))/))
(1+
2 (g)
(37)
some E satisfies
Σ E 200
(gh -Phgh+1)
Smn, Ah E
-E 10 (
sh " by. (q. (36)
then by Eq. (37), we have for any / E [H]
log (199)6)) rht (g) (1+1)
7
33(3 (0gg(+))(()11113)
(e.g., by picking 1) 1/33)
So only need to guarantee
3- logg(1H9)))))) S 3r
3r
- v
(191/))))))
(38)
3
Proof of part (ii). Similar to (i), for any (t,h. [T] H F, let X (f) be defined as
(i)= = (Jr(1 Mo //+1111111 ( 1 [l]))
((Tnfh+t))(0 R( a fh- (1) (T.+1))))
Also let ( B(x) g4 - x (f), that {xx is martingale difference
sequence adapts to the filtration { 1==1' and ( (f) S 2 almost surely.
Thus, by same arguments Eqs. (36) and (37) (as well as applying Lemma 26), we have
E | (f) " 5 (fn
(39)
and for any
and any 1) = (0,7/)), with probability at least 1 1-6,
10g(#111166
Σ [ (f)
g 11 <n
E
"
119()1)1/6)
=1-1) Σ E x (f) |-
Σ xx)()))
(40)
n
Therefore, f F(ot), we have
(f) = Σ (fa -a)"))))))))) fh+
((Tafi42)<))) -
(fn(2)) aa - (1t
min 1 FF
(6
< s (frrlhi))
min Ck (1 K.F,
$ $Po..
(41)
We then combine Eqs. (39) to (41) and obtain
---1
Σ E g0
(fn
Σ E x (/) g
(by Eq. (39))
40

---

Published as a conference paper at ICLR 2023
1og(H1/1/6)
1--1
+ 1- t=1
())
(f)
(by Eq. (40)
(1 (1-1//1
log( 1og(H(/11/6)
+ 1-
Boff
(by Eq. (41))
(1 (1-1)/1
- 5log(#151/6)) (1151/6)+ 2/aoff
(by e.g., setting v) = 1/3)
-P2
So we only need to guarantee
(42)
Putting everything together. to hold:
By Eqs. (38) and (42), we know we only need the following inequality
3t
5log( + + S looloogHH//1 /1))
3
= BBr 2 6: + 18log /1)/8))
This is satisfied via the condition of Theorem 23.
Combining (i) and (ii), simply obtain for any h [H).
4
(fr- 10-Tffft1i0 f Foff foff _ fn TTfh-11
Σ
B go) (fr
-Tffnn+n SB..he
(b))
f.-1
9h --hhh+1
(by Assumption 2 and B3 S 31)
(gh -Poght1:9 "J.
(by (i)
This completes the proof.
41


Reviews:
[{"review_id": "oCHzVO8Nab", "reviewer": "Reviewer_LEoz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new notion of coverability, and shows its sufficiency for efficient online reinforcement learning. This new notion is compared with existing concepts from both offline and online RL. For offline RL, the authors show other weaker notions of coverage are not sufficient for efficient exploration. For online RL, they show their notion are independent from existing complexity measures, including Bellman rank and Bellman-Eluder dimension, and provide a new complexity measure that unifies these notions. ", "summary_of_the_review": "The work is novel and provides impressive results, based on simple but inspiring observations. I would suggest it be accepted. ", "strength_and_weaknesses": "Strength: \n\n1. The topic is important and the idea is novel. Both offline RL and online RL are important topics for the community and the paper serves as a bridge of the two formulations. In particular, the idea that the notion in offline RL can facilitate online exploration is novel and may serve as an inspiring point for future researches. \n\n2. The story is complete. The authors compare their notion with existing notations for both online and offline RL, which addresses the necessity and novelty of their findings. The example of block MDP is also a good point, which shows how the authors' findings can actually result in a sharper sample complexity, compared with previous works. \n\nWeakness:\n\n1. Part of the technical contribution is limited, since the algorithm and some of the analysis are directly copied from existing works. However, it shouldn't be considered as a big problem since the paper itself is mainly focused on the analysis instead of the algorithm design, and the paper does show its own novelty in the regret analysis. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "eS3IIAIKrU", "reviewer": "Reviewer_PRRf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors have introduced the concept of coverability, and related it to the sample efficiency in the online reinforcement learning. This idea is very interesting and the paper is well written with detailed description of everything. ", "summary_of_the_review": "N/A", "strength_and_weaknesses": "*Strengths*\n- The paper is well written. \n- The authors have addressed a crucial challenge of sample efficiency in reinforcement learning and the paper is quite relevant to the community. \n- The authors have introduced the concept of coverability with taking motivation from the idea of concentrability from offline RL which is quite interesting. \n\n*Questions to Authors*\n\n- It would have been nice to show the effect of coverability coefficient via empirical studies. \n\n- Is it possible to have coverability coefficient =0 ? \n\n- How difficult is it to construct the confidence sets in practice? Is the approach feasible? \n\n- Is it possible to extend this framework to continuous state-action spaces? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XSbUmf0bOot", "reviewer": "Reviewer_p7d7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers a setting of RL where the learner has access to ofﬂine data, yet also has the ability to online interact with the environment. The main contribution of the paper is to show that under a data distribution with good coverage, we can enable sample-efficient online RL. The paper introduces a new notation, called coverability which is weaker than the concentrability coefficient in offline RL and shows that it is enough for sample-efficient online RL. In addition, the paper also shows (1) several weaker notions of coverage which are sufficient for ofﬂine RL, but insufficient for online RL; (2) existing complexity measures for online RL such as Bellman rank and Bellman-Eluder dimension are insufficient for sample-efficient online RL. \n\n", "summary_of_the_review": "Due to my concerns about the main contributions of this paper, I am toward rejecting it.  If the authors can address my concern, I am willing to increase my score. ", "strength_and_weaknesses": "Strengths:\n- The paper addresses an important setting of RL: online RL with access to ofﬂine data\n- The paper is generally well written\n\nWeaknesses:\n- However, I have some concerns about the novelty of the main contribution of the paper.  A very recent result under review of ICLR 2023 [1] shows that under the Concentrability assumption as Definition 1 (similar to the coverability assumption as the paper proposed), it is enough to achieve an \"optimal\" offline RL, without any interaction with the environment. These results seem correct to me. Then, \n - If we can access offline data and assume that offline data has good coverage as stated in Definition 2 (lower bound of Concentrability assumption), so do we really need the online RL?\n - If we really still need the online RL, then it seems that the coverability condition on offline data that the paper proposed is not enough weak to keep a sample-efficient online RL.    \n\n[1] https://openreview.net/forum?id=ZsvWb6mJnMv&referrer=%5BReviewer%20Console%5D(%2Fgroup%3Fid%3DICLR.cc%2F2023%2FConference%2FReviewers%23assigned-papers)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%