Bellman Residual Orthogonalization for Offline Reinforcement Learning
Authors: Andrea Zanette
Martin J. Wainwright
Venue: NeurIPS 2022 Accept (2022)
Keywords: offline RL
weight function
confidence intervals
policy optimization

Abstract: We propose and analyze a reinforcement learning principle that
approximates the Bellman equations by enforcing their validity only
along a user-defined space of test functions.  Focusing on
applications to model-free offline RL with function approximation, we
exploit this principle to derive confidence intervals for off-policy
evaluation, as well as to optimize over policies within a prescribed
policy class.  We prove an oracle inequality on our policy
optimization procedure in terms of a trade-off between the value and
uncertainty of an arbitrary comparator policy.  Different choices of
test function spaces allow us to tackle different problems within a
common framework.  We characterize the loss of efficiency in moving
from on-policy to off-policy data using our procedures, and establish
connections to concentrability coefficients studied in past work.  We
examine in depth the implementation of our methods with linear
function approximation, and provide theoretical guarantees with
polynomial-time implementations even when Bellman closure does not
hold.

Bellman Residual Orthogonalization for Offline Reinforcement Learning
Andrea Zanette
Department of Computer Sciences and Electrical Engineering University of California, Berkeley zanettebberkeley edu
Martin J. Wainwright
Department of Electrical Engineering and Computer Sciences, Department of Mathematics, Massachusetts Institute of Technology. and
Department of Computer Sciences and Electrical Engineering,
Department of Statistics, University of California, Berkeley wainvrigwork0gmai. com
Abstract
We propose and analyze a reinforcement learning principle that approximates the Bellman equations by enforcing their validity only along an user-defined space of test functions. Focusing on applications to model-free offline RI. with function approximation, exploit this principle to derive confidence intervals for off-policy evaluation, as well as to optimize over policies within a prescribed policy class. We prove oracle inequality on policy optimization procedure in terms of a trade-off between the value and uncertainty of an arbitrary comparator policy. Different choices of test function spaces allow us to tackle different problems within a common framework. We characterize the loss of efficiency moving from on on-policy off-policy data using procedures, and establish connections to concentrability coefficients studied in past work. We examine in depth the implementation of methods with linear function approximation, and provide theoretical guarantees with polynomial-time implementations even when Bellman closure does not hold.
Introduction
Markov decision processes (MDP) provide general framework for optimal decision-maie making in sequential settings (c.g., [Put94] Ber95al Ber95b)). Reinforcement learning refers to a general class of procedures for estimating near-optimal policies based data from unknown MDP (e.g., [BT96 (B18)) Different classes of problems can be distinguished depending on our access to the data-generating mechanism. Many modern applications of RL involve learning based pre-collected or offline dataset. Moreover, the state-action spaces are often sufficiently complex that becomes necessary to implement function approximation. In this paper, focus model-free offline reinforcement learning (RL) with function approximation, where prior knowledge about the MDP is encoded via the value function. In this setting, we focus two fundamental problems: (1) offline policy evaluation-namely, the task of accurately predicting the value of target policy; and (2) offline policy optimization, which the task of finding gigh-performance policy.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

There are various broad classes of approaches to off- offi-p evaluation, including importance sam- pling [Pee00] T 6 LLIZI8. as well regression- based methods [LP03 MS03 CJ19]. Many methods for offline policy optimization build on these techniques, with line of recent pa- pers including the addition of pessimism (YW221 XCJ+21 ZWB21
We provide a more detailed
summary of the literature in Appendix
A.3
dinripleeddiffeeettt from importance sampling or regression-based methods-to learn from an offline dataset. It belongs to the class of weight learning algorithms, which leverage an auxiliary function class to either encode the marginalized importance weights of the target policy [LTZI88 [X22b),, or estimates of the Bellman errors [ASM08 CJ19 XJ20b). Some work has considered kernel classes [FRTL20] or other weight classes to construct off-policy estimators [UH]20] as well as confidence intervals at the population level JH20 However, these works do not examine depth the statistical aspects of the problem, nor elaborate upon the design of the weight function classes
In contrast, this work investigates different model-free
The The last two considerations are essential to obtaining data-dependent procedures accompanied by rigorous guarantees, and to provide guidance on the choice of weight class, which are key contributions of this paper.
For space reasons, we motivate our approach in the idealized case where the Bellman operator is known in Appendix A..] and compare with the weight learning literature at the population level in Appendix AA. Let us summarize our main contributions in the following three paragraphs. Conceptual contributions: Our paper makes two novel contributions of conceptual nature:
1. We propose a method, based on approximate empirical orthogonalization of the Bellman residual along test functions, to construct confidence intervals and perform policy optimization.
2. We propose sample-based approximation of such principle, based on self-normalization and regularization, and obtain general guarantees for parametric as well as non-parametric problems.
The construction of the estimator, its statistical analysis, and the concrete consequences (described in the next paragraph) are the major distinctions with respect to past work on weight learning methods [UHJ20, [H20]. Our analysis highlights the statistical trade-off's in the choice of the test functions. (See Appendix A.2 for comparison with past work at the population level.)
Domain-specific results: order to illustrate the broad effectiveness and applicability of our general method and analysis, we consider several domains of interest. We show how to recover various results from past work to obtain novel ones by making appropriate choices of the test functions and invoking our main result. Among these consequences, we discuss the following:
1. When marginalized importance weights are available, they can be used as test class. In this case we recover a similar results as the paper [XJ20b]; however, here we only require concentrability with respect to a comparator policy instead of over all policies the class.
2. When some knowledge of the Bellman error class is available, it can be used as test class. Similar results have appeared previously either with stronger concentrability (CJ19 or in the special case of Bellman closure 21)
3. We provide test class that projects the Bellman residual along the error space of the Q class. The resulting procedure is as an extension of the LSTD algorithm [BB% to non-linear spaces, which makes natural approach if no Nomain-speciff knowledge is available. A related result is the lower bound by [FKSLX21, which proves that without Bellman closure learning is hard even with small density ratios. In contrast, our work shows that learning is still possible even with large density ratios.
Finally, our procedure inherits some form of "multiple robustness". For example, the two test classes corresponding to Bellman completeness and marginalized importance weights can be used together, and guarantees will obtained if either Bellman completeness holds or the importance weights are correct. We examine this issue in Section 4.4
Linear setting: We examine in depth an application to the linear setting, where we propose the first computationally tractable policy optimization procedure without assuming Bellman completeness.
'For instance, the paper 2RTL20 only shows validity of ther intervals, not a performance bound: on the other hand, the paper [H20 gives analyses at the population level, and so does not address the alignment of weight functions with respect to the dataset in the construction of the empirical estimator, which we do via self normalizaoioo and regularization. This precludes obtaining the same type of guarantees that present here.

---

The closest result here is given in the paper [ZWB2I]. which holds under Bellman closure. Our procedure can be thought of making use of LSTD-type estimates so establish confidence intervals for the projected Bellman equations, and then using an iterative scheme for policy improvement.
2 Background and set-up
We begin with some notation used throughout the paper. For a given probability distribution p over a space X, we define the (ip))inne product and semi-norm as (f1, f2) = [f]fff2), and Ilfill f1fifffppp The identity function that returns one for every input is denoted by 1. We frequently use notation such as c, c', C, C1, 02 etc. to denote constants that can take on different values in different sections of the paper.
2.1 Markoy decision processes and Bellman errors
We focus on Soimite-horizon discounted Markov decision processes Put94
SB18 with discount factor 7 E [0, 1). state space 8, and an action set A. For each state-action pair (s, a), there is a reward distribution R(s, a) supported in [0, 1] with mean r(s, a), and a transition IP(- 88 a).
BT%
A (stationary) stochastic policy maps states to actions. For given policy, its Q-function is the discounted sum of future rewards based on starting from the pair (s,a). and then following the policy ı in all future time steps Q (s. a) = r(s, a) + Ex=0 > 1 As).A)) (So. Ao) = a)], where the expectation is taken over trajectories with AA T.. S,), and Sh+1 P(-
Sh, An) for = 1, 2....... We also use (=, = Ea (=, A) and define the Bellman evaluation operator as (T"Q) a) = r(s, a) + Es+=P(]s,,) ((S+ .). The value function satisfies (=( = Q" 7). In our analysis, we assume that policies have action-valle functions that satisfy the uniform bound (u)( 12" a)l s 1. We also interested in approximating optimal poli- cies, whose value and aetion-valus functions are defined as (*(s) = V (s) = sup, V*(s) (s) and @*(s,a)= Q" (x,a) = sup, Q" (s.a).
We assume that the starting state Su is drawn according to Vstatt and study V E V (So))-
The discounted occupancy measure associated with policy æ is defined as (s, a) (1
7) En P An) (s, a)). We adopt the shorthand notation E, for expectations over
dr. For any functions f.g x A R. we make frequent use of the shorthands E, def ((s.a)=d, [[(S,))) and (J, g). def Eys.Ayyd, [S(S, A) g(S, A)] Note moreover that we have (1. f) Ex [f] where 1 denotes the identity function.
For a given Q-function and policy æ, let us define the temporal difference error (or TD error) associated with the sample (s,a, a, r, st) and the Bellman error (8,a)
(8 (=) def Q(s, a) - - -Q .m),
())))(s,a) def Q(s, r(s,a) - 7B, (F..) Q(s xx).
The TD error is random variable function of z, while the Bellman error its conditional expectation with respect to the immediate reward and successor state at (s, a). Many of our bounds involve the quantity E, Q = Bys,Ay_d, [ (S)
Finally, introduce the data generation mechanism. A more general sampling model is described in Appendix B
Assumption (I.i.d. dataset). An i.i.d. dataset is collection D = ((s, 04 T'y 8 .,)) such that for each i 1,..., .....,, n have (st, 02, 0,) i and conditioned on (8t, ai o.), we observe noisy reward = r(s;, 0;) + my with E(na Fi] 0, |rsl < 1 and the next state st ~ a())
2.2 Function Spaces and Weak Representation
Our methods involve three different types of function spaces, corresponding to policies, action- value functions, and test functions. A test function f is a mapping (s, a, o) + f(x, a, o) such that sup (f(s a, o)| < 1, where is an optional identifier containing side information. Our methodology involves the following three function classes:
policy class II that contains all policies of interest (for evaluation or optimization);
for each म, the predictor class "a of action-value functions Q that we permit; and
for each the test function class F that to enforce the Bellman residual constraints.
3

---

We use the shorthands Q = Unen Q" and F = = We assume weak realizabiliry:
Assumption 2 (Weak Realizability). For a given policy n, the predictor class Q is weakly realizable with respect to the test space 9 and the measure μ if there exists predictor Q Q" such that
(f. Q = for all f f E and
(1, Q+)x 0.
(I)
The first condition requires the predictor satisfy the Bellman equations on average. The second condition amounts to requiring that the predictor returns the value of π at the start distribution: using Lemma stated in the sequel, have
ES (S. V = Egsesn 12 - (5)
1 E, Q. F
1- (1, -
(1, 0.
1-7
1-7
This weak notion should be contrasted with strong realizability, which requires function Q" E Q that satisfies the Bellman equation in all state state-action pairs.
A stronger assumption that we sometime use is Bellman closure, which requires that (*(Q) Q" for all Q E Q". The corresponding 'weak' version is given in Appendix A..4
3 Policy Estimates via the Weak Bellman Equations
In this section, we introduce our high-level approach, first the population level and then in terms of regularizeddnormalize sample-based approximations.
3.1 Weak Bellman equations, empirical approximations and confidence intervals
We begin by noting that the predictor Q" satisfies the Bellman equations everywhere in the state- action space, i.e., 8 = 0. However, if our dataset is "small" relative to the complexity of (functions) on the state-action space, then it is unrealistic to enforce such a stringent condition. Instead, the idea is control the Bellman error in weighted-average sense, where the weights given by a set of test functions. At the idealized population level (corresponding to an infinite sample size), we consider predictors that satisfy the conditions
(S,B*) = 0, for all E g"
where f" a user-defined set of test functions. The two main challenges here are how to use data to enforce approximate version of such constraints (along with rigorous data-dependent guarantees), and how to design the test function space. We begin with the former challenge.
Construction of the empirical set: Given a dataset D = {(si, di, ri, 8 oz) ))) we can approxi- mate the Bellman errors by a linear combination of the temporal difference enrors:
/ [(s, a) -
s(si, as) [Q(s;, - r; - ;))
(3)
=B (s.aa
= a(st,,,,
Note that the approximation (3) corresponds to a weighted linear combination of temporal differences. Written more compactly in inner product notation, equation (3) reads (f, (², = (f.8"Q),, n. where (s.a.rist (e)e((f)((s)) a, r,r,st,,)
(f.g)n= = - E(
In general, the action value function Q" does not satisfy (f, (=Q²), = 0 because the empirical approximation (3) involves sampling error. For these reasons, in order (approximately) identify Q", we impose only inequalities. Given a class of test functions 9", a radius parameter p 2 0 and regularization parameter À 2 0, we define the set
(;;
def
I such that
1f.o0mmmll VIA +X
S
VE for all f E Fm
(4)
When the choices of (p, A) are clear from the context, we adopt the shorthand @: (3 or Gg when the function class 3r is also clear. If gx and Q have finite cardinality, p In [ Q In 1/8. where 5 a prescribed failure probability.
Our definition of the empirical constraint set has two key components: first, the division by / f + À corresponds to form of self-normalization, whereas the addition of X corresponds to

---

form of regularization. Seff-normalization is needed so that the constraints remain suitably scale- invariant. More importantly- in conjunction with the regularization that have poor coverage under the dataset do not have major effects on the solution. In particular, the empirical norm Il in the seff-normalization measures how well the given test function covered by the dataset. Any test function with poor coverage (i.e., Il = 0) will not yield useful information, and the regularization counteracts its influence. In our guarantees, the choices of À and o are critical; as shown in our theory, typically have À = p/n, where p scales with the metric entropy of the predictor, test and policy spaces. Disregarding p. the right-hand side of the constraint decays 1/ v nn, that the constraints enforced more tightly the sample size increases.
ensures that test functions
Confidence bounds and policy optimization: First, for any fixed policy π, we can use the feasi- bility set 4 to compute the lower and upper estimates
(5) corresponding to estimates of the minimum and maximum value that the policy и can take at the initial distribution. The family of lower estimates can be used to perform policy optimization over the class II, in particular by solving the max-min problem
V
def
min
Es-vam (QS,, m)}, and
V def max
max (p.;()))::7)
ES-war (Q(S,))
max T TEll
min ES [)S. QEêT
or equivalently
max V xEIl
Form of guarantees Let us now specify and discuss the types guarantees that we establish for our estimators 5 and (6. All of our theoretical guarantees involve j--baeed counterpart C, of the data-dependent set Cn More precisely, define the population set
(4:T daf
QEET such that
K(BTT) VIVII=+
S
10
for all /E
where (f. g)2 def ff d) is the inner product induced by a distribution over (s, a). As before, we use the shorthand notation е, when the underlying arguments are clear from context. Moreover, in the sequel, generally ignore the constant 4 in the definition (7) by assuming that p is rescaled appropriately e.g. that we use factor of 1 in defining the empirical set.
It should be noted that in contrast to the set CT, the set C, is non-random and it is defined in terms of the distribution a and the input space (II, I, Q). relaxes the orthogonality constraints in the weak Bellman formulation ( Our guarantees for off-policy confidence intervals take the following form:
Coverage guarantee:
min
Va
V
(8a)
Width bound:
max
V
P
V
EE
(8b)
I-
QEE
Turning to policy optimization, let स be solution the max-min criterion (6) Then we prove result of the following type:
Oracle inequality:
V
max
v
ETB Q QEeR())
max
(9)
Evalustion uncortointy
Note that this result guarantees that the estimator competes against an oracle that can search over all policies, and select one based on the optimal trade-off between its value and evaluation uncertainty.
3.2 High-probable brobabprobbbilityy guarantees
In this section, we present some high- pigbbbbrbbbblitty guarantees. So as to facilitate understanding under space constraints, we state here results under simplifying assumptions: (a) the dataset originates from fixed distribution, and (b) the classes F and Q have finite cardinality. We emphasize that Appendix B provides far more general version of this result, with an extremely flexible sampling model, and involving metric entropies of parametric or non parrmmrmer function classes.
"See Section B for precise definition of the relevant μ for fairly general sampling model.
5

---

Theorem 1 (Guarantees for finite classes), Consider triple (II,3, Q) that is weakly Bellman realizable (Assumption 2 an ii.d. dataset (Assumption) } and the choices of log((5([MT12)
log(1/6)} and X = p. n. for some constants e,c'. Then w.p. at least 1 - 8:
Policy evaluation: For any satisfying the coverage (8a) and width bounds (8b)
11, the estimates (V Vinxs) specify a confidence interval
Policy optimization: Any max-min policy (6) ग satisfies the oracle inequality 9
4
Concentrability Coefficients and Test Spaces
In this section, develop connections concentrability coefficients that have been used in past work, and discuss various choices of the test class. Like the predictor class Q", the test class 9"' encodes domain knowledge, and thus its choice is delicate. Different from the predictor class, the test class does not require a 'realizability' condition. As general principle, the test functions should be chosen orthogonal
possible with respect to the Bellman residual, so as enable rapid progress towards the solution; at the same time, they should be sufficiently "aligned" with the dataset, meaning that I|I or its empirical counterpart || should be large. Given a test class, each additional test function posits a new constraint which helps identify the correct predictor; at the same time, it increases the metric entropy (parameter p), which makes each individual constraints more loose. In summary, there are trade-offs to be made in the selection of the test class F, much like Q.
In order assess the statistical cost that we pay for off off-policy data, it is natural to define the off-policy cost coefficient (OPC) as
def max QEer
2T2 (1+ x)
(1,
K (T P; A)
max QEeR
(10)
With this notation, off-policy width bound (8b) can be re-expressed
2
(Ila)
min
while the oracle inequality 9 for policy optimization can be re-expressed in the form
max TEll
V - vI+X V P
(11b)
Since ~ p/n, the factor / + can be bounded by constant the typical case n p. We now offer concrete examples of the OPC, while deferring further examples to Appendix A.5
4.1 Likelihood ratios
Our broader goal is to obtain small Bellman error along the distribution induced by π. Assume that one constructs test function class F of possible likelihood ratios.
Proposition 1 (Likelihood ratio bounds), Assume that for some constant by, the test function defined 1 d. (s.a) belongs to rrd and satisfies I| I Then the OPC coefficient satisfies as f (x(s ba p(s,a)
(s(S.A) A(S.A)
(3) E
+02
(8)
by (1+6a))
K
(12)
1+A
1+1
Here by is scaling parameter that ensures (s.a) The proof is in Appendix D.I Since A = An + 0 as increases, the OPC coefficient is bounded by multiple of the expected ratio E,, M(S,A)
|f oo I 1. Concretely one can take b,
(s, p(s,a)"
(S,A4)) Up to an additive offset,
this expectation equivalent to the -dsitrributio between the policy-induced occupation measure d, and getta-generatig distribution μ. The concentrability coefficient can be plugged back into Eqs. (Ila) and (TTb) to obtain a concrete policy optimization bound. In this case, we recover a result similar to (X120b), but with much milder concentrability coefficient that involves only the chosen comparator policy.

---

4.2
The error test space
We now turn to the discussion of choice for the test space that extends the LSTD algorithm to non-linear spaces. A simplification to the linear setting is presented later in Section
As is well known, the LSTD algorithm [B96] can be seen minimizing the Bellman error projected onto the linear prediction space Q. Define the transition operator (s, a) E -= (( ,,), and the prediction error realizability. The Bellman error can be re-written as Q = 8 Q - B Q = (I ypah )e. When realizability holds, in the linear setting and at the population level, the LSTD solution seeks to satisfy the projected Bellman equations
Q QT, where Q is Q-function from the definition of weak
U 0, for all f E.
(13)
In the linear case, E. is the class of linear functions O used as predictors; when Q" is non-linear, we can extend the LSTD method by using the (nonlinear) error test space 3 = E = {Q QT): Since &.r is unknown (as it depends on the weak solution QT), we choose instead the larger class
E" = Q' QQQ'' E )*),
which contains E.. The resulting approach can be seen as performing projection of the Bellman operator B into the error space Σ., much like LSTD does in the linear setting. However, different from LSTD, our procedure returns confidence intervals as opposed a point estimator. This choice of the test space is related to the Bubnov-Galerkin method [Rep17] for linear spaces; it selects the test space 9"' to be identical to the trial space E. that contains all possible solution errors.
Lemma (OPC coefficient from prediction error). For any test function class I" 2 E", we have
lell
(1.8")
Iell LITTR 1P
(LIZ->"")
KT S max QEQ + (e, Q
max SEE.
(14)
The above coefficient measures the ratio between the Bellman error along the distribution of the target policy æ and that projected onto the error space Σ. defined by Q" It is a concentrability coefficient that always applies, as the choice of the test space does not require domain knowledge. See Appendix D.2 for the proof, and Appendix AA6 for further comments and insights, as well as simplification in the special case of Bellman closure.
4.3
The Bellman test space
In the prior section we controlled the projected Bellman error. Another longstanding approach in reinforcement learning is to control the Bellman error itself, for example by minimizing the squared Bellman residual. In general, this cannot be done if only an offline dataset is available due the well known double sampling issue. However, in some cases we can use an helper class to try to capture the Bellman error. Such class needs be a superset of the class of Bellman test functions given by
g def {BT
(15)
Any test class that contains the above allows us to control the Bellman residual, as we show next. Lemma (Bellman Test Functions). For any test function class F"r that contains FB. we have
|B sa
for any Q eTa))
(16a)
Moreover, the off-policy cost coefficient is upper bounded as
(4) S C1 sup
1 QIl (1i)
KJ
C1 sup
(L
B Q
S Ci sup (s
p(s.a) (s,a)
(16b)
QE
QEQ
See Appendix D.4 for the proof of this claim.
Consequently, whenever the test class includes the Bellman test functions, the off-policy cost coefficient at most the ratio between the squared Bellman residuals along the data generating distribution and the target distribution. If Bellman closure holds, then the prediction error space Ex introduced in Section 4.2 contains the Bellman test functions: for Q E Qa we can write BTQ T e 8r, This fact allows to recover result in the recent paper [XC in the special case of Bellman closure, although the approach presented here is more general.
7

---

4.4 Combining test spaces
Often, it is natural to construct a test space that is union of several simpler classes. A simple but valuable observation is that the resulting procedure inherits the best of the OPC coefficients. Suppose that we are given collection {5m m m== of M different test function classes, and define the union 1M
9rt ===Ud - mm For each m I..... M, let K be the OPC coefficient defined by the function class In and radius p. and let KT (3) be the OPC coefficient associated with the full class. Then we have the following guarantee:
Lemma (Multiple test classes). K" (3) minm=11,.... M K m
This guarantee straightforward consequeece of our construction of the feasibility sets: in particular, have (3) nM C, (Fmm), and consequently, by the variational definition of the off-policy cost coefficient K (*)(F) as optimization over (F), the bound (3) follows. In words, when multiple test spaces are combined, then our algorithms inherit the best (smallest) OPC coefficient over all individual test spaces. While this behavior is attractive, one must note that there is a statistical cost to using a union of test spaces: the choice of p scales function of F via its metric entropy. This increase in p must be balanced with the benefits of using multiple test spaces
Linear Setting
In this section, we turn to a detailed analysis of our estimators using function classes that are linear in feature map. Let Φ S x A + Rd be a given feature map, and consider linear expansions (w, o(s,))) = Ej= wr a). The class of linear functions takes the form
Iw (s,a) a) def
c def ((s.a) Iu (s, a) w Rdd ||l|e S 1}.
(17)
Throughout analysis, assume that ()(ss,))l: I for all state-action pairs.
Following the approach in Section 4.2 which is based on the LSTD method, we should choose the test function class f L, as in the linear case the prediction error is linear.
In order to obtain a computationally efficient implementation, "simpler" subset of L. In particular, for linear functions, it is not hard to show that the estimates min and max from equation (5) can be computed by solving quadratic program, with two linear constraints each test function. (See Appendix(A.8fion the details.) Consequently, the computational complexity scales linearly with the number of test functions. Thus, if we restrict ourselves finite test class contained within L, we will obtain a computationally efficient approach.
need to use test class that is
5.1 A computationally friendly test class and OPC coefficients
Define the empirical covariance matrix Σ = Ei= Φ. where o; def /= oss, a.). Let (ū,} be the eigenvectors of empirical covariance matrix Σ,, and suppose that they normalized to have unit fo-norm. We use these normalized eigenvectors to define the finite test class
jf de
Un.j = I,...,d d} where f5(s,a) def (ū,, ((s,a)
(18)
few observations are in order:
This test class has only functions, so that our QP implementation has 2d constraints, and can be solved in polynomial time. (Again, see Appendix [A.8 for details.)
Since TrH is subset of L the choice of radius p c( d log 1/8) is valid for some constant
Concentrability: When weak Bellman closure does not hold, then our analysis needs to take into account how errors propagate via the dynamies. In particular, we define the next-state feature extractor (s, del Eg Est T), along with the population covariance matrix Σ def Ey (0(s, a)o (s, a)), and its X-regularized version Σx def Σ AI. We also define the matrices
レ del [T
def (M)) >Σ, ( 7 kytt).
X,
'For space reasons, we defer to Appendix A.7 an application which we construct a test function space as a union of subclasses, and thereby obtain a method that automatically leverages Bellman closure when it holds. falls back importance sampling if closure fails, and falls back to worst-case bound in general.

---

The matrix Σ+ is the coos-covariianc between successive states, whereas the matrix Σ B,Bo is suitably renormalized and symmetrized version of the matrix Σ - which arises naturally from the policy evaluation equation. We refer quantities that contain evaluations at the next-state (e.g., x)*") as bootstrapping terms, and now bound the OPC coefficient in the presence of such terms: Proposition 2 (OPC bounds with bootstrapping). Under weak realizability, have
K (3*) I с d d "0
with probability at least -
(19)
(EXT
See Appendix E.1 for the proof. The bound (19) takes a familiar form, as involves the same matrices used to define the LSTD solution. This is expected, as approach here is essentially equivalent the LSTD method; the difference is that LSTD only gives a point estimate as opposed to the confidence intervals that we present here; however, they are both derived from the same principle, namely from the Bellman equations projected along the predictor (error) space.
The bound quantifies how the feature extractor é together with the bootstrapping term o= averaged along the target policy и, interact with the covariance matrix with bootstrapping Σ X.Boo It is an approximation the OPC coefficient bound derived in Lemma [ The bootstrapping terms capture the temporal difference correlations that can arise in reinforcement learning when strong assumptions like Bellman closure do not hold. As a consequence, such an OPC coefficient being small is sufficient condition for reliable off-policy prediction. This bound on the OPC coefficient always applies, and it reduces to the simpler one (20) when weak Bellman closure holds, with no need to inform the algorithm of the simplified setting, see Appendix [.33] for the proof.
Proposition 3 (OPC bounds under weak Bellman Closure). Under Bellman closure, we have
KT (TT"") S c dd] Φ ET
with probability at least 1 5.
(20)
5.2 Actor-critic scheme for policy optimization
Having described practical procedure to compute V now turn to the computation of the max-min estimator for policy optimization. We define the soft-max policy class
Hin
def (s.
e(0(o.0).0)
|00| - T. 0 E TR
(21)
E. I elsin.t),
In order to compute the max- max-min solution (6) over this policy class, we implement an actor-critic method, in which the actor performs a variant of mirror descent
At each iteration 1= 1. T, the policy ne E Tin can be identified with parameter 0₂ E Rdd
The sequence is initialized with 0, 0.
Using the finite test function class (18) based on normalized eigenvectors, the pessimistic TH is computed by solving quadratic program, as previously described. This value estimate min computation returns the weight vector wi of the associated optimal action-value function.
Using the action-value vector WA, we update the actor's parameter as
--1 0, + 1pu where
log AAi
is stepsize parameter.
(22)
We now state a guarantee on the behavior of this procedure, based on two OPC coefficients:
Ki = d d and K sup xell
[ 70 7012 " (1
(23)
Moreover, in making the following assertion, assume that every weak solution Q can be evaluated against the distribution of a comparator policy मे 11, i.c., (1, assumption is still weaker than strong realizability).
Q.) & = 0 for all E II. (This
Theorem (Approximate Guarantees for Linear Soft-Max Optimization). Under the above con- ditions, running the procedure for T rounds returns policy sequence { )T such that, for any comparator policy से E TI,
T
logiA A T
d dlog(n (
(24)
T 1=1
Optimization error
Statistical
'Strictly speaking, is mirror ascent, but the conventional terminology.

---

with probability at least - 8. This bound always holds with KT) = (2y and moreover, it holds
with K3) = K(1) when weak Bellman closure in force.
See Appendix For the proof. Whenever Bellman closure holds, the result automatically inherits the more favorable concentrability coefficient (2) as originally derived Proposition 3 The resulting bound is only v worse than the lower bound recently established in the paper [ZWWB2T] However, the method proposed here is robust, in that it provides guarantees even when Bellman closure does not hold. In this case, have guarantee in terms of the OPC coefficient K (ay- Note that is uniform version of the one derived previously in Proposition the policy class. This supremum arises due to the use of gradient- based method, which implicitly searches over policies in bootstrapping terms; see Appendix A.9 for a more detailed discussion of this issue.
2 in that there is an additional supremum over
Acknowledgment
AZ was partially supported by NSF-FODSI grant 2023505. In addition, this work was partially supported by NSF-DMS grant 2015454, NSF-IIS grant 1909365, well Office of Naval Research grant BOR--00014-18-11
to MJW. The authors are grateful to Nan Jiang and Alekh Agarwal for pointing out further connections with the existing literature, as well the reviewers for pointing out clarity issues.
References
[AMS07] András Antos, Rémi Munos, and Csaba Szepesvári. Fitted Q-iteration in continuous action-space MDPs. 2007.
[ASM08] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89-129, 2008.
[ASN20) Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic per- spective offline reinforcement learning. In International Conference Machine Learning, pages 104-114. PMLR, 2020.
[BB96] Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1-3):33-57, 1996.
[Ber95a] D. P. Bertsekas. Dynamic programming and stochastic control, volume 1. Athena Scientific, Belmont, MA, 1995.
[Ber95b] D.P. Bertsekas. Dynamic programming and stochastic control, volume Athena Scientific, Belmont, MA, 1995.
[BGB20] Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed-dataset policy optimization. arXiv preprint arXiv:2009.0677 000-99999. 2020.
[BLL+11] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[BT%)] Dimitri P Bertsekas and John Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
[CJ19] Jinglin Chen and Nan Jiang. Informatiin--theortiicc considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051, 2019.
[CQ22) Xiaohong Chen and Zhengling Qi. On well-posedness and minimax optimal rates of nonparametric q-function estimation in off-policy evaluation. arXiv preprint arXiv:2001.06169, 2022.
10

---

[DJL21] Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. arXiv preprint arXiv:2103.11883, 2021.
[DW20] Yaqi Duan and Mengdi Wang. Minimax-optiimal off-policy evaluation with linear function approximation. arXiv preprint arXiv:2002.095 2020.
[Eva10] Lawrence C Evans. Partial differential equations, volume 19. American Mathematical Soc., 2010.
[FCG18] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pages 1447-1456. PMLR, 2018.
[FGSM16] Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Regularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research, ((1)):4899-8877 2016.
[FKSLX21] Dylan J. Foster, Akshay Krishnamurthy, David Simchi- Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation, 2021.
[Fle84] Clive AJ Fletcher. Computational Galerkin methods. In Computational Galerkin methods, pages 72-85. Springer, 1984.
[FRTL20] Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu. Accountable off-policy evaluation with kernel bellman statistics. In International Conference on Machine Learning, pages 3102-311 2112-111.. PMLR, 2020.
[FSMI0] Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems (NIPS), 2010.
[Gal15] Boris Grigoryevich Galerkin. Series solution of some problems of elastic equilibrium of rods and plates. Vestmik inchenerov i tekhnikov, 19(7):897-908, 1915.
[Haz21] Elad Hazan. Introduction online convex optimization, 2021.
[HJD+21] Botao Hao, Xiang Ji, Yaqi Duan, Hao Lu, Csaba Szepesvári, and Mengdi Wang. Bootstrapping statistical inference for off-policy evaluation. arXiv preprint arXiv:2102.03607, 2021.
[JGS+19] 19] Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprins arXiv: 197.00090. 2019.
[JH20] Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. arXiv preprint arXiv:2002.0208/ 2020.
[JKA+17] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Doina Precup and Yee Whye Teh, editors, International Conference Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 1704-1713, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[JL16] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, pages 652-661 PMLR, 2016.
[JW211] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? International Conference on Machine Learning, pages
PMLR, 2021.
[K+03] Sham Machandranath Kakade et On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.

---

[KFTL19] Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. arXiv preprint arXiv:/906.0000 2019.
[KHSL21] Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. Should i run offline reinforcement learning or behavioral cloning? In Deep RL Workshop NeurIPS 2021, 2021.
[KRNJ20] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model-based offline reinforcement learning. arXiv preprint arXiv:2005.05951/ 2020.
[KU19] Nathan Kallus and Masatoshi Uchara. Efficiently breaking the curse of horizon in off- policy evaluation with double reinforcement learning. arXiv preprint (tt::1999008800 2019.
[LLTZ18] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems, pages 5356-5366, 2018.
[LP03] Michail G Lagoudakis and Ronald Parr. Lquarss policy iteration. Journal of machine learning research, 4(Dec):1107-1144 2003.
[LSAB20] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202, 2020.
[LTDC19] Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improve- ment with baseline bootstrapping. In International Conference on Machine Learning. pages 3652-3661. PMLR, 2019.
[LTND21] Jonathan N Lee, George Tucker, Ofir Nachum, and Bo Dai. Model selection in batch policy optimization. arXiv preprint arXiv:2112.123200 2021.
[MS08] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9MMay)885-8857 2008.
[Mun03] Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560-567, 2003.
[Mun05] Rémi Munos. Error bounds for approximate value iteration. In AAAI Conference on Artificial Intelligence (AAAI), 2005.
[ND20] Ofir Nachum and Bo Dai. Reinforcement learning via Fonkael-Rockafellar duality. arXiv preprint arXiv:2001.01866, 2020.
INDGL20] Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. arXiv preprint urXiv:2006.099: 09359, 2020.
[NDK*19 19] Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:19122 02074. 2019.
[Pre00] Doina Precup. Eligibility traces for off oof-cc policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[Pu194] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Pro- gramming. John Wiley & Sons, Inc., New York, NY, USA, 1994.
[Rep17] Sergey Repin. One hundred years of the Galerkin method. Computational Methods in Applied Mathematics, 17(3):351-357, 2017.
[RZM+21] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv: 2021.
12

---

[SB18] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT Press, 2018.
[SSB 20] Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, Nicolas Heess, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002.08330 2020.
[TB16] Philip Thomas and Emma Brunskill.
Data-efficient off- policy evaluation for reinforcement learning. International Conference on Machine Learning, pages 2139-2148, 2016.
19] Ziyang Tang, Yihao Feng. Lihong Li, Dengyong Zhou, and Qiang Liu. Doubly robust bias reduction in infinite horizon off- off-policy estimation. arXiv preprint 1rX1v:1900.07186. 2019.
[UHJ20] Masatoshi Uchara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, pages
PMLR, 2020.
[UD+211] Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.02981, 2021.
[US21] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage, 2021.
[VJY21] Cameron Voloshin, Nan Jiang, and Yisong Yue. Minimax model learning. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 1612-1620. PMLR, 2021.
[Wai19] Martin J Wainwright. Hlig--immensooal statistics: A non-asymptotic viewpoint, vol- ume 48. Cambridge University Press, 2019.
[WFK20] Ruosong Wang, Dean Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.1 /885, 2020.
[WN2+20] Ziyu Wang, Alexander Novikov, Konrad Zoina, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, et al. Critic regularized regression. arXiv preprint arX1v:2006.15134, 2020.
[WTN19] Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint 19Xiv:1911.1136] 2019.
[XC Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:2006.06926, 2021.
[X]20a] Tengyang Xie and Nan Jiang. Batch value- function approximation with only realizabil- ity. arXiv preprint arXiv:2008.cm 049900 2020.
[XJ20b] Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. volume 124 of Proceedings of Machine Learning Research, pages 550-559, Virtual, 03-06 Aug 2020. PMLR.
[XMW19] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, pages 9668-9677 2019.
[YB10] H. Yu and D. P. Bertsekas. Error bounds for approximations from projected linear equations. Mathematics of Operations Research, 35(2):306-329, 2010.
13

---

[YBW20] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near optimal provable uniform convergence in off-policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.03776. 2020.
[YND+20] Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. arXiv preprint arXiv:2007.03438 2020.
[YQCC21] Chao-Han Huck Yang. Zhengling Qi, Yifan Cui, and Pin- Yu Chen. Pessimistic model selection for offline deep reinforcement learning, 2021.
[YTY+20] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005.1 13299, 2020.
[YW20] Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3948-3958, PMLR, 2020.
[YW21] Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. arXiv preprint arXiv:2110.08653 2021.
[YWDW] Ming Yin, Yu-Xiang Wang. Yaqi Duan, and Mengdi Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism.
[Zan20] Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online RL. arXiv preprint arXiv:20/2.08005. 2020.
[ZDLS20] Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.09072, 2020.
ZHH [2] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline rein- forcement learning with realizability and single-policy concentrability. arXiv preprint arXiv:2202.04634 2022.
[2J721] Zihan Zhang, Xiangyang Ji, and Yuan Zhou. Almost optimal batch-regret tradeoff for batch linear contextual bandits, 2021.
[ZLW20] Shangtong Zhang, Bo Liu, and Shimon Whiteson. Gradientdice: Rethinking general- ized offline estimation of stationary values. In International Conference on Machine Learning, pages 11194-1220... PMLR, 2020.
[2SU+22] Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang. Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block MDPs: A model-free representation learning approach, 2022.
[ZWB21] Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits actor- critic methods for offline reinforcement learning. arXiv preprint 108.v:218..08811 2021.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Limitations include the choice of the test functions
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The work is theoretical in nature, negative societal impacts anticipated
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "j1VtC947pF", "reviewer": "Reviewer_ikh4", "summary": "The main idea of Bellman residual orthogonalization proposed by this paper is to approximate the Bellman equations by enforcing their validity along a user-defined space of test functions. Then, this work utilizes this idea to construct confidence intervals for OPE as well as to optimize over policies in the model-free offline reinforcement learning with function approximation setting. \n\nIn contrast to the standard importance sampling (IS) and regression based methods for OPE, the approach, derived from the Bellman residual orthogonalization principle, is a kind of weight learning algorithms. Specifically, the proposed method leverages an auxiliary function class to either encode the marginalized importance weights of the target policy or estimates of the Bellman errors. In particular, the authors propose a sample-based approximation of this idea via self-normalization and regularization. \n\n", "questions": "Firstly, what are the key advantages of the methods for OPE and policy optimization based on Bellman residual orthogonalization over standard approaches for both tasks in the offline setting? \n\nSecondly, given the rationale of the proposed principle, the current version may be further improved by providing analysis and guidance regarding which tasks in RL, besides OPE, could be better solved using the same idea. \n\nLast but not least, test functions play a critical role in the proposed methods and are used to encode domain knowledge of interest. Accordingly, it is very important carefully design the test class. Although the paper points out that the choice of the test functions are contingent on the problems and several principles that the design of the test function space should satisfy, the current version lacks a systemic guidance for doing so. ", "limitations": "As this work focusing on a RL method from a theoretical aspect, the authors have analyzed certain technical limitation, such as the way to design a good test class, the pros and cons of using a combined test classes, etc.\n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed Bellman residual orthogonality seeks to control the Bellman error in a weighted-average way where the weights are derived from a set of test functions chosen by the users. Therefore, the choice of the test class is crucial and contingent on the problem of interest, but it is also challenging to choose the right one. This paper has discussed several overarching principles that should be adopted to guide the design of the test function space. For instance, the test class should be delicately designed in order to encode domain knowledge of interest. However, there is a gap between such principles and practical procedures to do so. In this sense, this current version could be improved by analyzing the pros and cons of different test functions in-depth and developing a principled way to make such decision. \n\nIn addition, this paper utilizes the aforementioned principle to tackle two RL problems, off-policy evaluation and policy optimization, in the offline RL setting with function approximation. As these two RL tasks have been investigated extensively and many existing approaches are available, it is important to compare the performance of the method developed in this paper compared to existing techniques, which would help verify the technical soundness and practical effectiveness of the proposed idea. \n\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YcxluWlfhiR", "reviewer": "Reviewer_HGjj", "summary": "The authors propose an offline policy evaluation and optimization method introducing a test class (discriminator). The policy optimization method is performed pessimistically by constructing the version space. In the linear case, it is at least computationally efficient. They also propose a new off-policy coefficient, which would result in several known or new coefficients in various scenarios. \n", "questions": "Can we consider an NPG-type policy optimization method with general function approximation with this framework like [XCJ+21] beyond the linear case? If so, that's interesting since their result relies on Bellman closeness. ", "limitations": "Not applied to this work. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think it is a thought-provoking paper. I will vote for acceptance. But I think some parts of the acknowledgments are not exactly fair as I will mention later. It might be better to be fixed. \n\n(Strengths) \n\n* They propose a unified framework with CPC that can capture known results and new results. \n\n* Results in Section 4.3 (a generalization of LSTD) are very interesting.  \n\n* In Section 5.1, I feel prop 2 and prop 3 are kind of known. But, viewing it in a unified way is still interesting.  Related to this point, the computationally efficient algorithm (Section 5.2) without Bellman completeness is interesting. (Though I feel this algorithm is known and the bellman completeness type result is known as author acknowledged) \n\n(Weakness) \n\nThe downside is some of the concrete results, which come from a unified framework are known. Some of them are well-acknowledged. But I feel some of them are not acknowledged in direct ways. ( Irrespective of that, unified thinking itself is a valuable and thought-provoking contribution! )  \n\nMore specifically,  for domain-specific results, \n\n* Page 2 bullet point 1 : contribution 1, “however, here we only require concentrability with respect to a comparator policy instead of over all policies in the class.” Umm. I think this is over claimed. It is explicitly mentioned in [JH20]. Though they did not give finite sample results, I feel this part is not so difficult ( I remember the authors mentioned it either). So, I think it is fair to acknowledge like \"this observation is obtained in JH20, and we make it formal\".  (I see a related acknowledgment is written in a footnote. But this writing way is a bit vague.) \n\n* Page 2 bullet point 4: “Finally, our procedure inherits some form of “multiple robustness”. For example, the two test classes corresponding to Bellman completeness and marginalized importance weights can be used together, and guarantees will be obtained if either Bellman completeness holds or the importance weights are correct” This is also kind of known I feel. In OPE context, e.g., UIJ+21. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "V0uitMyeNt0", "reviewer": "Reviewer_xTJV", "summary": "This work studies offline policy evaluation and offline policy optimization. The setting is that of discounted rewards, model-free offline RL with function approximation. The main contribution of the paper is a general framework for studying offline policy evaluation through the lens of weak convergence of the Bellman error to zero with respect to a family of test functions. This allows for stating very general policy evaluation and optimization bounds under somewhat weak but reasonable conditions (Assumption 1). The authors give meaningful interpretations of their bounds under stronger assumptions like Bellman closure or using importance sampling weights. Further, the authors recover some versions of some prior work results in the setting of linear MDPs.", "questions": "Is weak realizability indeed a weaker condition than realizability? It seems to me that it would amount to realizability if the test function class for example contained all indicators of (s,a)-pairs.\n\nWhat is the measure \\mu? It seems like throughout the paper it is used as the measure from which the data is collected but I never saw a formal definition outside of using it as the measure under which Assumption 1 holds.\n\nHow does the second equality hold in Equation 10? It seems like the measure d^\\pi has been swapped for \\mu, but this does not seem trivial to me.\n\nWhere is b_\\pi defined in Proposition 1 and what is it?\n\nWhat is the definition of a prediction P^\\pi(Q) in Definition 1 on page 19? Is it just a mapping from the Q-fucntion class to itself?\n\nWhat is K^\\pi_* on line 750?\n\nIn Lemma 6 it seems like \\lambda can become arbitrarily small so is there no explicit dependence on the number of mixture components?\n\nWhere is Y_n(Q,\\pi) defined (display under line 1172)?\n", "limitations": "This work is theoretical and it is hard to judge what the societal impact will be.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1.) Originality -- the idea of relaxing some of the known conditions under which offline learning is possible to their weak counterparts is novel and the main theoretical result is novel to the best of my understanding.\n\n2.) Quality -- the generality of Theorem 3 is very nice.\n\n3.) Clarity and significance -- showing how to use the derived results in the linear setting exhibits potentially a general recipe for deriving meaningful bounds in the function approximation setting with weaker conditions than in prior work.  \n\nWeaknesses: \n\n1.) Computational efficiency -- the key results make use of computing upper and lower empirical value functions for a given policy \\pi, which requires optimizing over the empirical constraint set depending on the TD error and the Q-function class. While for linear MDPs this can be done some-what efficiently, in general it seems like such a computation would require time which is linear in the size of the test function class. Given that in two of the demonstrated examples (LSTD error test space and Bellman test space) the test function class has complexity proportional to the complexity of the Q-function class it is unclear how to efficiently carry out such computations beyond linear models.\n\n2.) Presentation -- the paper is somewhat technical and the main results require introducing a good amount of notation. This, however, is not done in a very good way. I found myself often not being able to recall or understand notation introduced earlier in the paper. It does not help that a lot of the notation is also introduced on the fly and scattered between different sections. Further, given that the main result is bounding the off-policy width through OPC, it would have been good to give interpretable bounds soon after the OPC is introduced in Eq. 10. Some of these bounds are hidden in Appendix A, e.g. Lemma 4, Lemma 6, and it might have suited the presentation better if they were exhibited in the main paper.\n\nAdditional comments: \n\n-- the notation used in the proof in C.1.1 for C^\\pi_n is not good. It is important to include the dependence on \\rho, otherwise the first inequality in the display under line 1081 would not hold.\n\n-- the proof of Theorem 3 seems to be structured around using Proposition 4 and checking that Equation 37 holds, however, this is not done explicitly or at least I have missed it. Otherwise, Proposition 4 does not seem to be used anywhere in the paper.\n\nOverall I think this is a good paper, however, improving the presentation and discussing computationally efficient algorithms beyond the linear setting can strengthen the paper even further.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I5QZkC3sz_", "reviewer": "Reviewer_eZ2Z", "summary": "This paper studied and analyzed a principle way to approximate bellman equations, where the authors constrain the value function in a set that was controlled by user-defined test functions and empirical Bellman errors. Under this unified principle, the authors are able to construct confidence intervals for off-policy evaluation, and also performing pessimistic offline policy learning using the lower bound. Besides, the authors also establish connections to concentrability coefficients studied in past work", "questions": "- [4] is a recent / concurrent work, whose main objective is started with density ratio. I wonder if it is possible to consider the Q as the test function, and construct empirical set for the density ratio function? And what's the connection of this new principle and the principles discussed in the paper( density ratio as the test function) ? \n\n- Would you mind explaining the notion of $o$? What would it could be in the real world? like context? \n\n\n\n[1] Jiang, et.al . Minimax value interval for off-policy evaluation and policy optimization, NeurIPS 2020.   \n[2] Feng, et.al. Accountable Off-Policy Evaluation With Kernel Bellman Statistics, ICML 2020.   \n[3] Feng, et.al. Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Bounds, ICLR 2021.    \n[4] Zhan, et.al. Offline Reinforcement Learning with Realizability and Single-policy Concentrability, COLT 2022.   \n", "limitations": "There is not potential negative societal impact of this work. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- **Originality**.   \nThe idea of constructing the empirical set and then use the empirical set to construct confidence interval has been explored in the prior works [1,2,3]. For instance, [2,3] aim to provide computational confidence interval, where the authors constrain the test function into a rkhs space, and the empirical set in [3] seems to be the same as Equation (7) in this paper.  **But**, [2,3] mainly focus on how to obtain computational confidence intervals, this paper provide more theoretical results such as offline policy optimization and results under weaker assumption.  Moreover,  the discussion in Section 4, the connections to concentrability coefficients in the prior works are very interesting. \n\n- **Quality**.   \nThis paper is technically sound. The authors provide many new results under this framework (such as offline policy improvement). \n\n- **Clarity**.   \nThis paper is well-written. I am new to this written style, the readers had better to read the appendix to get the background. Besides, is it possible to have a conclusion section that includes summary of the work and also some discussions on the future work? \n\n- **Significance**.   \nI think this is a very good paper, especially I like the explanation of connection between the Concentrability Coefficients and test spaces. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept