A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning
Authors: Zixiang Chen
Chris Junchi Li
Huizhuo Yuan
Quanquan Gu
Michael Jordan
Venue: ICLR 2023 notable top 25% (2023)
Keywords: general function approximation
sample-efficient RL
optimization-based exploration
Eluder dimension
Bellman rank
witness rank
complexity measure
hypothesis class

Abstract: With the increasing need for handling large state and action spaces, general function approximation has become a key technique in reinforcement learning (RL). In this paper, we propose a general framework that unifies model-based and model-free RL, and an  Admissible Bellman Characterization (ABC) class that subsumes nearly all Markov decision process (MDP) models in the literature for tractable RL. We propose a novel estimation function with decomposable structural properties for optimization-based exploration and the functional Eluder dimension as a complexity measure of the ABC class. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed, achieving regret bounds that match or improve over the best-known results for a variety of MDP models. In particular, for MDPs with low Witness rank, under a slightly stronger assumption, OPERA improves the state-of-the-art sample complexity results by a factor of $dH$. Our framework provides a generic interface to design and analyze new RL models and algorithms.

Published as a conference paper at ICLR 2023
A GENERAL FRAMEWORK FOR SAMPLE- EFFICIENT FUNCTION APPROXIMATION IN REINFORCEMENT LEARNING
Zixiang Chen'; Chris Junchi L Angela Yuan Quanquan Guä, Michael I. Jordan
t Department of Computer Science, University of California, Los Angles
{ (chenzx19, hzyuan, agu uulal
Department of Electrical Engineering and Computer Sciences, University of California, Berkeley junchi liteiikeeeeeeeeeee edd, jordan & www.eeeeeeeeee.................e edu Department of Statistics, University of California, Berkeley
ABSTRACT
With the increasing need for handling large state and action spaces, general function approximation has become key technique in reinforcement learning (RL). In this paper, we propose a general framework that unifies model-based and model-free RL, and Admissible Bellman Characterization (ABC) class that subsumes nearly all Markov Decision Process (MDP) models in the literature for tractable RL. We propose a novel estimation function with decomposable structural properties for optimization-basee exploration and the functional eluder dimension as a com- plexity measure of the ABC class. Under our framework, a new sample-efficient algorithm namely OPtimization-baaa based ExploRation with Approximation (OPERA) is proposed, achieving regret bounds that match or improve over the best-known results for a variety of MDP models. In particular, for MDPs with low Witness rank, under a slightly stronger assumption, OPERA improves the state-of-the-art sample complexity results by factor of dH. Our framework provides generic interface to design and analyze new RL models and algorithms.
INTRODUCTION
Reinforcement learning (RL) decision-making process that seeks maximize the expected reward when an agent interacts with the environment (Sutton & Barto 2018). Over the past decade, RL has gained increasing attention due to successes in a wide range of domains, including Atari games (Mnih et al.] 2013), Go game (Silver et al.] 2016). autonomous driving (Yurtsever et al.) 2020), Robotics (Kober et al. 2013). etc. Existing RL algorithms can be categorized into value- based algorithms such as Q-learning (Watkins) 1989) and policy-based algorithms such as policy gradient (Sutton et al. 1999). They can also be categorized as a model-fre approach where one directly models the value function classes, alternatively, model-basee approach where one needs to estimate the transition probability.
Due to the intractably large state and action spaces that are used to model the real-world complex environment, function approximation in RL has become prominent in both algorithm design and theoretical analysis. It is a pressing challenge to design sample-efficient RL algorithms with general function approximations. In the special case where the underlying Markov Decision Processes (MDPs) enjoy certain linear structures, several lines of works have achieved polynomial sample complexity and/or VT regret guarantees under either model-free or model-based RL settings. For linear MDPs where the transition probability and the reward function admit linear structure, Yang & Wang (2019) developed variant of Q-learning when granted access to generative model. et al. (2020) proposed an LSVI-UCB algorithm with Ö V d H3T) regret bound and Zanette et al.
(202aa) further extended the MDP model and improved the regret (ld VT). Another line of
work considers linear mixture MDPs Yang & Wang (2020); Modi et al. (202)) Jia et al. (2020); Zhou et al. (2021a), where the transition probability can be represented by a mixture base models.
In Zhou et al. (222aa), an Ö(dH minimax optimal regret was achieved with weighted linear
"Equal contribution.

---

Published as a conference paper at ICLR 2023
DEC*
ABC Class
Bellman Representability
(Our Work)
Dimension
Eluder Dimension
Generalized Bilinear Class
Bellman
Witness Rank
Linear
Rank
KNR
Linear
Tabular
Mixture
Figure 1: Venn-Diagram Visualization of Prevailing Sample-Efficien RL, Classes. As by far the richest concept, the DEC framework is both a necessary and sufficient condition for sample-efficient interactive learning. BE dimension is a rich class that subsumes both low Bellman rank and low eluder dimension and addresses almost all model-free RL classes. The generalized Bilinear Class captures model-base -based RL settings including KNRs, linear mixture MDPs and low Witness rank MDPs, yet precludes some eluder-dimension based models. Bellman Representability another unified framework that subsumes the vanilla bilinear classes but fails to capture KNRs and low Witness rank MDPs. Our ABC class encloses both generalized Bilinear Class and Bellman Representability and subsumes almost all known solvable MDP cases, with the exception of the Q' state-action aggregation and deterministic linear Q" MDP models, which neither Bilinear Class nor our ABC class captures.
regression and a Bernstein-type bonus. Other structural MDP models include the block MDPs (Du et al. 2019) and FLAMBE (Agarwal et al., 2020b) to mention a few.
In a more general setting, however, there is still gap between the plethora of MDP models and sample-efficient RL algorithms that can learn the MDP model with function approximation. The question remains open as to what constitutes minimal structural assumptions that admit sample- efficient reinforcement learning. To answer this question, there are several lines of work along this direction. Russo & Van Roy (2013); Osband & Van Roy (0014) proposed an structural condition named eluder dimension, and Wang et al. (2020) extended the LSVI-UCB for general linear function classes with small eluder dimension. Another line of works proposed low-rank structural conditions, including Bellman rank (Jiang al. 2017 Dong et al.) (020)) and Witness rank (Sun al., 2019)). Recently, Jin et al. (2021) proposed a complexity called Bellman cluder (BE) dimension. which unifies low Bellman rank and low eluder dimension. Concurrently, [u et al. (222) proposed Bilinear Classes, which can be applied to variety of loss estimators beyond vanilla Bellman error. Very recently, Foster et al. (202T) proposed
Coefficient (DEC), which is necessary and sufficient condition for sample-efficient interactive learning. To apply DEC to RL, they proposed a RL class named Bellman Representability, which can be viewed as generalization of the Bilinear (SanesssSSSSSSSae
Class. Nevertheless. Sun et al. (2019) is limited to model-based RL, and Jin et al. (2021) is restricted to model-free RL. The only frameworks that can unify both model-based and model-free RL are Du al. (201)) Foster al. (2021), but their sample complexity results when restricted special MDP instances do not always match the best-known results. Viewing the above gap, we aim to answer the following question:
Is there a unified framework that includes all model-free and model-based RL classes while maintaining sharp sample efficiency?
In this paper, we tackle this challenging question and give a nearly affirmative answer to it. We summarize our contributions follows:
We propose a general framework called Admissible Bellman Characterization (ABC) that covers a wide set of structural assumptions in both model-free and model-based RL, such as linear
In this paper, we use FLAMBE refer to both the algorithm and the low-rank MDP with unknown feature mappings.
2

---

Published as a conference paper at ICLR 2023
MDPs, FLAMBE, linear mixture MDPs, kemnlizedd nonlinear regulator (Kakade et al. 2020). etc. Furthermore, our framework encompasses comparative structural frameworks such as the low Bellman eluder dimension and low Witness rank.
Under our ABC framework, we design a novel algorithm, OPtimization-basel ExploRation with Approximation (OPERA), based on maximizing the value function while constrained in a small confidence region around the model minimizing the estimation function.
We apply our framework to several specific examples that are known to be not sample-efficient with value-based algorithms. For the kernelized nonlinear regulator (KNR), our framework the first general framework to derive vT regret-bound result. For the witness rank, our framework yields sharper sample complexity with mild additional assumption compared to prior works.
We visualize and compare prevailing that both the general Bilinear Class and our ABC frameworks capture most existing MDP classes, including the low Witness rank and the KNR models.
RL frameworks and ours in Figure [ We can
Notation. For a state-action sequence Q1.01...., SH in our given context, we use Tn == ($1, o1...., sk) to denote the o-algebra generated by trajectories up to step h [H]. Let y denote the policy of following the max-Q strategy induced by hypothesis f. When write y. as n' for notational simplicity. We write Sp ~ π to indicate the state-action sequence are generated by step h E [H] by following policy x(- 8) and transition probabilities P(- | s,a) of the underlying MDP model M. We also write a₁ ~ π to mean on ~ .(- 8), for the h-th step. Let ll lll denote the 22-norm and || oooo the -norm of a given vector. Other notations will be explained at their first appearances.
f we
2 PRELIMINARIES
We consider a finite-horizon, episodic Markov Decision Process (MDP) defined by the tuple M (S, A, P, r, H), where S is the space of feasible states, A is the action space. H is the horizon in each episode defined by the number of action steps in episode, and TP {TP,, ) NE(M] is defined for every h E [H] as the transition probability from the current state-action pair (8h, a4) E S x A to the next state S1+1 E S. We use (s, a) 2 0 to denote the reward received at step h E [H] when taking action a at state and assume throughout this paper that for any possible trajectories, Σ Th (sh: an) E [0, 1]. deterministic policy
sequence of functions {TH : S A A where each Ta specifies a strategy at step h. Given a policy æ, the action-value function defined to be the expected cumulative rewards where the expectation is taken over the trajectory distribution generated by
(. 5h, on), TT.. ne)) as
H
(7, == E
TM (wwss,ax)) -h=hh
Σ
9h = =, an = a
Similarly, we define the state-value function for policy a as the expected cumulative rewards as
H
(s) = E
Σ Linkk
The (sw,, ax) 8h = 8
We use n² denote the optimal policy that satisfies V (s) max, (s) for all e S (Puterman 2014]. For simplicity, we abbreviate V as V and Q as Qi Moreover, for a sequence of value functions {Qn)ne the Bellman operator at step h is defined as:
(ThQn-1) (s, rr a) + Es max (s', E'EA
We also call Qn - (Th.u+1) the Bellman error (or Bellman residual). The goal of an RL algorithm to find an e-optimal policy such that VTT(ss) (a1) - V/* (s1) S e. For an RI. algorithm that updates the policy T' for T iterations, the cumulative regret is defined as
T
Regret(T) := Σ [vi(s))-
3

---

Published as a conference paper at ICLR 2023
Hypothesis Classes. Following Du et al. (2021) we define the hypothesis class for both model-free and model-based RL. Generally speaking, a hypothesis class is a set of functions that are used to estimate the value functions (for model-free RL) or the transitional probability and reward (for model-based RL). Specifically, a hypothesis class F on a finite-horizon MDP is the Cartesian product of H hypothesis classes F Fi .... x Fir in which each hypothesis f (e(H) F can be identified by a pair of value functions {Q₁, Vj) {Qr.5, Vi., h Based on the value function pair, it is natural to introduce the greedy policy T (s) = arg m Qn.r(s,, a) at each
step h (H) and the corresponding ys)s the sequence of time-dependent policies { h=0 An example of model-free hypothesis class is defined by sequence of action-value function {Qu. hee The corresponding state- value function is given by:
H-1
(s, = Ea-ta,, (
In another example that falls under the model-based RL setting, where for each hypothesis f F we have the knowledge of the transition matrix y and the reward function ry- We define the value function Qh. corresponding to hypothesis f as the optimal value function following My ry))
( a) = (T,,,
and Vh.s(s) = Vi,M, (5).
We also need the following realizabiliity assumption that requires the true model My. (model-based RL) or the optimal value function f (model-free RL) to belong to the hypothesis class F.
Assumption 1 (Realizability). For an MDP model M and a hypothesis class F, we say that the hypothesis class F is realizable with respect M if there exists I" E F such that for any h [M], (7, a) = Qr. (8, a). We call such f* an optimal hypothesis.
This assumption has also been made in the Bilinear Classes (Du et al. 2021) and low Bellman cluder dimension frameworks (Jin et al. (202I). We also define the e-covering number of F under a well-defined metric p of a hypothesis class F:?
Definition 2 (c-covering Number of Hypothesis Class). For any c > 0 and hypothesis class F, we use (c) to denote the c-covering number, which is the smallest possible cardinality of (an c-cover) F. such that for any f E F there exists f' E F. such that p(J, f') S
Functional Eluder Dimension. We proceed to introduce our new complexity measure, eluder dimension, which generalizes the concept of eluder dimension firstly proposed in bandit literature (Russo Van Roy| 2013 2014). It has since become a widely used complexity measure for function approximations in RL (Wang et al. 2020; Ayoub et al. 2020 Jin et al. 2021 Foster et al. 2021 Here we revisit its definition:
neeaure,,uunctioal functional
Definition 3 (Eluder Dimension). For a given space X' and class F of functions defined on X, the eluder dimension dimg (F, E) is the length of the existing longest sequence Ti,... In E X' satisfying
for some c' 2 and any 2 S n, there exist f1, f2 F such that v E (fi(z:) fa(x:))² < d
while (xx) - fe (xt) > é'
The eluder dimension is usually applied to the state-action space X' = S x A and the corresponding value function class F S x - R (Jin et al., 2021 Wang et al. 2020 We extend the concept of eluder dimension
complexity measure of the hypothesis class, namely, the functional eluder dimension, which is formally defined as follows.
Definition 4 (Functional Eluder Dimension). For given hypothesis class F and a function G defined on F F, the functional eluder dimension (FE dimension) dim G, c) is the length of the existing longest sequence fi....,f. fn E F satisfying for some è' 2 c and any < < n, there
exists E F such that VE (G(g, < é' while (G(g.ft) > é' Function G is dubbed as the coupling function.
The notion of functional eluder dimension introduced in Definition i generalizable in straightfor- ward fashion to a sequence G == (G ( [ of coupling functions: we simply set dimyx G,c) = max dimpe (F, GRs é) to denote the FE dimension of [G)] The Bellman eluder (BE)
Forr example for model-free cases where f.g are value functions, p(f g) = max flfa- - lol. For model-based RI. where f.g are transition probabilities, we adopt p(P, Q max [(vaP, v which is the maximal (squared) Hellinger distance hetween two prohahility distribution sequences.
4

---

Published as a conference paper at ICLR 2023
dimension recently proposed by (Jin et al. 2021) is in fact special case of FE dimension with specific choice of coupling function sequence." As will be shown later, our framework based on FE dimension with respect the corresponding coupling function captures many specific MDP instances such as the kernelized nonlinear regulator (KNR) (Kakade et al. 2020) and the generalized linear Bellman complete model (Wang al.) 2019), which not captured by the framework of low BE dimension. As we will see in later sections, introducing the concept of FE dimension allows the coverage of a strictly wider range of MDP models and hypothesis classes.
3 ADMISSIBLE BELLMAN CHARACTERIZATIO FRAMEWORK
In this section, we introduce the framework of admissible Bellman characterization.
3.1 ADMISSIBLE BELLMAN CHARACTERIZATION
Given an MDP M, a sequence of states and actions $1, ......, SH. two hypothesis classes FF and 9 satisfying the realizability assumption (Assumption V= (v(s a, s') S x x S + R), the estimation function = {fr., he(m, is an Rd valued function defined on the set consisting of ob := ($), 4h sh-1) E S x Ax f F. E G and E V and serves as surrogate loss function of the Bellman error. Note that our estimation function is vector-valued function, and is more general than the scalar-valued estimation function (or discrepancy function) used in Foster al. (202T); Du et al. (202T). The discriminator v originates from the function class the Integral Probability Metrics (IPM) (Müller 1997) is taken with respect to (as metric between two distributions), and is also used in the definition of Witness rank (Sun et al. 2019). We use a coupling function Gh. (J, g) defined on J to characterize the interaction between two hypotheses f.g E F. The subscript f is an indicator of the true model and is by default unchanged throughout the context. When the two hypotheses coincide, our characterization of the coupling function reduces to the Bellman error.
and a discriminator function class
Definition 5 (Admissible Bellman Characterization). Given an MDP M, two hypothesis classes F,9 satisfying the realizability assumption (Assumption [T and FF C g, an estimation function la,y' (8 x A S) F x G x + IRd,, an operation policy Top and a constant (0. 1]. we say that G an admissible Bellman characterization of (M,F99, E) if the following conditions hold:
(i) (Dominating Average Estimation Function) For any f.g F
max Egg rogg Mop [ss4 [En.g fa+1, fh, v) sh. anl 112 (Gn.)((f.g)².. VEV
(ii) (Bellman Dominance) For any (h, f) E [H] x F, R [En, BEnTT ( an) - r(hn an) V1+1, (s++1)) S (f.
We further say (M,F,9,
is an ABC class if G is an admissible Bellman characterization of
In Definition 5 one can choose either Top = Fg or Top fT. We refer readers to for further explanations on Top- The ABC class is quite general and de facto covers many existing MDP models;
see (3.2 for more details.
Comparison with Existing MDP Classes. Here we compare our ABC class with three recently pro- posed MDP structural classes: Bilinear Classes (Du et al. 2021), low Bellman eluder dimension (Jn et al. 2021), and Bellman Representability (Foster et al.
2021
Bilinear Classes. Compared to the structural framework of Bilinear Class in Du et al. (2021
Definition 4.3), Definition of Admissible Bellman Characterization does not require bilinear structure and recovers the Bilinear Class when we set Gt,f- (o..f-(f.9) = (Wx(g) - Wx(s*), (f)) Our ABC class is strictly broader than the Bilinear Class since the latter does not capture low cluder dimension models, and our ABC class does. In addition, the ABC class admits an estimation function that is valuer, and the corresponding algorithm achieves VT-rrgred for KNR case while the Bil BiL algorithm for Bilinear Classes (Du et al. 2021) does not.
Indeed, when the coupling function is chosen as the expected Bellman error Go /) := E., (Q To Qo.h+) where Tr denotes the Bellman operator, we recover the definition of BE dimension (Jin al. 2021 i.c. (Fi G) = diimss(F, G. WWe assume F C G throughout this paper and in the general case where F & G. we overload & FUg.
5

---

Published as a conference paper at ICLR 2023
Low Bellman Eluder Dimension. S the MDP class of low BE dimension when E fh- 9h. v) == Qi.g(Sh, a4) Th (1++1,($5+11). Moreover, our definition unifies the -ttppe and Q-type problems under the same framework by the notion of Top. We will provide a more detailed discussion on this in $3.2) Our extension from the concept of the mellman estimation function (i.e. the surrogate of the Bellman error) enables to accommodate model-based RL for linear mixture MDPs, KNR model, and low Witness rank.
Bellman Representability; Foster et al. 2021) proposed DEC framework which is another MDP class that unifies both the Bilinear Class and the low BE dimension. Indeed, our ABC framework introduced in Definition 3 shares similar spirits with the Bellman Representability Definition F.1 in Foster et al. (021)) Nevertheless, our framework and theirs bifurcate from the base point: our work studies optimization-based exploration instead of the posterior sampling-basee exploration in Foster et al. (202I). Structurally different from their DEC framework, our ABC requires estimation functions be vector-valued, introduces the discriminator function v, and imposes the weaker Bellman dominance property (i) in Definition than the corresponding one as in Foster al. 220TT, Eq. (166)). total, this allows broader choices of coupling function G as well as our ABC class (with low FE dimension) to include as special instances both low Witness rank and KNR models, which are not captured in Foster et al. (2021).
Decomposable Estimation Function. Now we introduce the concept of decomposable estimation function, which generalizes the Bellman error in earlier literature and plays pivotal role in our algorithm design and analysis.
Definition 6 (Decomposable Estimation Function). A decomposable estimation functiino E (S x A x S) x F x g x V Rdd, is function with bounded fn-norm such that the following two conditions hold:
ii) (ecomposability) There exists an operator that maps between two hypothesis classes T(-)
F F G such that for any I E F, (h. J'.:: v) E [H] x F x G x V and all possible on,
f (on, Jh+1,gh, 9h; v) - E.g.1 [ (on, fa+1, 9h, u) 8h, an. En.g JA+1, T()n, v).
Moreover, if f*, then T()) - holds.
(ii) (Global Discriminator Optimality) For any f E F there exists a global maximum vi((f) E V such that for any (h. f g, v) E [ x F x G x and all possible On.
|| ( f1+1, fk, (f)) 8h, an
B [Cn, ((0o,ohntaa fn. u) 8h. ax ||-
Compared with the discrepancy function or estimation function used in prior work (Du et al. 2021 Foster al. 2021), estimation function (EF) admits the unique properties listed as follows:
(a) Our EF enjoys a decomposable property inherited from the Bellman error intuitively speaking, the decomposability can be seen as a property shared by all functions in the form of the difference of measuuuuael function and meeasurable function;
(b) Our EF involves discriminator class and assumes the global optimality of the discriminator on all (8%, an) pairs;
(c) Our EF is a vector-valued function which is more general than a scalar-valued estimation function (or the discrepancy function).
We remark that when f = 9. Eaa. (on, fh+1, Sn; v) Sh. an) measures the discrepancy in optimality between f and ʃ In particular, when 1 Ban, (en,r(on. Jh+1, Să. v) 8h, an)
O. Consider a special case when p (O,, fa 1, Ih. u) == Qr (Sh, an) - -r(s,, ah) (
Then the decomposability (i) in Definition 6 reduces to
QQn. (Sh, an) r(sh, an) - V (Tn Vn+ ax) r(n,, an) (
on) - (T. (1+1)
In addition, we make the following Lipschitz continuity assumption on the estimation function.
'The decomposahility item i in Definition
6 directly implics that Generalized Completeness condition
similar Assumption 14 of et al. (021 holds.

---

Published as a conference paper at ICLR 2023
Assumption 7 (Lipschitz Estimation Function), There exists L > 0 such that for any (". E [M] x J
F G x V. ()
F and all possible oh
(1.56199 - la. (t. w))
(. v) - (.f. 2 s Lp(g. 3) 8) no - L| -1 (....) 1 (. ) S Lp(S', .)).
I f),
((..(199))))) - f (- g.
Note that we have omitted the subscript h of hypotheses in Assumption 7 for notational simplicity. We further define the induced estimation function class as C = ( f. v) : (h, f. f.g. v) e [H] x xF x F x G x VJ. We can show that under Assumption 7 the covering number of the induced estimation function class L can be upper bounded as Ne(c)) S N3 ( (. (1 ( where Nz(e), Na(e), (e)() are the e-covering number of F, 9 and V. respectively. Later in our theoretical analysis in $ our regret upper bound will depend the growth rate of the covering number or the metric entropy, log Nc(s).
3.2 MDP INSTANCES IN THE ABC CLASS
In this subsection, we present a number of MDP instances that belong to ABC class with low FE dimension. As we have mentioned before, for all special cases with f fh+ 9h. == (h, (x) FA (8h+1) both conditions in Definition 5 are satisfied automatically with Gr. = Es,. ".. TFg QQ.. (8h, ag) Th 1 (#6+++ JJ. The FE dimension under this setting recovers the the BE dimension. Thus, all model-free RL models with low BE dimension (Jin ctt al. 2021) belong to our ABC class with low FE dimension. In the rest of this subsection, our focus shifts to the -bsed RLs that belong the ABC class: linear mixture MDPs, low Witness rank, and kemnliizdd nonlinear regulator.
Linear Mixture MDPs. We start with a model-based RL with a linear structure called the linear mixture MDP (Modi et al., [2000] Ayoub al. 2020; (hou et al. 2021b). For known transition and reward feature mappings oi (8, 0, 8 ) AxS > H. (b(s, a): S A - H taking values in a Hilbert space H and unknown 0* H. linear mixture MDP assumes that for any (s, a, 8') E S x A x S
and h E [H]. the transition probability Ps(s'' s, a) and the reward function r(s, a) are linearly parameterized as
Pa 8, a, = (0% (ss a, a,,"))
r(s,a) = (%% (s,a))
We provide the following proposition, which shows that linear mixture MDPs belong to the ABC class with low FE dimension.
Proposition 8 (Linear Mixture MDP c ABC with Low FE Dimension). The linear mixture MDP model belongs to the ABC class with estimation function
f (on, f Dh. 8) = 07. (sn an) + Σ blsn, an, an, s' (ot1. - rh - (944)) (3.1)
and coupling function f (On. - 0% Eenanway W#sh,, an) + E. o(sn, an. s' ('+t,, Moreover, it has a low FE dimension.
Low Witness Rank. We defer the formal definition of witness rank to EE.2 and provide the following proposition showing that low Witness rank models belongs to our ABC class with low FE dimension.
Proposition 9 (Low Witness Rank C ABC with Low FE Dimension). The low Witness rank model belongs the ABC class with estimation function
(on, fh+1, 9h. v) = Ezngs v(sh, an. 3) u(sh, ass Sh41), and coupling function Gh,y- (f.g) = (W)(g))xn,()) Moreover, it has a low FE dimension.
(3.2)
Kernelized Nonlinear Regulator. The kernelized nonlinear regulator (KNR) proposed recently by Mania et al.) (2020); Kakade et al. (2020) models a nonlinear control dynamics on an RKHS H of finite or countably infinite dimensions. Under the KNR setting, given current sh, Ob at step h E [H] and a known feature mapping @ S x A + H. the subsequent state obeys a Gaussian distribution with mean vector U/ d(s), an) and homoskedastic covariance I²1, where {Uă E Rdd. H) he(A]
are true model parameters and d, is the dimension of the state space. Mathematically, we have for each h 1......... H.
sh+1
0s an) + Ei++1 where Eh+1 o00
(3.3)
Furthermore, we assume bounded reward r E [0, 1] and uniformly bounded feature map [| a)ll N B. The following proposition shows that KNR belongs the ABC class with low FE dimension.
7

---

Published as a conference paper at ICLR 2023
Algorithm I OPtimizatiinn-assee ExploRation with Approximation (OPERA)
Initialize: DA. for h I...., H 2: for iteration t = 1. 1.2.... T do
3: Set x" == xy where ft is taken argmaxfez fer (1.r(s1, subject to
[-1
L-1
(oh. v)l
inf on
Σ 5
(nh In-1, = for all h e [M]
VEV
(4.1)
4: For any h E [H]. collect tuple (rh, Sh, an 8h+1) by rolling in sp. n² and executing an Test
5: Augment Dj = Dn {(rns 8h, on, 8h+1)]
6: end for
7: Output: Nout uniformly sampled from {T') ME=
Proposition 10 (KNR C ABC with Low FE Dimension). KNR belongs to the ABC class with estimation function
On.gr(On, 1h+1,9h: v) Ungg an) 8h+1,
(3.4)
and coupling function Gh.f (f,g) = v BBn, an ~r, [1(Un, ( 12) Moreover, it has low FE dimension.
Although the dimension of the RKHS H can be infinite, our complexity analysis depends solely on its effective dimension dø.
ALGORITHM AND MAIN RESULTS
In this section, we present an RL algorithm for the ABC class. Then we present the regret bound of this algorithm, along with its implications several MDP instances in the ABC class.
4.1 OPERA ALGORITHM
We first present the OPtimization based ExploRation with Approximation (OPERA) algorithm in Algorithm [ which finds an e-optimal policy in polynomial time. Following earlier algorithmic art in the same vein e.g., GOLF (Jin et al. 202T). the core optimization step of OPERA optimization- based exploration under the constraint of identified confidence region; additionally introduce an estimation policy Test sharing the similar spirit as in Du et al. (202I). Due to space limit, we focus on the Q-type analysis here and defer the V -ttype results to $D the appendix."
Pertinent to the constrained optimization subproblem in Eq. (4. T of our Algorithm [ we adopt the confidence region based on a general DEF, extending the Bellman-error crrmaan-rroo-basedd confidence region used in Jin et al. (202T). As result of such an extension, models such as low Witness rank and KNR. Similar to existing literature on RI. theory with general function approximation, our algorithm is in general computationally inefficient. Yet OPERA is oracle efficient given the oracle for sol the optimization problem in Line of Algorithm discuss its computational issues in detail in E.
algorithm can deal with
complex
[
We will
E.2 and E.3
4.2 REGRET BOUNDS
We are ready to present the main theoretical results of our ABC class with low FE dimension:
Theorem 11 (Regret Bound of OPERA). For an MDP M, hypothesis classes F,G, a Decomposable Estimation Function l satisfying Assumption 7 an admissible Bellman characterization G, suppose (M,F, G, G) is an ABC class with low functional eluder dimension. For any fixed (0. 1), in Algorithm
we choose f = O (
[ Then for the on-policy case when Top = Test = R with probability at least 8, the regret upper bounded by
Regret(T) o II T dimpr (F.G.VI/T) :B)
'Here and throughout our paper we considers Text = x² for Q-type models. For V --type models, we instead consider Tes (AA) to he the uniform distribution over the action space. Such representation of estimation policy allows unify the Q-type and V-type models in single analysis.
8

---

Published as a conference paper at ICLR 2023
We defer the proof of Theorem 11 together with corollary for sample complexity analysis, to $ in the appendix. We observe that the regret bound of the OPERA algorithm dependent on both the functional eluder dimension dimpr and the covering number of the induced DEF class
In the special case when DEF is chosen the Bellman error, the relation (f G. vI/T) = dimmar(F II, (1/T holds with being the function class induced by { f F), and our Theorem 11 reduces to the regret bound in Jin al. (2021) (Theorem 15). We will provide detailed comparison between our framework and other related frameworks in S when applied to different MDP models in the appendix.
4.3 IMPLICATION FOR SPECIFIC MDP INSTANCES
Here we focus on comparing our results applied to model-based RLs that are hardly analyzable in the model-free framework in $3.2 We demonstrate how OPERA can find near-optimal policies and achieve a state-of-the-ar sample complexity under our new framework. Regret-bound analyses of linear mixture MDPs and several other MDP models can be found in $B in the appendix.
We highlight that Algorithm 1 not only provides simple optimization- -abbaa-ttd----d scheme, recovers previous near-optimal algorithms in literature (Algorithms 2 and 4 in $ when applied to specific MDP instances, but also reduces novel Algorithm for low witness rank MDPs with improved sample complexity.
Low Witness Rank. We first provide a sample complexity result for the low Witness rank model structure. Let [M] and [V] be the cardinality of the model class? M and discriminator class V, respectively, and W. be the witness rank (Definition 28) of the model. We have the following sample complexity result for low Witness rank models.
Corollary 12 (Finite Witness Rank). For an MDP model M with finite witness rank structureand any fixed (0, 1). we choose 3 O (Iog((T))M)))))))) (MM)))))))))) in Algorithm | With probability at least 1 1--0 6, Algorithm outputs an c-optimal policy Tou within T = O (H2 [/ (1²2)) trajectories.
Proof of Corollary 12 is delayed $ Compared with previous best-known sample complexity due to Sun et al. (2019), sample complexity is superior by factor of dH up to polylogarithmic prefactor in model parameters.
result of Ô (HF log( M|] //)///2///
Kernel Nonlinear Regulator. Now we turn to the implication of Theorem I1 for learning KNR models. We have the following regret bound result for KNR.
Corollary 13 (KNR). For the KNR model in Eq. (3.3 and any fixed 5 E (0, 1), we choose B = O dodd log² (6)) in Algorithm 1 by Ô (112 /doT3/o/)
With probability at least - 8, the regret is upper bounded
We remark that neither the low BE dimension nor the Bellman Representability classes admit the KNR model with a sharp regret bound. Among earlier attempts, [uu et al. (2021) $6) proposed to use a generalized version of Bilinear Classes to capture models including KNR, Generalized Linear Bellman Complete, and finite Witness rank. Nevertheless, their characterization requires imposing monotone transformations on the statistic and yields a suboptimal (T3/4) regret bound. Our ABC class with low FE dimension is free of monotone operators, albeit that the coupling function for the KNR model is not of a bilinear form.
5 CONCLUSION AND FUTURE WORK
In this paper, we proposed unified framework that subsumes nearly all Markov Decision Process (MDP) models in existing literature from model-based and model-free RLs. For the complex- ity analysís, we propose new type of estimation function with the decomposable property for optimization-hann based exploration and use the functional eluder dimension with respect to an admissible Bellman characterization function as the complexity measure of our model class. In addition, we proposed a new sample-efficient algorithm, OPERA, which matches or improves the statc-of-the-art sample complexity (or regret) results.
On the other hand, we notice that some MDP instances are not covered by our framework such as the Q* state-action aggregation, and the deterministic linear Q' models where only Q" has linear structure. We leave it as a future work include these MDP models.
Hypothesis class reduces to model class (Sun et al. 2019) when restricted to model-based setting. 'The definition of witness rank adopts V-type representation and hence we only derive the sample complexity of our algorithm. For detailed discussion on the V-type cases, we refer readers $ in the appendix.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
We thank the anonymous reviewers for their helpful comments. ZC, AY and QG are supported in part by the National Science Foundation CAREER Award 1906169 and IIS-200991., MIJ is supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014- 1-2764 and by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-2941 and NSF grant I1S-1901252.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
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, pp. 1638-1646. PMLR, 2014.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in neural information processing systems, 33: 13399-13412, 2020a.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20107, 2020b.
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances Neural Information Processing Systems, 30, 2017.
Brian DO Anderson and John B Moore. Optimal control: linear quadratic methods. Courier Corporation, 2007.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning Volume 70, pp. 263-272. JMLR. org, 2017.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482. 2002.
Steven Bradtke. Reinforcement learning applied to linear quadratic regulation. Advances in neural information processing systems, 5, 1992.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, (0ct):2133231, 2002.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. 2008.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed- horizon reinforcement learning. Advances in Neural Information Processing Systems, 28, 2015.
10

---

Published as a conference paper at ICLR 2023
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-67) 2020.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-557--9 PMLR, 2021.
Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou, Root-n-regret for learning in markov decision processes with function approximation and low bellman rank. In Conference on Learning Theory, pp. 1554-1557. PMLR, 2020.
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. Provably efficient reinforcement learning with aggregated states, arXiv preprint arXiv: 1ee. 2019.
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, pp. 1665-1674. PMLR, 2019.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2/ 12. 13487, 2021.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-lerniin provably efficient? In Advances in Neural Information Processing Systems, pp. 4878-4878, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
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, 2021.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems, 53:15312-15322 2020.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))983-1006, 1998.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 121388:128-12 2013.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285-318, 1988.
Horia Mania, Michael I Jordan, and Benjamin Recht. Active learning for nonlinear system identifica- tion with guarantees. arXiv preprint NXiv:2006.10277 2020.

---

Published as a conference paper at ICLR 2023
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443, 1997.
Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. 2020.
Advances in Neural Information Processing Systems,
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
Martin L Puterman. Markov decision processes: discrete stochastic dynumic programming. John Wiley & Sons, 2014.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability, Advances in Neural Information Processing Systems, 23, 2010.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems, 26, 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 122111223)) 2014.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwesser, Ioannis Antonoglou, Veda Panncershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. Nature, 529(7587):4844489, 2016.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995. 2009.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2933.. PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Nolan Wagener, Ching-An Cheng, Jacob Sacks, and Byron Boots. An online learning approach to model predictive control. arXiv preprint arXiv:/902. /902.08967 2019.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2020.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv: 13, 2019.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD Thesis, Cambridge University, 1989.
12

---

Published as a conference paper at ICLR 2023
Grady Williams, Andrew Aldrich, and Evangelos Theodorou. Model predictive path integral control using covariance variable importance sampling. arXiv preprint arXiv: 1509.01 149, 2015.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004, PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.04622, 2020.
Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of autonomous driving: Common practices and emerging technologies. IEEE Access, 8:58443-58469, 2020.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. arXiv preprint arXiv:1901.000 2019.
Andrea Zanette, Alessandro Lazarie, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020a.
Andrea Zanette, Alessandro Lazarie, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 13:11756-1 11766, 2020b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532-44706 PMLR, 2021a.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pp. 12793-12802. PMLR, 2021b.
13

---

Published as a conference paper at ICLR 2023
APPENDIX
The appendix is organized as follows. discusssss the related work, providing comparisons with previous frameworks based on both coverage and sharpness of sample complexity. SB compares our regret bound and sample complexity specific examples and discusses several additional examples including reactive POMDPs, FLAMBE, LQR, and the generalized linear Bellman complete model. prooes the main results (Theorem II and Corollary 26 on sample complexity of OPERA). D explains the --tyee setting and the corresponding results. dissuusse the OPERA algorithm when being applied special examples (linear mixture MDPs, low Witness rank MDPs, KNRs). the delayed proofs of technical lemmas.
s details the proofs relevant to FE dimension.
A RELATED WORK
Tabuler RL. Tabular RL considers MDPs with finite state space S and action space A. This setting
has been extensively studied (Auer et al. 2008 Dann & Brunskill] 2015: Brafman & Tennenholtz
2002 Agrawal & Jial 2017 Azar al. 2017: Zanette & Brunskill 2019: Zhang 2020) and the
minimax-optimal regret bound is proved be O (H (Jin al. 2018 Domingues et al.
2021. The minimax optimal bounds suggests that the tabular RL is ceeemaaioo-thooretice hard for
large [| and |A]. Therefore, in order to deal with high-dimensional state-action space arose in many
real-world applications, more advanced structural assumptions that enable function approximation are demand.
Complexity Measures for Statistical Learning. In classic statistical learning, variety of com- plexity measures have been proposed to upper bound the sample complexity required for achieving a certain accuracy, including VC Dimension (Vapnik, 1999). covering number (Pollard) 2012). Rademacher Complexity (Bartlett & Mendelson 2002). sequential Rademacher complexity (Rakhlin ctt al., 2010)) and Littlestone dimension (Littlestone) 1988). However, for reinforcement learning, is major challenge to find such general complexity measures that can be used to analyze the sample complexity under a general framework.
RL with Linear Function Approximation. A line of work studied the MDPs that can be repre- sented as a linear function of some given feature mapping. Under certain completeness conditions, the proposed algorithms can enjoy sample complexit//regret.o scaling with the dimension of the feature mapping rather than ||] and [A]. One such class of MDPs is linear MDPs (Jin et al. 2020 Wang et al. 2019 [Neu & Pike-Burke| 2020), where the transition probability function and reward function are linear in some feature mapping over state-action pairs. Zanette al. (2020a b) studied MDPs under weaker assumption called low inherent Bellman error, where the value functions are nearly linear w.r.t. the feature mapping. Another class of MDPs is linear mixture MDPs (Modi al. 2020 Jia et al. 2020 Ayoub et al. 2020 Zhou et al. 2021b] Cai et al. 2020). where the transition probability kernel is linear mixture of number of basis kernels. The above paper assumed that feature vectors
are known in the MDPs with linear approximation while Agarwal et al. (2020b) studied a harder setting where both the feature and parameters are unknown in the linear model.
RL with General Function Approximation. Beyond the linear setting, recent line of research attempted to unify existing sample-efficient approaches with general function approximation. Ossand structural condition named eluder dimension. |Wang al. (2020)
& Van Roy 2014) proposed
further proposed an efficient algorithm LSVI-UCB for general linear function classes with small eluder dimension. Another line of works proposed low-rank structural conditions, including Bellman rank
(Jiang et al. 2017 Dong et al. 2020) and Witness rank (Sun et al. 2019). Yang et al. (2020) studied the MDPs with a structure where the action-value function can be represented by a kernel function or an over-paramen parameterized neural network. Recently, Jin et al. (2221) proposed complexity called Bellman eluder (BE) dimension. The RL problems with low BE dimension subsume the problems with low Bellman rank and low eluder dimension. Simultaneously Du et al. (2021) proposed Bilinear Classes, which can be applied to a variety of loss estimators beyond vanilla Bellman error, but with possibly worse sample complexity. Very recently, Foster et al. (2021) proposed Coefficient (DEC), which is a necessary and sufficient condition for sample-efficient interactive learning. To apply DEC to reinforcement learning. Foster et al. (2021) further proposed RL class named Bellman Representability, which can be viewed as a generalization of the Bilinear Class. In Table I we compare our ABC framework with other structural RL frameworks in terms of the model coverage and sample complexity.

---

Published as a conference paper at ICLR 2023
Bilinear Class
Low BE
DEC and Bellman Representability
ABC Class (with Low FE Dimension)
Dimension
Linear MDPs
d2
dH2j2
dHH2/22
Yang & Wang 2019 1 Jin et al. 2020
Linear Mixture MDPs
d/11"/22
x
d 1/13//2
d/111/e2
Modi et al. 2020
Bellman Rank
&HAAee
&HAA/
Jiang al. 2017
Eluder Dimension
x
dimg 22
ding 1//
dime H²/2²
WWan et al. 2020
Witness Rank
W.
Sun et 2019
Low Occupancy Complexity
d2H1/22
de22
d2H3/2
dHH2/62
Du ct al. 2021
Kernelized Nonlinear Regulator
d2d,1+412
Kukade et 2020
Linear Q*
dH11/2
d22222
de d'113/22
dHH2/
Du al. 2021 2021
Table Comparison of sample complexity for different MDP models under different RL frameworks. indicates that the original work of framework does not provide an explicit sample complexity result for that model (although can be computed in principle), "X" indicates the model is not included in the framework for complexity analysis. For models with the linear structure on a d-dimensional space, we present the sample complexity in terms of d. For models with their own complexity measures, use Wx to denote the witness rank, dimg the eluder dimension, d& the dimension of H in KNR and d, the dimension number of the state space of KNR. The dependency on p-covering number is deliberately ignored for Bellman rank, eluder dimension, and the witness rank.
B A ADDITIONAL EXAMPLES
In this section, we compare our work with other results in the literature in terms of regret bounds/sample complexity. First of all, as we mentioned earlier $ when taking DEF as (n,, fh+1, Ih. (h. ax) тл - V ($++1) the ABC function reduces to the average Bellman error, and our ABC framework recovers the low Bellman eluder dimension framework for all cases compatible with such an estimation function. On several model-free structures, our regret bound equivalent to that of the GOLF algorithm (Jin et al. 202I). For example for linear MDPs, OPERA exhibits a (dH LLH /T) regret bound that matches the state-of- offtthe-rrt result on linear function approximation provided in Zanette al. (2020a). For low eluder dimension models, the dependency on the eluder dimension in our regret analysis is (Vd)) while the dependency in Wang al. (2020) (dd). Also, for models with low Bellman rank d, our sample complexity scales linearly in d as in Jin al. (202T) while complexity in Jiang et al.) (2017) scales quadratically.
For model-based RL settings with linear structure that not within the low BE dimension framework such as the linear mixture MDPs,
OPERA algorithm obtains dy. H.T regret bound and d 2 /e2 sample complexity result. In comparison, Jia et al. (2020); Modi et al. (020) proposed an UCRL-VTR algorithm on linear mixture MDPs with a dH /TT regret bound, and Zhou et al. 2021a)
improves this result by / H via Bernstein-tyre type bonus for exploration. The Bilinear Classes Du al. (02T)) is general framework that covers linear mixture MDPs as special case. The sample complexity of the BiLin-UCB algorithm when constrained to linear mixture models is d (2 /
which 2 worse than that of OPERA in this work. In terms of lower bound, when specialized to linear mixture MDPs, our result of OdH matches the lower bound provided in Zhou et al. (2021a) up to a factor of 1/2
In the rest of this section, we compare on six additional examples: the linear Q- model (Du et al. 202T). the low occupancy complexity model (Du al. 2021). kernel reactive POMDPs. #LAMBe/Feature Selection, Linear Quadratic Regulator, and finally Generalized Linear Bellman Complete. Moreover, added discussion on the Q" state-action aggregation model.
2

---

Published as a conference paper at ICLR 2023
B. LINEAR QVIV*
The linear Q'IV* model was proposed Du et al. (2021). In addition to the linear structure of the optimal action-value function Q", further assume linear structure of the optimal state-value function V* We formally define the linear Q*/V" model as follows:
Definition 14 (Linear QV Definition 4.5 in Du et al. 2021). A linear Q' model satisfies for two Hilbert spaces H1, H2 and two given feature mappings ((s, a) : x A H1, 15(8') S + H2,
there exist w H1, 0 E H2 such that
(s. (wh, ((s.))
and Vi((') (6% (ss)))
for any E [H] and (s, 05 Axx
Suppose that 7i and H2 has dimension number dj and d2, separately, Du ct al. (0021) shows that linear Q* model belongs the Bilinear Class with dimension d dj + d2 and BiLin-UCB algorithm achieves an O H" sample complexity. On the other hand the sample complexity of
OPERA is of Ō( d22
B.2 Low OCCUPANCY COMPLEXITY
The low occupancy complexity model assumes linearity on the state-action distribution and has been proposed in Du (20TT) We recap its definition formally follows:
Definition 15 (Low Occupancy Complexity, Definition 4.7 7 in Du et al. 2021). A low occupancy complexity model an MDP M satisfying for some hypothesis class F. Hilbert space H and feature mappings (u(:,)) -) 8 A H. 4h E [H] that there exists a function hypothesis classes 3n : + H such that
d an) (3 (f), on (8),
VS V(sh. an) S A.
Du al. (2021) proved that the low occupancy complexity model belongs to the Bilinear Classes and has sample complexity of d3 /r2 under the BiLin-UCB algorithm. In the meantime, the low occupancy complexity model admits an improved sample complexity of d2 H2 /22 under the OPERA algorithm.
B.3 KERNEL REACTIVE POMDPS
The Reactive POMDP (Krishnamurthy et al. 2016 is a partially observable MDP (POMDP) model that can described by the tuple (S, O Drr, H). where S and A are state and action spaces respectively. O is the observation space, T is the transition matrix that maps each (s, a) E S A to probability measure on S and determines the dynamics of the next state as 8h+1 ~ T(- 8h, an). ). O the emission measure that determines the observation о₁, O(- sx) given current state $y. The reactiveness of a POMDP refers to the property that the optimal value function Q" depends only on the current observation and action. In other words, for all h, there exists fí O A [0, 1] such that for any given trajectory
[0i, aj,...,
ox] and dx, we have
Q'(Th an) JN (oh,aa)
Given the definition of a reactive POMDP, we define the kemeel reactive POMDP (Jin et al. follows:
2021 as
Definition 16 (Kernel Reactive POMDP). A kernel reactive POMDP is reactive POMDP that satisfies for each h E [ and a given seperable Hilbert space H. there exist feature mappings Φn S 7 and thy, and vi is bounded in the sense that for any V(-): S [0, 1). ||EEes (s3))(()))lx 1.
' such that the transition matrix (s' (s' ss,a) (0n a), , the (s'))
In Jin al. (2021). the authors showed that the kernel reactive POMDP with vanilla estimation VA+i. (SK+1) ) has V-type BE dimension bounded by the effective dimension. According to Proposition 34 the kernel reactive POMDP model also has low FE dimension bounded by the effective dimension.
function Es. (On, Jh+1,, 9h. Qn.g (Sh, ( r -a))aa;)r--
B. 8.4 FLAMBE/FEATURE SELECTION
For FLAMBE/feature selection model firstly introduced in Agarwal et al. (2020b), similarity is shared with the linear MDP setting but the main difference lies in that the feature mappings are unknown. We formally define the feature selection model as follows:
3

---

Published as a conference paper at ICLR 2023
Definition 17 (Feature Selection). A low rank feature selection model is MDP M that satisfies for any h E [H] and given Hilbert space H. there exist unknown feature mappings μ S and 6² S A + H. such that the transition probability satisfies:
Pa(d' 8, a) - 1 (6') (s,
We consider the feature selection model with DEF (oh, fh+1: Ih, u) = Qng (Sh an) Th VI+ti,(8h+1)) In Du et al. (2021) they have proved in Lemma A.1 that
Egn Ben~xyo way (sn, - rn Vh+1.(88411) XW)()):
(B.1)
where
Wh(f) = 1 (s) -((s)))sss (el(s)))-ByrPPdlaae (s) [V+11, ds,
BES
(g) = BBn
(5h-11 a1-1)]
We note that Eq. [B.I ensures condition i1 and iij in Definition 5 at the same time and the ABC of the feature selection setting has bilinear structure that enables us to apply Proposition 35 to conclude low FE dimension.
B.5 LINEAR QUADRATIC REGULATOR
In a linear quadratic regulator (LQR) model (Bradtke 1992
Anderson & Moore, 2007: Dean et al.
Ra and K dimensinal action space A C R The transition dynamics of an LQR model can be written in matrix form so that the induced value function is quadratic (Jiang al. 2017). We formally define the LQR model as follows:
2020), consider the d dimensional state space S
Definition 18 (Linear Quadratic Regulator). A linear quadratic regulator model is an MDP M such that there exist unknown matrix A Idd B E Rdx R and Q E Rd satisfying for vh E [H] and zero-centered random variables En, Th with E
and [[ o² that
Sh+1 1 Ash + Bab + Ch.
F = s, Qan + aj an + Th
The LQR model has been analyzed in Du et al. (202T) and proved to belong to the Bilinear Classes. Du et al. (202I) used the hypothesis class defined as
Fr = [(Cn, An, On) Cn E kxd Ar Rddd On E E
For each hypothesis in the class f E F, the corresponding policy and value function are
Ty (sh) = Sh. Vn, = An, + On,f-
Under the above setting, (1+t1,(5h+41) and Lemma A.4 in Du et al. (2021) showed that
the DEF for LQR en (on, 1h,, v) Qh an) Ph
E Ean [Qn,5 an) - rh (++t, (WW))) (WaL(),
(B.2)
where
- (A (a) = [vec(An, - 2- Ch,
BCh,s) A T BCn,)))
On. - Ont1s - traceeAA E1)
(x = [vec (Ee, 11)
We note that Eq. (.22) ensures condition and in Definition I simulaaneousy and the ABC of the LQR model setting admits a bilinear structure that enables us to apply Proposition 35 and conclude low FE dimension.
6.6 GENERALIZED LINEAR BELLMAN COMPLETE
Next we introduce the generalized linear Bellman complete model, showing that ABC class with low FE dimension captures this model even without the monotone operator vx used in Du et al.
(022
4

---

Published as a conference paper at ICLR 2023
Definition 19 (Generalized Linear Bellman Complete). A generalized linear Bellman complete model consists of an inverse link function o R - R$ and a hypothesis class J : (Fr o (0, ((s,a)) 0n H. ||0, S R), he(m such that for any F and vh [H] the Bell-
man completeness condition holds:
r(s,a) + EE, max d')) E Hn.
d'EA
By the choice of the hypothesis class F, we know that there exists a mapping Th H. - H. such that (On(0)))))) T ((s, a)) r(s,a) + Eg max
max (f%41.
(B.3)
a'EA
We note that in Du et al. (022)) they choose a discrepancy function dependent on a discriminator function v. In this work, choose different estimation function that allows much simpler calculation and sharper sample complexity result. We let
En (on, 11 Ih. -h. v) == a ( an)) max 1
By Eq. (B.)
it is easy to check that the above DEF satisfies the decomposable condition. Assuming b, Lemma 6.2 in Du et al. (021) has already shown the Bellman dominance property
S that
BBnnarr (Qn.f(9h, an) - Va+ 1,5 (8h+1)]]]
b/ (veo ((On.) (T,,00,,,,, (1(0++1,)) (Ben,on~z,, an)o(sh T))
(W)
Next, illustrate that the Dominating Average EF condition holds in our framework. We have
E Ban Kop [eaL (ong fr. v) sh: 1l
E. Es (( ax)) (T (0x+1.)) 1 ( (oss
2 a a.snarr ((On.- (0n- 2 (8h,
a (Wr(), ((())) (W)))))))))))
where
(f(f) = vec ((On.) Th T TT(Ott1.))))
Xx())= vec (Es,,a ((s), an (8())
Analogous to the KNR case and the proof of Lemma 30 the aforementioned model with ABC has low FE dimension.
function
B.7 Q' STATE-ACTION AGGREGATION
Finally, we consider the Q" state-action aggregation model (Dong et al. 2019), which cannot be covered by the bilinear classes (Du et al. 2021). We illustrate that our ABC framework covers this model with nonlinear coupling function.
Definition 20 (Q" state-action aggregation). We call an MDP M Q" state-action model if there exists a ((s, E(s, a) = E(s', a"), then Q* (s'
x + such that for any state-action pairs (s, (s',a') E S A, ((s'',a a'). The dimension d of the Q" state-action aggregation model defined as the cardinality of B, i.c., d = |B]
For each element E B, we note that for all (s) E S x A satisfying ((s.a) = 6, they share the same value of Q(s, a). For notational simplicity, we use Q(b) to denote this common value for all as b. Moreover, we let w7 be d-dimensional vector of all aggregated values with (w)),, = Q(b) and (s, a) can be expressed as linear function on the aggregated values:
(s, a) (w), (ss a))
where (s, : S > (0, 1)d is one-hot vector satisfying
(bbs, a))s = 1 when {(s, b and (v'ss, a)); 0 otherwise.

---

Published as a conference paper at ICLR 2023
For this case, we use the hypothesis class defined as
Fn ww IR ]NE
where we take
Q8.g(8,a)= = (Wh..g g. (8 a))
Vig(s') = max a'EA
We define the DEF as the Bellman residual and conclude that Cn Cn I,+ Dh, v) (hh an)) Th Vh.g (8 (8h ah)) - Vi
(sh, an) - (sn+1]]
= (wh.g who (88 a)) ())-
max
(whh.g th (84+11, - max (wh (sn+1, d'EA
a'EA
(B.4)
Taking expectation over the distribution on on given by sh, ag ~ ay and 8h41 ~ Phs we have
E Een,o [en (On, Ih+1 Ih. vi]
= (Wh,g Wh Esn,anwyy (sh an))
-Banay I~P,,
max (wn.gg (88+11, e'EA
e'EA max (1rhs ((n+11
(B.5)
If we define G(g, f) by the right hand side of (B.5). it is obvious that G with & defined in (B.4) serves as the coupling function and the estimation function of ABC class, respectively. In the mean time, Equation (B.5) cannot be expressed as inner product of some (J')), Xa(g) and thus cannot be covered by Du al. (202T). Nevertheless, in our ABC framework, it unclear if the FE dimension of JF with respect to Gh,r" (:)-) can be bounded in nontrivial way (i.e., < |S| LA).
C PROOF OF MAIN RESULTS
In this section, we provide proofs of our main result Theorem IT and sample complexity corollary of the OPERA algorithm. Originated from proof techniques widely used in confidence bound based RL algorithms Russo & Van Roy (2033) our proof steps generalizes that the GOLF algorithm Jin et al. (021) but admits general DEF and ABCs. We prove our main result as follows:
C. PROOF OF THEOREM
We recall that the objective of an RL problem is to find coopimall pol- icy satisfying Vi (s VT (s1) < e. Moreover, the regret of an RL problem is defined as EL (1) - VIT (s1), where 7² the output policy of an algorithm at time t.
Proof of Theorem 77
Step 1: Feasibility of ʃ" First of all, we show that the optimal hypothesis 1 lies within the confidence region defined by Eq. (4.1) with high probability:
we choose , e(log (T (P) + p) for some large enough constant e. Then with probability at least 8. f satisfies for any E [T]:
Lemma 21 (Feasibility of f*). In Algorithm I given p > 0 and
max VED
Σ 1e fh-1, e)1
inf ED
Σ Me (% fi41 Sh. w)(?? < (O3).
Lemma 21 shows that each round of updates the optimal hypothesis f stays in the confidence
region depicted by Eq. (4.1) with radius ((33). We delay the proof of Lemmal 21 to $E22 Lemma 21
together with the optimization procedure Line 3 of Algorithm iimplies an upper bound of (/1(ss)
Vi (s1) with probability at least - 5 as follows:
(ir(s) VT (s1) S Vi,, - (s1)
(C.1)
Step 2: Policy Loss Decomposition. The second step is to upper bound the regret by the summation of Bellman emror.. We apply the policy loss decomposition lemma in liang al. (2017).

---

Published as a conference paper at ICLR 2023
Lemma 22 (Lemma in Jiang et al. 2017 Vf H.
(51)) V/ (81)
E aa wor (t Th (n+1,
Combining Lemma 22 with Eq. (C.1) we have the following:
H
(i(()) - VT (81) & (s) - VT (81)
Σ
E E an wast (1 - Th (s
=
(C.2)
Step 3: Small ABC Value in the Confidence Region. The third step is devoted to controlling the cumulative square of Admissible Bellman Characterization function. Recalling that the ABC function is upper bounded by the average DEF, where each feasible DEF stays in the confidence region that satisfies Eq. (4.1). we arrive at the following Lemma 23
Lemma 23. Algorithm I given p > and 8 > we choose c(log (T))) + Tp) for some large enough constant c. Then with probability at least 1 - 6, for all (f. h) E [T] [H], we have
(f < 013).
(C.3)
The proof of Lemma 23 makes use of Freedman's inequality (the precise version in Agarwal et (2014) and we delay the proof to SF.
Step 4: Bounding the Cumulative Bellman Error by Functional Eluder Dimension. In the fourth step. we aim to traslate the upper bound of the cumulative squared ABC at (ft, (*) in Eq. (C.3 to an upper bound of the cumulative ABC Lemma 41 in Jin et al. (2021) and Lemma 2 in Russo & Van Roy (2013). Lemma 24 controls the sum of ABC functions by properties of the functional eluder dimension.
f(). The following Lemma 24 adapted from
Lemma 24. For a hypothesis class and given coupling function G(; F FXFF R with bounded image space [G(--)] I C. For any pair of sequences {frkerm, (ather C Satisfyiig for all e [T]. E (G(f...))) < B, the following inequality holds for all f [7] and >
Σ G(fi. s 50 (dimp Gt + C minft, dimpa (F,G,w)) + tw)
The proof of Lemma
24 is in
Step 5: Combining Everything. In the final step, we combine the regret bound decomposition argument, the cumulative ABC bound, and the Bellman dominance property together to derive our final regret guarantee.
For any h E [H]. we take G(.,)) = Gn,r- (s:), = St = and w = / in Lemma 24 By
Eq. CC3
Lemma 23 we have for any h E [H] and E [T].
Σ G (f (()))) so (v Vdimpe(FF Gh, 3/T)) + C min(t, dimpe(F, Gh.r' v1/T)) + Vi
s <olv dimmee (F, 1/TT)
We recall our choice of B = c clog (THN +P)) Taking 7,, we have
Gh. (f). 5
/iimr [F,G..r., log (TH))(1/T)//)) -t
< 0
dimpe (J,G, log (THN((//T//))
7

---

Published as a conference paper at ICLR 2023
Combining this with property ( in Definition and decomposition C.2 result that with probability at least 1 - 6,
conclude our main
T
Σ (1)
(x1)
G (f'
K
t= h=1
0 H
T dimme(F G. 1/T) log (THN2(1/T)/0)
This completes the whole proof of Theorem
C.2 SAMPLE COMPLEXITY OF OPERA
Corollary 25 (Sample Complexity of OPERA), For an MDP M with hypothesis classes F, G that satisfies Assumption [ and Decomosable Estimation Function satisfying Assumption 7 If there exists an Admissible Bellman Characterzation G with low functional eluder dimension. For any
x2,2 E (0, 1], we choose 3 = [o diima(F.G, 2. (5) + dimea (F,G, H for some
2²,
large enough constant c. For the on-policy case when Top = Test = n², with probability at least 1 - Algorithm D outputs a e-optimal policy Fout within T trajectories where
dimrr G, H log
THNE
x2,2 (Fmue(F.G.5)1) 18 H²
T
x²22
Proof of Corollary have that
25
By the policy loss decomposition
Lemma 23 and Lemma
T
Σ
(s1)
VT' (s1)
Gh.f (f',
KT
h=1
0
H
dimpe (F, G,G)
log (THNc(P))/0)
+ +D)
Hw)
Hw
T
(C.4)
Taking w # and p dimpa F,G, u2 ,
x²2²
the above Eq.
C.4
becomes
T
H
dimpe [. x log (THNc(0)/0)) +c)
Σ
(81) (T((s) <0
K
T
Taking
T dimpr (F, G, RC log (TH H²
x222
yields the desired result.
D Q-TYPE AND T-PEPE SAMPLE COMPLEXITY ANALYSIS
In Definition 5 we note that there are two ways to calculate the ABC of an MDP model depending on the different choices of the operating policy Top Specifically, if Top Tg. call it the Q-type ABC. Otherwise, Top Ty, we call it the Vttpee ABC. For example, when taking
Gh,f (f. g)
annw, [Qn., (Sh, an) r(sk, ax) (
the FE dimension of Gh,r- (f.9) recovers the Q-type BE dimension (Definition in Jin et al. (021)
When taking
Gh, (f.g) = Rey an Qu. (8h. an) r(sn, an) - V V
the FE dimension of Gr.f (f. g) recovers the V-type BE dimension (Definition 20 in Jin et al. 2022
The algorithm for solving Q-type or V V-type models slightly differs in the executing policy West- We
use Tes n² for Q-type models in Algorithm I while Teat ((A) is the uniform distribution on action set for V-type models.
8

---

Published as a conference paper at ICLR 2023
The Q-type characterization and the V-type characterization have respective applicable zones. For example, the reactive POMDP model belongs to ABC with low FE dimension with respect to V- type ABC while inducing large FE dimension with respect to Q-type ABC. On the contrary, the low inherent bellman error problem in Zanette et al. (2020a) is more suitable for using Q-type characterization rather than V-type characterization. For general RL models, often prefer Q-type ABC because the sample complexity of V-type algorithms scales with the dimension of the action space |A]. Due the uniform executing policy, we will only be able derive regret bound for Q-type characterizations, as is explained in Jin et al. (202T).
In $ and [C] we have illustrated regret bound and sample complexity results for the Q-type cases where we let Fop = Test π' through Algorithm complexity result for V-type ABC models.
the following Corollary 26 we prove sample
Corollary 26. For an MDP M with hypothesis classes F. 9 that satisfies Assumption I and a Decomposable Estimation Function i' satisfying Assumption 7 If there exists Admissible Bellman Charactcrization with low functional cluder dimension. For any & E (0, 1], if we choose = O
Tp). For V-type models when Top
Test n², with probability least [A] Alldigg (F.ngeeFG..... m) log(T (NNN)())/0)
1 - Algorithm outputs e-optimal policy Tout within T
x²,,2
trajectories where p dimue G. JH"
The proof of Corollary 26 basically follows the proof of Theorem I| and We again have feasibility of f and policy loss decomposition. However, due to different sampling policy, the proof of Lemma 23 differs at Eq. (F.5) Instead, we have
Proof of Corollary 26
Corollary 25
max E waa aa Esni [Xi(h, sh, an]
VEV
[(at, = Fz (sh))
max Egg rat (A)
Bants [Xi(h, 8h, anl
VEV
1/1.A|
1 1(ah = fT (8h))
max E ros aa (AA)
||B [en, fh+11 1it4iifhh fho 2) sn, on] 1|2
NEV V
1/(AA|
0[A|| (3 Rtp + R²1)). 1=1
(D.1)
Thus, Eq. C.. in Lemma becomes
(f,,))) O(IA1)).
The rest of the proof follow the proof of Corollary 25 with an additional |A] factor. By the policy loss decomposition (C.2) and Lemma 24 have that
T
(i((s) - VT (81)
G (J'
T
h=1
H
llgg (THNN(())/8)
Hw
<
Al dimpr (F,
+ ()) +
K
T
(D.2)
2,22 Kt and p dimmi (.a, F.G. 23 y
Taking w =
the above Eq. D.2)
becomes
1f
1 - (st) s s H | (F. G, ss log (THNc(P)/0) +c).
T
Taking
[A] dimpr (F,G. G, KE log (THNc(P)/8) H²
n22
yields the desired result.

---

Published as a conference paper at ICLR 2023
E PROOF FOR SPECIFIC EXAMPLES
In this section, we consider three specific examples: línear mixture MDPs, low Witness rank MDPs, and KNRs. We explains how our framework exhibits superior properties than other general frameworks on these three instances of MDPs. For reader's convenience, we summarize the conditions introduced in Items (i) (i) in Definition 6 and also Items (1 in Definition [ that are essential for
any RL models to fit in our framework:
Decomposability:
f (on; Jh+1. Sh. v) E (on, Ja+1, 9h. sh; an) fn (on, Sh+1, T(f),,))
Global Diseriminator Optimality:
|| ( (on, fh+1, Sa. of 8b, an) 2 |B (o, fa+1, Su. st: anl
Dominating Average EF:
max Eay Tg BBA,1 (on, J4+1, (n,1,,,,)) 8h, an] (Gh. NEV
Bellman Dominance:
(Qn, an) - r(8n, an) - Vn+i.((Nn+ S (G..s-(J..))
E. LINEAR MIXTURE MDPS
In this case, choose Fr 9n {0, H). Thus, the hypothesis classes F and consist of the set of parameters 0 l E H. Moreover, for each hypothesis class f = (01.f1... OH.s) E F, the value function with respect to f satiafies for any h E [H] that
(n. a) = 0h,s (v((,,)) a) + do..t.,
where @Vi+a,, (8, a) = Eves Ms, a, s') V/) (5'). It is natural to define the DEF by En fnt111 9h. v) 0hi (hsh am) + @v (sh, and] - Th Vn++. (141)((5h1)))
If use 4// to denote the matrix ( + ov [sh ab) (v + - 10h 4-1 t-1
Oh
and y denote the vector (rh 1 (5)+1)) ..... ......Th
Vati,f (s/tt1)) Eq. (4.1 in Algo-
Th ....,
rithm under linear mixture setting can be written in matrix form as:
1 h
yh
111
inf |10 t/o 2112 < B.
(F.1)
Taking 0n. arg min ||0 q/- T
112 1 ( ))
/% (yy and E
2 (0% simple algebra yields
112 11= = || (0n.) Slas-Op.. 0n.)) 2/,-111 -On.)- T
| 1n,c 2
1107,, 2/- yh 111 inf 10 2 yn
0
x
(E.2)
So Algorithm| [ reduces to Algorithm 2
In particular, the confidence region defined by Eq. E.2) in Algorithm is the same as the confidence region used in the upper confidence RL with value-targeted regression (UCRL-VTR) algorithm (Tia et al. 2020 Ayoub et al. 2020). While in UCRL-VTR, they perform step-by-step local optimization within the confidence region, resulting in a confidence bonus added upon the Q value function, our Algorithm 2 follows global optimization scheme, where the objective is the total expected return by following the optimal policy under the current hypothesis. The design principle of the global optimization the same as the ELEANOR algorithm (Zanette et al., 2020a). In fact, the difference between UCRL-VTR with Algorithm 2 is analogous to the difference between LSVI-UCB (Jin et al. 2020) with ELEANOR (Zanette et al. 20200a).
Algorithm 2 exhibits a v regret bound and de H22222 sample complexity result, as will be shown later in this subsection. Compared with the d H4/e2 sample complexity in Du et al. (021). our
10

---

Published as a conference paper at ICLR 2023
Algorithm 2 OPERA (linear mixture MDPs)
Initialize: D/. 2: for iteration f = 1. 2,.... T do
for h I....,
3: Set x" := x where f is taken argmaxfez (51, subject to
On. = i (0 )))
|oa. 0n. 0 S 3 for for h E [M] (E.3)
4: For any h E H collect tuple (ri, 8h, an, 8h-1) by executing ~ x²
5: Augment D = Dn, {(rh, 8h; un, 81+1)]
6: end for
7: Output: Yout uniformly sampled from M_=
algorithm improves over the best-known results on general frameworks that subsumes linear mixture comparisons the linear mixture model in S
MDPs. We provide
In terms of computation, assume that there exists planning oracle for the optimization problem in Line 3 of Algorithm that requires B time complexity to solve. Then for each E [T], h E [H]. the
computational complexity of the rest of the algorithm is dominated by the computation of 12 and the total computational complexity would be O + d' HT).
Next, we proceed to prove that linear mixture MDP belongs ABC class with low FE dimension.
Proof of Proposition In the linear mixture model, we choose hypothesis class Fr. = G =00 e H.,, and DEF function
lu (Oh, fu+1, Ih, v) 1h,
0 wish an) an) + Σ pshn an s v' rh (142))((h421).
(a) Decomposability. Taking expectation over + and obtain that
Esp-1 g fa+1, 9h, v) 8h; an) (fn.g 07) (bn Σ
psnn an, o')n
Thus, we have
En (on, Snt1, -EEn (en Jn+1, 8h, an)
=07) (ssn, (x)n)ax)= an) + Σ plon, an, o'Vai,
= En. fh-1, fh. v).
(b) Global Discrininator Optimality holds automatically since is independent of u.
(c) Dominating Average EF. We have the following inequality for linear mixture models:
Ba e ||B (en. (on, (on, fh41, fn, v) st. an] ||
an, an, 5'Ve. ))
Engagrein (On.s 0h)
d(sh, an) Σ
6¹
(0h.. 0%) Esn.on
(b()n))))+ an) + Σ
bssn an, an, 5'V
(E,4)
(d) Bellman Dominance. On the other hand, we know that
Engian (Qn, an)) ra. (
= Emn,araa (0n..- 0h)
(Ssn, an) + Σ b(sn, an, V')
=(On. - 87) EmiounTy
((sn,an) an) + a olsn, ab, V
(B.5)
11

---

Published as a conference paper at ICLR 2023
Algorithm 3 OPERA (Low Witness Rank MDPs)
Initialize: D/
for h I....,
2: for iteration f = 1, 1.2.... T do
3: Set x" == ky where f is taken argmax (1. subject to
Sa v an v(shi ai sh+1))
(Ea-sn oshh, ohe v(sh als shur))) S all h [H] (E.7)
inf Σ
(E
4: For any h E [1]. collect tuple (rh, Sh, On, 8h41) by rolling in 84 or and executing as
U(A)
5: Augment D Dr U [(rh. 8h. on $1+1)}
6: end for
7: Output: Toat uniformly sampled from (m')
(e) Low FE Dimension. Observe from Eqs.
E.4 and
E.5 that choose ABC function of an
linear mixture MDP as
G (f. = (8n.)- - 0%) Ben,annT,
sinn an) + Σ slsn, an. 5' Vi)zzg(0')
(E.6)
The next Lemma 27 proves that the FE dimension of F with respect to the coupling function Gh,,- (f,g) is less than the effective dimension of the parameter space H.
Lemma 27, The linear mixture MDP model has FE dimension & (d)) with respect to the ABC defined in (E.6).
We prove Lemma 27 in
Thus, we conclude our proof of Proposition g
From the above Proof of Proposition we see that linear mixture MDPs perfectly fit our framework. We apply Theorem 11 and Corollary 25 to linear mixture MDPs and conclude directly that Algorithm has regret upper bound of dH VT together with sample complexity upper bound of d H² matching the best-known results that uses Hoeffding-type bonus for exploration.
E.2 LOW WITNESS RANK MDPS
In this subsection, we provide a novel method for solving low Witness rank MDPs as a direct application of the OPERA algorithm. The witness rank is important model-based assumption that covers several structural models including the factored MDPs (Kearns) 1998). Also, all models with low Bellman rank structure belong to the class of low Witness rank models while the opposite does not hold (Sun et al.) 2019). Although the witness rank models can be solved in model-free manner, model-free algorithms cannot find near-optimal solutions of general witness rank models in polynomial time. Meanwhile, existing frameworks (Sun et al.) 2019 Du et al.) (021] with an efficient algorithm does not exhibit sharp sample complexity results. We recall that in low Witness model-based parameters (transition kernel and reward function) made. Based on this, there are two recent lines related approaches. [Sun et al. (2019) first proposed algorithm that eliminates candidate models with high estimated witness model misfits. On the other hand, Du et al. 2021) proposed a general algorithmic framework that would imply an optimization-ball bassdd algorithm on low Witness rank models.
rank settings, hypotheses
The following definition is generalized version of the witness rank in Sun al. (2019), where require the discriminator class V to be complete, meaning that the assemblage of functions by taking the value at (s, a) from different functions also belongs V.
Definition 28 (Witness Rank). For an MDP M. a given symmetric and complete discriminator class V (Va heja VA C S x A x S + IR and hypothesis class F., we define the Witness rank of M as the smallest d such that for any hypotheses f.g F. there exist mappings X,, F Rdd
12

---

Published as a conference paper at ICLR 2023
and Wi: : F + Fd and constant (0, 1], the following inequalities hold for all h [H]:
max Es Es a [gggg (Sh. ob S) EgnPA (sh, ah 5)] 2 (W.(g),xx(f)) BE V (5) - (Wi (x)
(E.8)
"EVa
R K as [B V
(E.9)
We prove an improved sample complexity result over existing literature and illustrate the differences in design scheme of algorithm. We present the pscudocode in Algorithm 3 Note that in Eq. (E.7). we replace the DEF in Eq. (4.1) by (3.2). Next, we elaborate the design scheme of algorithm in comparison with [Sun et al. 2019 and Du al. (202T). Note that the DEF
Ez-g, U(),, ap. 8) USh On, 11++1) is similar with the discrepancy function used in Du et al. (2021)
except for an importance sampling factor. Moreover, after taking sup over discriminator functions, the expected DEF equals the witnessed model misfit in [un et al. (2019). Although Du et al.) (202T) did not explicitly give an algorithm for witness rank, we observe some general differences between OPERA and BiLin-UCB (Du ct al. (021). The confidence region used in Algorithm 3 (simplified version for comparison) is Li(eg)
g ((t) S B centered at the optimal hypothesis, while
the confidence region used in BiLin-UCB is Σ; 4 Egs kq(ii) 3' that bound an estimate of l centered O. Similarly in BiLin-UCB, [unn al. (2019) also attempts to bound batched estimate of E. Their algorithm constantly eliminates out of range models, enforcing small witness model misfit on prior distributions. The analysis in [Sun et al. (2019) and[Du et al.) (2021), however, does not enforce the additional assumption on the discriminator class; we obtain a sharper sample complexity as in Corollary [2]
2
If assume that there exists a planning oracle for solving the optimization problem in 3f Algorithm 3 with B time complexity. The computation in the rest of the algorithm is dependent on the structure of discriminator class V and the hypothesis class G. We omit the discussion here as the planning oracle with total computational complexity of ((BT) is usually the dominating term. In the forthcoming, we prove that low Witness rank MDPs belongs to ABC class with low FE dimension.
Proof of Proposition In the low Witness rank model, we choose hypothesis class Fn = Gn = M, and DEF function
(oh: fa+1, 9h, v) Ez-gn (shh, an. 3) - v(sh. ah. sh+1).
(E.10)
Without loss of generality, we assume that the discriminator class V is rich enough in the sense that if Vs, a E S x A, :.. E V. then v(s, a, s') ;= V a.)) E V (if not, we can use rich enough V induced by V). an assumption generally satisfied by common discriminator classes. For example, Total variation, Exponential family, MMD, Factored MDP in (Sun et al. (2019) all use rich enough discriminator class. Also, if V = [v: ||e|| S c) class is rich enough.
for some absolute constant e, the function
(a) Decomposability. Taking expectation over $/+1 of Eq. (E.10) and we obtain that
E Esuts Te fn.1.9h. Sns axl = Eang, u1 an.3) - Ezn,, usn ap 3). (E.11)
Thus, we have
E (Ons fa+1, U) Een, (On fh+1, u) 8h, an)
TaNB, u(sh: ar: 8) En(on fh+1, v).
u( ah; 8k+1)
(b) Global Discriminator Optimality. Eq. E. implies that
Brssi (On, fh) 8h, an) = / u(sn, an, s) (fi(s 8h, ax) - Ps(s sn, ax)) ds.
We define (f) a, a.) (s, a's where
/ u(s, ((s,a, (F a) PA(5 s,a)) ds.
Ussa := arg max wEV
It is easy to verify that (f) satisfies for all h E [H] and (sh. an) E S x A,
E (on, Jn+1, Jn, (T)) sh, sh,an) 2 Es a (es (on, fu+1, Sn, v) 8h, an) Finally, the symmetry of V concludes the global discriminator optimality.
13

---

Published as a conference paper at ICLR 2023
(c) Dominating Average EF. We have the following inequality for low Witness rank model:
max OATT (o fn+1, fh. v) 8/, axlal
NEV
max B 0 (B (8h,, On 8) EgnP, (8h,, (b, (/, 8))
vEV
(1)
max NEV
E
B uSh an. 3) Ba-p, (s On 3) 24 - -.g
(Wx(f),Xxo)))
(E.12)
where the last inequality (i) follows Definition 28 of witness rank.
(d) Bellman Dominance. On the other hand, by Definition 28 we know that
K Ee, anrxy 1Qn. (sh, an) - -rh (1++1,/(*+11) < (W.(f),xx(f))
(E.13)
(e) Low FE Dimension. We see from Eq. (2112 and E.13 that we can choose ABC function with low Witness rank RL model as
Gh.y (f.g) = (VV
(E.14)
The next Lemma 29 proves that the FE dimension of F with respect to the coupling function G (f.g) is less than the dimension Wx of the witness model.
Lemma 29, The low Witness rank MDP model has FE dimension S O(W,) with respect the ABC defined in (E.14).
We prove Lemma 29 in
Thus, conclude proof of Proposition 9
By Proposition we can straightforwardly derive the sample complexity by applying Corollary 26 For better understanding of the context, we present complete proof of the sample complexity result of witness rank model in $E.4
E.3 KERNELIZED NONLINEAR REGULATOR
In the KNR setting introduced in $3.2 the norm of 84+1 might arbitrarily large the random vector ch+1 is large in magnitude. On the contrary, framework requires the boundedness of the DEF. To resolve this issue, we note the tail bound of one-dimensional Gaussian distribution indicates that for any given positive .::
$12 [ e 212 S e
t -1/2 Le-111
1
-e
Thus, for TH i..dd -valued random vectors cf ON(0, and fixed 8 E (0, 1), there exists event B with P(B) 5 such that ||c llc I ( (o holds event B.
We first provide the application of OPERA on the KNR model, the algorithm is written in Algorithm Note that by similar algebra as in Eq. (.2). the confidence set (E.15) is equivalent to
[[Un, (2t, 8,
where 21, = ( and Ün, is the optimal solution to the least square problem ) U s/. a 11. The OPERA algorithm reduces to the LC3 algorithm 2020 except that LC is under homogeneous setting. The only difference between Al Algorithm and LC is that in Eq. (5. LC sums over i and H and we can only sum over
arg minl Σ 1-1
in Kakade
because of the inhomogeneous setting.
Bringing the choice of 3 in Corollary yields regret bound of Ō (Vdd In comparison,
LC in Kakade et al. 2020) has a regret bound of δ (dold. + +d)dd+d))) H3) The improved factor
of VH is due to the reduction from the time-inhomogencous setting the homo-hooogsssuus setting. Thus, our regret bound matches the state-of-the-eee result on KNR instances (Kakade et al.) 2020) regarding the dependencies on dg d,, H. However, de d, in result is slightly looser than
14

---

Published as a conference paper at ICLR 2023
Algorithm 4 OPERA (kernelized nonlinear regulator)
Initialize: D/ 2: for iteration f = 1. 1.2,.. 2..... T do
for h I....,
3: Set x" := xy where ft is taken argmax yer (1.((11, subject to
((u,,o(shh sht1
inf an EDR
(nno sh+il? 2
for all h [H]
(E.15)
4: For any [H], collect tuple (Ph, Sh, ah, ah, 8h-1) by executing 8h, an x²
5: Augment D Dn U [(r,, 8h, On, 8h+1)}
6: end for
7: Output: Tout uniformly sampled from {T²)²=
ds(d, + dg.) in Kakade et al. 2020) and can be possibly improved by instance-specine analysis of KNR. Similar to the linear mixture MDP case, if we assume that there exists a planning oracle for the optimization problem in Line B of Algorithm that requires B time complexity solve, the rest of the algorithm can be solved efficiently in (dd + d.) time complexity. So the total computational complexity of Algorithm is OBBT + (dg + H.)HT).
In addition, would like remark that such as MPPI (Williams et al., (015) and DMDMPC (Wagener et al., (019) to solve the optimization problem in Line 3 of Algorithm 4 This approach has been used in Kakade al. (2020), where they
adapt algorithms from the optimal control literature
designed the LC algorithm for solving KNRs. In particular, they leveraged the MPPI algorithm for the planning oracle and provided rich empirical results.
Proof of Proposition 10 In the KNR model, we choose hypothesis class Fr Gn = {U E pd. ||U|| RR, and DEF function
(on, fht Un.g ax) Sh+1.
(a) Decomposability. Taking expectation over 8/+1 and we obtain that
Banty [eA (on, fh+1, 9h. u) 8h, an) (Un.g Uh),
Thus, we have
Ea (on, fa41,9h, 9h, u) Erg.s (on, fa+1, v) sh, an] UNo(s), a.) 8h41 = En(on, Sa41, Sh v).
(b) Global Discriminator Optimality holds automatically since is independent of v.
(c) Dominating Average EF. We have the following inequality for the KNR model:
EegannoT, |E (on, fn+1, fr. v) sh, an] 1|? = Ern |l(Un.. -
(E.16)
(d) Bellman Dominance. On the other hand, we know that
2H E Esn.y
Esp, way (Sh, Th (1+t))
1(Un.,
Ug) (s)) an)
σ
(E.17)
(c) Low FE Dimension. We see from Eqs. linear mixture MDP as
E. and E.17 that we can choose ABC function of an
Gh,f- (f.--(f))
v
Beg Ben [( UR)6(sH,
(E.18)
and KNR has an ABC with k = TH The next Lemma proves that the FE dimension of F with respect the coupling function Gh.f- f- (f.g) can be controlled by dø:
Lemma 30. The KNR model has FE dimension O(dg) with respect to the ABC defined in (E. 8
We prove Lemma 30 in
Thus, conclude proof of Proposition T0
15

---

Published as a conference paper at ICLR 2023
E.4 PROOF OF COROLLARY
12
In this subsection, we provide sample complexity guarantee for models with low Witness rank. In the main text in 44.3 presented Corollary [2 for M and V with finite cardinality for convenience of comparison with previous works. Here, we prove general result for model class M and discriminator class V with finite p-covering.
Proof of Corollary [2 We start the proof by showing that V* VIT (s1) can be upper bounded by a sum of Bellman errors, which is a simple deduction from the policy loss decomposition lemma in Jiang et al. (2017) and is the same the equality in Eq. (C.2) in the proof of Theorem [I in $ Next, we verify that f satisfies constraint (E.7) so that taking fr = arg max ($1) in the confidence region yields (s1) S (s1).
Lemma 31 (Feasibility of f*). In Algorithm given 0 and 5 > 0, we choose / =
Tp) for some large enough constant c, then with probability at least 1 - 6, I satisfies for any / E [T]:
c(log (TH)Mp (
max Σ
[B , u (sh 3) - v(sh an ))
B Bangy u u(hh ah, - vlhh, (h+ s s
inf 9A ED
We prove Lemma 31 in The next Lemma 32
is devoted to controlling the average squared DEF.
Lemma 32. Algorithm given > and O. we choose = c(log (THMM Voo Tp) for some large enough constant then with probability least 1 5, for all (t, h) E [T] [H) have
max E NEV eq ONNE
(B (1sh/ og. 3) P
((AA))
Proof is delayed to By Lemma 32 and properties of the witness rank in Definition we have
max E Es Mara (B ushh o). Ez- (- at 5)) 2
"EV
max E, MR.NTT VEV
(Er 0(8), oh, Ex an 3)) ((
Applying Lemma 24 with Gn.y-(f.g) = (Wilf)xN(0) and gi = f fth we have
Σ (WWA)) (VVAA/ddmmm Gn w) + tw
Policy loss decomposition
yields
1
VI (s1) 0 A AlimFe(F (h) log (TH (MH,M,,. (P/111/1)))
(V,1/0)
Hw
T ΣV Vi((s) -
+ +
+
T
K
Taking H and p Timm T the above Eq. C.4
becomes
1 T
H H AA dimpe [F, G, $ log (H +c).
T ΣΣ (i VF (si) 00
T
t=1
Taking
T dimm (F, G, log (TH, (V/8 H²
k22E h+1
yields the desired result.
16

---

Published as a conference paper at ICLR 2023
E.5 PROOF OF COROLLARY 13
We can directly apply Theorem IT to the KNR model based on Proposition To to obtain the regret bound result. For better understanding of our framework, we illustrate the main features in the proof of Corollary 13 that are different from the proof of Theorem
To resolve the unboundedness issue, unfold the analysis of KNR case and event B analogous to the argument in $E.3 However, doing so would impose an additional /d, factor induced by estimating the f--norm of multivariate Gaussians. lieu to this, we present a sharper convergence analysis that incorporates KNR instance-specific structures. We recall the DEF of the KNR model:
Proof of Corollary [3
conclude a
(on, fu+1, gh. v) - Ungg(ssn an) 8h+1.
We first define auxilliary random variable
X²hh, f. = (41 fh+1, Ih. w))² (en I n1)²
= ||Un, 6h, ah) sh+ 112 ( oi) - sh 112
=(Unn. - Us) ()): (Uh.f ( sh ax) - 26
=I((Un.s -o d11 2 ((Un,) U (6 ai;), (/+1)-
By the boundedness of operator Un. f. Uj and uniform boundedness of @0 a), we obtain that af)ll S 4B2 Ba. The conditional distribution of ((Uh.f - ( af)),, d4+1) a zero-mean Gaussian with variance (uI) - (os,,, df2 S
By the tail bound of Gaussian distributions along with standard union bound, we know that with probability at least
1 --d. 6,
-()),s- ah) o S0
( (TH/8)
holds uniformly for all t E [7] and h E [M] Thus, we bound the absolute value of the auxillary variable X, by Xx| S Ro where R is positive and of order (Vlog(TH/5)) Taking expectation with respect to 8141, we have
Besta (Xc(h, 8h, on) |[(Uh.F UK)oss
On the other hand,
Exa+1
(x, 8h, an
= -Es
(1l(Unn. - (2) di)1l 2 ((Uns (sh ah), < sh, an
[I[Un, UN) at)11 + 4 (LUn, UN) o.)). ) " s/s as
= -Ba
EEN [ll(Un.s -
- (1) ||| + 4l -U)),, ? 88, un)
50 2 2 (N, vv)) 8h, anl)
By taking Z, (h, f. v) E E.,., (h, f,v) sh, anl with |Z, < 2Ro in Freedman's inequal-
ity F.I) in Lemma 33 we have for any satisfying 0 < 1 < शाेन almost surely, with probability at least 1 8:
Esn.r [Xihh, v) sh, an] + log(6
E4.0
1Ro21) Σ
1=1
1=1
Optimizing over we have
t Σ
8h, and log(ō-1) + R²O0 log(ō R²o2log(001) 10)(0-1))
Σ
2
0
Ro
E
(x,
(E.19)
17

---

Published as a conference paper at ICLR 2023
Following the same Freedman's inequality (Lemma 33) and p-covering argument as as in the proof of Theorem II with derivations detailed SF.I we have with probability 2 - and O (o² log [T (TH))()))))))) apT):
E [BRn f (n) all
Es sy ~ |l(Un.)" Un))((k, a& < 0(3).
1=1
1=1
Feasibility of f can be derived by taking the same auxilliary random variable and analyze on Ei= (i, f. v) as in the proof of Lemma 31
As explained in SE.3 we can apply Lemma 24 with w = / p 7.
G (f.g) v (a
an)1
and have
Σ
Esn - / [1(Un. - (s)) an)ll & o dimpe (F,G, (F.G.VI/T) V1/T) log (THN2(1/T)) -t 1=1
The rest of the proof follows by applying Bellman dominance, policy loss decomposition and calculating the FE dimension based on Gh, (f.g), which is shown in Lemma 30 We therefore obtain that
T
T
H
Σ (i'(s)) - Vi (s1)
G (f(f")
K
t=1
H
0
T dimpr GF (THNN((117)))))
K
δ H22 (dd.T
F PROOF OF TECHNICAL LEMMAS
We start with introducing the Freedman's 's inequality that are crucial in proving concentration properties our main results.
Lemma 33 (Freedman-Styyle Inequality, Agarwal et al. 2014). Consider an adapted sequence {Ze, Jt)..1...... that satisfies E [Z, J.-1] = and Z, S for any = 1.2.... T. Then for any 8 > 0 and r E [0, 1. it holds with probability at least 8 that
T E 2)m
log(8-1)
Σ
E [2
J-1]
(F.1)
"
Before proving our technical lemmas, we note that for notational simplicity we use the expectation Era-1 [- Sh, an] to denote the conditional expectation with respect the transition probability of the true model at The value of sh, a₁ is data dependent (might be s af or si, of depending on the function inside the expectation).
F. PROOF OF LRMMA A 23
Proof of Lemma 23 We recall that & has bounded norm in Definition 6 and assume that Ile,, fh+1, Ih. w)ll < R for Vh E [H], f', F,g G, v E throughout the paper. For
sequence of data D {rf, sh ahe of $1111112.... we first build an auxiliary random variable
defined for every (1, h, J.
[T] x [H]
x F V and consider
(h, f. v) = 1 (o,, fnt1, fn. )² 11 (o), fut1, T(f), 1)
where the randomness is due to uniformly sampling the data sequence Pr. We know that |X (h, fl R². Take conditional expectation of X, with respect to 8h, Oh, we have by definition that
E Ex,e1
[X, | 8h. anl
Eans [I]en, (oh, f1-1, Sha 2² ||e,, frot T() r)]l sn, on)
18

---

Published as a conference paper at ICLR 2023
Using the fact that ||a||2 ||b]12 (a - b, b) for arbitrary vectors a, and property i m Definition D we have
E (h, f. shi anl = (ln, (oh, fh+1, fn, En Jn+1, T(f): v), E (a, (0), fh+1, Sn, v) + f (ohs fn+1. T(f), v) Sh. an)
=I|Ban11 (en fa411 Sn, v) 8h, an 11?
On the other hand,
Esst1
(x, f: f))² 1 an
- Bo [[Ie,, (0h fht1, v) bn fa T()),,
I (o fn+1, fh. 2) + kn. ( F ((f),, u)1l sh. as]
< 4 [eat [en, (oh f fi. v) sh an 11
I 4 E (X, S: 8ks ap]
By taking Z: = (h, f. Ba (Xe(h, v)) 8h, an) with 17 < 2R in Freedman's inequal-
ity F.I in Lemma 33
we have for any satisfying O 28Z with probability at least - 6:
Var [X, f.v) 8/i anl + log(8-1)
2 0
Ban1a [f(h,,( 18, 8h, log(d-1)
0
log(d-)
< 0
Sh, an |RR B (K, f.
17
Taking 17
2R we have
28v Σ1
; (h. (s..0
Σ 2, 0
2R,
E. (,(hf. Sh. anl log(b-1) + 2R² log(ō-1)
(F.2)
Similarly by applying Freedman's 's inequality to Ein, that for any three-tuple (1, f), the following holds with probability at least 28:
i-1 Z, and combining with Eq.
F.2
we have
Σ 1=1
Z
0
2R.
Σ 1=1
Esn.. [K, f.v) sh, anl log(8-1) + 2R log(o
We note that in $3 we have that L admits p-covering of F,9, V. meaning that for any En (c, J.9. v) and a p > 0 there exists P and a four-tuple f.g. 0) F3 Fp x Op x V/ such that (x. en (1 u) S p, where Fj, Sp. V3 are 7-covers of F, G, respectively. This is denoted by (f', F. T. Lp. In definition of X,. is always taken f or function of T()). Then T is Lipschitz, as mostly the expectation operator, we omit the ğ in the tuple and use (f'F Cp to denote an element in the p-covering. By taking union bound over L,, we have with probability at least 28 that the following holds for any (f F. C.-
J,0
Esnra
Xi(h,Fo0
sh. an
50
2R,
Esnt1
(,(h,
8h, ah 2R2,
(F3)
19

---

Published as a conference paper at ICLR 2023
where
(h, f) (TNcc(m) log 5
[ fn+1, fn. 0)]l (on fu+1, T(f)s, T)1? and Further for any X; f", v), we choose the threc-tuple (f,
arg
min
ft (,,E,
- (h, f お) S p and by the p-covering argument, we arrive at
1-1 Σ
(h, f0))=
[1le (0h Phtz 8)| 1| (o,, Ph:1 7(f),, 8)1
i=1
( - 0(3 + Rtp),
| (oh fh of
(F4)
where (i) comes from constraint (4.1) of Algorithm with we derive the following
Combining
Benta [1 ft, sh, an 50(3+ + R21).
Applying the p-covering argument as before, we conclude
Eo (', 8h, an] - 0 + Rtp + R²1).
IIXX
VEV
Global optimality of the discriminator in (ii)oo of Dmmpsssion that oi is the optimal discriminator under any distribution or summation of Sh, an (and thus max is interchangeable with summation):
a ~ Bea+s (on th fh. shh an) 11?
E Besaarriil Beass (on, fi+1 Sho 8hy an 11? Vo V.
Thus, we have
max E Es w Bents [en (Oh, fh+11 Sh: v) sh. an] 1|2
VEV
E b 0% mx
Eants (en Sh+1 vx(")) 8h, an 11?
1=1
and also
E sn ror! Bougy (on, fhur (f((f)) sh, an.an] 1|?
max VEV
E Banas won
Bea+s [en, (On, fh+11, Shr v) sh; 0n 112
max VEV
E Es m E Eenes [Xi f)) sh an] s 50(8 Rtp + R²2).
(F.5)
We apply property in Definition 5 and conclude that
(G.,)
which finishes the proof of Lemma 23
20

---

Published as a conference paper at ICLR 2023
F.2 PROOF OF LEMMA 21
Proof of Lemuna 21 For a data set DA. to sh aj sh 2..... first build an auxillary random variable defined for every ht v) E [T] x [H] x F x V
(h, | (o), fh. fr. u) || (oh, Sh. u)|
By similar derivations as the proof of Lemma 23 we have
Beut1
[K, S/, an]
= (Bent1 [en, (oh, fh. fhs v) sns anl)
Bas+1
(h, 0))² sh: an
I ER [K, f. 8n, an]
Take Z, (h, 2, - (h,
u) Sh; and with Zel S 2R in Freedman's inequality (H.
in Lemma 33 Then via the same procedure as in the proof of Lemma [3 we have that for any four-tule (t, h S, v), the following holds with probability least 26:
Σ X,(h, f.
Σ
E Eanty (. 8h, an)
0
2R
E Ean [x,(h,fee) sn 1og(6-06611))) + 2R log(0-1))
Thus, have
Σ S(R lo)(
By the same p-covering argument in the proof of Lemma 23 there exists p-covering of such that we can take a union bound over L, and have - (,, s O (R², Rtp) where
HTN2(0))
1. log
Then for f", any f E F and any v E V, we can use the nearest three-tuple
8
T, in the p-covering and conclude that
Σ
[1 Sh, v)1 110- Sh, w)] = max
max LEV
NEV
1=1
This in sum finishes our proof of Lemma with O (R2 (Rpt).
F.3 PROOF OF LEMMA A 24
Proof of Lemma 24 The proof basically follows Appendix $C of Russo & Van Roy (2013) and Appendix $D of Jin et al. 2021). We first prove that for all & E (7).
I[G(ffk > c) (8/² dimprg
(F6)
Let m == EL gx)l > <), then there exists {si...., 8m which is subsequence of [t]
such that G(fs) 90, ....., G(fem: Iem)
We first show that for the sequence (f Smm C F, there exists j [m] such that fa, is
c-independent on at least J. [(m - 1)/ //dimpe(FF.. G. disjoint sequences in [fa....., fap-1
(Russo & Van Roy 2013). We will prove this by following procedure. Starting with singleton sequences B
Br, = (fez} and j L + For each j. if fa, is e-dependent on Bi.... Br, we already achieved our goal and the process stops. Otherwise, there exist i E [4] such that fay is e-dependent of B, and update B, = B, U (fe, Then we add increment j by and continue the process. By the definition of FE dimension, the cardinally of each set BI...., cannot larger than (imrE((F, G, e) at any point in this process. Therefore, by pigeonhole principle the process stops by step j I. I.din T.din G,e) +
21

---

Published as a conference paper at ICLR 2023
Therefore, we have proved that there exists j such that : > and faz is e-independent with at least L [(m - 1) dimp e) disjoint sequences in {fe....., fe,-1 J. For each of the sequences (fi..... f.J. by definition of the FE dimension in Definition we have that
(e(fx.99))) 2e.
(I:7)
Summing all of bounds
F.7 for L disjoint sequences together we have that
(G) 2 Le = [(m - dimpe dmm
(F.8)
1=1
The left hand side of (F8) can be upper bounded by 8 due the condition of lemma. Therefore, we which completes the proof of (F.6).
have proved that B [Im - 1)/ dimpg(F, G, -,
Now let d = dim g (F, G, w) and sort (i)........... by , Then we have that
in nonincreasing order, denoted
G(f) =
Σ ck k=1
Σ
1ex S
[w)+
+ Σ c lex w) S tw
1 w). c
(F99
For E [1] we want to give an upper bound for those ej (ex > w). Assume ex > w, then for any a such that ex > a 2 w, by (F.6., we have that
k <
(er > w) S (3/a² + 1) d)dime((FFF....o (G, (8/02 1)d,
which implies that a S vd3/(k-d d). Taking the limit a - cx we have that Ck S min v d3/(k - d), C}. Finally, we have that
dB
Σ c lee > w) s minfd,t) f) C+
Σ
d
idd+1
["' 2 -1/ S min(d,t] C CC22
s fd, C + dBB
(F.10)
Plugging
F.10 into
F.9 completes the proof.
F.4 PROOF OF LEMMA
32
We assume that ||0||>0 S B and treat B as an absolute constant (B in Sun et al. (2019) in the following derivations. For a dataset Dr = (rh she ag 1441h112...... T, we first build an auxillary random variable defined for every (t, f. u) [T] [ x F X
Proof of Lemma 32
(hh [(Ez- oh, ah oh.+))))++)))
(Rz-g-v(sh xh, 3) v(sho ah 1))
where the randomness lies the sampling of the dataset Dn. We know that [x(h, f)l S 4B2 almost surely. Take conditional expectation of X, with respect 8h, On, we have by definition that
Ba [Xi(h, f.v) sh, an] E.
(Ea ai, 3) v(sh an x)+1))
(Ezngr 00
(5/, ai, 3) 0(s an sh+ 2
st, an)
Using the fact that a bb2 = (aab)(a++ + b) and E u(s o 3) Ex v(s oi 3) is nonrandom given Sh, Oh, we have
E..11 Sk, | 8h, an]
= (B ar. 3) - Bi 1( (b/, ai, 3))
Esnii [Ban ah 3) + Ba v0 (1h, ah, 3) 20(sh at, sh41) 1)1 sh, arl
-BBzyo(sh af, 3) Egny 1 3)
22

---

Published as a conference paper at ICLR 2023
On the other hand,
Banss [
f vx) 8n, mn] s Bonts [( 3) R3 0(5 8)) 41]²
8b: an
16B2² (Egngu(s), ax1 3) Bx- 1/5//100000/ a 3))²
I 16B3 Bants (h, f, Sh, an]
By taking Ze f f. Eass1 [X, f. Sh an with [Z < 8B a.s. in Freedman's '
inequality (F.1) in Lemma 38 by the same procedure as in the proof of Lemmal 23 we have that for any four-tuple (t, h, f, v), the following holds with probability at least 20:
Σ (1, f,))
Σ Bens [X, sn. anl
0o 4B
Σ Ear [x, f.v) 8h, anl log(6-1) SB² 10g(8-1)
(F.11)
Let M, be p-cover of M and V p-cover of V. By taking union bound over all (t, h, f', v²) E [T] x [H] Mo x Vo, we have with probability least 25 that the following holds for any
f' E Mp, e' Vp.
Xilh, 8' 00)
Σ Ean [Xi(h, v', ) sh, anl
S 0 4B
Eant (x((h, 8n, anl 8B2,
(F.12
where i = log( M.llM ). Further for any f calculated at E [T] and any v E V, we choose f' arg minje. conclude
dist(F, f*) where dist is the distance measure M. d' -in,vv, (v', v) and
Xi(h, l',')
(Banrit'shh 3) - v'(sh ah, 1)) (Bons- osh, oh. v r/(s)//// ah, sh+ 1))
(Ez ah. u v'(sho ah x)+))) (Rzuge of (8/ ah. v (sh, a 1) )) O(BIp)
2 O(3 + Btp),
(F.13)
where (i) is due the constraint of Algorithm following
Combining F.12 with F.13 we derive the
Ea [Xi(h, 8h, an) s O(B Btp + B²t).
Note that f' is chosen the nearest model ft in the p-covering of M and for any u there exists nearest o' in the p-covering of V. we conclude
[X,(,, ()) 8h, on] S <0B + Btp + B²1).
max WEV
(ii) in Definition 6 in $ E.2 and we apply the global optimality of the discriminator in the proof of Lemma 23d obtains
Note we also have proved property
max E Ema.i VEV
[chh, 8h, an) 00 Btp + B².).
23

---

Published as a conference paper at ICLR 2023
Multiplying (E o 3) - Ez-g- 0(5 ai 3)]² by 1/|4|
_ taking expectation on sj
T², o ny and again using the global discriminator optimality, we arrive at
max E a vEV
(EEng, u(sh (h. eo 3)
1-1
I(a), = (shi)
(Eang u(s) o). - -E ush, 3))²
max VE
h No .0 (((A)
1/|A1
( (3 + Btp + B²()),
which concludes the proof.
F.5 PROOF OF LEMMA A 31
Proof of Lemma 37 For a dataset Dn = trh, ans oh+1 1. we first build an auxillary random variable defined for every (t, f. v) E [T] x [H] xF
(e, = (ES. (0 ah, 8) v(sh ah, x)+1))² (Ezng- x) - v(sh, an s/ 1)]
By Eq. F.I.p. with probability at least 25,
X, f.
Σ Bes [h, D) sh. anl
4B
Σ 1=1
Eos [X,(h, | sh, anl log(6-1) 8B2 log(8-1) 18g10((811)
Let M, be a p-cover of M and VP a p-cover of V. By taking a union bound over all (1, h. v*) E [T] [H] M2 x Vp we have with probability least 25 that the following holds for any f' E 2p.
Xilhi
Espi [X,(h, f,,') | sh, anl
50
4B
8h, an + 8B2, R Bant (Xi(h,,,,
where = log
HT HTIMP
Thus, we have
8
Σ x(.
Further for any f E F and any v E V, we choose I = arg min jem, dist(J, where dist is the distance measure on M, v' mingev, (v', v) and have
Σ (,() = Σ TBa 3) v(sh ar s/ 1))
Σ (Ez ah, - u(sh ah, sh+1)
1=1
< o B2: + Bpt).
Thus,
max BEV
Σ
ss aj, ((s
o(sh aj, s sh-1))² inf
(Bang u(hh oh af sh+ $
9E0
which concludes the proof.
24

---

Published as a conference paper at ICLR 2023
G PROOF FOR FUNCTIONAL ELUDER DIMENSION
In the following proposition, we prove that the Bellman eluder (BE) dimension (Jin et al. 2021 is special case of the FE dimension when (g f) == E (gh- - Tngh+1).
Proposition 34. For any hypothesis class F, taking coupling function G to be the union of {Gx : Fs Fh + R..=1..... with each (g. f) Bay,, (gh Thgh+1))
dimpg (F, G, e) v dimpe (F, e).
Proof of Proposition 34 By definition of the functional eluder dimension, dF G) max dimpr (F, GR.e),
be(m]
where dimpa(F, G is the length of the longest sequence satisfying for every E [n], V E (Gt, I é' and (9t, > Bringing in Gn(9, f) == B y (gh - Thgnn-))
we have fi,...; fu is also the longest sequence that satisfies for some 91 .1...., In that
Σ B (gen - Ththatti) sC, and E (gt. Thgeat1)l 6
Thus, dimpo( ((I TT..F, 1I,,)) 6) 2
Taking maximum over h E [H]. we have
dJmmr(FF (J, max dimpr (F,Gr; S max dimpe((T TT)FF I, 6) = dimpreFF IT,,),
k((m)
ke(l]]
which concludes our proof.
Combining Proposition 34 with Proposition 29 in Jin et al. (2021). it is straightforward to conclude that FE dimension is smaller than the effective dimension. In particular, Proposition 33 says dimpg is controlled by dimpa, Proposition 29 in Jin al. (2021) says dimpe is controlled by the effective dimension dimefr, therefore low effective dimension would imply ABC with low FE dimension.
In the following paragraphs and Proposition 35 we prove this conclusion from sketch to grant a better understanding of the FE dimension.
The effective dimension (Jin al., 2021) (or equivalently, critical information gain (Du al. 2021
(xn(X,, e) of a set X' is defined as the smallest interger n >> 0 such that
1 n
sup Rn EX
log det
I+
Σ F.
Remark 5.2 in Du et al. 2021 showed that for finite dimensional setting with X' S Red and ||>||| S B, den(X',) e) = (d).. Moreover, the effective dimension can be small even for infinite dimensional RKHS case.
In the next proposition, prove that when the coupling function exhibits bilinear structure G(f.g) X()) with feature space X (X(g) E H g F} and [[X(g)) vB, the functional eluder dimension in Definition always less than the effective dimesion of X.
Proposition 35. For any hypothesis class and coupling function G(., F expressed in bilinear form (J), X(g)) H. we have
that can be
dimpa (F, F,G.e) S der (x,c/VB).
The proof basically follows the proof of Proposition 29 in Jin et al. 1 with modifications specified for the functional eluder dimension. Given a hypothesis class J and
Proof of Proposition 35
coupling function G(.,)) F x F R. Suppose there exists c'-iddepenent sequence fi, Jn E F such that there exist 91 In F.
Σ (G(g. se,
t [n].
(G.1)
(G),,
E [n].
25

---

Published as a conference paper at ICLR 2023
When G(f.9) = (W)))x((g)) the above becomes
((f))) sc,
E [n].
(G.2)
(W))), ((E)) >6
L [n].
Defining Σ, EE ((A)())) + eh I. we have by Eq.
G.2 that [[W(,,,, S V26'.
Furthermore,
é <I((W()) & (w)ll -1 S V2e (
Thus, we have [x(()))) 2 & for any & [n)]. By applying the log-determinant argument, we have
det (2n+1) ((ntt)))) log det (eel (Ex)
B
Σ log
1 + [ log
1+
The above equality implies
))
B 1+ 222 Σ
S min Ire 2 S exp
log det
- 1.
(G.3)
2
Taking n = der(d' e/ /VVBB yields
exp ( 1 det
_
n B
B n
sup
leg
I
SE
72
2. Ex
2
which contradicts with the inequality
G.3 and concludes our proof.
We now provide the detailed proofs of Lemmas 27
29
and
30
G.1 PROOF OF LEMMA 27
Proof of Lemma 27 Taking
Gh.f-(f.g) = (0h.g 0 Emn.nsntT
(i(sh, an) + an
an, o'
where (f) Sn. 8% (g) E Esn.ay woy (s,, an) +E o(sh, Oh, V') in
Proposition 35 Properties the effective dimension yield that the FE dimension of the linear mixture MDP model is < (d).
G.2 PROOF OF LEMMA
29
Proof of Lemma 29 Taking Gr.r-(f.g) = ()())) in Proposition 35| and properties of the effective dimension yields the conclusion that the FE dimension of low Witness rank MDP model is ((W)).
G.3 PROOF OF LEMMA 30
We first introduce two auxillary lemmas:
Lemma 36. Let random variable x; E Rdd and El S B², Then we have that
1
log det (I
1 n-
Σ
E B|
dl dlog
1 nB²
n
n
Proof. We first have
trace
I
1 Σ
B[xa,,]]
71 1)
d+
Bl|la111 11 S d
nB²
A t=0
1=0
26

---

Published as a conference paper at ICLR 2023
Therefore, using the Determinant-Trast inequality, get the first result,
trace [ + xx4 Ei=o B[zee]])
log det x x E(0 - dlog
I d (1+
nB² d1
d
Dividing from the both side of the inequality completes the proof.
The following lemma is a variant of the well-known Elliptical Potential Lemma DDni et al. 2008 Srinivas al. 2009 Abbasi- Yadkori et al., 2011 Agarwal et al.. 2020ap.
Lemma 37 (Randomized elliptical potential), Consider sequence of random vectors (zo...., Tr-1) 1). Let A > 0 and No Al and M1 =go Ex= B[xxx]] we have that
det(Er)
min log (E[T]
1+
E
log
T
det(A/)
Proof. By definition of Σx we have that
log det (E++1) = log det(E,) + log det(I D,
1/21/2 E ((E,) 1/3).
1/22
(G.4)
Denote A, Mx 1/2 2|2,2 [(2,) with eigenvalue X1 , da
0, we have that
det(1 + A²) = II (As + 1121+ Σ x = trace(1 + Ad) = 1 + El E|
(G.5)
Plugging G.5 into G.4 gives that
log 2 log det (E,) + log(1 + El| .) 2 log det(E,) + min log
1 E x
tE(2)
Taking telescope from 0 to t T - completes the proof.
Proof of Lemma 30 Given hypothesis class F and coupling function G(:))) :F R. Let n to be defined as follows,
n = min {n E N: n 2 edg log(1 + 4nd, R² /dd())
Then we have that n = Ö(ds). We will prove dim, sF, G,e) < n by contradiction. Suppose that
(im G, c) > n, there exists an c' c'-independent (where c' c) sequence fI...., E F such that there exist .1.....90 In F,
Σ GGg.. f()) se,
te [n].
(G.6)
G f&)l >
LE [m].
Recall that the ABC function of KNR model is defiend as,
Gh,f (f.9) V(vee ((Un.) U2) (Uh, Uz)), vec (B.n, ((sn an (o)(( T))
E.n.aN [Uh, UN) an..
Therefore, condition
G. can be reduced to
Ess Nxy, |l(Un. U2)0( - an)l <é, t [n],
(G.7)
UT)
LE [n].
27

---

Published as a conference paper at ICLR 2023
Denote J. [dg] and J E [d,] to be the rows of Un.g. and Uz. Taking square over both side of the inequalities in (G.7) gives that
d.
Ba My [Uhag (k,))( un)] Se
l LE [m],
(G.8)
d
Σ
E as Na [Uh,ge UNn))0(sh an)] E?
E [m].
i=1
Define Σ, = Ei= E sn n (h)(s,) (c2/4d, I. Then by G.8 we have
that
(Uh.ow - D
Bsn nn (1Uhiel (hs)) (6 /4d,
Σ Ben Ben Un.se. 12
E Bss. N,, [UUnaaa--hh an)s + (c2/Ad,R²)) [2d, max
| 2d, max 1 13]
26
where the first equality is by the Gauchy-Schwarte inequality and the last inequality is by 1l S on lla S R, 11 I ||2g|12 I R. Furthermore we have that
d,
<
B Benaa N [[ - (N5) a=
j=1
d2
E, E [(hniies - 1 /////// x, 1/2 ((sh.an)?
j=1
d.
E B [1(Uh. Uni / Esn. ||, 1/2 1/2_1//(ssn0000 as)h
ax)
j=1
=E,, E
Er, (/2 313 Σ IlUnn.ge. MR
where the last inequality is by the Cauchy-Sehine Schwarz inequality for random variables. Thus, we have
that E Ea ~ 15= 1/2 (88.
11)11 2 1/2 for all & E [n]] By applying Lemma 37 we have that
min log(1 + Ess. EE, 1/2 ps 12) [E|n]
5 log /det(in+1)) = log det (I+ (E)
4d, n e
Σ
Enn (d(sn an)o(sn, [T) TI).
The above equation further implies that
log det (1
Rd e2
Esn, Ben way (dss,, an) an) an)
[ + E.n. 11,, 1/2 (ss an)11) > log(3/2).
min log [)
On the other hand, Lemma 36 implics that
Egg an ~x (o(sn, an an) an) < log (1+
And, dge?
1 log det (1 Rd e²
5 -1
n
This leads to contradiction because d' 2 and log(3/2) dF G,e) O(dg).
e1_ We complete the proof of
28

---

Published as a conference paper at ICLR 2023
0.7
Average Cumulative Reward
0.6
0.5
0.4
0.3
0.2
Optimal
0.1
Random
OPERA
0.0
2000
4000
6000
8000
10000
Number of Episodes
Figure 2: Cumulative regret comparison in the first 10000 episodes of different RL algorithms (i.e.,
OPERA, Optimal Policy, Random Policy). Results are averaged over 10 runs.
H EXPERIMENT
In this section, we earry out experiments to evaluate the empirical performance of our algorithm OPERA for linear mixture MDPs (Algorithm 2). In this experiment, we construct an MDP M with dimension = 3 and episode length И = 5. The state space consists of H + different states 21...., -2 and the action space A {-1, 1] consists of 2d different actions. For each step [H] and episode & E [K]. . we assume that the reward function r(s, a) known (so no need to introduce 1 in Section E.Tp. In particular, for all s h H, the reward function (s a) = if and only if 8 = 2 and rx(s, a) 0 otherwise. For each step It [H] and corresponding transition probability function Ph. # and 2 absorbing states. For other states Fz (1 < h < H), the transition probability satisfies that
Pa PA Ta a) 0.95 (0.01 1,-1, a),
(4 Th, a) 0.05 (0.01 1,-1.a),
where each 1ø-1 is (d - 1) dimeennsil vector of all ones, a E A is also a (d 11) dimeensiiaa vector. Then we have that P 24. a) (0%, (( a, 24)) where 0% [0.01 14-1, 1], and p(xw, nn) are as follows,
(aw,,,, [-a, 0.95] if < h < H and N/ h +
blar,, [a, 0.05 1 < h < H and h' = H + 2.
6(IM,, an) = 10.-1.1] if = h = H +1.
d(TN,, a, .h) = [0 -
o(aN, a, .T) = O.,, otherwise.
Here 0a-1 is (d - -)ddimensional vector of all zeros. We compare our algorithm OPERA with the following baselines: Optimal (optimal policy) and Random (uniformly random policy which
chooses actions uniformly from .A). For numerical stability, we add AI to Σ(0 with À and
CVX (Diamond & Boyd 2016 Agrawal et al. 2018) to approximately solve (E.3 when
implement Algorithm [ The cumulative rewards of different algorithms averaged over 10 runs for that OPERA performs much better than the random policy and can converge to the optimal policy after 10000 episodes.
the first 10000 episodes plotted in Figure 2 We
29


Reviews:
[{"review_id": "Z56GDBASRq2", "reviewer": "Reviewer_TL1B", "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": "This paper presents a unified perspective and analysis for almost all of the existing sample efficient RL algorithms.\nThis notion is based on Admissible Bellman Characterisation, and provides an a bound in terms of the functional eluder dimension.\nTogether with this analysis, the authors present an algorithm OPERA, which really is a general form of optimism in the face of uncertainty.\nWhile this algorithm is not necessarily practical (it may not be computable) it provides some general flavour of the types of results that might be possible.", "summary_of_the_review": "This paper collates many existing results in the OFU-RL literature with function approximation.\nBy revisiting the functional eluder dimension under the ABC condition, they show that OPERA algorithm provides a more unified perspective on statistically efficient reinforcement learning.", "strength_and_weaknesses": "There are several things to like about the paper:\n- The writing and paper structure are good, and give a good overview of the many lines of research in this area.\n- The general analysis and flavour of the results are clear and concise. Take, for example, Theorem 12 as an example. This clearly highlights the main dependencies in the regret bound.\n- The ABC class supersedes the many different notions of complexity, as outlined well in Figure 1.\n\nThere may be a few places where the paper falls down in terms of top-level impact:\n- First, it feels like this work is really mostly consolidating/summarising threads of research that have been going on for a while in the eluder-dimension++ pieces of RL with generalization. This is valuable, but feels more \"cleaning up\" than forging new course.\n- The OPERA algorithm is really more of a high-level principle than a practical algorithm. Thinking about how we can make scalable/practical algorithms is probably not just an \"unnecessary complication\" but I agree it is OK to leave this to future work in this conference paper.\n- There is a *lot* of material to go through in reviewing this paper... so many theorems and definitions. This is great for clarity, since it allows a motivated reader to go through piece by piece, but there is a slight concern with *so many* pieces that it takes away from the \"main thing\".", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Cmutf92NDLO", "reviewer": "Reviewer_JjVG", "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": "This paper proposes a unified framework which encompasses both model-based and model-free MDP algorithms. The framework, Admissible Bellman Characterization, covers a wide range of MDPs. The key idea is to use decomposable estimation function which has decomposable sturctural properties for optimization-based exploration (which is also their algorithm). To measure the complexity of model class, they use the functional eluder dimension. ", "summary_of_the_review": "It is good paper, written quite well. It improves on the existing frameworks which could not preserve the sample complexity bounds. ", "strength_and_weaknesses": "Strength:\n1. The authors proposed a unified framework which covers a large section of MDPs, both model-free and model-based\n2. The framework maintains the best-known sample complexity results for special instances.\n3. They also propose a novel algorithm, OPtimization-based ExploRation with Approximation (OPERA), which maximizes the value function constrained in a small confidence region around the model minimizing the estimation function.\n\nWeakness:\nAlthough this framework improves the sample bounds, it is as generic as the existing framework, meaning the algorithms which were not covered in previous framework (such as those with state-action aggregation) are also not covered here.", "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": "A_ydt3OtuR", "reviewer": "Reviewer_2LkA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 proposes a general framework which unifies problem complexity measures with function approximation in the model-based and model-free lens for reinforcement learning.  In particular, the authors propose Admissible Bellman Characterization (ABC) class that subsumes many prior models for problem complexity in the prior literature.  The authors also provide a new algorithm, OPERA, achieving regret bounds that match or improve over the prior literature.\n\nMore concretely, the authors consider an MDP $(S,A,r,P,H)$ where $S$ is state space, $A$ the action space, $r$ the reward function and $P$ the global transition distribution, and $H$ the horizon.  Given access to a function class (representing either the transition kernel in model-based or the $Q$ function for model-free) typical algorithms come up with complexity measures of the function class and design algorithms with sublinear regret with respect to that complexity measure.  The main point of this paper is to present a unified complexity measure framework that includes all model-free and model-based RL classes, while simultaneously allowing a simple algorithm with sample efficiency guarantees.  To this lens, the authors make two several frameworks:\n1. The authors propose a new framework called ABC that covers structural assumptions previously studied in model-free and model-based RL.  To some extent, the framework can be thought of as extending the Eluder Dimension to include (a) arbitrary coupling functions for measuring the error, (b) a discriminator function which characterizes the interaction between different hypotheses\n2. Under the ABC framework the authors design an algorithm OPERA based on maximizing value function in a confidence region around model estimation - showing that the framework has sublinear regret guarantees.\n\n## Questions\n- What is the role of $\\pi_{est}$ on page 8?\n\n## Minor Comments\n- FLAMBE is used to refer to both the model and the algorithm\n- Value terms are swapped in regret definition on page 3\n- Definition of $\\pi_f(s)$ on bottom of page 3 has typo in it", "summary_of_the_review": "The paper provides strong theoretical contributions for developing a framework which unifies model-based and model-free RL via their Admissible Bellman Characterization formulation - which subsumes most models in the literature for tractable RL with function approximation.  The paper is extremely well written, although very technical, but highlights the main differences and contributions between the paper and the related work. However, the paper offers no empirical results (or discussion on computational tractability of their proposed algorithm), although standard in the RL with function approximation literature.\n\n", "strength_and_weaknesses": "## Strengths\n\n1. The authors provide a novel problem complexity measure which subsumes several others which are studied in the literature.\n2. The authors provide a simple algorithmic framework based on optimistic principle over uncertainty sets which achieves strong regret performance.\n\n## Weaknesses\n\n1. The authors include no discussion on the computational complexity of the algorithm.\n2. There are no theoretical matching lower bounds (or discussion along this point)\n3. The authors provide no empirical results of their algorithm's performance\n4. The theoretical contributions and algorithm design seems like a straightforward extension of prior mechanisms with general function approximation techniques.  The novel algorithmic contributions could be highlighted more in the writing.\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": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%